{"id":"5874d276-6955-4db9-a095-cdc94c2495c4","arxiv_id":"2509.07760","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every r≥3, the exact chromatic profile of the transitive tournament T_r is (3r-7)/(3r-4); directed odd cycles have 2-color profile 1/2, and the three non-directed pentagon orientations have 2-color profile 1/3.","lead":"This paper proves exact minimum out-degree thresholds that force digraphs avoiding certain forbidden patterns to be colorable, including a directed version of the Andrásfai-Erdős-Sós theorem. Why read it: it opens a systematic study of chromatic profiles for directed graphs and gives sharp constants for transitive tournaments and oriented odd cycles.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 1.1 upper bound relies on an unjustified replacement step in Claim 2.10.","rationale":"The reader's weakest assumption, Lemma 4.4, is external and affects only the pentagon profiles. The paper's own strongest claim is Theorem 1.1, and the most load-bearing unprotected step in its proof is the replacement argument in Claim 2.10. The assertion that Q_1' and Q_2' are transitive tournaments is essential for the maximality-of-t contradiction, and it is not justified when the symmetric difference of Q_1 and Q_2 has more than one vertex. This is a genuine gap in the written proof, not a disagreement with the consensus or an external dependency. I do not claim the theorem is false; the gap may be repairable by a careful choice of y_i or an additional argument from saturation. But as written, the proof of the main upper bound is incomplete, so the manuscript still needs revision before Theorem 1.1 is fully verified. Since the reader's verdict was already CONDITIONAL, my read does not change that verdict, only the specific reason for it.","tokens_in":15735,"tokens_out":23944,"duration_ms":195802,"concrete_test":"Re-derive the transitive-tournament assertion in Claim 2.10 by listing, for every q ∈ V(Q_i)\\{y_i\\}, the required arc between q and x and verifying it from the definitions of X, the 5-wheel-like digraph, saturation, and maximality of t. Focus on the case t ≤ r−4 with two distinct vertices q, q' in V(Q_i)\\V(Q_{3−i}) both not dominating x; show either such a configuration is impossible in a saturated T_r-free digraph or exhibit one. Alternatively, run a SAT/backtracking search for r = 5, 6 on n = 3r−3 vertices with minimum out-degree exceeding (3r−7)/(3r−4)n, looking for a saturated T_r-free digraph containing W_{r,t} and a vertex x ∈ X with d^+(W,x) > |W|−3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Claim 2.10 is the only step that yields the d^+(W,x) ≤ |W|−3 bound used in inequality (5) to contradict the minimum out-degree assumption in Theorem 2.7; without it the upper bound of Theorem 1.1 collapses. The proof chooses y_i ∈ V(Q_i)\\V(Q_{3−i}) that do not dominate x and asserts that Q_i' = Q_i − y_i + x is a transitive tournament on r−2 vertices. This does not follow. Membership in X gives only arcs from every vertex of Q_1∩Q_2 to x. For each other q ∈ V(Q_i)\\V(Q_{3−i}), the proof supplies no arc between q and x, nor an orientation consistent with the transitive order of Q_i. Saturation and maximality of t are invoked after this assertion, so they cannot justify it. When |V(Q_i)\\V(Q_{3−i})| ≥ 2, i.e. t ≤ r−4, the chosen y_i may leave another non-dominating or non-adjacent vertex in Q_i', so Q_i' need not be a transitive tournament. The argument therefore has an unproved structural premise at the heart of the main theorem. The external Lemma 4.4 flagged by the reader is a separate issue affecting only the pentagon profiles, not Theorem 1.1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the chromatic profile δ^+_χ(H,k) for digraphs. The main result, Theorem 1.1, determines the profile for transitive tournaments T_r: δ^+_χ(T_r, r−1) = (3r−7)/(3r−4), with sharpness given by double orienting an AES-type graph (the C_5 blow-up joined with K_{r−3} for r≥4, and the C_5 blow-up alone for r=3). Theorem 1.3 gives δ^+_χ(\\vec{C}_{2ℓ+1},2)=1/2 for every ℓ≥1. Theorem 1.4 gives δ^+_χ(C_5',2)=δ^+_χ(C_5'',2)=δ^+_χ(C_5''',2)=1/3. Section 2 proves the upper bound via a saturation argument using 5-wheel-like digraphs; Section 4 uses a selection lemma, embedding lemmas, and an odd-girth case split; Section 5 applies Theorem 1.1 through the diregularity lemma to obtain a stability result.","tokens_in":16057,"tokens_out":16303,"duration_ms":145926,"significance":"If completed, the paper is a substantial contribution to extremal digraph theory. Theorem 1.1 is an exact directed analogue of the Andrásfai–Erdős–Sós theorem with an explicit sharp construction, and Theorem 1.4 resolves the two-coloring profiles for all three non-directed pentagon orientations. The stability application in Theorem 1.2 is a natural and plausible consequence. The constructions and the general strategy are clear and well motivated. However, the proof of Theorem 1.1 contains an unproved structural step in Claim 2.10, and the proof of Theorem 1.4 relies on a selection lemma cited to an in-preparation manuscript; both issues are load-bearing and need to be addressed before the central claims can be considered established.","major_comments":[{"comment":"The step \"Let Q_i' = Q_i − y_i + x. Then Q_1' and Q_2' are transitive tournaments on r−2 vertices\" is not justified. The definition of X only guarantees that every vertex of Q_1∩Q_2 dominates x; for a private vertex q in V(Q_i)\\V(Q_{3−i}) with q≠y_i, the manuscript supplies no arc between q and x and no orientation consistent with the transitive order of Q_i. The condition that y_i does not dominate x only excludes the arc y_i→x; it does not place x at the position of y_i in the transitive order. If x→q for some private q that precedes y_i, or if x is non-adjacent to such a q, then Q_i' need not be a transitive tournament. Since the maximality of t is then applied to Q_1' and Q_2' to conclude d^+(W,x)≤|W|−3, and this bound is exactly what makes inequality (5) contradict the minimum-out-degree assumption, the upper-bound proof of Theorem 1.1 is incomplete at this point. A full proof of the transitivity of Q_i' (or a different argument for d^+(W,x)≤|W|−3) is required.","section":"Section 2, Claim 2.10"},{"comment":"Lemma 4.4 is stated as a result of Gao–Liu–Wu–Xue and cited to the in-preparation manuscript [11], with no proof given. This lemma is load-bearing: Corollary 4.5 applies it iteratively to construct the disjoint common out-neighbourhood sets X_1,...,X_k, and Lemma 4.6 uses those sets to embed arbitrary oriented cycles in digraphs with minimum out-degree at least (1/2+ε)n. Lemma 4.6 is in turn used in Lemma 4.7(iii) and in Case 1 of Theorem 4.11. As submitted, the upper-bound proof of Theorem 1.4 depends on an unverifiable premise from an unpublished source. The authors should either include a complete proof of Lemma 4.4 or replace it with a publicly available reference that contains the proof.","section":"Section 4, Lemmas 4.4–4.6"},{"comment":"In the odd-girth-five case, after Claim 4.12 the proof constructs C_5^1 explicitly, but for C_5^2 and C_5^3 it only says the argument is analogous and refers to Figure 4.6. Since Theorem 1.4 requires the upper bound δ≤1/3 for all three orientations, the omission is not merely cosmetic: the replacement sequences for the two remaining orientations must be specified and proved to produce oriented 5-cycles at every intermediate step and the required forbidden pentagon at the end. Please provide the full details for these two cases.","section":"Section 4, Theorem 4.11, Case 2"}],"minor_comments":[{"comment":"The sentence \"for each x∈X, there exists y_i ∈ ({w_i}∪V(Q_i))\\V(Q_{3−i}) that does not dominate x\" is ambiguous because it suggests a single vertex, while the subsequent argument needs two distinct vertices y_1 and y_2 with y_1∈V(Q_1)\\V(Q_2) and y_2∈V(Q_2)\\V(Q_1). Please state the choice of both vertices explicitly.","section":"Section 2, proof of Claim 2.10"},{"comment":"The phrase \"P=C−v is an oriented path of length k−1\" is inconsistent with the usual meaning of length as the number of arcs; since C has k vertices, P has k−1 vertices and k−2 arcs. Please rephrase as \"on k−1 vertices\".","section":"Section 4, Lemma 4.6"},{"comment":"The notation \"Fix 1≫γ≫d≫ε>0\" should be spelled out as a hierarchy of constants, and the object called the pε,dq-reduced graph R should be called a reduced digraph for consistency.","section":"Section 5, proof of Theorem 1.2"}],"recommendation":"major_revision","confidential_remarks":"The two cited in-preparation manuscripts [9] and [11] are used in load-bearing ways, and [11] in particular supplies a lemma for which no proof is available to the reader. If the author cannot provide a proof of Lemma 4.4 or make the manuscript available, the Theorem 1.4 upper bound should not be considered established. The Claim 2.10 issue is potentially repairable, but if the transitivity of Q_i' cannot be proved, the main theorem would need a different argument for the upper bound of Theorem 1.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read of arXiv:2509.07760. The headline: it's a promising paper with a real gap in the main proof. The directed AES theorem (Theorem 1.1) is a natural extension, and the lower-bound constructions are explicit and verifiable. If the gap is repaired, the result would be a solid contribution. But as written, the proof of Claim 2.10 does not go through.\n\nThe gap: In Claim 2.10, after assuming v→x, the author chooses y_i ∈ V(Q_i)\\V(Q_{3−i}) with y_i↛x, and asserts Q_i − y_i + x is a transitive tournament. Membership in X only gives arcs from the intersection V(Q1)∩V(Q2) to x; it says nothing about arcs between x and other vertices of Q_i. Removing a single non-dominating y_i does not ensure every remaining vertex in Q_i is comparable to x, especially when |V(Q_i)\\V(Q_{3−i})| ≥ 2. So the replacement step, and with it the bound d^+(W,x) ≤ |W|−3, is unsupported. Since that bound feeds directly into inequality (5) to contradict the minimum out-degree assumption, the upper bound of Theorem 1.1 is not yet proved.\n\nWhat's good: The definition of chromatic profile for digraphs is natural. The lower-bound constructions for all three theorems are concrete and check out. Theorem 1.3 (directed odd cycles) is simple and correct. The stability application (Theorem 1.2) is standard regularity-machinery stuff and looks fine once Theorem 1.1 is available.\n\nOther soft spots: Lemma 4.4 is cited to an unpublished manuscript [11] and is load-bearing for the pentagon upper bounds; the paper should either prove it or state it as a black box with constants. Theorem 4.11, Case 2, waves hands with \"the argument is analogous\" for C2_5 and C3_5; those details matter. Neither of these is as serious as the Claim 2.10 gap, but they need attention too.\n\nBottom line: The paper is worth engaging with. The idea is good and most of the scaffolding is honest. But I would not take Theorem 1.1 as proven yet. Send it to a referee who knows the area; the referee should focus on Claim 2.10 and ask whether the replacement can be fixed (e.g., by choosing y_i more carefully or proving that all other vertices dominate x). If that step is repaired, the paper is publishable; if not, the main result is open.","headline":"Nice directed AES package with a real gap in the central proof; the main theorem is not yet proven, but the paper is worth a careful referee.","tokens_in":16503,"tokens_out":8748,"would_cite":false,"duration_ms":72363,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35","05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a directed analogue of the classical minimum-degree coloring threshold: any digraph on $n$ vertices with no transitive tournament on $r$ vertices and minimum out-degree greater than $\\frac{3r-7}{3r-4}n$ is…","keywords":["chromatic profile","digraph","transitive tournament","minimum out-degree","Andr\\'asfai\\textendash Erd\\H{o}s\\textendash S\\'os theorem","oriented cycles","pentagon orientations","coloring"],"falsifier":"A finite search for a $T_r$-free digraph with $\\delta^+(D)>\\frac{3r-7}{3r-4}n$ and chromatic number at least $r$ would refute the main theorem; none is expected. Because the pentagon upper bound depends on Lemma 4.4, an independent verification of that lemma for small $t$ and $\\varepsilon$—or a counterexample where the common out-neighborhood fails to be linear—would settle whether the $1/3$ profile is truly established.","tokens_in":15552,"feed_emoji":"🎯","tokens_out":8338,"duration_ms":73421,"temperature":0.7,"pith_summary":"The paper determines exact density thresholds for coloring digraphs that avoid a specified oriented subgraph. Its main result is a directed analogue of the classical Andr\\'asfai\\textendash Erd\\H{o}s\\textendash S\\'os theorem: a digraph on $n$ vertices with no transitive tournament on $r$ vertices and minimum out-degree greater than $\\frac{3r-7}{3r-4}n$ must be $(r-1)$-colorable, and no smaller density works. It also fixes the 2-coloring profile of every directed odd cycle at $1/2$, and of the three non-directed orientations of the pentagon at $1/3$. The significance is a precise dictionary between local density and global colorability in directed graphs, matching the known undirected picture.","feed_headline":"A single density ratio forces coloring in tournament-free digraphs","feed_subtitle":"Above this exact density, tournament-free digraphs must be (r-1)-colorable—and the bound is sharp.","key_machinery":"The key transfer device is the double orientation map, which sends each undirected edge to a pair of antiparallel arcs and turns the undirected sharpness example into a sharpness example for the directed theorem. The upper bound is carried by a saturation argument built around the 5-wheel-like digraph $\\vec W_{r,t}$: two transitive tournaments on $r-2$ vertices sharing $t$ vertices, attached to vertices $v,w_1,w_2$ so that the only missing underlying edges are $vw_1$ and $vw_2$. Bounding the shared part $t\\le r-3$ and counting how many common out-neighbors large sets must have forces $\\delta^+(\\hat D)\\le \\frac{3r-7}{3r-4}n$, contradicting the density assumption. For the pentagon orientations, the mechanism is a selection lemma that produces long chains of large common out-neighborhoods (Corollary 4.5), which is then used to embed arbitrary orientations of short cycles in dense digraphs.","core_discovery":"The central claim is Theorem 1.1: for every $r\\ge 3$, $\\delta_\\chi^+(T_r, r-1) = \\frac{3r-7}{3r-4}$. In words, every $T_r$-free digraph with minimum out-degree above this fraction of $n$ is $(r-1)$-colorable, and the double orientation of the extremal graph used for the undirected theorem shows the constant cannot be lowered. The proof of the upper bound runs through a saturation argument: a maximal $T_r$-free digraph either has a complete multipartite underlying graph, in which case an induction on $r$ applies, or it contains a 5-wheel-like structure whose out-neighborhood counts contradict the density assumption. The same paper establishes the exact 2-coloring profiles for directed odd cycles ($1/2$) and for the three remaining pentagon orientations ($1/3$).","pith_inferences":["Beyond the paper's statements, the $1/3$ threshold for the pentagon orientations suggests that other orientations of odd cycles admitting a homomorphism to the directed triangle may also have profile $1/3$; the paper leaves this open in Question 2.","The lower-bound constructions all contain source vertices, so a natural test not performed here is whether the thresholds drop when minimum out-degree is replaced by minimum semi-degree.","If the unproved selection lemma were given explicit constants, the stability theorem's $o(n^2)$ arc-deletion bound might become quantitative, yielding a concrete exponent in the arc-deletion count.","The contrast the paper records between chromatic profiles and chromatic thresholds for the pentagon orientations suggests that profile equality need not track threshold ordering, a phenomenon worth testing on longer odd cycles."],"forward_implications":["The undirected Andr\\'asfai\\textendash Erd\\H{o}s\\textendash S\\'os theorem follows as a direct corollary by replacing each edge of a graph with a pair of antiparallel arcs.","A stability statement accompanies the main theorem: a $T_r[t]$-free digraph with minimum out-degree at least $\\frac{3r-7}{3r-4}+\\varepsilon$ times $n$ can be made $(r-1)$-partite by deleting $o(n^2)$ arcs.","The directed odd-cycle result means any digraph with minimum out-degree above $n/2$ and chromatic number at least $3$ must contain a directed odd cycle of every specified length.","For the pentagon, the identical $1/3$ profile for the three non-directed orientations says that above one-third density, avoiding any one of those orientations forces bipartiteness.","If the main theorem is correct, it gives a complete directed analogue of the classical minimum-degree-to-chromatic-number hierarchy for transitive tournaments."],"supporting_citations":[{"why":"Gives the undirected minimum-degree threshold for $K_r$-free graphs that Theorem 1.1 generalizes.","marker":"[4]"},{"why":"Supplies the simple 5-wheel-based proof of the undirected threshold that is adapted into the 5-wheel-like digraph argument for the upper bound.","marker":"[7]"},{"why":"Supplies the unproved selection lemma (Lemma 4.4) that builds common out-neighborhood chains used to embed cycle orientations in the pentagon upper bound.","marker":"[11]"},{"why":"Provides the directed regularity lemma underlying the stability theorem.","marker":"[2]"},{"why":"States the minimum-degree form of the directed regularity lemma used to prove stability.","marker":"[25]"}],"fun_headline_variants":["Exact density forces coloring in tournament-free digraphs","Sharp constant: tournament-free digraphs must be (r-1)-colorable","Density threshold solved for oriented cycles and tournaments","One ratio pins coloring of tournament-free digraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the pentagon results, the load-bearing assumption is an unproved selection lemma from an unpublished manuscript: among many large vertex sets, some fixed number always share a common out-neighborhood of linear size, with constants that do not degrade as $n$ grows; if that lemma fails, the upper bound showing profiles equal to $1/3$ loses its support.","fun_headline_variants_meta":{"raw":{"variants":["Exact density forces coloring in tournament-free digraphs","Sharp constant: tournament-free digraphs must be (r-1)-colorable","Density threshold solved for oriented cycles and tournaments","One ratio pins coloring of tournament-free digraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001003,"raw_usage":{"total_tokens":4260,"prompt_tokens":976,"completion_tokens":3284,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":3214}},"tokens_in":592,"tokens_out":3284,"duration_ms":22501,"temperature":1.0,"reasoning_tokens":3214,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:14:13.434864+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A finite search for a $T_r$-free digraph with $\\delta^+(D)>\\frac{3r-7}{3r-4}n$ and chromatic number at least $r$ would refute the main theorem; none is expected. Because the pentagon upper bound depends on Lemma 4.4, an independent verification of that lemma for small $t$ and $\\varepsilon$—or a counterexample where the common out-neighborhood fails to be linear—would settle whether the $1/3$ profile is truly established.","supporting_citations":[{"cited_title":"Andr´ asfai, P","cited_arxiv_id":null,"evidence_quote":"Gives the undirected minimum-degree threshold for $K_r$-free graphs that Theorem 1.1 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the simple 5-wheel-based proof of the undirected threshold that is adapted into the 5-wheel-like digraph argument for the upper bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the unproved selection lemma (Lemma 4.4) that builds common out-neighborhood chains used to embed cycle orientations in the pentagon upper bound."},{"cited_title":"Alon and A","cited_arxiv_id":null,"evidence_quote":"Provides the directed regularity lemma underlying the stability theorem."},{"cited_title":"The regularity method for graphs and digraphs","cited_arxiv_id":"1406.6531","evidence_quote":"States the minimum-degree form of the directed regularity lemma used to prove stability."}],"review_version":2}