Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

The Hamilton cycle space of random graphs

T0 review · 2 major / 5 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 The paper proves that, for an odd number of vertices, a random graph at the probability threshold where its minimum degree becomes at least 3 has, asymptotically almost surely, its Hamilton cycles spanning the entire cycle space over F2.

desk verdict Sharp threshold for Hamilton cycles generating the cycle space looks right in the critical window, but the full-range theorem is not proven in the text and one sketched regime is wrong as stated. read the letter →

arxiv 2506.19731 v2 pith:S53MOYOQ submitted 2025-06-24 math.CO

Dan Hefetz , Michael Krivelevich This is my paper · ORCID
classification math.CO MSC 05C8005C4505C38
keywords cyclespaceHamiltoncyclesrandomgraphsF2vectorminimumdegreeparityswitcherphasetransitionHamilton-connectedexpanders
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 a sharp threshold for Hamilton cycles to generate the full cycle space of a random graph. For an odd number of vertices, once p is at least (log n + 2 log log n + ω(1))/n, the random graph is asymptotically almost surely such that every cycle in the graph is an F2-linear combination of Hamilton cycles; at smaller p this fails because some vertex has degree at most two. This settles a question raised in [6] and parallels the classical threshold result for Hamiltonicity, with minimum degree 3 playing the role that minimum degree 2 plays for the existence of a single Hamilton cycle. The reader should care because the statement moves beyond "a Hamilton cycle exists" to "the Hamilton cycles are numerous and varied enough to describe the whole cycle structure of the graph."

What carries the argument

The central mechanism is the R-parity switcher, a construction that converts the structural obstruction R into a Hamilton-cycle parity flip. An R-parity switcher consists of an even cycle C containing an odd number of edges of R, together with vertex-disjoint paths pairing v_i with v_{2k-i+2} for the appropriate indices; concatenating a Hamilton path in the graph outside the switcher with one of two Hamilton paths inside the switcher produces a Hamilton cycle whose R-edge parity can be chosen freely. The structural lemma from [6] guarantees that when C_n(G) ≠ C(G) such an R exists — proper, cut-dense, and even on every Hamilton cycle — so any graph containing a parity switcher and a Hamilton path through the remainder contradicts the assumption. For random graphs, the paper adds lemmas that find a short parity-switching cycle while avoiding low-degree vertices, and a Hamilton-path lemma for large induced subgraphs with sufficiently large internal degrees.

What would settle it

A reader could test Lemma 2.2 directly by searching for an odd-n Hamiltonian graph with C_n(G) ≠ C(G) but no proper subgraph R satisfying conditions (C1)-(C3); such a graph would remove the starting point of the proof, and any infinite family of odd-n graphs at the stated p with δ(G) ≥ 3 and C_n(G) ≠ C(G) would refute the theorem.

Watch

Extended reading notes

Core claim

The central discovery is that, for an odd number of vertices, the random graph G(n,p) has its Hamilton cycles spanning the whole cycle space over F2 once p ≥ (log n + 2 log log n + ω(1))/n. This is the same threshold at which the minimum degree reaches 3, and the equality C_n(G) = C(G) holds asymptotically almost surely precisely there: below this p some vertex has degree at most 2 and the equality fails unless G is a forest. The proof argues by contradiction: if C_n(G) ≠ C(G), a structural lemma from [6] produces a proper subgraph R of G such that every Hamilton cycle contains an even number of R-edges while R is at least half as dense as G across every cut; the proof then builds a small R-parity switcher and a Hamilton path in the remainder to manufacture a Hamilton cycle with an odd number of R-edges, contradicting the defining property of R.

Load-bearing premise

The load-bearing premise is that whenever Hamilton cycles fail to span the cycle space, the graph has a proper subgraph R that uses at least half of G's edges across every cut and is met evenly by every Hamilton cycle; the proof's contradiction collapses if no such R is guaranteed.

Editorial extensions

If this is right

  • Above the threshold, the cycle space of G(n,p) has a basis consisting entirely of Hamilton cycles, so its dimension e(G) - v(G) + 1 is witnessed by Hamilton cycles alone.
  • The threshold is sharp: just below p = (log n + 2 log log n)/n, the equality fails asymptotically almost surely because the minimum degree drops to 2, giving a phase transition for Hamilton-cycle generation.
  • The restriction to odd n is intrinsic: for even n, the equality C_n(G) = C(G) can hold only for bipartite graphs, because an F2-sum of even cycles is always an even subgraph.
  • The Hamiltonicity threshold and the Hamilton-cycle-spanning threshold differ by an extra log log n factor, quantifying how much stronger the spanning property is than mere existence of a Hamilton cycle.

