Oriented Discrepancy of The Square of Hamilton Cycles

Jin Yan; Shuo Wei; Yangyang Cheng; Yufei Chang; Zhilan Wang

arxiv: 2605.20746 · v1 · pith:7MYT7GKMnew · submitted 2026-05-20 · 🧮 math.CO

Oriented Discrepancy of The Square of Hamilton Cycles

Yufei Chang , Yangyang Cheng , Zhilan Wang , Shuo Wei , Jin Yan This is my paper

Pith reviewed 2026-05-21 04:26 UTC · model grok-4.3

classification 🧮 math.CO

keywords oriented graphsHamilton cyclessquares of cyclesoriented discrepancyminimum degreespanning subgraphs

0 comments

The pith

Every sufficiently large oriented graph with minimum degree 2n/3 contains a squared Hamilton cycle whose oriented discrepancy exceeds a function of the degree and n.

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

The paper shows that a minimum-degree condition of 2n/3 forces the existence of a squared Hamilton cycle carrying a guaranteed directional imbalance in its edges. This extends an earlier result that obtained the same guarantee for ordinary Hamilton cycles. A reader would care because the result ties local edge orientations to a global spanning structure with measurable bias. If the claim holds, it means the same density threshold that produces a cycle also produces one with controlled imbalance between forward and backward directions.

Core claim

For all sufficiently large n, every oriented graph G on n vertices satisfying δ(G) ≥ 2n/3 contains a Hamilton cycle H such that the square of H has oriented discrepancy σ_max(H) bounded below by a positive function that depends on δ(G) and n.

What carries the argument

The square of a Hamilton cycle, together with the oriented discrepancy measure σ_max that records the largest imbalance between forward and backward oriented edges in that square.

If this is right

The same degree condition that guarantees an ordinary Hamilton cycle also guarantees one whose square carries positive oriented discrepancy.
The discrepancy lower bound is stated explicitly in terms of the minimum degree and the number of vertices.
The guarantee applies to every oriented graph meeting the degree condition once n is large enough.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same technique may extend to higher powers of Hamilton cycles under comparable degree conditions.
Random oriented graphs with minimum degree near 2n/3 could serve as test cases for the sharpness of the discrepancy bound.
Similar imbalance results might hold for other spanning structures that add a bounded number of local edges along a cycle.

Load-bearing premise

The minimum-degree threshold of 2n/3 is large enough to force both the existence of a squared Hamilton cycle and a positive lower bound on its maximum oriented discrepancy when n is large.

What would settle it

An explicit oriented graph on a large n with minimum degree at least 2n/3 in which every squared Hamilton cycle has oriented discrepancy strictly below the claimed function of δ(G) and n.

read the original abstract

For an oriented graph $G$, the oriented discrepancy problem concerns the existence of a spanning subgraph of $G$ with a large imbalance between its forward and backward edge orientations. Freschi and Lo proved the Dirac-type Hamilton cycle result in oriented graphs, and asked for an analogue for powers of Hamilton cycles under a minimum-degree condition. We show that, for sufficiently large $n$, every oriented graph $G$ on $n$ vertices with minimum degree $\delta(G)\geq 2n/3$ contains the square of a Hamilton cycle $H$ with $\sigma_{\max}(H)$ guaranteed to exceed a function depending on $\delta(G)$ and $n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends the Freschi-Lo Hamilton cycle theorem to squares of cycles in oriented graphs with an oriented discrepancy bound.

read the letter

Hi colleague, The main point with this paper is that it proves the square of a Hamilton cycle exists in oriented graphs with min degree 2n/3 for large n, and with a discrepancy guarantee that depends on the degree. This directly fills the gap that Freschi and Lo pointed out for powers of cycles. The work does well by not raising the degree condition, which means the embedding argument for the square must be flexible enough to also optimize the orientations for better discrepancy. Credit to them for making the extension work under the existing threshold. The soft spots are that we only get the result for large n, so the proof likely has some absorption or regularity steps that require big n to clean up the constants. The exact discrepancy function is not given in the abstract, which leaves open how good it really is compared to what the degree allows. Also, without the full proof, it's tough to see if the discrepancy is achieved by a simple choice or requires careful selection at each step. No major flaws jump out from the stress test, though, and the central argument looks consistent. This is aimed at combinatorialists who follow results on Hamilton cycles in oriented graphs. Someone reading the Freschi-Lo paper would find this a natural follow-up and get something concrete from it. I recommend sending it to peer review. The idea is clear and the claim seems supported by the setup. Cheers

