pith. sign in

arxiv: 2309.12607 · v3 · submitted 2023-09-22 · 🧮 math.CO

Robust Hamiltonicity in families of Dirac graphs

Michael Anastos , Debsoumya Chakraborti This is my paper

Pith reviewed 2026-05-24 07:04 UTC · model grok-4.3

classification 🧮 math.CO
keywords Dirac graphsHamilton cycle transversalsminimum degreecounting Hamilton cyclesedge-disjoint packingrandom subgraphsgraph families
0
0 comments X

The pith

Any collection of n Dirac graphs on n vertices contains at least (c n)^{2n} distinct Hamilton cycle transversals.

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

The paper proves quantitative versions of Hamiltonicity for families of Dirac graphs, each with minimum degree at least n/2 on the same n vertices. It shows that any such collection admits at least (c n)^{2n} Hamilton cycle transversals, where each transversal is a Hamilton cycle whose edges are assigned bijectively to the n graphs so that every edge lies in its assigned graph. This lower bound is optimal up to the choice of c. The same families also contain n/2 pairwise edge-disjoint transversals when n is large. These statements extend the classical counting theorems for Hamilton cycles in one Dirac graph to the multi-graph setting via a spread measure on the transversals.

Core claim

Every collection of n Dirac graphs on n vertices contains at least (c n)^{2n} different Hamilton cycle transversals (H, φ) for an absolute constant c > 0, and this count is optimal up to c. For sufficiently large n every such collection spans n/2 pairwise edge-disjoint Hamilton cycle transversals, which is best possible. The proofs rest on constructing a spread measure supported on the set of all Hamilton cycle transversals of the family.

What carries the argument

A spread measure on the set of Hamilton cycle transversals of a family of Dirac graphs, used to obtain both the counting lower bound and the edge-disjoint packing.

If this is right

  • The threshold probability for the existence of a Hamilton cycle transversal in random subgraphs of Dirac graphs is determined up to constant factors in several models.
  • The number of transversals is at least (c n)^{2n} and this order is tight.
  • n/2 edge-disjoint transversals always exist and this packing number cannot be increased in general.
  • The results recover the known counting theorems for Hamilton cycles inside a single Dirac graph as the special case of identical graphs.

Where Pith is reading between the lines

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

  • The spread-measure method may extend to other spanning subgraphs such as Hamilton paths or spanning trees in families of dense graphs.
  • The robustness shown here indicates that the minimum-degree condition supplies enough independent choices to make many graphs simultaneously Hamiltonian-compatible.
  • It would be natural to test whether the packing result holds for smaller degree conditions or for random rather than worst-case families.

Load-bearing premise

A spread measure with the required spreading properties can be constructed on the Hamilton cycle transversals whenever every graph in the family meets the Dirac minimum-degree condition.

What would settle it

An explicit collection of n Dirac graphs on n vertices that admits strictly fewer than n^{2n} Hamilton cycle transversals would disprove the counting statement.

read the original abstract

A graph is called Dirac if its minimum degree is at least half of the number of vertices in it. Joos and Kim showed that every collection $\mathbb{G}=\{G_1,\ldots,G_n\}$ of Dirac graphs on the same vertex set $V$ of size $n$ contains a Hamilton cycle transversal, i.e., a Hamilton cycle $H$ on $V$ with a bijection $\phi:E(H)\rightarrow [n]$ such that $e\in G_{\phi(e)}$ for every $e\in E(H)$. In this paper, we determine up to a multiplicative constant, the threshold for the existence of a Hamilton cycle transversal in a collection of random subgraphs of Dirac graphs in various settings. Our proofs rely on constructing a spread measure on the set of Hamilton cycle transversals of a family of Dirac graphs. As a corollary, we obtain that every collection of $n$ Dirac graphs on $n$ vertices contains at least $(cn)^{2n}$ different Hamilton cycle transversals $(H,\phi)$ for some absolute constant $c>0$. This is optimal up to the constant $c$. Finally, we show that if $n$ is sufficiently large, then every such collection spans $n/2$ pairwise edge-disjoint Hamilton cycle transversals, and this is best possible. These statements generalize classical counting results of Hamilton cycles in a single Dirac graph.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that every collection of n Dirac graphs on n vertices contains at least (cn)^{2n} different Hamilton cycle transversals (H,φ) for some absolute constant c>0 (optimal up to c), and that every such collection spans n/2 pairwise edge-disjoint Hamilton cycle transversals for sufficiently large n (best possible). It determines thresholds for the existence of a Hamilton cycle transversal in collections of random subgraphs of Dirac graphs in various settings. All proofs rely on constructing a spread measure on the set of Hamilton cycle transversals from the minimum-degree condition alone; this generalizes classical counting results for Hamilton cycles in a single Dirac graph.

