Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

Andrew Treglown; Louis DeBiasio

REVIEW 1 major objections 4 minor 23 references

Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.09793 v1 pith:2VJEDIQA submitted 2025-05-14 math.CO

Louis DeBiasio , Andrew Treglown This is my paper · ORCID

classification math.CO MSC 05C2005C4505C35

keywords Hamiltoncyclesdirectedgraphsminimumdegreearbitraryorientationsorientedrobustoutexpanderspancyclicitystrongconnectivity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Read 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.

The 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.

The 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.

Does 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.

This 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.

Referee Report

1 major / 4 minor

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.

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 (1)

[Appendix 5.1, Lemma 5.2] 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].

minor comments (4)

[Section 2, Lemma 2.2] 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.
[Proof of Theorem 1.3] 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)'.
[Appendix 5.1, proof of Theorem 5.4] 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.
[Appendix 5.1, proof of Lemma 5.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central theorem is derived from external black-box results and new structural/embedding lemmas, with no fitted parameters renamed as predictions.

full rationale

The paper's main result, Theorem 1.3, is proved by combining two independent components: Proposition 2.1, which partitions the digraph into robust outexpanders via Lemmas 2.2 and 2.3, and Proposition 3.1, which embeds every orientation of a Hamilton cycle into that partition. Proposition 3.1 invokes Taylor's Theorem 3.4 for the single-class case, Observation 3.6 (Havet-Thomasse) for an auxiliary tournament embedding, and Theorem 3.5 for the multi-class path embedding. Theorem 3.5 is stated as a modification of Taylor's externally cited Theorem 3.4 and is derived in the appendix from Taylor's Lemma 60 and Lemma 5.1, not from the theorem it is used to prove. The self-citations, DeBiasio-Kuhn-Molla-Osthus-Taylor [6] and DeBiasio-Molla [7], appear only as background and as open-problem framing; they are not load-bearing premises of the proof. No parameter is fitted to the target Hamilton cycle, and no quantity called a prediction is defined in terms of the conclusion. The apparent incompleteness in the sketch of Lemma 5.2 noted by a skeptical reader is a potential correctness gap in transferring robust expansion to random parts, not a circularity: it concerns whether an external argument is correctly adapted, not whether the theorem is assumed in its own proof. Thus the derivation chain is not circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proof introduces no empirically fitted parameters and no new objects. It relies on external theorems from Taylor [20], Ghouila-Houri [8], Aldred-Holton-Min [1], and standard probabilistic tools. Those dependencies are listed above as axioms.

assumptions (6)

domain assumption Taylor's Theorem 3.4: a robust (ν,τ)-outexpander with linear minimum semi-degree contains every orientation of a Hamilton cycle.
Used as the external embedding engine in Proposition 3.1 and derived from [20, Theorem 49]; the current paper does not reprove it.
domain assumption Taylor's Lemma 5.1: robust outexpanders contain all oriented paths of moderate length between prescribed endpoints.
Quoted from [20] and used repeatedly in the proof of Theorem 3.5.
domain assumption Lemma 60 / Lemma 5.2: robust outexpanders can be split into prescribed-size robust outexpanders with uniform degree control.
Lemma 5.2 generalizes [20, Lemma 60]; the paper gives only a proof sketch using the digraph regularity lemma.
standard math Ghouila-Houri's theorem: strongly connected digraph with δ(G)≥n has a directed Hamilton cycle.
Used in Observation 1.9 to extract directed 2-factors; a classical external result.
domain assumption Aldred, Holton and Min degree characterisation of pancyclicity.
Used in the moreover part of Theorem 1.6 to ensure pancyclicity of the double-edge graph.
standard math Kővári, Sós and Turán theorem and Chernoff bounds for the hypergeometric distribution.
Used in Case 1 of Theorem 1.6 and in the random partition argument in Lemma 5.2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree." pith.science (2026). https://pith.science/paper/2VJEDIQA

@misc{pith2026250509793,
  author       = {Pith},
  title        = {Pith review of: Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2VJEDIQA}},
  note         = {Machine review of arXiv:2505.09793}
}

