{"id":"cf6cb34f-fd46-4ada-967e-3689038e2a7f","arxiv_id":"2505.22189","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The maximum number of directed k-cycles in an n-vertex oriented graph with no directed l-cycle is Theta(n^k) when k does not divide l, Theta(n^(k-1)) when k divides l, and the leading constant is determined for large l.","lead":"This paper counts directed cycles of length k in arrow-only graphs that cannot contain a directed cycle of length l. It determines the growth rate for every k and l and, for large l, the leading constant, with several different optimal constructions.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 16 in §3.2.1 is false (p_2 in a random orientation of K_{n/2,n/2} is Θ(n^3), not O(n^2)); the proof of Lemma 12 and hence Theorem 11 collapses.","rationale":"The paper's central contribution is the order-of-magnitude dichotomy (Theorem 4) and the leading asymptotics for large ℓ (Theorems 8 and 11). Theorem 4 appears sound, and Theorem 8's proof is largely standard, but Theorem 11 depends essentially on Lemma 12, whose proof relies on Claim 16. Claim 16 is not merely unproven; it is false, even for the random bipartite orientation that is the extremal construction of Theorem 11. The error is a concrete algebraic mistake: p_1(v) is the in-degree, so Σ d^+(v)p_1^2(v) cannot be replaced by the number of arcs. Consequently, the bound p_{2j} ≤ n(n/4)^{2j-1} has the wrong order of magnitude for j=1 (and hence for the p_{k-4} term used in Claim 17). Because this false estimate is needed to force the graph to be bipartite, the proof of Lemma 12, and therefore of Theorem 11, does not go through. The reader's weakest assumption identified the unpublished manuscript [17] for Theorem 23; that is a legitimate concern, but it affects a secondary exact-value result, not the main large-ℓ theorem. The internal flaw in Claim 16 is more load-bearing: without a repaired proof, the paper's headline statement that the dense value is determined for all large ℓ is not established. The paper contains genuinely useful techniques and several correct-looking proofs, and a corrected version would be worth reconsidering, but as submitted the central claim rests on a false lemma.","tokens_in":23183,"tokens_out":31833,"duration_ms":331680,"concrete_test":"Take a balanced random orientation of K_{n/2,n/2} and compute p_2, the number of directed 2-paths. The expectation is 2·(n/2)·(n/2)(n/2-1)·(1/4) = n^3/16 - n^2/8, which exceeds the claimed bound n(n/4)^1 = n^2/4 for all n > 8. Equivalently, evaluate the displayed identity in the proof of Claim 16: S_1 = Σ_v d^+(v)d^-(v)^2 ≈ n^4/64, while e(G) = n^2/4. Either computation disproves Claim 16 and removes the only upper bound on p_{k-4} used in Claim 17.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing weakness is internal: Claim 16 in §3.2.1 is false as stated. It asserts p_{2j} ≤ n(n/4)^{2j-1} for every j in the graphs considered. In its proof, the displayed induction base reads Σ_v d^+(v) p_1^2(v) = e(G), but p_1(v) = d^-(v), so the left-hand side is Σ_v d^+(v)d^-(v)^2, not the number of arcs. This is not a harmless typo: in a balanced random orientation of K_{n/2,n/2}, the expected number of directed P_2 subgraphs is ~n^3/16, whereas the claimed bound for j=1 is n^2/4; for n > 8 the inequality fails. This counterexample has no odd cycles, is C_ℓ-free for odd ℓ, and every arc lies in a directed C_k for even k, so it is squarely within the scope of Lemma 12. The false bound is then used in Claim 17 as p_{k-4} ≤ n(n/4)^{k-5}; for k=6 this replaces a Θ(n^3) quantity by O(n^2), destroying the estimate t_v ≤ 0.45(n/4)^5 that produces the minimum-degree contradiction. Since Lemma 12 is the entire proof of Theorem 11 (the random-bipartite dense case), the main large-ℓ theorem is unproven as written. The reader's concern about unpublished [17] is secondary; the flaw here is a falsifiable error in a central chain of the paper's own argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the generalized Turán problem for oriented graphs, determining the maximum number of directed k-cycles in an n-vertex oriented graph that contains no directed l-cycle. The main results are an order-of-magnitude classification for all k,l (Theorem 4), asymptotic values in the dense setting for large l (Theorems 8 and 11), several small-cycle cases (Theorems 20, 23, 24, 26, 27, 28, 31, and 33), and an analogous theorem for directed graphs (Theorem 35). Theorems 8 and 11 together are intended to settle the leading constant whenever l is large and k does not divide l, with extremal constructions given by balanced blow-ups of a directed cycle or by a random orientation of a complete bipartite graph.","tokens_in":23523,"tokens_out":26218,"duration_ms":256635,"significance":"If the results were established, they would constitute a substantial contribution to generalized Turán theory for directed graphs: the paper gives a complete order of magnitude for every pair (k,l) and, for large forbidden cycle lengths, identifies the leading constant and the extremal construction. The paper also contains some sound and elegant components, notably the induction proof of Theorem 4, the weight argument of Lemma 9, and the eigenvalue bound of Lemma 13, and it provides a reproducible Flagmatic script for one of the small cases. However, two load-bearing statements in the proof machinery are false as written, and a third main theorem depends on an unpublished external manuscript. These issues leave the paper's headline results unproven in the submitted form.","major_comments":[{"comment":"Claim 16 is false. It asserts p_{2j} ≤ n(n/4)^{2j-1} for every positive integer j. In the proof, the displayed base equality reads Σ_v d^+(v)p_1^2(v) = e(G), but p_1(v) is defined as the number of directed P_1 ending at v, so p_1(v) = d^-(v); the left-hand side is therefore Σ_v d^+(v)d^-(v)^2, not e(G). This is not a harmless typo: in a balanced random orientation of K_{n/2,n/2}, the expected number of directed P_2 subgraphs is n^3/16 + o(n^3), while the claimed bound for j=1 is n(n/4) = n^2/4. The inequality fails already at j=1. Since Claim 17 uses p_{k-4} ≤ n(n/4)^{k-5} to control the number of ways to complete a k-cycle through a low-degree vertex, the proof of the minimum-degree bound δ(ẽG) > 2n/23 collapses. Consequently Lemma 12, which is the entire proof of Theorem 11, is unsupported, and the large-ℓ random-bipartite case is not proved.","section":"3.2.1"},{"comment":"Observation 1 is false as stated. Let F = C_6 and let H be the oriented graph consisting of two directed triangles sharing one vertex. Under the paper's definition, H is a homomorphic image of C_6: map the six vertices of C_6 to the sequence a,b,c,a,d,e, where a,b,c and a,d,e are the two triangles. A balanced blow-up of H contains no C_6, because the underlying undirected graph has no cycle of length 6. However, deleting o(n^2) arcs cannot destroy all copies of H: to eliminate H one must delete all arcs of at least one of the two directed triangles, which requires Θ(n^2) deletions. Thus the reduction used at the start of Section 3 — 'remove o(n^2) arcs using Observation 1 to delete from G all homomorphic images of C_ℓ' — is not valid. This clearing step is used in the proofs of Theorems 8, 11, 24, 26, 28, 31, and 35, so those upper-bound proofs lack a valid foundation and would need a substantially different reduction.","section":"1.1"},{"comment":"The upper bound for ex(n,C_4,C_3) is imported entirely from the unpublished manuscript [17] (Hu–Lidický–Volec, 'Inducibility of orientations of C_4'). No proof of the relevant inducibility result is given in this paper, and no public version of [17] is referenced. The stated constant n^4/(4^4-1) + o(n^4) is therefore conditional on an external result that the present manuscript does not make available to the reader. For a main theorem, this dependency should be removed or the external result should be published and cited in a verifiable form.","section":"3.3.2"}],"minor_comments":[{"comment":"The flag-algebra proof is presented only as a Flagmatic script; the generated certificate is not included, and the target bound 15/64 is not reconciled with the claimed constant 1/512 n^5. Without the certificate or an explanation of the normalization, the proof is not independently verifiable from the manuscript.","section":"3.3.3, Theorem 27"},{"comment":"The same symbol w(D) is used for both the forward and reverse sampling weights in the proof of Lemma 9; renaming the second weight would improve readability.","section":"2, Lemma 9"},{"comment":"The text contains numerous formatting artifacts and typos, such as missing spaces in the abstract, 'forex(n,C_4,C_3)' in Section 3.3.2, and inconsistent arrow/bold notation for cycles. A careful copyedit is needed.","section":"1"},{"comment":"The final optimization step in the proof of Theorem 28 is only sketched ('Optimizing the sizes of the six blobs ... gives in both cases the same blob sizes ...'); the computation should be shown to confirm the claimed constant 27/16.","section":"3.3.3, Theorem 28"}],"recommendation":"reject","confidential_remarks":"The manuscript contains two independent false statements in its proof machinery (Claim 16 and Observation 1), and Theorem 23's upper bound is not self-contained. Even if the theorems are true, the submitted proofs do not establish the headline results. I would encourage the authors to repair the reduction and the counting argument before resubmission; the order-of-magnitude part (Theorem 4) and the eigenvalue bound (Lemma 13) appear sound and worth preserving."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real contribution, not a repackaging. The directed analogue of the generalized Turán problem for cycles has not been treated before, and the paper settles the order of magnitude for every k and l, gives leading asymptotics for all dense pairs with l large, and finds a genuinely varied set of extremal constructions for small l. The main proof machinery — thick-arc induction, the Král'-Norin-Volec weight argument, and the eigenvalue bound for orientations of complete bipartite graphs — is standard but applied carefully, and most of the heavy lifting is self-contained.\n\nOn the stress-test: the alleged collapse of Lemma 12 does not happen. The test reads p_2 as the number of length-two directed paths, but the paper defines P_r as a path on r vertices, i.e. r-1 arcs, so P_2 is a single arc and p_2 is just the edge count. The induction base is correct: p_1(v) = 1 for all v, so the sum of d^+(v) p_1^2(v) over v equals e(G). The random orientation of K_{n/2,n/2} has p_2 ~ n^2/4, exactly matching the claimed bound, not n^3. Claim 16 is fine, and the subsequent estimates in Claim 17 check out. I could not find a load-bearing internal error in the proof of Theorem 11.\n\nThe real soft spots are external dependencies and one compressed optimization. Theorem 23 imports its upper bound from the unpublished manuscript [17], so the exact constant for (k, l) = (4, 3) is not self-contained. Theorem 27 provides a Flagmatic script but no generated certificate, so the verification is not reproducible from the text alone. And Theorem 28's final blob-size optimization is asserted rather than proved. All three are addressable, and none affects the main order-of-magnitude result or the large-l dense asymptotics.\n\nThe citation pattern is honest: the self-citations are to results actually used, and the open problem for (5, 4) is stated plainly. This paper deserves a serious referee, not a desk rejection. I would send it out and ask the authors to either resolve the dependence on [17] or mark the (4, 3) theorem explicitly conditional, and to supply certificates or detailed derivations for the two computer-assisted/optimization steps. It is well worth discussing in a reading group.","headline":"Strong, original paper on the directed generalized Turán problem; the stress-test's objection to Claim 16 rests on a misreading of the path notation, and the real soft spots are the unpublished [17] and insufficiently documented computer-assisted steps.","tokens_in":24070,"tokens_out":9283,"would_cite":true,"duration_ms":85445,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every k and l, the paper determines how many directed k-cycles an oriented graph can have without a directed l-cycle: order n^k when k does not divide l, order n^{k-1} when it does.","keywords":["generalized Turán problem","directed cycles","oriented graphs","extremal graph theory","blow-up constructions","divisibility dichotomy","sparse setting","dense setting"],"falsifier":"Check the unpublished inducibility bound by computing, for small $n$, the maximum number of induced copies of each orientation of $C_4$ in an oriented graph and comparing the extremal construction with the iterated blow-up of $\\vec C_4$; a higher density or a different extremal construction would invalidate $\\mathrm{ex}(n,\\vec C_4,\\vec C_3)=\\frac{n^4}{4^4-1}+o(n^4)$. Equivalently, a computer search for directed-triangle-free oriented graphs whose directed 4-cycle count beats the iterated blow-up on the same vertex set would decide the matter.","tokens_in":23005,"feed_emoji":"🌀","tokens_out":19271,"duration_ms":176018,"temperature":0.7,"pith_summary":"An oriented graph is a directed graph with at most one arc between any two vertices. The paper asks: if such a graph on $n$ vertices contains no directed $\\ell$-cycle $\\vec C_\\ell$, how many directed $k$-cycles $\\vec C_k$ can it contain? It proves the order of magnitude for every pair: $\\Theta(n^k)$ when $k\\nmid \\ell$ and $\\Theta(n^{k-1})$ when $k\\mid \\ell$. For large forbidden length $\\ell$ it identifies the leading constant, showing that a balanced blow-up of a shorter directed cycle is extremal except in one parity case, where a random orientation of a complete balanced bipartite graph is better. For small $\\ell$ the extremal constructions are many and varied, and the paper determines leading constants for several representative pairs, leaving the case $(k,\\ell)=(5,4)$ open.","feed_headline":"Divisibility decides directed cycle counts","feed_subtitle":"The maximum is roughly n^k when k does not divide l, n^(k-1) when it does; blow-ups are extremal.","key_machinery":"The argument runs through three devices. First, a clearing step uses the directed regularity lemma and the blow-up lemma to delete $o(n^2)$ arcs so that all homomorphic images of $\\vec C_\\ell$ (closed directed walks of length $\\ell$) disappear, losing only $o(n^k)$ copies of $\\vec C_k$. Second, a weighting lemma counts copies of $\\vec C_k$ by averaging probabilities of 'good sequences' around each cycle; together with the AM-GM inequality it bounds the count by $\\frac nk(\\frac nd)^{k-1}$ whenever every vertex has at most $2k/d$ neighbours on any $\\vec C_k$, and this neighbourhood bound is forced by forbidding cycles with one arc reversed through a coin-representation theorem. Third, in the bipartite exception, a high-minimum-degree plus no-short-odd-cycle argument forces the extremal graph to be bipartite, and an eigenvalue majorization inequality bounds the cycle count by $\\frac2k(\\frac n4)^k$.","core_discovery":"Writing $\\mathrm{ex}(n,\\vec C_k,\\vec C_\\ell)$ for the maximum number of directed $k$-cycles in an $n$-vertex oriented graph with no directed $\\ell$-cycle, the paper establishes the dichotomy $\\mathrm{ex}(n,\\vec C_k,\\vec C_\\ell)=\\Theta(n^k)$ if $k\\nmid\\ell$ and $=\\Theta(n^{k-1})$ if $k\\mid\\ell$ (Theorem 4). In the dense case, for $\\ell\\ge 2(k-1)^2$ and $k\\nmid\\ell$, let $d$ be the smallest divisor of $k$ greater than $2$ that does not divide $\\ell$; then, when $k$ is odd, $\\ell$ is even, or $d\\le 4$, the value is $\\frac{n}{k}(\\frac{n}{d})^{k-1}+o(n^k)$, attained by a balanced blow-up of $\\vec C_d$. When $k$ is even, $4\\nmid k$, $\\ell$ is odd, and $3\\nmid k$ or $3\\mid\\ell$, with $\\ell>33k^2$, the value is $\\frac{2}{k}(\\frac n4)^k+o(n^k)$, attained by a random orientation of a complete balanced bipartite graph. For small $\\ell$ the paper computes several exact leading constants: $\\frac{n^4}{4^4-1}+o(n^4)$ for $(4,3)$ via an iterated blow-up of $\\vec C_4$, $(\\frac n4)^4+o(n^4)$ for $(4,6)$, $\\frac{n^5}{512}+o(n^5)$ for $(5,3)$, $\\frac{27}{16}(\\frac n5)^5+o(n^5)$ for $(5,7)$, and $(\\frac n5)^5+o(n^5)$ for $(5,8)$ and $(5,13)$. It also solves the sparse example $(3,6)$ with value $\\frac14 n^2+o(n^2)$. The directed-graph analogue for large $\\ell$ not divisible by $k$ is $\\frac nk(\\frac nd)^{k-1}+o(n^k)$ with $d$ the smallest positive divisor of $k$ not dividing $\\ell$.","pith_inferences":["The same divisibility dichotomy should survive when the forbidden object is any fixed orientation of a cycle of length $\\ell$: the paper's final remarks show such a cycle is homomorphic to $\\vec C_\\ell$, so its upper bounds apply, but the extremal constructions may need to be re-optimized for each orientation.","The threshold-orientation construction used for the open case $(5,4)$ suggests that between pure blow-ups and random orientations there is a continuous family of extremal graphs parameterized by monotone functions; testing this family computationally for other unsolved pairs could reveal a general interpolation principle.","The conjectured formula $\\mathrm{ex}(n,\\vec C_3,\\vec C_{3t})\\sim \\frac{t-1}{4}n^2$ indicates a family of extremal graphs with one small blob and two large parts; verifying $t=3$ would give the first sparse-case constant beyond the $(3,6)$ example and might expose a general sparse construction.","On the open question of $\\mathrm{ex}(n,\\vec C_5,\\vec C_4)$, the paper's lower bound $0.0517\\binom n5$ comes from a monotone orientation of a blow-up of a 7-cycle plus chords; a natural testable extension is to optimize the monotone threshold function beyond the form $\\min(x+c,1)$ to see whether the constant can be pushed closer to the computer-assisted upper bound."],"forward_implications":["The order of magnitude is now known for every pair $(k,\\ell)$, closing the directed-cycle version of the generalized Turán problem at the $\\Theta$ level.","For large $\\ell$, the extremal graph is almost always a balanced blow-up of a shorter cycle: the shortest divisor $d>2$ of $k$ that does not divide $\\ell$ determines both the construction and the constant.","In the one parity exception—$k$ even, $\\ell$ odd, $d\\ge 5$—the extremal graph is a random orientation of a complete balanced bipartite graph, giving $\\frac2k(\\frac n4)^k+o(n^k)$ copies.","For small $\\ell$ no single construction dominates: iterated blow-ups, transitive tournaments inside blobs, and unbalanced blow-ups with bipartite patches each win for different pairs, showing many genuinely different extremal regimes.","The directed-graph version of the problem has the same order of magnitude and the same type of blow-up extremal value for large $\\ell$, with $d$ now allowed to be $2$."],"supporting_citations":[{"why":"It supplies the weighting/AM-GM method used in Lemma 9 to bound cycle counts under a bounded-neighbourhood condition.","marker":"[19]"},{"why":"It supplies the coin-representation theorem (Corollary 3) that converts forbidden homomorphic images into divisibility contradictions throughout the dense proofs.","marker":"[5]"},{"why":"It provides the unpublished inducibility result for orientations of $C_4$ on which the exact constant for $(k,\\ell)=(4,3)$ in Theorem 23 depends.","marker":"[17]"},{"why":"It gives the maximum number of triangles in a $K_4$-free graph, used to bound directed triangles when $\\vec C_4$ or $\\vec C_5$ is forbidden.","marker":"[7]"},{"why":"It establishes the extremal pentagon count in triangle-free graphs used in the $\\vec C_5$ upper bounds.","marker":"[13]"},{"why":"It independently establishes the same extremal pentagon count used in the $\\vec C_5$ upper bounds.","marker":"[16]"},{"why":"It forces bipartiteness in the random-bipartite case once high minimum degree and absence of short odd cycles have been proved.","marker":"[3]"},{"why":"It gives the eigenvalue majorization inequality used to bound directed cycles in an orientation of a complete bipartite graph.","marker":"[10]"},{"why":"It supplies the directed regularity lemma used to remove homomorphic images of the forbidden cycle.","marker":"[1]"},{"why":"It supplies the blow-up lemma used in the clearing argument that deletes homomorphic images with a loss of only $o(n^k)$ copies.","marker":"[18]"}],"fun_headline_variants":["Divisibility dictates directed cycle extremals","k ∤ ℓ gives ~n^k cycles, k | ℓ gives ~n^{k-1}","Blow-ups realize extremal directed cycle counts","Exact directed Turan numbers for cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact constant for the $(k,\\ell)=(4,3)$ case rests on an unpublished manuscript's claim about the largest possible density of induced 4-cycles in an oriented graph; if that claim is wrong or does not transfer to counting directed 4-cycles, the stated constant is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Divisibility dictates directed cycle extremals","k ∤ ℓ gives ~n^k cycles, k | ℓ gives ~n^{k-1}","Blow-ups realize extremal directed cycle counts","Exact directed Turan numbers for cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3447,"prompt_tokens":1181,"completion_tokens":2266,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":797,"completion_tokens_details":{"reasoning_tokens":2195}},"tokens_in":797,"tokens_out":2266,"duration_ms":18953,"temperature":1.0,"reasoning_tokens":2195,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:14:04.282175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the unpublished inducibility bound by computing, for small $n$, the maximum number of induced copies of each orientation of $C_4$ in an oriented graph and comparing the extremal construction with the iterated blow-up of $\\vec C_4$; a higher density or a different extremal construction would invalidate $\\mathrm{ex}(n,\\vec C_4,\\vec C_3)=\\frac{n^4}{4^4-1}+o(n^4)$. Equivalently, a computer search for directed-triangle-free oriented graphs whose directed 4-cycle count beats the iterated blow-up on the same vertex set would decide the matter.","supporting_citations":[{"cited_title":"A bound on the inducibility of cycles.Journal of Combinatorial Theory, Series A, 161:359–363, 2019","cited_arxiv_id":null,"evidence_quote":"It supplies the weighting/AM-GM method used in Lemma 9 to bound cycle counts under a bounded-neighbourhood condition."},{"cited_title":"On a problem of partitions.American Journal of Mathematics, 64(1):299–312, 1942","cited_arxiv_id":null,"evidence_quote":"It supplies the coin-representation theorem (Corollary 3) that converts forbidden homomorphic images into divisibility contradictions throughout the dense proofs."},{"cited_title":"Inducibility of orientations ofC4","cited_arxiv_id":null,"evidence_quote":"It provides the unpublished inducibility result for orientations of $C_4$ on which the exact constant for $(k,\\ell)=(4,3)$ in Theorem 23 depends."},{"cited_title":"On the number of complete subgraphs contained in certain graphs.Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 7(3):459–464, 1962","cited_arxiv_id":null,"evidence_quote":"It gives the maximum number of triangles in a $K_4$-free graph, used to bound directed triangles when $\\vec C_4$ or $\\vec C_5$ is forbidden."},{"cited_title":"On the maximum number of five-cycles in a triangle-free graph.Journal of Combinatorial Theory, Series B, 102(5):1061–1066, 2012","cited_arxiv_id":null,"evidence_quote":"It establishes the extremal pentagon count in triangle-free graphs used in the $\\vec C_5$ upper bounds."},{"cited_title":"On the number of pentagons in triangle-free graphs.Journal of Combinatorial Theory, Series A, 120(3):722–732, 2013","cited_arxiv_id":null,"evidence_quote":"It independently establishes the same extremal pentagon count used in the $\\vec C_5$ upper bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It forces bipartiteness in the random-bipartite case once high minimum degree and absence of short odd cycles have been proved."},{"cited_title":"On a theorem of Weyl concerning eigenvalues of linear transformations: II.Proceed- ings of the National Academy of Sciences, 36(1):31–35, 1950","cited_arxiv_id":null,"evidence_quote":"It gives the eigenvalue majorization inequality used to bound directed cycles in an orientation of a complete bipartite graph."},{"cited_title":"Testing subgraphs in directed graphs.Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003","cited_arxiv_id":null,"evidence_quote":"It supplies the directed regularity lemma used to remove homomorphic images of the forbidden cycle."},{"cited_title":"Sárközy, and Endre Szemerédi","cited_arxiv_id":null,"evidence_quote":"It supplies the blow-up lemma used in the clearing argument that deletes homomorphic images with a loss of only $o(n^k)$ copies."}],"review_version":1}