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

Dan Hefetz; Michael Krivelevich

REVIEW 2 major objections 4 minor 1 cited by

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

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Hamilton cycles are shown to span the full cycle space of random regular graphs and of randomly perturbed dense graphs.

desk verdict Solid extension of Hamiltonicity to cycle-space generation for random regular graphs, but Theorem 1.2's proof is only a sketch with a real gap in the vertex-deletion transfer. read the letter →

arxiv 2507.04488 v1 pith:SB25GU2I submitted 2025-07-06 math.CO

Dan Hefetz , Michael Krivelevich This is my paper

classification math.CO MSC 05C8005C4505C38

keywords cyclespaceHamiltoncyclesrandomregulargraphsrandomlyperturbedparityswitcherexpanderHamilton-connectedF2-vector

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

This paper asks whether the longest cycles of a random graph force all cycles. It establishes that, once the degree is a sufficiently large constant $d$, a random $d$-regular graph on an odd number of vertices has, with probability tending to 1, the property that every cycle is a linear combination over the two-element field $\mathbb{F}_2$ of Hamilton cycles. For even $n$, the same conclusion holds with cycles of length $n-1$ in place of Hamilton cycles. It also proves the analogous generation statement for randomly perturbed graphs: a dense graph of linear minimum degree, after adding $G(n, C/n)$ random edges, has its cycle space spanned by Hamilton cycles. These results sharpen known Hamiltonicity theorems from existence of a Hamilton cycle to generation of the whole cycle space.

What carries the argument

The load-bearing object is the $R$-parity switcher: given a hypothetical subgraph $R$ of $G$ that meets every Hamilton cycle in an even number of edges, one seeks an even cycle $C$ in $G$ with an odd number of $R$-edges, together with vertex-disjoint short paths pairing opposite vertices of $C$. Concatenating $C$ with a Hamilton path of the remaining graph yields a Hamilton cycle with odd $R$-intersection, contradicting the defining property of $R$ and forcing $C_n(G)=C(G)$. The proof constructs the switcher inside $G_{n,d}$ using edge-distribution estimates, expansion lemmas for graphs of high minimum degree, a partition lemma that keeps many neighbours of every vertex on both sides of a cut, and the theorem that every sufficiently strong expander is Hamilton-connected; the Hamilton path step is then immediate.

What would settle it

Fix a large even $d$ and odd $n$, sample $G \sim G_{n,d}$, and compute over $\mathbb{F}_2$ the rank of the set of incidence vectors of all Hamilton cycles; the theorem predicts this rank equals $|E(G)|-|V(G)|+1$ with probability tending to 1, so samples with smaller rank appearing with non-vanishing frequency as $n$ grows would refute Theorem 1.1. For Theorem 1.2, check whether some vertex deletion $G-v$ violates the edge-distribution estimate of Lemma 4.2(a) with a slightly relaxed constant; any such vertex would break the mutatis mutandis step for even $n$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: there is an absolute constant $d_0$ such that for every $d \ge d_0$, if $G \sim G_{n,d}$ with $n$ odd, then a.a.s. $C_n(G)=C(G)$. Theorem 1.2 covers even $n$: a.a.s. $C_{n-1}(G)=C(G)$. Theorem 1.3 states that for every constant $\delta>0$ there is a constant $C=C(\delta)$ such that if $H$ has minimum degree at least $\delta n$ and $G \sim G(n, C/n)$, then a.a.s. $C_n(H\cup G)=C(H\cup G)$ for odd $n$. The conclusion in each case is not merely Hamiltonicity but that the Hamilton cycles, or the nearly longest cycles when $n$ is even, form a generating set for the vector space of all cycles over $\mathbb{F}_2$. The proof for regular graphs relies on expansion and edge-distribution properties of $G_{n,d}$ to run a parity-switcher argument, and the perturbed-graph proof uses the dense graph's minimum degree together with the random edges to preserve expansion after deleting the small switching structure.