abstract

In 1960, Ghouila-Houri proved that every strongly connected directed graph $G$ on $n$ vertices with minimum degree at least $n$ contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph $G$ on $n$ vertices and with minimum degree at least $(1+o(1))n$ contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when $G$ is not strongly connected. In fact, this minimum degree condition forces every orientation of a cycle in $G$ of every possible length, other than perhaps the directed cycles.

Figures

Figures reproduced from arXiv: 2505.09793 by the authors.

**Figure 1.** Case 1(b): An example with q = 4 We now know in which classes we wish to embed each segment P ′ i of P ′ . This tells us how many vertices are ‘left’ in each class Vj that we need to cover using P. In particular, note that by the way we defined T, there are at least ρn vertices in each class Vj that will not be used for embedding P ′ ; 2 so these vertices will have to be covered by P. We will embed P so that it goes… view at source ↗

**Figure 2.** Case 2, Step 2 First suppose that 0 < ds ≤ η 6β . Since |Vs| ≥ ηn, how we defined ns and ns−1, together with (3.1), implies that ns − ns−1 ≥ ηn − 2βn. Using this with (3.1) ensures that we can select ds sinks xk s 1 , . . . , xk s ds on Ps where (D1) ns−1 + 2βn < ks 1 < ks 2 < · · · < ks ds < ns − 2βn; (D2) xk s 1 , . . . , xk s ds do not lie on the directed segment P ∗ s ; (D3) for all 1 ≤ i < j ≤ ds we have that k… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[20]

A. Taylor. The regularity method for graphs and digraphs.arXiv preprint arXiv:1406.6531, 2014. 1.2, 2, 3, 3.4, 3, 5.1, 5.1, 5.1, 3, 5.1

arXiv 2014
[1]

R. E. L. Aldred, D. A. Holton, and Z. K. Min. A degree characterisation of pancyclicity.Discrete Math., 127:23–29, 1994. 1.2, 5.2

work page 1994
[2]

J. A. Bondy. Pancyclic graphs I.J. Combin. Theory Ser. B, 11:80–84, 1971. 1.2

work page 1971
[3]

A. H. Busch, M. S. Jacobson, T. Morris, M. J. Plantholt, and S. K. Tipnis. Improved sufficient con- ditions for the existence of anti-directed Hamiltonian cycles in digraphs.Graphs Combin., 29(3):359–364,

work page
[4]

M.-C. Cai. A counterexample to a conjecture of Grant.Discrete Math., 44(1):111, 1983. 1.1, 4

work page 1983
[5]

P. Camion. Chemins et circuits hamiltoniens des graphes complets.C. R. Acad. Sci. Paris, 249:2151– 2152, 1959. 1.1

work page 1959
[6]

DeBiasio, D

L. DeBiasio, D. K¨ uhn, T. Molla, D. Osthus, and A. Taylor. Arbitrary orientations of Hamilton cycles in digraphs.SIAM J. Discrete Math., 29(3):1553–1584, 2015. 1.1, 1.5

work page 2015
[7]

DeBiasio and T

L. DeBiasio and T. Molla. Semi-degree threshold for anti-directed Hamiltonian cycles.Electron. J. Combin., 22(4):P4.34, 2015. 1.1

work page 2015

Show all 23 references

[8]

Ghouila-Houri

A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien.C.R. Acad. Sci. Paris, 251(4):495–497, 1960. 1.1, 1.1, 1.2

1960
[9]

D. Grant. Antidirected Hamiltonian cycles in digraphs.Ars Combin., 10:205–209, 1980. 1.1

1980
[10]

Gr¨ unbaum

B. Gr¨ unbaum. Antidirected Hamiltonian paths in tournaments.J. Combin. Theory Ser. B, 11(3):249– 257, 1971. 1.1

1971
[11]

H¨ aggkvist and A

R. H¨ aggkvist and A. Thomason. Oriented Hamilton cycles in digraphs.J. Graph Theory, 19(4):471–479,
[12]