Referee Report

0 major / 3 minor

Summary. The paper proves that for all sufficiently large n, every oriented graph G on n vertices with minimum degree δ(G) ≥ 2n/3 contains the square of a Hamilton cycle H such that the oriented discrepancy σ_max(H) exceeds a positive function of δ(G) and n. The result extends the Dirac-type Hamilton cycle theorem of Freschi and Lo to the square of the cycle while adding a discrepancy guarantee, using the same minimum-degree threshold to ensure sufficient flexibility for embedding two-step paths and selecting orientations that produce the desired imbalance.

Significance. If the result holds, it meaningfully extends discrepancy theory to powers of Hamilton cycles in oriented graphs at the same degree threshold already known to force directed Hamilton cycles. This indicates that the extra structure required for squares can be accommodated without strengthening the degree condition, which is a positive sign for potential generalizations to higher powers. The explicit dependence of the discrepancy bound on δ(G) and n is a strength, as is the use of standard absorption or regularity techniques to absorb constants for large n.

minor comments (3)

Abstract: the lower bound on σ_max(H) is described only as 'a function depending on δ(G) and n'; stating the explicit form (or at least its leading term) in the abstract or Theorem 1.1 would make the quantitative strength of the result immediately clear.
Introduction: ensure that the notation σ_max(H) and the precise definition of oriented discrepancy are introduced before any informal discussion of the main result.
The proof sketch in §3 relies on an embedding lemma for two-step paths; a short remark clarifying how the minimum-degree condition supplies the extra room needed for orientation choices would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, as well as for the recommendation of minor revision. The assessment correctly identifies the extension of the Freschi-Lo theorem to squares of Hamilton cycles together with the oriented discrepancy guarantee at the same minimum-degree threshold. We are pleased that the potential for further generalizations is noted.

Circularity Check

0 steps flagged

No significant circularity; derivation builds on external prior result

full rationale

The paper extends the known Dirac-type Hamilton cycle theorem of Freschi and Lo (external authors) to squares of Hamilton cycles in oriented graphs under the same minimum-degree threshold δ(G) ≥ 2n/3, while adding an oriented discrepancy bound σ_max(H). The abstract and description present this as a direct extension using the flexibility afforded by the existing degree condition for embedding two-step paths and selecting orientations; no equations or steps reduce by construction to self-defined quantities, fitted inputs renamed as predictions, or load-bearing self-citations. The 'sufficiently large n' qualifier absorbs standard regularity/absorption constants without circularity. The result remains self-contained against the cited external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard background results in oriented-graph Hamiltonicity and the assumption that n is large enough for the degree condition to suffice; no free parameters, new entities, or ad-hoc axioms are visible from the abstract.

axioms (1)

standard math Dirac-type minimum-degree conditions suffice for Hamilton cycles in oriented graphs (as proved by Freschi and Lo)
The abstract explicitly builds on that prior result and extends it to squares.

pith-pipeline@v0.9.0 · 5640 in / 1192 out tokens · 45091 ms · 2026-05-21T04:26:17.756342+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.5: ... σ_max(H) ≥ max{n, f(δ(G), n) − ξn} ... using Diregularity, Blow-up, absorbing 2-paths and reservoir
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 4.5 (Almost covering lemma) ... σ_max(Q) ≥ g(δ(G), n) − O(d)n via T_r / T_{r-1} tiling and N_r, M_n parameters

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

J. Ai, Q. Guo, G. Gutin, Y. Lan, Q. Shao, A. Yeo, Y. Zhou, Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition,arXiv:2501.05968v2 [math.CO]. 1

work page arXiv
[2]

Alon and A

N. Alon and A. Shapira, Testing subgraphs in directed graphs,J. Comput. Syst. Sci.69 (2004) 353–382. 3.1