Reading between the lines

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

  • A natural hitting-time version, not addressed in the paper, asks whether in the random graph process the first moment δ(G) ≥ 3 (with n odd) already forces C_n(G) = C(G); the proof works with a slack f(n), so answering this would require estimates at the exact hitting time.
  • The parity-switcher argument appears portable to pseudorandom graphs with mild expansion and minimum degree at least 3, since the structural lemma is purely graph-theoretic and the random-graph lemmas only supply expansion and degree concentration; that would connect this result to the pseudorandom Hamilton-space theorem cited as [6], but would need a separate proof.
  • One could test whether cycles of length n - o(n) also span the cycle space at the same threshold, because the parity-switcher cycle is short and the Hamilton path is long, so the same tools may extend to slightly shorter cycles.
  • The proof implicitly identifies the obstruction: below the threshold, degree-2 vertices cannot lie on any Hamilton cycle, so any failure of spanning is caused by such vertices; this suggests that similar spanning-family thresholds for other subgraphs appear exactly when the last minimal-degree obstacle disappears.
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.

Referee Report

2 major / 5 minor

Summary. The paper studies, for G ~ G(n,p) with n odd, when the incidence vectors of Hamilton cycles span the full cycle space C(G) over F2. The main result, Theorem 1, states that if p ≥ (log n + 2 log log n + ω(1))/n, then a.a.s. C_n(G) = C(G), and that this is sharp up to the ω(1) term. This answers a question of Christoph, Nenadov, and Petrova. The proof follows the parity-switcher recipe of [6]: assuming C_n(G) ≠ C(G), Lemma 2.2 produces a subgraph R with parity and density conditions; the authors then construct a small R-parity-switcher and a Hamilton path in the remaining graph, using a mix of expansion lemmas, random graph estimates, and a careful treatment of vertices of unusually low degree (SMALL). The detailed proof is written for the window p = (log n + 2 log log n + f(n))/n with 1 ≪ f(n) ≪ log log n; the cases of larger p are relegated to a sketch in the final paragraph of Section 3.

Significance. If the full statement is established, the paper resolves an open problem and improves the known sufficient condition for C_n(G) = C(G) in random graphs from p ≥ C log n / n to the optimal p ≥ (log n + 2 log log n + ω(1))/n, matching the threshold for δ(G) ≥ 3. The parity-switcher framework is applied in a new low-degree setting, and the random graph estimates are standard and free of fitted parameters. The main caveat is that the theorem as stated covers all larger p, while the written proof is complete only on a narrow f(n)-window; the extension is sketched rather than rigorously verified, and one claim in the sketch is inaccurate as stated. This makes the correctness of the full threshold statement contingent on additional technical work.

major comments (2)
  1. [Section 3, proof of Theorem 1, final paragraph] Theorem 1 is stated for every p ≥ (log n + 2 log log n + ω(1))/n, but the detailed proof is written only for p = (log n + 2 log log n + f(n))/n with 1 ≪ f(n) ≪ log log n. Since C_n(G) = C(G) is not monotone, the extension to larger p cannot be taken for granted. The sketch for (1+ε) log n / n ≤ p ≤ C log n / n says that properties (P1)-(P3) can be replaced by δ,Δ = Θ(log n) and that there are no small-degree vertices; however, for p close to (1+ε) log n / n, vertices of degree at most log n / 10 (the SMALL threshold used throughout the paper) exist a.a.s., so the claim as written is false. A correct extension must either redefine SMALL with a smaller threshold depending on ε and re-verify the relevant estimates, or give a genuinely different argument. The intermediate regime (log n + 2 log log n + ω(1))/n ≤ p ≤ (1+ε) log n / n is also only asserted to require 'minor technical changes'. The authors should supply these details or restrict the theorem statement accordingly.
  2. [Lemma 3.10 and proof of Theorem 1, Step (S2b)] The graph G1 is asserted to satisfy the property P_{2/3}(n/log n, sqrt(log n)/2) by Lemma 3.6. However, Lemma 3.6 only establishes |N_{H\F}(X)| ≥ |X| sqrt(log n) for |X| ≤ n (log log n)^2 / log n, while the property P_{2/3}(n/log n, sqrt(log n)/2) requires this expansion for all |X| ≤ n/log n. The expansion for sets of size between n (log log n)^2 / log n and n/log n is likely true, but it requires an additional argument (e.g., using property (P6) together with the minimum degree of G1); the citation to Lemma 3.6 alone does not cover the required range. This is load-bearing because Theorem 2.8 is applied with n0 = n/log n.