Load-bearing premise

The even-$n$ proof assumes, without a separate demonstration, that deleting any one vertex from the random regular graph leaves a graph whose expansion and edge-count behaviour are still good enough for the odd-$n$ argument to run through, even though the remaining graph is no longer regular.

Editorial extensions

If this is right

For odd $n$, every cycle in a random $d$-regular graph with $d$ a large constant is an $\mathbb{F}_2$-sum of Hamilton cycles, so the Hamilton cycles alone determine the whole cycle space.
For even $n$, cycles of length $n-1$ generate the whole cycle space; since any Hamilton cycle can be written as a sum of two such shorter cycles, the Hamilton cycle space is contained in this span.
In the randomly perturbed model, the same constant-ratio perturbation $C/n$ that guarantees Hamiltonicity also guarantees that Hamilton cycles span the cycle space.
A direct adaptation of the proof gives an analogous result for $(n,d,\lambda)$-graphs with $d$ as small as $C \log n/\log(d/\lambda)$, stated in the paper as Theorem 5.1.
The generation property is not destroyed by removing small sets of vertices, because the switcher construction and the Hamilton path step run on graphs left after deleting $O(\log n/\log d)$ vertices.

Reading between the lines

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

A next test is the open question of the optimal degree threshold: whether $d_0=4$, or $d_0=3$ for the even-$n$ version, already suffices; the parity-switcher construction needs short parity cycles and robust expansion, so the true threshold may be visible already at constant $d$.
For even $n$, a reader could try to prove directly that deleting one vertex from $G_{n,d}$ preserves the exact expansion and edge-distribution lemmas with slightly worse constants; such a lemma would replace the mutatis mutandis sketch with a checkable statement and would likely generalize to other one-vertex-deletion arguments in random regular graphs.
The paper's closing question about reducing the random perturbation to $p=\omega(n^{-2})$ under an independence-number bound looks plausible, since the parity-switcher steps only require short paths in the random edges, which much sparser random graphs still typically provide.

Share X Bluesky LinkedIn Reddit HN

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

The paper proves that for sufficiently large constant degree d, the Hamilton cycles (or cycles of length n−1 when n is even) generate the entire F2-cycle space of G_{n,d}, and it extends Bohman–Frieze–Martin to cycle-space generation for randomly perturbed graphs. The main new content is Theorem 1.1, and the proof is a careful adaptation of the Christoph–Nenadov–Petrova parity-switcher recipe to constant-degree expanders. Theorems 1.1 and 1.3 are proved in detail with standard tools, and the argument reads coherently. This is a genuine within-subfield advance, not a branch reorganizer.

The soft spots are concentrated in Theorem 1.2 and in one subcase of Lemma 4.11. The proof of Theorem 1.2 says the proof of Theorem 1.1 carries over mutatis mutandis to every vertex-deleted graph G_v = G − v. That is not established. G_v is not a random (n−1)-regular graph; when d is odd it is not regular at all, so Lemmas 4.3, 4.5, 4.7, and Theorem 4.13 do not formally apply. The paper only argues the edge-distribution lemma (Lemma 4.2) transfers with a slightly worse constant. The later lemmas need uniform verification for every deletion, and the expansion lemma (Lemma 4.5) in particular relies on regular-degree assumptions. This is the load-bearing step for the even-n result, and as written it is a genuine gap, though I suspect it is patchable with routine work.

In Lemma 4.11, case (2), if the selected chord xy ∈ E(G)\E(R) has both endpoints on the shortest odd cycle C′, the path P_x is constructed in (R \ (V(C′) ∪ {y})) ∪ {x,u}, but x has been deleted. The path cannot start at x. The direct even cycle formed by an arc of C′ plus xy would work and should be mentioned; the omission is a small patchable gap, not a fatal flaw.