work page 2004
[3]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar, On the discrepancies of graphs,Electron. J. Combin.27 (2020) P2.12. 1

work page 2020
[4]

Balogh, B

J. Balogh, B. Csaba, A. Pluh´ ar and A. Treglown, A discrepancy version of the Hajnal– Szemer´ edi theorem,Combin. Probab. Comput.30 (2021) 444–459. 1

work page 2021
[5]

Balogh, A

J. Balogh, A. Freschi and A. Treglown, Ramsey-type problems for tilings in dense graphs,Eur. J. Combin(2025) 104228 3.2, 3.6

work page 2025
[6]

Bang-Jensen and G

J. Bang-Jensen and G. Gutin,Digraphs: Theory, Algorithms and ApplicationsSpringer, Lon- don, 2000. 2.1 13

work page 2000
[7]

Bradaˇ c, Powers of Hamilton cycles of high discrepancy are unavoidable,Electron

D. Bradaˇ c, Powers of Hamilton cycles of high discrepancy are unavoidable,Electron. J. Com- bin.29 (2022) P3.22. 1

work page 2022
[8]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph and L. Gishboliner, Minimum degree threshold forH-factors with high discrepancy,Electron. J. Combin.31 (2024) P3.33. 1

work page 2024
[9]

Chang, Y

Y. Chang, Y. Cheng, Z. Wang, S. Wei, and J. Yan, An Ore-type Theorem for Oriented Discrepancy of Hamilton Cycles,arXiv:2603.18915v2 [math.CO]. 1, 1.3, 6

work page arXiv
[10]

DeBiasio, J

L. DeBiasio, J. Han, A. Lo, T. Molla, S. Piga, and A. Treglown, Powers of Hamilton cycles in oriented and directed graphs,Combin. Probab. Comput.35(1) (2026), 101–133. 1

work page 2026
[11]

Dirac, Some theorems on abstract graphs.Proc

G.A. Dirac, Some theorems on abstract graphs.Proc. Lond. Math. Soc.2 (1952) 69-81. 1

work page 1952
[12]

Dragani´ c, D

N. Dragani´ c, D. Munh´ a Correia, and B. Sudakov, Tight bounds for powers of Hamilton cycles in tournaments,J. Combin. Theory Ser. B158 (2023) 305–340. 1

work page 2023
[13]

Dragani´ c, F

N. Dragani´ c, F. Dross, J. Fox, A. Gir˜ ao, F. Havet, D. Kor´ andi, W. Lochet, D. M. Correia, A. Scott, and B. Sudakov. Powers of paths in tournaments.Combin. Probab. Comput.30 (2021) 894–898. 4.3

work page 2021
[14]

P. Erd˝ os. Ramsey ´ es Van der Waerden t´ etel´ evel Kapcsolatos Kombinatorikai K´ erd´ esekr˝ ol,Mat. Lapok.14 (1963) 29–37. 1

work page 1963
[15]

Erd˝ os and J

P. Erd˝ os and J. H. Spencer, Imbalances ink-colorations,Networks1 (1971) 379–385. 1

work page 1971
[16]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown, A note on colour-bias Hamilton cycles in dense graphs.SIAM J. Discrete Math.35 (2021) 970–975. 1

work page 2021
[17]

Freschi and A

A. Freschi and A. Lo, An oriented discrepancy version of Dirac’s theorem,J. Combin. Theory, Ser. B169 (2024) 338–351. 1, 1.2, 1, 1.4, 6

work page 2024
[18]

Gishboliner, S

L. Gishboliner, S. Glock, A. Sgueglia, Tight Hamilton cycles with high discrepancy,Combin. Probab. Comput.34 (2025) 565-584. 1

work page 2025
[19]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Colour-biased Hamilton cycles in random graphs,Random Struct. Algorithms60 (2020) 289–307. 1

work page 2020
[20]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Discrepancies of spanning trees and Hamilton cycles,J. Comb. Theory, Ser. B154 (2022) 262–291. 1

work page 2022
[21]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Oriented discrepancy of Hamilton cycles,J. Graph Theory103 (2023) 780–792. 1

work page 2023
[22]

