{"id":"2726e067-8067-4bbb-ad34-a0955bd4c966","arxiv_id":"2505.09793","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A minimum degree of (1+o(1))n in an n-vertex digraph forces every orientation of a Hamilton cycle, except the directed cycle when the graph is not strongly connected.","lead":"This paper proves that any large directed graph in which every vertex has at least (1+o(1))n incident edges contains every possible orientation of a Hamilton cycle, with one exception tied to strong connectivity. The result settles the asymptotic minimum-degree threshold for a question that connects Ghouila-Houri's theorem to tournament results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.5 is the load-bearing black box; its sketched proof for k≥3 leaves a gap in the robust-expander splitting step, and the main theorem collapses without it.","rationale":"The reader's weakest assumption correctly identifies Theorem 3.5 as the fragile point. I agree and sharpen the concern: the gap is not merely that the proof is sketched, but that the specific transfer step 'Ri = R' in Lemma 5.2 is not a formality. The reduced digraph of the induced subgraph G'[Wi] is defined on intersections Wi ∩ Vj, whose sizes are smaller than the original clusters by a factor that can be as small as ε^{1/3}. Robust expansion thresholds scale with the total number of vertices in the reduced digraph, so claiming that Ri inherits robust (ν/4,4τ)-outexpansion from R requires a slicing lemma that is not stated or proved. Without Lemma 5.2, Theorem 3.5 has no proof, and Proposition 3.1 has no embedding tool; the proof of Theorem 1.3 is therefore incomplete as written. I do not regard this as evidence that the theorem is false: the claimed result is plausible and consistent with the surrounding literature, and the missing step may be supplied by a more careful parameter hierarchy. But the manuscript as submitted relies on an unverified central lemma, so the verdict should be CONDITIONAL rather than ACCEPT: the proof of Lemma 5.2 must be completed (or an explicit citation to a full proof must be supplied) before the main theorem can be considered established.","tokens_in":22926,"tokens_out":10747,"duration_ms":98648,"concrete_test":"Write out Lemma 5.2 completely for t=3, W0=∅, with explicit constants, and verify the robust-expansion transfer. In particular, after the random partition, compare the reduced digraph R of G' (on k clusters of size m) with the reduced digraph Ri of G'[Wi] (on parts Wi∩Vj of size ≈ (mi/n)m). Prove or disprove that Ri inherits the robust (ν/4,4τ)-outexpansion property from R; if the inherited ν-term must be rescaled by ε^{1/3}, determine whether the stated hierarchy ν'≪ε≪ν can absorb that factor. If it cannot, Theorem 3.5 needs a corrected hierarchy and a complete proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim (Theorem 1.3) is reduced, in Section 3, to Proposition 3.1, and every case of Proposition 3.1 calls Theorem 3.5 to embed a prescribed oriented path inside each robust expander G[Vi] with fixed endpoints. Theorem 3.5 is therefore the load-bearing tool. Appendix 5.1 derives it from Lemma 5.2, and Lemma 5.2 is given only as a proof sketch. The specific gap is in the transfer of robust expansion to the random parts. The sketch asserts that the reduced digraph Ri of G'[Wi] is 'the same' as the reduced digraph R of G'. But Ri is defined on parts Vj^i = Wi ∩ Vj of size roughly (mi/n)|Vj|, which can be as small as ε^{1/3} times the original cluster size, so Ri is not R; it is a smaller, unevenly weighted blow-up. Robust outexpansion of R (with threshold νk/4 in the cluster count) does not automatically pass to Ri: the ν-term must be rescaled by the part-size ratio, and the claimed hierarchy 0<1/n0≪ν'≪ε≪ν gives no such rescaling. The sentence 'as argued at the end of the proof of Lemma 60 in [20]' is exactly where a non-obvious slicing lemma would be needed, and none is stated. Since Theorem 3.5 is the only mechanism for embedding arbitrary specified orientations inside each class with prescribed endpoints, the main theorem is not fully established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an asymptotic generalization of Ghouila-Houri's theorem: for every η>0, every sufficiently large n-vertex digraph with minimum total degree at least (1+η)n contains every orientation of a Hamilton cycle, except that the directed Hamilton cycle may be absent when the digraph is not strongly connected. The proof develops a robust-expander partition (Proposition 2.1) that decomposes such a digraph into robust outexpanders with sparse forward edges between them, and an embedding lemma (Proposition 3.1) that assembles arbitrary orientations of a Hamilton cycle from paths embedded inside these expanders. The embedding uses a universal linking theorem (Theorem 3.5) whose proof is deferred to an appendix and depends on a splitting lemma (Lemma 5.2) that is only sketched. The paper also derives corollaries for all oriented cycles of arbitrary length (Theorem 1.6) and for directed 2-factors.","tokens_in":23253,"tokens_out":49130,"duration_ms":410208,"significance":"If the central theorem is accepted, it is a substantial result: it asymptotically determines the minimum degree threshold for forcing every orientation of a Hamilton cycle in a digraph, generalizes Ghouila-Houri's theorem for strongly connected digraphs, asymptotically resolves a conjecture on anti-directed Hamilton cycles, and asymptotically strengthens the semi-degree theorem of DeBiasio, Kühn, Molla, Osthus and Taylor. The proof introduces a new structural partition tool (Proposition 2.1) and a clean reduction to a universal linking statement in robust expanders. However, the main theorem rests on Theorem 3.5, whose appendix proof relies on a lemma that is only sketched; this is a load-bearing presentation gap that needs to be addressed before the result is fully validated.","major_comments":[{"comment":"Lemma 5.2 is load-bearing for the main theorem: Theorem 3.5 (universally k-linked) is applied in every case of Proposition 3.1, and the appendix proves Theorem 3.5 only through Lemma 5.2. The proof of Lemma 5.2 is a sketch, and the crucial transfer step is not demonstrated. The assertion that 'the reduced digraph R_i of G'[W_i] is the same as the reduced digraph R of G'' is imprecise: at best (P1) shows that every edge of R is an edge of R_i, and the reverse inclusion is not needed for the expansion argument, but the proof does not say this. More importantly, the final sentence 'as argued at the end of the proof of Lemma 60 in [20]' covers exactly the non-obvious step where robust outexpansion of the reduced digraph (a property about cluster indices) is converted into robust outexpansion of G[W_i] (a property about individual vertices) despite the parts V_j^i having sizes only about (m_i/n)|V_j|, which can be as small as ε^{1/3} times the original cluster size. This step requires a slicing lemma and a careful calculation; it is not a routine one-liner. Since the main theorem collapses without Theorem 3.5, the authors should either provide a complete proof of Lemma 5.2 in the appendix or give a precise, self-contained statement of the slicing lemma and the transfer calculation, with exact references to the corresponding argument in [20].","section":"Appendix 5.1, Lemma 5.2"}],"minor_comments":[{"comment":"In the proof of Lemma 2.2, the sentence beginning 'if |C|≤(ατ−ν)n' is missing a connective; it should be 'If |C|≤(ατ−ν)n, then...'. Also, the displayed inequality after the degree counting appears to have a small constant discrepancy: the term 2νn|A| becomes 3νn|A| in the following line; the authors should check the constants.","section":"Section 2, Lemma 2.2"},{"comment":"For the directed Hamilton cycle in the case where G is strongly connected, the proof should explicitly invoke Ghouila-Houri's theorem (Theorem 1.1) rather than leaving it implicit in the phrase 'except for perhaps the directed Hamilton cycle (in the case when G is not strongly connected)'.","section":"Proof of Theorem 1.3"},{"comment":"Theorem 5.4 is stated without proof, and the explanation that it follows from Step 4 of the proof of Theorem 3.4 in [20] is very brief. Since this is a standard and plausible modification, a few more sentences describing how the prescribed vertex is embedded would help the reader verify the claim.","section":"Appendix 5.1, proof of Theorem 5.4"},{"comment":"The claim that 'the reduced digraph R_i of G'[W_i] is the same as the reduced digraph R of G'' should be replaced by the weaker and more accurate statement that R_i contains R as a spanning subdigraph, since the restriction of an ε-regular pair of density at least d to the random subset is ε^{1/2}-regular of density at least d−ε, but the converse need not hold.","section":"Appendix 5.1, proof of Lemma 5.2"}],"recommendation":"major_revision","confidential_remarks":"The paper presents a significant and well-organized contribution, and my own reading of the new structural arguments (Propositions 2.1 and 3.1) suggests they are sound. The main obstacle is the appendix: Lemma 5.2, on which Theorem 3.5 depends, is only sketched, with the key transfer step delegated to an arXiv preprint rather than proved. I would be willing to support acceptance if the authors supply a complete proof of Lemma 5.2 or a detailed modification of Taylor's Lemma 60, including the slicing argument and the robust-expansion transfer. The result itself appears correct and within the scope of the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead DeBiasio-Treglown's paper. The main theorem is exactly what it claims: minimum degree (1+o(1))n forces every orientation of a Hamilton cycle, except the directed one when the digraph is not strongly connected. That asymptotically settles the Grant/DeBiasio-Molla anti-directed problem and is a genuine extension of Ghouila-Houri. The pancyclicity corollaries (every oriented cycle of all lengths except long directed cycles) are new as well.\n\nThe architecture is sound. Proposition 2.1 gives a robust partition: either the whole digraph is a robust outexpander, or it splits into a few large robust outexpanders with edges roughly forming a transitive-tournament blow-up. Then Proposition 3.1 embeds any orientation by threading segments through the classes. The case analysis is intricate but plausible; I did not find an obvious hole in the main embedding steps.\n\nThe soft spot is the appendix. Theorem 3.5 (universally k-linked) is load-bearing, and it is derived from a sketched Lemma 5.2 via a \"tweak\" of Lemma 60 in Taylor's unpublished manuscript. The proof of Lemma 5.2 is only a sketch, and the key transfer from robust expansion of the reduced digraph to robust expansion of the random slices is summarized in one sentence citing Taylor. I checked the stress-test claim that the reduced digraph Ri is \"not R\" because the parts are smaller. I think that specific objection is a misreading: their regularity lemma gives densities either 0 or at least d, so the induced reduced digraph on the sliced clusters has exactly the same edge set as R, regardless of part sizes. The hierarchy nu' << epsilon << nu is exactly what makes the vertex-level expansion go through. So the concern as stated does not land. The real issue is simply that the proof of a central lemma is not written out; a referee will need Taylor's paper in hand to verify the tweak.\n\nDoes that make the paper flawed? Not as far as I can tell. The dependence on external material is explicit, and this is normal for the area. But it does mean the proof is not self-contained at this stage. If Taylor's Lemma 60 has the full argument, Theorem 3.5 is fine; if not, the main theorem has a gap. That is a presentation problem, not an evident mathematical error.\n\nThis paper is for anyone working on Hamilton cycles in digraphs or minimum-degree thresholds. It deserves a serious referee. I would send it to review and ask the referees to pay close attention to Appendix 5.1. I would not desk-reject.","headline":"A strong new threshold result that asymptotically resolves the anti-directed Hamilton cycle conjecture; proof is convincing in outline, with a terse appendix that should be checked carefully.","tokens_in":23766,"tokens_out":10329,"would_cite":true,"duration_ms":97403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C45","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every sufficiently large n-vertex digraph with minimum degree at least (1+η)n contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle when the digraph is not strongly connected.","keywords":["Hamilton cycles","directed graphs","minimum degree","arbitrary orientations","oriented cycles","robust outexpanders","pancyclicity","strong connectivity"],"falsifier":"Test the one sketched ingredient directly: in a robustly expanding digraph with linear minimum semi-degree, take the simplest untreated case of Lemma 5.2—a small prescribed set $W_0$ that must be completed to a partition into two robustly expanding subgraphs of prescribed sizes, the case already known when $W_0$ is empty. Finding a counterexample would break the embedding step and with it the proof of the main theorem; finding a complete proof would settle the step the appendix leaves sketched.","tokens_in":22744,"feed_emoji":"🔀","tokens_out":14267,"duration_ms":129529,"temperature":0.7,"pith_summary":"The paper proves an asymptotic strengthening of the classical theorem that strongly connected n-vertex digraphs with minimum degree at least n always contain a directed Hamilton cycle. It shows that minimum degree at least (1+o(1))n forces every possible orientation of a Hamilton cycle, with one exception: the all-directed cycle may fail when the digraph is not strongly connected. The result matters because it moves a phenomenon previously known only in tournaments into the general setting of dense directed graphs, at the natural degree threshold just above n. The same condition also forces every oriented cycle of every length up to n, except possibly directed cycles.","feed_headline":"Min degree just above n forces every Hamilton-cycle orientation","feed_subtitle":"Except the all-directed cycle in non-strongly-connected digraphs; shorter oriented cycles follow too.","key_machinery":"The proof is carried by two structural tools. Proposition 2.1 partitions an n-vertex digraph with δ(G)≥(1+1/(k+1)+ζ)n into at most k parts, each a robust (ν,τ)-outexpander with large minimum degree, with edges between parts oriented almost like a blow-up of a transitive tournament; if no cut is found the whole graph is itself a robust outexpander. Proposition 3.1 then shows that such a partition can host every orientation of a Hamilton cycle. The key object inside that step is Theorem 3.5, a 'universally k-linked' embedding result: a robust outexpander with linear minimum semi-degree (each vertex has in-degree and out-degree at least a positive fraction of the block size) can simultaneously host prescribed oriented paths of prescribed lengths with prescribed start and end vertices. That linking theorem, together with the robust-expander partition, is what turns the global cycle problem into a collection of independent block-embedding problems.","core_discovery":"The primary result is Theorem 1.3: for every η>0, every sufficiently large n-vertex digraph G with δ(G)≥(1+η)n contains a copy of every orientation of a Hamilton cycle, apart from the directed Hamilton cycle in the case when G is not strongly connected. This is asymptotically tight, because digraphs with minimum degree slightly below this can fail to contain any Hamilton cycle, and non-strongly-connected examples can fail to contain the directed one. The paper also derives the pancyclic consequence (Theorem 1.6 and Corollary 1.7) that the same degree condition contains every oriented cycle on at most n vertices except perhaps directed cycles, and identifies the asymptotic minimum-degree threshold for forcing a directed cycle of a specified length (Corollary 1.8).","pith_inferences":["An exact analogue is not proved here; the authors pose the open problem whether $\\delta(G)\\ge n+1$ already forces every non-directed orientation, and the methods of this paper do not reach that threshold.","The partition into robust outexpanders (Proposition 2.1) looks transferable to other spanning oriented structures, such as powers of cycles or bounded-degree oriented trees, whenever the corresponding linking theorem can be established.","The directed-cycle threshold suggests a broader dichotomy: just above $(1+1/(k+1))n$, a high-degree digraph is either expanding or a nearly transitive blow-up, so the extremal obstruction to long directed cycles is a rigid orientation between large blocks rather than a sparse cut."],"forward_implications":["Every digraph with $\\delta(G)\\ge(1+\\eta)n$ contains every orientation of a Hamilton path, not only of a Hamilton cycle.","The same degree condition forces every oriented cycle of every length up to $n$, except possibly directed cycles.","The asymptotic threshold for forcing a directed cycle of length between $\\lceil n/(k+1)\\rceil$ and $\\lceil n/k\\rceil$ is $(1+1/(k+1))n$, with the blow-up of a transitive tournament as the extremal obstruction.","For even $n$, the result asymptotically settles the conjecture that minimum degree at least $n+1$ forces an anti-directed Hamilton cycle.","The minimum-degree theorem asymptotically generalizes the sharp semi-degree theorem, since ordinary minimum degree is at least twice the minimum semi-degree."],"supporting_citations":[{"why":"Supplies the classical strong-connectivity theorem and the tightness examples that Theorem 1.3 asymptotically generalizes.","marker":"[8]"},{"why":"Provides the robust-expander theorem that every orientation of a Hamilton cycle exists in a robust outexpander, and the linking lemmas from which Theorem 3.5 is derived.","marker":"[20]"},{"why":"Introduces robust outexpansion and the Hamilton cycle result underlying Proposition 2.1's partition into expander blocks.","marker":"[15]"},{"why":"Supplies the tournament path-embedding theorem used as Observation 3.6 to route short segments through the auxiliary transitive tournament in the embedding proof.","marker":"[13]"},{"why":"Gives the pancyclicity result on which the moreover part of Theorem 1.6 relies.","marker":"[2]"},{"why":"Supplies the degree characterisation of pancyclic graphs used to prove the moreover part of Theorem 1.6.","marker":"[1]"}],"fun_headline_variants":["Min degree (1+o(1))n forces every oriented Hamilton cycle","High min degree in digraphs yields all Hamilton cycle orientations","Near-perfect min degree: every Hamilton cycle orientation appears","Min degree just above n gives every orientation of Hamilton cycle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central claim depends on a linking theorem, proved only as a sketch in the appendix, that a sufficiently dense and well-connected block can host several prescribed oriented paths with prescribed endpoints at once; if that theorem fails, the main result does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Min degree (1+o(1))n forces every oriented Hamilton cycle","High min degree in digraphs yields all Hamilton cycle orientations","Near-perfect min degree: every Hamilton cycle orientation appears","Min degree just above n gives every orientation of Hamilton cycle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00013,"raw_usage":{"total_tokens":1055,"prompt_tokens":806,"completion_tokens":249,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":422,"completion_tokens_details":{"reasoning_tokens":177}},"tokens_in":422,"tokens_out":249,"duration_ms":2858,"temperature":1.0,"reasoning_tokens":177,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:23:31.038014+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the one sketched ingredient directly: in a robustly expanding digraph with linear minimum semi-degree, take the simplest untreated case of Lemma 5.2—a small prescribed set $W_0$ that must be completed to a partition into two robustly expanding subgraphs of prescribed sizes, the case already known when $W_0$ is empty. Finding a counterexample would break the embedding step and with it the proof of the main theorem; finding a complete proof would settle the step the appendix leaves sketched.","supporting_citations":[{"cited_title":"Ghouila-Houri","cited_arxiv_id":null,"evidence_quote":"Supplies the classical strong-connectivity theorem and the tightness examples that Theorem 1.3 asymptotically generalizes."},{"cited_title":"K¨ uhn, D","cited_arxiv_id":null,"evidence_quote":"Introduces robust outexpansion and the Hamilton cycle result underlying Proposition 2.1's partition into expander blocks."},{"cited_title":"Havet and S","cited_arxiv_id":null,"evidence_quote":"Supplies the tournament path-embedding theorem used as Observation 3.6 to route short segments through the auxiliary transitive tournament in the embedding proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the pancyclicity result on which the moreover part of Theorem 1.6 relies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the degree characterisation of pancyclic graphs used to prove the moreover part of Theorem 1.6."}],"review_version":1}