Overall the paper is honest and the citations are appropriate. Theorem 1.3 appears solid, and Theorem 1.1 is likely correct. The main question is whether the authors can fill in the Theorem 1.2 proof. I would not desk-reject this; it deserves referee time. My recommendation: send to peer review, and instruct the referee to press for a rigorous proof of Theorem 1.2 and a fix for Lemma 4.11 case (2).

Referee Report

2 major / 4 minor

Summary. The paper studies when Hamilton cycles span the F2-cycle space of a graph. It proves three main results: (1) if n is odd and d is sufficiently large, then for G ~ G_{n,d} one has a.a.s. C_n(G)=C(G); (2) if n is even and d is sufficiently large, then a.a.s. C_{n-1}(G)=C(G); and (3) if H has minimum degree at least δn and G ~ G(n,C/n) with C sufficiently large, then a.a.s. C_n(H∪G)=C(H∪G). The proofs use the parity-switcher framework of Christoph, Nenadov, and Petrova, the Hamilton-connectivity theorem for expanders, and probabilistic estimates for random regular graphs. Theorem 1.1 and Theorem 1.3 are proved in detail; Theorem 1.2 is proved only by a sketch, and Theorem 5.1 in the concluding remarks is also only sketched.

Significance. If the results hold, they are substantial strengthenings of known Hamiltonicity theorems: in random regular graphs and in randomly perturbed dense graphs, Hamilton cycles (or cycles of length n-1) generate the entire cycle space over F2. The paper makes appropriate use of standard tools and gives careful probabilistic estimates in the proofs of Theorems 1.1 and 1.3. It does not rely on fitted parameters or ad hoc entities. The main weakness is the proof of Theorem 1.2, which is load-bearing for the even-n case and is currently not established at the same level of rigor as the other results.

major comments (2)

[Section 4, proof of Theorem 1.2] The transfer of the proof of Theorem 1.1 to every vertex-deleted graph G_v is the central step for even n, but it is not actually carried out. The text says that the proof 'carries over mutatis mutandis' and that the remaining parts are 'essentially the same', yet G_v is not distributed as G_{n-1,d}, and when d is odd it is not regular at all. One must therefore re-verify uniformly for all G_v the structural inputs used in Section 4: Lemma 4.2(a), Lemma 4.5, Lemma 4.7, Lemma 4.11, and Theorem 4.13, and one must also prove that every G_v is a c-expander before Theorem 2.6 can replace Theorem 4.1. Since Theorem 1.2 is advertised as the remedy for the parity restriction in Theorem 1.1, this missing uniform argument is load-bearing and cannot be left as a sketch.
[Lemma 4.11, Case (2)] In the non-bipartite case, if the chosen edge xy in E(G)\E(R) has both endpoints on the chosen shortest odd cycle C', then the constructed path P_x in R \ (V(C') ∪ {y}) from x to u cannot exist as written, because x has been deleted from the graph in which the path is supposed to lie. The subcase can be repaired by taking the chord xy together with one of the two arcs of C' to form an even cycle with exactly one edge outside R, but this subcase is not mentioned. Since Lemma 4.11 supplies Step (S2a) in the proof of Theorem 1.1, this gap must be closed.

minor comments (4)