minor comments (5)
  1. [Section 3, before Theorem 3.1] There is a typo: 'prcisely' should be 'precisely'.
  2. [Lemma 3.6, proof] In the final inequality, property (P5) is invoked with N = N_{H\F}(X), but (P5) requires |B| = |A| sqrt(log n). If |N| < |X| sqrt(log n), one must first extend N to a set B of size exactly |X| sqrt(log n) before applying (P5). This should be stated explicitly.
  3. [Lemma 3.9, case (1.2.2)] The claim that G[U] is a.a.s. not bipartite is justified only by citing (P2). The actual fact needed is that a random graph with p = Θ(log n / n) has no independent set of size Ω(n); this follows from (P6) and should be stated explicitly.
  4. [Lemma 3.10, application of Lemma 3.5] The application of Lemma 3.5 should specify that it is applied to the induced subgraph on S \ SMALL (or an equivalent graph), since the hypothesis deg_H(v,Y) ≥ δ for every v ∈ V(H) would otherwise fail for vertices in S ∩ SMALL, whose degree into Y may be zero.
  5. [Proof of Theorem 1, final paragraph] The sentence 'a similar argument, though with various technical changes, works for larger values of p' is too terse for the announced range of Theorem 1. Readers need to know which definitions (especially SMALL) and which constants are changed in each regime, and why the expansion and parity-switcher lemmas remain valid in those regimes.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from independently proved random-graph lemmas and a cited structural lemma from [6]; none of the proof steps reduce to the target statement.

full rationale

The paper's central claim is Theorem 1, that a.a.s. C_n(G)=C(G) for p above the delta(G)>=3 threshold. The proof is a contradiction: assuming C_n(G) != C(G), Lemma 2.2 (quoted from [6], a different research group) yields a subgraph R with properties (C1)-(C3). The authors then use the parity-switcher recipe of [6] to construct a Hamilton cycle with an odd number of R-edges, contradicting (C2). All additional ingredients are proved in the paper (Lemmas 3.3, 3.4, 3.6, 3.7, 3.8, 3.9, 3.10) from standard Chernoff bounds and union bounds, or quoted from published external sources: Theorems 3.1 and 3.2 are classical threshold results, Theorem 2.6 is a published expander result, Theorem 2.8 is a published embedding result from [9], and Lemma 3.5 is a published partition lemma from [15]. Although [9] and [15] have overlapping authors with the present paper, they are prior peer-reviewed results with stated assumptions that do not include C_n(G)=C(G); invoking them is not circular. No parameter is fitted to data, and no quantity that the theorem predicts is used as an input. The only notable gap is that the proof is written in detail only for p=(log n+2loglog n+f(n))/n with 1 << f(n) << loglog n; the remaining regimes are delegated to a sketch ('minor technical changes' / 'similar, and in fact simpler, argument'). This is a completeness and correctness concern about the full threshold statement, not a circularity concern. Accordingly, no circular step can be exhibited, and the appropriate score is 0.

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

The proof is a deterministic structural argument (CNP recipe plus expander tools) applied to a probabilistic model. It introduces no fitted parameters and no new theoretical entities. The non-probabilistic load is carried by the cited structural lemmas, most importantly Lemma 2.2; the probabilistic load is carried by Chernoff bounds and the standard thresholds. The only local constants are proof devices, not parameters fitted to data.