K¨ uhn, D

D. K¨ uhn, D. Osthus, Embedding large subgraphs into dense graphs. InSurveys in combi- natorics 2009, volume 365 of London Math. Soc. Lecture Note Ser.Cambridge Univ. Press, Cambridge, (2009) 137-167. 3.1

work page 2009
[23]

Kelly, D

L. Kelly, D. K¨ uhn, D. Osthus, A Dirac-type result on Hamilton cycles in oriented graphs, Combin. Probab. Comput17 (2008) 689-709. 3.2, 3.1, 3.4 14

work page 2008
[24]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi, Blow-up Lemma,Combinatorica17 (1997) 109-

work page 1997
[25]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi, Proof of the Seymour conjecture for large graphs, Ann. Comb.2 (1998) 43–60. 1, 1.1

work page 1998
[26]

Koml´ os, M

J. Koml´ os, M. Simonovits. Szemer´ edi’s regularity lemma and its applications in graph theory. In Combinatorics, Paul Erd˝ os is Eighty, Vol. 2 (Keszthely, 1993), 295-352, 1996. 3.5

work page 1993
[27]

Levitt, G

I. Levitt, G. N. S´ ark¨ ozy, and E. Szemer´ edi, How to avoid using the regularity lemma: P´ osa’s conjecture revisited,Discr. Math.310 (2010) 630–641. 4, 4.7, 4.8, 4.9, 5.1

work page 2010
[28]

Generate 12 adjacency matrices of non-isomorphic tournamentsT 5

V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput.15 (2006) 229–251. 2.2 15 A Verification ofM 5 = 3 In this section, we verify the equalityM 5 = 3 using a Python program. The first part of the program enumerates all non-isomorphic tournaments on five vertices, and the second part checks t...

work page 2006

[1] [1]

J. Ai, Q. Guo, G. Gutin, Y. Lan, Q. Shao, A. Yeo, Y. Zhou, Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition,arXiv:2501.05968v2 [math.CO]. 1

work page arXiv

[2] [2]

Alon and A

N. Alon and A. Shapira, Testing subgraphs in directed graphs,J. Comput. Syst. Sci.69 (2004) 353–382. 3.1

work page 2004

[3] [3]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar, On the discrepancies of graphs,Electron. J. Combin.27 (2020) P2.12. 1

work page 2020

[4] [4]

Balogh, B

J. Balogh, B. Csaba, A. Pluh´ ar and A. Treglown, A discrepancy version of the Hajnal– Szemer´ edi theorem,Combin. Probab. Comput.30 (2021) 444–459. 1

work page 2021

[5] [5]

Balogh, A

J. Balogh, A. Freschi and A. Treglown, Ramsey-type problems for tilings in dense graphs,Eur. J. Combin(2025) 104228 3.2, 3.6

work page 2025

[6] [6]

Bang-Jensen and G

J. Bang-Jensen and G. Gutin,Digraphs: Theory, Algorithms and ApplicationsSpringer, Lon- don, 2000. 2.1 13

work page 2000

[7] [7]

Bradaˇ c, Powers of Hamilton cycles of high discrepancy are unavoidable,Electron

D. Bradaˇ c, Powers of Hamilton cycles of high discrepancy are unavoidable,Electron. J. Com- bin.29 (2022) P3.22. 1

work page 2022

[8] [8]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph and L. Gishboliner, Minimum degree threshold forH-factors with high discrepancy,Electron. J. Combin.31 (2024) P3.33. 1

work page 2024

[9] [9]

Chang, Y

Y. Chang, Y. Cheng, Z. Wang, S. Wei, and J. Yan, An Ore-type Theorem for Oriented Discrepancy of Hamilton Cycles,arXiv:2603.18915v2 [math.CO]. 1, 1.3, 6

work page arXiv

[10] [10]

DeBiasio, J

L. DeBiasio, J. Han, A. Lo, T. Molla, S. Piga, and A. Treglown, Powers of Hamilton cycles in oriented and directed graphs,Combin. Probab. Comput.35(1) (2026), 101–133. 1

work page 2026

[11] [11]

Dirac, Some theorems on abstract graphs.Proc