[Proof of Theorem 1.3, application of Lemma 3.5] Lemma 3.5 is applied to sets A and B of all sizes at least δn/3 and n/3, but Lemma 3.2 is stated only for sets of exact size αn and βn. The gap is easily closed by passing to subsets of the exact sizes, but the text should say so explicitly.
[Section 5, Theorem 5.1] Theorem 5.1 is stated as a theorem but its proof is only a sketch. If it is meant to be a theorem, full details should be provided; otherwise it should be labelled as a sketched consequence or moved to a conjecture/open-problem discussion.
[Lemma 4.4] The statement of Lemma 4.4 has a typesetting problem: the inequality involving e^{1 - min{a,b}^2/(5m^2)} δ is not clearly readable. Please clarify the exponent and the role of the parameter δ.
[Proof of Theorem 1.1, application of Lemma 4.4] When Lemma 4.4 is applied to Y = V(G) \ V(C), the sizes of the parts A and B are not stated precisely; since Y has n - |C| vertices rather than exactly n vertices, the text should specify a=|A| and b=|B| and check the required degree bounds with the small loss from |C| taken into account.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from external expander-mixing and Hamilton-connectivity tools, not from their own conclusions.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Theorems 1.1 and 1.3 follow the external recipe of Christoph, Nenadov, and Petrova (Lemma 2.1 and the S1-S5 steps), with each structural ingredient (edge distribution via the expander mixing lemma, expansion via Lemma 4.5, short paths via Lemma 4.7, parity switchers via Lemma 4.11, path packing via Theorem 4.13) proved from stated assumptions independent of the target equality. The cited results by the authors' own group ([15], [16], [21]) are published theorems with explicit hypotheses that do not include C_n(G)=C(G); they are genuine external support, not self-citation load-bearing. The only weak point is the final paragraph of Section 4, where Theorem 1.2 is justified by saying the proof of Theorem 1.1 'carries over mutatis mutandis' to each vertex-deleted G_v; this is an unproved uniformity transfer and a potential correctness gap, especially for odd d where G_v is irregular, but it is not circular, because it does not define the conclusion in terms of its inputs or rename a fitted quantity as a prediction. No fitted parameters or invented entities occur, and no theorem is reduced to its own assumptions.

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

No fitted free parameters; all constants are existential. The central claim depends on several cited structural theorems, all standard in the area. The only domain assumption is the unproved transfer to vertex-deleted subgraphs in Theorem 1.2.

assumptions (6)

standard math Lemma 2.1, the parity-switcher characterization of failure of C_n(G)=C(G), is used as a black box.
Imported from [7]; it is the core structural step in every proof.
standard math Theorem 2.6: every sufficiently large c-expander is Hamilton-connected.
From [11]; used in Step S3 to find Hamilton paths.
standard math Theorem 4.1: G_{n,d} with d≥3 is a.a.s. Hamiltonian.
From [24,25]; supplies the Hamiltonicity needed in Step S1 for the random regular theorem.
standard math Theorem 4.13: disjoint paths exist in sparse expanders under the property P_alpha.
From [10]; used to build the parity-switcher paths in the random regular proof.
standard math Theorem 3.1: perturbed dense graphs are a.a.s. Hamiltonian.
From [5]; supplies Step S1 for the randomly perturbed theorem.
domain assumption Deleting one vertex from G_{n,d} leaves a graph inheriting the expansion and edge-distribution properties used in Theorem 1.1.
Assumed in the proof sketch of Theorem 1.2; not formally verified and not exactly the G_{n-1,d} model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Hamilton cycle space of random regular graphs and randomly perturbed graphs." pith.science (2026). https://pith.science/paper/SB25GU2I