assumptions (7)
  • standard math Chernoff-type concentration inequalities for binomial random variables (Theorem 2.1).
    Used throughout Lemma 3.3 and later to control degrees and edge counts; stated but not proved.
  • domain assumption Lemma 2.2 of [6]: if an odd-n Hamiltonian graph has C_n(G) != C(G), there exists a proper subgraph R such that every Hamilton cycle has an even number of R-edges and e_R(A,B) >= e_G(A,B)/2 for every partition A∪B.
    Black-box structural characterization; the S1-S5 contradiction argument depends on it.
  • domain assumption Theorem 2.6 of [10]: every sufficiently large c-expander is Hamilton-connected.
    Used in Lemma 3.10 to obtain a Hamilton path in Step S3.
  • domain assumption Theorem 2.8 of [9]: graphs with property P_alpha(n0,d) plus an edge condition on large sets admit pairwise vertex-disjoint paths between prescribed pairs.
    Main tool for Step S2b; cited from a paper coauthored by the present second author.
  • domain assumption Theorem 3.1: p >= (logn+loglogn+omega(1))/n is the a.a.s. Hamiltonicity threshold.
    Provides the Hamiltonian start for Step S1; cited from [13].
  • domain assumption Theorem 3.2: p >= (logn+2loglogn+omega(1))/n is the a.a.s. threshold for minimum degree at least 3.
    Necessity anchor and used to ensure small-degree vertices have outside neighbors; cited from [13].
  • domain assumption Lemma 3.5 of [15]: a balanced partition with controlled degrees exists under a maximum-degree condition.
    Used to split V\(SMALL∪U) into two parts with degree lower bounds; cited from a paper coauthored by both present authors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Hamilton cycle space of random graphs." pith.science (2026). https://pith.science/paper/S53MOYOQ

@misc{pith2026250619731,
  author       = {Pith},
  title        = {Pith review of: The Hamilton cycle space of random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S53MOYOQ}},
  note         = {Machine review of arXiv:2506.19731}
}
abstract

