{"id":"08ef283f-dbdf-4502-8dce-9a5c6a711b4a","arxiv_id":"2507.04488","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"The paper proves that in random regular graphs of any sufficiently large constant degree, the longest cycles generate the entire cycle space with probability tending to one. It proves the same for a dense graph perturbed by a sparse random graph, upgrading the classical randomly perturbed Hamiltonicity theorem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 rests on an unproved 'mutatis mutandis' transfer of the Theorem 1.1 proof to vertex-deleted graphs G_v; the sketch does not establish that the needed lemmas hold for every G_v uniformly.","rationale":"I read the paper in good faith. The main contribution, Theorem 1.1, is presented in detail and most lemmas are deterministic consequences of edge distribution; Theorem 1.3 also appears coherent. The central weak spot is exactly the one identified by the reader: Theorem 1.2 is a headline result but is given only a sketch asserting that the whole Theorem 1.1 proof works for every vertex-deleted graph G_v. The reader's framing that G_v must be 'close enough' to G_{n-1,d} is apt, although the real issue may be even simpler: the proof needs a uniform transfer of a list of lemmas, not a distributional comparison of G_v to a random regular graph. I agree with the reader's weakest_assumption. The gap is serious enough to make Theorem 1.2 conditional, but not to reject the paper: the transfer may well be fillable, since Lemma 4.2's high-probability event is universal over all disjoint sets A,B and hence is inherited by every G_v on subsets avoiding v. The proposed concrete test would force the authors to write out the missing verification; if it fails, Theorem 1.2 would need to be weakened or proved differently. This does not change the reader's CONDITIONAL verdict.","tokens_in":15160,"tokens_out":27530,"duration_ms":306402,"concrete_test":"Write a self-contained proof of Theorem 1.2 that, for a fixed high-probability event E for G, verifies for every v each lemma used in Theorem 1.1 on G_v using only subsets of V(G)\\setminus{v}. In particular, in Lemma 4.11's non-bipartite case, include the subcase in which the chosen missing edge xy lies inside V(C'): check that one of the two C'-arcs plus xy is an even cycle with exactly one non-R edge and length O(log n). The transfer is settled if all lemmas can be re-derived without additional random-regular distributional input; otherwise Theorem 1.2 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most exposed premise is the proof of Theorem 1.2 in the final paragraph of Section 4. The proof says the proof of Theorem 1.1 'carries over mutatis mutandis' to G_v = G - v for every v, and from this concludes C_{n-1}(G_v) = C(G_v). This is load-bearing because Theorem 1.2 is advertised as the remedy for the parity restriction in Theorem 1.1, and the subsequent deduction C_k(G) subset C_{n-1}(G) collapses without it. What is missing is a uniform proof that each G_v inherits every structural input used in Section 4: Lemma 4.2(a) edge counts, Lemma 4.5 expansion, Lemma 4.7 short paths, Lemma 4.11's parity switcher, and Theorem 4.13's path packing. The text only says removal of one vertex has 'almost no effect' on Lemma 4.2 and that the remaining parts are 'essentially the same'; but G_v is not distributed as G_{n-1,d}, and when d is odd it is not regular at all, so the random-regular-specific lemmas do not transfer formally. There is also an unhandled subcase in Lemma 4.11's non-bipartite proof: if the selected missing 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') union {y}) cannot exist as written, because x has been removed; the direct even cycle from an arc of C' plus xy is not mentioned. Since Theorem 1.2 applies the whole Theorem 1.1 proof to every G_v, this transfer is the weakest link.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15506,"tokens_out":11125,"duration_ms":125956,"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":[{"comment":"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.","section":"Section 4, proof of Theorem 1.2"},{"comment":"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.","section":"Lemma 4.11, Case (2)"}],"minor_comments":[{"comment":"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":"Proof of Theorem 1.3, application of Lemma 3.5"},{"comment":"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.","section":"Section 5, Theorem 5.1"},{"comment":"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 δ.","section":"Lemma 4.4"},{"comment":"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.","section":"Proof of Theorem 1.1, application of Lemma 4.4"}],"recommendation":"major_revision","confidential_remarks":"The central issue is Theorem 1.2: its proof is a sketch of a non-trivial transfer to non-regular vertex-deleted graphs. If the authors can supply a complete uniform argument for the transfer, the paper is likely acceptable. The gap in Lemma 4.11 is local and repairable. I see no circularity or novelty concerns; the paper relies on prior results in a standard way and addresses a natural question in the area."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nIn 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.\n\nOverall 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).","headline":"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.","tokens_in":16006,"tokens_out":3284,"would_cite":true,"duration_ms":35227,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C45","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"Hamilton cycles are shown to span the full cycle space of random regular graphs and of randomly perturbed dense graphs.","keywords":["cycle space","Hamilton cycles","random regular graphs","randomly perturbed graphs","parity switcher","expander graphs","Hamilton-connected","F2-vector space"],"falsifier":"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$.","tokens_in":1949,"feed_emoji":"🔁","tokens_out":1954,"duration_ms":128654,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hamilton cycles generate the cycle space of random regular graphs","feed_subtitle":"For odd n, Hamilton cycles; for even n, cycles of length n-1; random perturbation also works.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the R-subgraph lemma and the parity-switcher recipe (Lemmas 2.1 and 2.3) that the whole proof is built around.","marker":"[7]"},{"why":"Gives the a.a.s. Hamiltonicity of randomly perturbed dense graphs used as step (S1) in Theorem 1.3.","marker":"[5]"},{"why":"Gives the a.a.s. Hamiltonicity of random regular graphs that supplies step (S1) in Theorem 1.1.","marker":"[24, 25]"},{"why":"Provides the eigenvalue bound on $G_{n,d}$ that underlies the edge-distribution estimates in Lemma 4.2.","marker":"[12]"},{"why":"The expander mixing lemma used to convert the eigenvalue bound into Lemma 4.2's discrepancy estimates.","marker":"[2]"},{"why":"The theorem that every c-expander is Hamilton-connected, used for step (S3).","marker":"[11]"},{"why":"The embedding theorem for vertex-disjoint paths in expanders used to build the parity-switcher paths (Theorem 4.13).","marker":"[10]"},{"why":"The partition lemma that keeps large neighbourhoods on both sides after removing the switching cycle (Lemma 4.4).","marker":"[16]"},{"why":"The edge-concentration estimate for random d-regular multigraphs used in the short-path neighbourhood lemma (Theorem 4.9).","marker":"[21]"}],"fun_headline_variants":["Hamilton cycles generate the entire cycle space of random regular graphs","Odd n: Hamilton cycles generate all cycles in random regular graphs","Even n: cycles of length n-1 generate the whole cycle space","Random perturbed graphs: Hamilton cycles generate the cycle space"],"cache_read_input_tokens":18048,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hamilton cycles generate the entire cycle space of random regular graphs","Odd n: Hamilton cycles generate all cycles in random regular graphs","Even n: cycles of length n-1 generate the whole cycle space","Random perturbed graphs: Hamilton cycles generate the cycle space"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000792,"raw_usage":{"total_tokens":3588,"prompt_tokens":1141,"completion_tokens":2447,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":757,"completion_tokens_details":{"reasoning_tokens":2376}},"tokens_in":757,"tokens_out":2447,"duration_ms":19068,"temperature":1.0,"reasoning_tokens":2376,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:48:23.559816+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"The Hamilton space of pseudorandom graphs","cited_arxiv_id":"2402.01447","evidence_quote":"Supplies the R-subgraph lemma and the parity-switcher recipe (Lemmas 2.1 and 2.3) that the whole proof is built around."},{"cited_title":"Bohman, A","cited_arxiv_id":null,"evidence_quote":"Gives the a.a.s. Hamiltonicity of randomly perturbed dense graphs used as step (S1) in Theorem 1.3."},{"cited_title":"Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society 195 (910), (2008)","cited_arxiv_id":null,"evidence_quote":"Provides the eigenvalue bound on $G_{n,d}$ that underlies the edge-distribution estimates in Lemma 4.2."},{"cited_title":"Alon and J","cited_arxiv_id":null,"evidence_quote":"The expander mixing lemma used to convert the eigenvalue bound into Lemma 4.2's discrepancy estimates."},{"cited_title":"Dragani´ c, M","cited_arxiv_id":null,"evidence_quote":"The embedding theorem for vertex-disjoint paths in expanders used to build the parity-switcher paths (Theorem 4.13)."},{"cited_title":"Hefetz, M","cited_arxiv_id":null,"evidence_quote":"The partition lemma that keeps large neighbourhoods on both sides after removing the switching cycle (Lemma 4.4)."},{"cited_title":"Rigid partitions: from high connectivity to random graphs","cited_arxiv_id":"2311.14451","evidence_quote":"The edge-concentration estimate for random d-regular multigraphs used in the short-path neighbourhood lemma (Theorem 4.9)."}],"review_version":1}