@misc{pith2026250704488,
  author       = {Pith},
  title        = {Pith review of: The Hamilton cycle space of random regular graphs and randomly perturbed graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SB25GU2I}},
  note         = {Machine review of arXiv:2507.04488}
}

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)$ is the subspace of $C(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We prove that asymptotically almost surely $C_n(G_{n,d}) = C(G_{n,d})$ holds whenever $n$ is odd and $d$ is a sufficiently large (even) integer. This extends (though with a weaker bound on $d$) the well-known result asserting that $G_{n,d}$ is asymptotically almost surely Hamiltonian for every $d \geq 3$ (but not for $d < 3$). Since $n$ being odd mandates that $d$ be even, somewhat limiting the generality of our result, we also prove that if $n$ is even and $d$ is any sufficiently large integer, then asymptotically almost surely $C_{n-1}(G_{n,d}) = C(G_{n,d})$. An influential result of Bohman, Frieze, and Martin asserts that if $H$ is an $n$-vertex graph with minimum degree at least $\delta n$ for some constant $\delta > 0$, and $G \sim \mathbb{G}(n, C/n)$, where $C := C(\delta)$ is a sufficiently large constant, then $H \cup G$ is asymptotically almost surely Hamiltonian. We strengthen this result by proving that the same assumptions on $H$ and $G$ ensure that $C_n(H \cup G) = C(H \cup G)$ holds asymptotically almost surely.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

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.

Reference graph

Works this paper leans on

25 extracted references · 21 canonical work pages · cited by 1 Pith paper

[1]

Aigner-Horev, D

E. Aigner-Horev, D. Hefetz, and M. Krivelevich, Cycle lengths in randomly perturbed graphs, Random Structures and Algorithms 63(4) (2023), 867–884

work page 2023
[2]

Alon and J

N. Alon and J. H. Spencer, The Probabilistic Method , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, fourth edition, 2015

work page 2015
[3]

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

work page 1990
[4]

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

work page 2019
[5]

Bohman, A

T. Bohman, A. Frieze, and R. Martin, How many random edges make a dense graph Hamilto- nian?, Random Structures and Algorithms 22 (2003), 33–42

work page 2003
[6]

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

work page 1981
[7]

The Hamilton space of pseudorandom graphs

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

work page Pith review arXiv 2024
[8]

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

work page 2013

Show all 25 references

[9]

G. A. Dirac, Some theorems on abstract graphs, Proceedings of the London Mathematical Society 3(1) (1952), 69–81

1952
[10]

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
[11]

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

2024 arXiv
[12]

Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society 195 (910), (2008)

J. Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society 195 (910), (2008)

2008
[13]

Hahn-Klimroth, G

M. Hahn-Klimroth, G. S. Maesaka, Y. Mogge, S. Mohr, and O. Parczyk, Random perturbation of sparse graphs, Electronic Journal of Combinatorics 28 (2021), Paper 2.26

2021
[14]

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

1983
[15]

Hefetz and M

D. Hefetz and M. Krivelevich, The Hamilton cycle space of random graphs, arXiv preprint arXiv:2506.19731v1, 2025

2025 arXiv
[16]

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
[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
[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
[19]

Hou and Z

X. Hou and Z. Yin, Dirac-type condition for Hamilton-generated graphs, arXiv preprint arXiv:2503.15950v1, 2025. 16

2025 arXiv
[20]

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
[21]

Krivelevich, A

M. Krivelevich, A. Lew, and P. Michaeli, Rigid partitions: from high connectivity to random graphs, arXiv preprint arXiv:2311.14451v2, 2023

2023 arXiv
[22]

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

1985
[23]

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

1985
[24]

R. W. Robinson and N. C. Wormald, Almost all cubic graphs are Hamiltonian, Random Struc- tures and Algorithms 3 (1992), 117–126

1992
[25]

R. W. Robinson and N. C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms 5 (1994), 363–374. 17

1994

Pith tools

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

[1] [1]

Aigner-Horev, D

E. Aigner-Horev, D. Hefetz, and M. Krivelevich, Cycle lengths in randomly perturbed graphs, Random Structures and Algorithms 63(4) (2023), 867–884

work page 2023

[2] [2]

Alon and J

N. Alon and J. H. Spencer, The Probabilistic Method , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, fourth edition, 2015

work page 2015

[3] [3]

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

work page 1990

[4] [4]

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

work page 2019

[5] [5]

Bohman, A

T. Bohman, A. Frieze, and R. Martin, How many random edges make a dense graph Hamilto- nian?, Random Structures and Algorithms 22 (2003), 33–42

work page 2003

[6] [6]

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

work page 1981

[7] [7]

The Hamilton space of pseudorandom graphs

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

work page Pith review arXiv 2024

[8] [8]

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

work page 2013