The cycle space of a graph $G$, denoted $C(G)$, is a vector space over ${\mathbb F}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then $C_n(G)$ denotes the subspace of $C(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. A classical result in the theory of random graphs asserts that for $G \sim \mathbb{G}(n,p)$, asymptotically almost surely the necessary condition $\delta(G) \geq 2$ is also sufficient to ensure Hamiltonicity. Resolving a problem of Christoph, Nenadov, and Petrova, we augment this result by proving that for $G \sim \mathbb{G}(n,p)$, with $n$ being odd, asymptotically almost surely the condition $\delta(G) \geq 3$ (observed to be necessary by Heinig) is also sufficient for ensuring $C_n(G) = C(G)$. That is, not only does $G$ typically have a Hamilton cycle, but its Hamilton cycles are typically rich enough to span its cycle space.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. On graphs whose cycle space is spanned by their Hamilton cycles

    math.CO 2026-06 unverdicted novelty 7.0 of 10

    Under strengthened Chvátal-Erdős, McDiarmid-Yolov and dominating-set conditions with odd n, the cycle space equals the Hamilton-cycle subspace.

  2. The Hamilton cycle space of random regular graphs and randomly perturbed graphs

    math.CO 2025-07 conditional novelty 7.0 of 10

    Hamilton cycles span the full cycle space asymptotically almost surely in random regular graphs of sufficiently large constant degree, and in randomly perturbed dense graphs.

Reference graph

Works this paper leans on

28 extracted references · 16 canonical work pages · cited by 2 Pith papers

  1. [6]

    Christoph, R

    M. Christoph, R. Nenadov, and K. Petrova, The Hamilton space of pseudorandom graphs, arXiv preprint arXiv:2402.01447, 2024

    arXiv 2024

  2. [1]

    Alspach, S

    B. Alspach, S. C. Locke, and D. Witte, The Hamilton spaces of Cayley graphs on abelian groups, Discrete Mathematics 82 (2) (1990), 113–126

    1990

  3. [2]

    J. D. Baron and J. Kahn, On the cycle space of a random graph, Random Structures and Algorithms 54(1) (2019), 39–68

    work page 2019

  4. [3]

    Ben-Shimon, A

    S. Ben-Shimon, A. Ferber, D. Hefetz, and M. Krivelevich, Hitting time results for Maker-Breaker games, Random Structures and Algorithms 41 (2012), 23–46

    work page 2012

  5. [4]

    Bollob´ as, The evolution of sparse graphs, in Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, (1984), 35–57

    B. Bollob´ as, The evolution of sparse graphs, in Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, (1984), 35–57

    work page 1984

  6. [5]

    J. A. Bondy and L. Lov´ asz, Cycles through specified vertices of a graph,Combinatorica 1 (1981), 117–140

    1981

  7. [7]

    DeMarco, A

    B. DeMarco, A. Hamm, and J. Kahn, On the triangle space of a random graph, Journal of Combinatorics 4(2) (2013), 229–249

    2013

  8. [8]

    Dragani´ c, S

    N. Dragani´ c, S. Glock, D. Munha Correia, and B. Sudakov, Optimal Hamilton covers and linear arboricity for random graphs, Proceedings of the American Mathematical Society 153 (2025), 921–935

    work page 2025

Show all 28 references
  1. [9]

    Dragani´ c, M

    N. Dragani´ c, M. Krivelevich, and R. Nenadov, Rolling backwards can move you forward: on embedding problems in sparse expanders, Transactions of the American Mathematical Society 375 (7) (2022), 5195–5216

    2022

  2. [10]

    Dragani´ c, R

    N. Dragani´ c, R. Montgomery, D. Munha Correia, A. Pokrovskiy, and B. Sudakov, Hamiltonicity of expanders: optimal bounds and applications, arXiv preprint arXiv:2402.06603v2, 2024. 16

    2024 arXiv

  3. [11]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi, On the evolution of random graphs,Bull. Inst. Statist. Tokyo 38 (1961), 343–347

    1961

  4. [12]

    Ferber, G

    A. Ferber, G. Kronenberg, and E. Long, Packing, counting and covering Hamilton cycles in random directed graphs, Israel Journal of Mathematics 220 (2017), 57–87

    2017

  5. [13]

    Frieze and M

    A. Frieze and M. Karo´ nski,Introduction to Random Graphs, Cambridge University Press, 2015

    2015

  6. [14]

    I. B.-A. Hartman, Long cycles generate the cycle space of a graph, European Journal of Com- binatorics 4 (1983), 237–246

    1983

  7. [15]

    Hefetz, M

    D. Hefetz, M. Krivelevich and T. Szab´ o, Sharp threshold for the appearance of certain spanning trees in random graphs, Random Structures and Algorithms 41 (2012), 391–412

    2012

  8. [16]

    Hefetz, D

    D. Hefetz, D. K¨ uhn, J. Lapinskas, and D. Osthus, Optimal covers with Hamilton cycles in random graphs, Combinatorica 34 (2014), 573–596

    2014

  9. [17]

    Heinig, On prisms, M¨ obius ladders and the cycle space of dense graphs, European Journal of Combinatorics 36 (2014), 503–530

    P. Heinig, On prisms, M¨ obius ladders and the cycle space of dense graphs, European Journal of Combinatorics 36 (2014), 503–530

    2014

  10. [18]

    Heinig, When Hamilton circuits generate the cycle space of a random graph, arXiv preprint arXiv:1303.0026, 2013

    P. Heinig, When Hamilton circuits generate the cycle space of a random graph, arXiv preprint arXiv:1303.0026, 2013

    2013 arXiv

  11. [19]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski,Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000

    2000

  12. [20]

    F. Knox, D. K¨ uhn, and D. Osthus, Edge-disjoint Hamilton cycles in random graphs, Random Structures and Algorithms 46 (2015), 397–445

    2015

  13. [21]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi, Limit distributions for the existence of Hamilton circuits in a random graph, Discrete Mathematics 43 (1983), 55–63

    1983

  14. [22]

    A. D. Korshunov, Solution of a problem of Erd˝ os and R´ enyi on Hamilton cycles in non-oriented graphs, Soviet Math. Dokl. 17 (1976), 760–764

    1976

  15. [23]

    Krivelevich and W

    M. Krivelevich and W. Samotij, Optimal packings of Hamilton cycles in sparse random graphs, SIAM Journal on Discrete Mathematics 26 (2012), 964–982

    2012

  16. [24]

    Lee and B

    C. Lee and B. Sudakov, Dirac’s theorem for random graphs, Random Structures and Algorithms 41 (2012), 293–305

    2012

  17. [25]

    S. C. Locke, A basis for the cycle space of a 2-connected graph, European Journal of Combina- torics 6 (1985), 253–256. 17

    1985

  18. [26]

    S. C. Locke, A basis for the cycle space of a 3-connected graph, Annals of Discrete Mathematics 27 (1985), 381–397

    1985

  19. [27]

    Montgomery, Hamiltonicity in random graphs is born resilient, Journal of Combinatorial Theory, Series B 139 (2019), 316–341

    R. Montgomery, Hamiltonicity in random graphs is born resilient, Journal of Combinatorial Theory, Series B 139 (2019), 316–341

    2019

  20. [28]

    P´ osa, Hamiltonian circuits in random graphs, Discrete Mathematics 14 (1976), 359–364

    L. P´ osa, Hamiltonian circuits in random graphs, Discrete Mathematics 14 (1976), 359–364. 18

    1976

Pith tools

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