Significance. If the spread measure construction holds, the results give optimal counting and packing statements that extend the classical theorems on Hamilton cycles in Dirac graphs to the setting of families. The explicit construction of a spread measure supported on the transversals of any family of Dirac graphs is a technical strength that enables the threshold, counting, and packing claims uniformly from the degree condition.

minor comments (2)
  1. [§1] §1: the introduction states the main counting and packing corollaries but does not include a forward reference to the section containing the spread-measure construction; adding one would improve readability for readers focused on the corollaries.
  2. Notation for the family ℊ and the map φ is introduced clearly in the abstract but should be restated verbatim at the beginning of the first technical section to avoid any ambiguity when the random-subgraph thresholds are stated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept. The report contains no major comments requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity; spread measure is independent construction

full rationale

The paper's central results (counting lower bound of (cn)^{2n} transversals and packing of n/2 edge-disjoint ones) are derived as corollaries from an explicit construction of a spread measure supported on the transversals of any family of Dirac graphs, using only the minimum-degree condition. This construction is combinatorial and independent of the target counting/packing quantities; the existence result of Joos-Kim is cited only for the base case and does not carry the new quantitative claims. No equations reduce a prediction to a fitted input by construction, no self-citation chain is load-bearing for the spread measure, and the derivation does not rename known results or smuggle ansatzes. The claims are therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The claims rest on standard graph-theoretic axioms (minimum-degree conditions and basic cycle properties) plus the existence of a spread measure constructed from the Dirac condition; the only free parameter is the existential constant c whose precise value is not computed.

free parameters (1)
  • c
    Absolute positive constant appearing in the lower bound (cn)^{2n}; its existence is asserted but no explicit value or computation is given.
axioms (1)
  • standard math Dirac graphs (minimum degree at least n/2) satisfy the classical Hamiltonicity properties used as background
    Invoked throughout to guarantee the base graphs admit Hamilton cycles before random subgraphs and transversals are considered.