F. Havet. Oriented Hamiltonian cycles in tournaments.J. Combin. Theory Ser. B, 80(1):1–31, 2000. 1.1

2000
[13]

Havet and S

F. Havet and S. Thomass´ e. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld’s conjec- ture.J. Combin. Theory Ser. B, 78(2):243–273, 2000. 1.1, 3, 4

2000
[14]

K¨ uhn and D

D. K¨ uhn and D. Osthus. A survey on Hamilton cycles in directed graphs.Eur. J. Comb., 33(5):750–766,
[15]

K¨ uhn, D

D. K¨ uhn, D. Osthus, and A. Treglown. Hamiltonian degree sequences in digraphs.J. Combin. Theory Ser. B, 100(4):367–380, 2010. 2, 2

2010
[16]

M. J. Plantholt and S. K. Tipnis. Vertex-oriented Hamilton cycles in directed graphs.Electron. J. Combin., 16(1):R115, 2009. 1.1

2009
[17]

L. R´ edei. Ein kombinatorischer satz.Acta Litt. Szeged, 7:39–43, 1934. 1.1

1934
[18]

Rosenfeld

M. Rosenfeld. Antidirected Hamiltonian paths in tournaments.J. Combin. Theory Ser. B, 12(1):93–99,
[19]

Rosenfeld

M. Rosenfeld. Antidirected Hamiltonian circuits in tournaments.J. Combin. Theory Ser. B, 16(3):234– 242, 1974. 1.1

1974
[21]

Thomason

A. Thomason. Paths and cycles in tournaments.Trans. Amer. Math. Soc., 296(1):167–180, 1986. 1.1

1986
[22]

Thomassen

C. Thomassen. Anti-directed Hamiltonian circuits and paths in tournaments.Math. Ann., 201:231–238,
[1973]

Before this, we introduce the main results used to obtain Theorem 3.5

1.1 5.Appendix: Proofs of Theorems 1.6 and 3.5 5.1.Deriving Theorem 3.5.In this subsection we prove Theorem 3.5. Before this, we introduce the main results used to obtain Theorem 3.5. 18 The following lemma of Taylor [20] allows us to find any not too short, not too long orien...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [20]

A. Taylor. The regularity method for graphs and digraphs.arXiv preprint arXiv:1406.6531, 2014. 1.2, 2, 3, 3.4, 3, 5.1, 5.1, 5.1, 3, 5.1

arXiv 2014

[2] [1]

R. E. L. Aldred, D. A. Holton, and Z. K. Min. A degree characterisation of pancyclicity.Discrete Math., 127:23–29, 1994. 1.2, 5.2

work page 1994

[3] [2]

J. A. Bondy. Pancyclic graphs I.J. Combin. Theory Ser. B, 11:80–84, 1971. 1.2

work page 1971

[4] [3]

A. H. Busch, M. S. Jacobson, T. Morris, M. J. Plantholt, and S. K. Tipnis. Improved sufficient con- ditions for the existence of anti-directed Hamiltonian cycles in digraphs.Graphs Combin., 29(3):359–364,

work page

[5] [4]

M.-C. Cai. A counterexample to a conjecture of Grant.Discrete Math., 44(1):111, 1983. 1.1, 4

work page 1983

[6] [5]

P. Camion. Chemins et circuits hamiltoniens des graphes complets.C. R. Acad. Sci. Paris, 249:2151– 2152, 1959. 1.1

work page 1959

[7] [6]

DeBiasio, D

L. DeBiasio, D. K¨ uhn, T. Molla, D. Osthus, and A. Taylor. Arbitrary orientations of Hamilton cycles in digraphs.SIAM J. Discrete Math., 29(3):1553–1584, 2015. 1.1, 1.5

work page 2015

[8] [7]

DeBiasio and T

L. DeBiasio and T. Molla. Semi-degree threshold for anti-directed Hamiltonian cycles.Electron. J. Combin., 22(4):P4.34, 2015. 1.1

work page 2015