G.A. Dirac, Some theorems on abstract graphs.Proc. Lond. Math. Soc.2 (1952) 69-81. 1

work page 1952

[12] [12]

Dragani´ c, D

N. Dragani´ c, D. Munh´ a Correia, and B. Sudakov, Tight bounds for powers of Hamilton cycles in tournaments,J. Combin. Theory Ser. B158 (2023) 305–340. 1

work page 2023

[13] [13]

Dragani´ c, F

N. Dragani´ c, F. Dross, J. Fox, A. Gir˜ ao, F. Havet, D. Kor´ andi, W. Lochet, D. M. Correia, A. Scott, and B. Sudakov. Powers of paths in tournaments.Combin. Probab. Comput.30 (2021) 894–898. 4.3

work page 2021

[14] [14]

P. Erd˝ os. Ramsey ´ es Van der Waerden t´ etel´ evel Kapcsolatos Kombinatorikai K´ erd´ esekr˝ ol,Mat. Lapok.14 (1963) 29–37. 1

work page 1963

[15] [15]

Erd˝ os and J

P. Erd˝ os and J. H. Spencer, Imbalances ink-colorations,Networks1 (1971) 379–385. 1

work page 1971

[16] [16]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown, A note on colour-bias Hamilton cycles in dense graphs.SIAM J. Discrete Math.35 (2021) 970–975. 1

work page 2021

[17] [17]

Freschi and A

A. Freschi and A. Lo, An oriented discrepancy version of Dirac’s theorem,J. Combin. Theory, Ser. B169 (2024) 338–351. 1, 1.2, 1, 1.4, 6

work page 2024

[18] [18]

Gishboliner, S

L. Gishboliner, S. Glock, A. Sgueglia, Tight Hamilton cycles with high discrepancy,Combin. Probab. Comput.34 (2025) 565-584. 1

work page 2025

[19] [19]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Colour-biased Hamilton cycles in random graphs,Random Struct. Algorithms60 (2020) 289–307. 1

work page 2020

[20] [20]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Discrepancies of spanning trees and Hamilton cycles,J. Comb. Theory, Ser. B154 (2022) 262–291. 1

work page 2022

[21] [21]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli, Oriented discrepancy of Hamilton cycles,J. Graph Theory103 (2023) 780–792. 1

work page 2023

[22] [22]

K¨ uhn, D

D. K¨ uhn, D. Osthus, Embedding large subgraphs into dense graphs. InSurveys in combi- natorics 2009, volume 365 of London Math. Soc. Lecture Note Ser.Cambridge Univ. Press, Cambridge, (2009) 137-167. 3.1

work page 2009

[23] [23]

Kelly, D

L. Kelly, D. K¨ uhn, D. Osthus, A Dirac-type result on Hamilton cycles in oriented graphs, Combin. Probab. Comput17 (2008) 689-709. 3.2, 3.1, 3.4 14

work page 2008

[24] [24]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi, Blow-up Lemma,Combinatorica17 (1997) 109-

work page 1997

[25] [25]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi, Proof of the Seymour conjecture for large graphs, Ann. Comb.2 (1998) 43–60. 1, 1.1

work page 1998

[26] [26]

Koml´ os, M

J. Koml´ os, M. Simonovits. Szemer´ edi’s regularity lemma and its applications in graph theory. In Combinatorics, Paul Erd˝ os is Eighty, Vol. 2 (Keszthely, 1993), 295-352, 1996. 3.5

work page 1993

[27] [27]

Levitt, G

I. Levitt, G. N. S´ ark¨ ozy, and E. Szemer´ edi, How to avoid using the regularity lemma: P´ osa’s conjecture revisited,Discr. Math.310 (2010) 630–641. 4, 4.7, 4.8, 4.9, 5.1

work page 2010

[28] [28]

Generate 12 adjacency matrices of non-isomorphic tournamentsT 5

V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput.15 (2006) 229–251. 2.2 15 A Verification ofM 5 = 3 In this section, we verify the equalityM 5 = 3 using a Python program. The first part of the program enumerates all non-isomorphic tournaments on five vertices, and the second part checks t...

work page 2006