pith-pipeline@v0.9.0 · 5778 in / 1417 out tokens · 36681 ms · 2026-05-24T07:04:52.592043+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Transversal Structures in Graph Systems: A Survey

    math.CO 2024-12 unverdicted novelty 2.0

    Survey compiling sufficient conditions for transversal m-edge structures in graph systems that extend classical extremal graph theory results, plus conjectures.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages · cited by 1 Pith paper

  1. [1]

    A rainbow version of Mantel’s theorem

    Ron Aharoni, Matt DeVos, Sebasti´ an Gonz´ alez Hermosillo de la Maza, Amanda Montejano, and Robert ˇS´ amal. “A rainbow version of Mantel’s theorem”. In:Advances in Combinatorics (2020), Paper No. 2, 12

    work page 2020

  2. [2]

    A rainbow r-partite version of the Erd˝ os-Ko-Rado theorem

    Ron Aharoni and David Howard. “A rainbow r-partite version of the Erd˝ os-Ko-Rado theorem”. In: Combinatorics, Probability and Computing 26.3 (2017), pp. 321–337

    work page 2017

  3. [3]

    Increasing the chromatic number of a random graph

    Noga Alon and Benny Sudakov. “Increasing the chromatic number of a random graph”. In: Journal of Combinatorics 1.4 (2010), pp. 345–356

    work page 2010

  4. [4]

    Robust Hamiltonicity of Dirac hypergraphs

    Michael Anastos, Debsoumya Chakraborti, Dong Yeap Kang, Abhishek Methuku, and Vincent Pfen- ninger. “Robust Hamiltonicity of Dirac hypergraphs”. In: Forthcoming (2023)

    work page 2023

  5. [5]

    Local resilience of almost spanning trees in random graphs

    J´ ozsef Balogh, B´ ela Csaba, and Wojciech Samotij. “Local resilience of almost spanning trees in random graphs”. In: Random Structures & Algorithms 38.1-2 (2011), pp. 121–139. REFERENCES 29

    work page 2011

  6. [6]

    On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs

    Sonny Ben-Shimon, Michael Krivelevich, and Benny Sudakov. “On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs”. In: SIAM Journal on Discrete Mathematics 25.3 (2011), pp. 1176–1193

    work page 2011

  7. [7]

    The evolution of sparse graphs

    B´ ela Bollob´ as. “The evolution of sparse graphs”. In: Graph theory and combinatorics (Cambridge,

    work page

  8. [8]

    From one to many rainbow Hamiltonian cycles

    Peter Bradshaw, Kevin Halasz, and Ladislav Stacho. “From one to many rainbow Hamiltonian cycles”. In: Graphs Combin. 38.6 (2022), Paper No. 188, 21

    work page 2022

  9. [9]

    A bandwidth theorem for graph transversals

    Debsoumya Chakraborti, Seonghyuk Im, Jaehoon Kim, and Hong Liu. “A bandwidth theorem for graph transversals”. In: arXiv preprint arXiv:2302.09637 (2023)

    work page arXiv 2023

  10. [10]

    Rainbow Pancyclicity in Graph Systems

    Yangyang Cheng, Guanghui Wang, and Yi Zhao. “Rainbow Pancyclicity in Graph Systems”. In: The Electronic Journal of Combinatorics (2021), P3–24

    work page 2021

  11. [11]

    A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

    Herman Chernoff. “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations”. In: The Annals of Mathematical Statistics (1952), pp. 493–507

    work page 1952

  12. [12]

    Proof of the 1-factorization and Hamilton decomposition conjectures

    B´ ela Csaba, Daniela K¨ uhn, Allan Lo, Deryk Osthus, and Andrew Treglown. “Proof of the 1-factorization and Hamilton decomposition conjectures”. In: Mem. Amer. Math. Soc. 244.1154 (2016), pp. v+164

    work page 2016

  13. [13]

    Hamiltonian cycles in Dirac graphs

    Bill Cuckler and Jeff Kahn. “Hamiltonian cycles in Dirac graphs”. In: Combinatorica 29 (2009), pp. 299–326

    work page 2009

  14. [14]

    On the resilience of long cycles in random graphs

    Domingos Dellamonica Jr, Yoshiharu Kohayakawa, Martin Marciniszyn, and Angelika Steger. “On the resilience of long cycles in random graphs”. In: Electronic Journal of Combinatorics 15.1 (2008), R32

    work page 2008

  15. [15]

    Some theorems on abstract graphs

    Gabriel Andrew Dirac. “Some theorems on abstract graphs”. In: Proceedings of the London Mathemat- ical Society 3.1 (1952), pp. 69–81

    work page 1952

  16. [16]

    Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs

    Asaf Ferber, Jie Han, and Dingjia Mao. “Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs”. In: arXiv preprint arXiv:2211.05477 (2022)

    work page arXiv 2022

  17. [17]

    Thresholds versus fractional expectation-thresholds

    Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park. “Thresholds versus fractional expectation-thresholds”. In: Annals of Mathematics 194.2 (2021), pp. 475–495

    work page 2021

  18. [18]

    Hamilton cycles in random graphs: a bibliography

    Alan Frieze. “Hamilton cycles in random graphs: a bibliography”. In: arXiv preprint arXiv:1901.07139 (2019)

    work page arXiv 1901

  19. [19]

    A general approach to transversal versions of Dirac-type theorems

    Pranshu Gupta, Fabian Hamann, Alp M¨ uyesser, Olaf Parczyk, and Amedeo Sgueglia. “A general approach to transversal versions of Dirac-type theorems”. In: arXiv preprint arXiv:2209.09289 (2022)

    work page arXiv 2022

  20. [20]

    Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

    Vishesh Jain and Huy Tuan Pham. “Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings”. In: arXiv preprint arXiv:2212.06109 (2022)

    work page arXiv 2022

  21. [21]

    On Hamilton cycles in Erd˝ os-R´ enyi subgraphs of large graphs

    Tony Johansson. “On Hamilton cycles in Erd˝ os-R´ enyi subgraphs of large graphs”. In:Random Struc- tures Algorithms 57.1 (2020), pp. 132–149

    work page 2020

  22. [22]

    On a rainbow version of Dirac’s theorem

    Felix Joos and Jaehoon Kim. “On a rainbow version of Dirac’s theorem”. In: Bulletin of the London Mathematical Society 52.3 (2020), pp. 498–504

    work page 2020

  23. [23]

    Thresholds and expectation thresholds

    Jeff Kahn and Gil Kalai. “Thresholds and expectation thresholds”. In: Combinatorics, Probability and Computing 16.3 (2007), pp. 495–502

    work page 2007

  24. [24]

    A topological colorful Helly theorem

    Gil Kalai and Roy Meshulam. “A topological colorful Helly theorem”. In: Advances in Mathematics 191.2 (2005), pp. 305–311

    work page 2005

  25. [25]

    Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor

    Dong Yeap Kang, Tom Kelly, Daniela K¨ uhn, Abhishek Methuku, and Deryk Osthus. “Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor”. In: Transactions of the American Mathematical Society (2023)

    work page 2023

  26. [26]

    Perfect match- ings in random sparsifications of Dirac hypergraphs

    Dong Yeap Kang, Tom Kelly, Daniela K¨ uhn, Deryk Osthus, and Vincent Pfenninger. “Perfect match- ings in random sparsifications of Dirac hypergraphs”. In: arXiv preprint arXiv:2211.01325 (2022)

    work page arXiv 2022

  27. [27]

    Reducibility among combinatorial problems

    Richard M Karp. Reducibility among combinatorial problems. Springer, 2010

    work page 2010

  28. [28]

    The optimal edge-colouring threshold

    Peter Keevash. “The optimal edge-colouring threshold”. In: arXiv preprint arXiv:2212.04397 (2022)

    work page arXiv 2022

  29. [29]

    Optimal spread for spanning subgraphs of Dirac hypergraphs

    Tom Kelly, Alp M¨ uyesser, and Alexey Pokrovskiy. “Optimal spread for spanning subgraphs of Dirac hypergraphs”. In: arXiv preprint arXiv:2308.08535 (2023)

    work page arXiv 2023

  30. [30]

    Edge-disjoint Hamilton cycles in random graphs

    Fiachra Knox, Daniela K¨ uhn, and Deryk Osthus. “Edge-disjoint Hamilton cycles in random graphs”. In: Random Structures & Algorithms 46.3 (2015), pp. 397–445

    work page 2015

  31. [31]

    Proof of the Seymour conjecture for large graphs

    J´ anos Koml´ os, G´ abor N S´ ark¨ ozy, and Endre Szemer´ edi. “Proof of the Seymour conjecture for large graphs”. In: Annals of Combinatorics 2 (1998), pp. 43–60

    work page 1998

  32. [32]

    Limit distribution for the existence of Hamiltonian cycles in a random graph

    J´ anos Koml´ os and Endre Szemer´ edi. “Limit distribution for the existence of Hamiltonian cycles in a random graph”. In: Discrete mathematics 43.1 (1983), pp. 55–63. 30 REFERENCES

    work page 1983

  33. [33]

    Solution of a problem of Erd˝ os and Renyi on Hamiltonian cycles in nonoriented graphs

    Aleksei Dmitrievich Korshunov. “Solution of a problem of Erd˝ os and Renyi on Hamiltonian cycles in nonoriented graphs”. In: Doklady Akademii Nauk . Vol. 228. 3. Russian Academy of Sciences. 1976, pp. 529–532

    work page 1976

  34. [34]

    Resilient pancyclicity of random and pseudorandom graphs

    Michael Krivelevich, Choongbum Lee, and Benny Sudakov. “Resilient pancyclicity of random and pseudorandom graphs”. In: SIAM Journal on Discrete Mathematics 24.1 (2010), pp. 1–16

    work page 2010

  35. [35]

    Robust Hamiltonicity of Dirac graphs

    Michael Krivelevich, Choongbum Lee, and Benny Sudakov. “Robust Hamiltonicity of Dirac graphs”. In: Transactions of the American Mathematical Society 366.6 (2014), pp. 3095–3130

    work page 2014

  36. [36]

    Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments

    Daniela K¨ uhn and Deryk Osthus. “Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments”. In: Advances in Mathematics 237 (2013), pp. 62–146

    work page 2013

  37. [37]

    Dirac’s theorem for random graphs

    Choongbum Lee and Benny Sudakov. “Dirac’s theorem for random graphs”. In: Random Structures & Algorithms 41.3 (2012), pp. 293–305

    work page 2012

  38. [38]

    Probability and computing: Randomization and probabilistic tech- niques in algorithms and data analysis

    Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic tech- niques in algorithms and data analysis . Cambridge university press, 2017

    work page 2017

  39. [39]

    Hamiltonicity in random graphs is born resilient

    Richard Montgomery. “Hamiltonicity in random graphs is born resilient”. In: Journal of Combinatorial Theory, Series B 139 (2019), pp. 316–341

    work page 2019

  40. [40]

    Hamiltonicity in random directed graphs is born resilient

    Richard Montgomery. “Hamiltonicity in random directed graphs is born resilient”. In: Combinatorics, Probability and Computing 29.6 (2020), pp. 900–942

    work page 2020

  41. [41]

    Transversal factors and spanning trees

    Richard Montgomery, Alp M¨ uyesser, and Yani Pehova. “Transversal factors and spanning trees”. In: Advances in Combinatorics (2022)

    work page 2022

  42. [42]

    Counting spanning subgraphs in dense hypergraphs

    Richard Montgomery and Mat´ ıas Pavez-Sign´ e. “Counting spanning subgraphs in dense hypergraphs”. In: arXiv preprint arXiv:2308.07195 (2023)

    work page arXiv 2023

  43. [43]

    Hamiltonian lines in graphs whose vertices have sufficiently large valen- cies

    C. St. J. A. Nash-Williams. “Hamiltonian lines in graphs whose vertices have sufficiently large valen- cies.” In: Combinatorial theory and its applications, III (Proc. Colloq., Balatonf¨ ured, 1969), , 1970, pp. 813–819

    work page 1969

  44. [44]

    A proof of the Kahn–Kalai Conjecture

    Jinyoung Park and Huy Tuan Pham. “A proof of the Kahn–Kalai Conjecture”. In: Journal of the American Mathematical Society (2023), to appear

    work page 2023

  45. [45]

    A toolkit for robust thresh- olds

    Huy Tuan Pham, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “A toolkit for robust thresh- olds”. In: arXiv preprint arXiv:2210.03064 (2022)

    work page arXiv 2022

  46. [46]

    Rota’s Basis Conjecture holds asymptotically

    Alexey Pokrovskiy. “Rota’s Basis Conjecture holds asymptotically”. In: arXiv preprint arXiv:2008.06045 (2020)

    work page arXiv 2008

  47. [47]

    Hamiltonian circuits in random graphs

    Lajos P´ osa. “Hamiltonian circuits in random graphs”. In: Discrete Mathematics 14.4 (1976), pp. 359– 364

    work page 1976

  48. [48]

    Threshold for Steiner triple systems

    Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Threshold for Steiner triple systems”. In: Geo- metric and Functional Analysis (2023), pp. 1–32

    work page 2023

  49. [49]

    Distributing vertices along a Hamiltonian cycle in Dirac graphs

    G´ abor N S´ ark¨ ozy and Stanley Selkow. “Distributing vertices along a Hamiltonian cycle in Dirac graphs”. In: Discrete mathematics 308.23 (2008), pp. 5757–5770

    work page 2008

  50. [50]

    On the number of Hamiltonian cycles in Dirac graphs

    G´ abor N S´ ark¨ ozy, Stanley M Selkow, and Endre Szemer´ edi. “On the number of Hamiltonian cycles in Dirac graphs”. In: Discrete Mathematics 265.1-3 (2003), pp. 237–250

    work page 2003

  51. [51]

    Local resilience of an almost spanning k-cycle in random graphs

    Nemanja ˇSkori´ c, Angelika Steger, and Miloˇ s Truji´ c. “Local resilience of an almost spanning k-cycle in random graphs”. In: Random Structures & Algorithms 53.4 (2018), pp. 728–751

    work page 2018

  52. [52]

    Robustness of graph properties

    Benny Sudakov. “Robustness of graph properties.” In: BCC. 2017, pp. 372–408

    work page 2017

  53. [53]

    Local resilience of graphs

    Benny Sudakov and Van H Vu. “Local resilience of graphs”. In: Random Structures & Algorithms 33.4 (2008), pp. 409–433

    work page 2008