{"id":"fda95e02-abfb-4acd-ae6a-1e257899479b","arxiv_id":"2506.19731","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In G(n,p) with n odd, the threshold p=(log n+2 log log n+ω(1))/n is both necessary and sufficient for Hamilton cycles to span the whole cycle space.","lead":"This paper proves that in a random graph with an odd number of vertices, once every vertex has degree at least three, the Hamilton cycles (cycles visiting every vertex) generate every cycle of the graph. It settles the exact edge-probability threshold for this property, an open problem in random graph theory.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is proved in detail only for p=(log n+2loglog n+f(n))/n with 1≪f(n)≪loglog n; the extension to all larger p is a sketch and does not verify the non-monotone property in the intermediate regimes.","rationale":"The reader's conditional verdict is reasonable, but I do not think the main remaining risk is the cited Lemma 2.2 from [6]: using a structural lemma from prior work is standard practice, and the paper's parity-switcher application of it is internally consistent. The more load-bearing gap is that Theorem 1 is claimed for every p above the threshold, while the detailed proof only covers a narrow f(n)-window. Because Cn(G)=C(G) is not monotone, larger p must be handled separately, and the final paragraph only sketches this. The sketch even contains a questionable simplification: for p just above (1+ε)log n/n, the minimum degree is Θ(log n) but with a constant smaller than 1/10, so SMALL as defined in the paper is not empty; one cannot simply replace (P1)-(P3) by δ=Θ(log n) without redoing the small-degree estimates. I reviewed the main f-window proof of Theorem 1 and found no fatal error in the parity-switcher construction, the expansion lemmas, or the application of Theorem 2.8. The conditional verdict should stand: the theorem is plausible and the hard window is well argued, but the full claimed range is not yet fully proven.","tokens_in":15900,"tokens_out":46408,"duration_ms":476472,"concrete_test":"Carry out the proof of Lemmas 3.9 and 3.10 for p=(1+0.1)log n/n with SMALL redefined as {v: deg(v)≤c_M log n} for a constant c_M below the minimum-degree constant, and re-derive the analogues of Lemma 3.3 (P2)-(P3) and Lemma 3.7 for this SMALL set; if the expansion or cut arguments fail, the sketched extension in the final paragraph is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 is stated for all p≥(log n+2loglog n+ω(1))/n, but the written proof is complete only for the window p=(log n+2loglog n+f(n))/n with 1≪f(n)≪loglog n. The final paragraph delegates three other regimes to sketches. Since Cn(G)=C(G) is not monotone, this is not an automatic extension. In the regime (1+ε)log n/n≤p≤C log n/n, the sketch says properties (P1)-(P3) can be replaced by δ,Δ=Θ(log n), which is supposed to eliminate SMALL; however, for p close to (1+ε)log n/n the minimum degree constant is well below the SMALL threshold: for p=1.1 log n/n, the minimum degree is about 0.02 log n, so vertices of degree ≤0.1 log n still exist a.a.s. A correct extension must either redefine SMALL with a smaller threshold and rerun the P2/P3 estimates, or give a genuinely different argument. The intermediate regime between the f-window and (1+ε)log n/n is also only asserted as 'minor technical changes'. Thus the full threshold statement is not yet established by the text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16131,"tokens_out":40396,"duration_ms":388308,"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":[{"comment":"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.","section":"Section 3, proof of Theorem 1, final paragraph"},{"comment":"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.","section":"Lemma 3.10 and proof of Theorem 1, Step (S2b)"}],"minor_comments":[{"comment":"There is a typo: 'prcisely' should be 'precisely'.","section":"Section 3, before Theorem 3.1"},{"comment":"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.","section":"Lemma 3.6, proof"},{"comment":"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.","section":"Lemma 3.9, case (1.2.2)"},{"comment":"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.","section":"Lemma 3.10, application of Lemma 3.5"},{"comment":"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.","section":"Proof of Theorem 1, final paragraph"}],"recommendation":"major_revision","confidential_remarks":"The central idea and the f-window proof appear sound, and the paper addresses a natural open problem. The main concern is that the full threshold statement of Theorem 1 is not completely proved in the text: the extension to larger p is only sketched, and the sketch contains a claim about small-degree vertices that is inaccurate for p just above (1+ε) log n / n. The second major comment about the coverage of Lemma 3.6 is also a fixable gap, but it is load-bearing for the detailed window. I would encourage the authors to expand the final paragraph into a rigorous treatment of the remaining regimes, or to state the theorem only for the f(n)-window plus the known C log n / n result of [6] if the intermediate cases cannot be completed. The reliance on Lemma 2.2 of [6] is acceptable as a prior result, but the authors may want to state its hypotheses carefully to reassure readers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this paper contains a genuine new theorem — the sharp threshold for Hamilton cycles to span the cycle space of G(n,p) — but the full-range statement is not proven as written; one of the sketched extensions is simply wrong.\n\nWhat’s new and what works: Theorem 1 answers the Christoph–Nenadov–Petrova question by pushing the threshold from p ≥ C log n/n down to the optimal (log n + 2 log log n + ω(1))/n, matching the δ(G) ≥ 3 necessity. The detailed proof in the critical window is coherent. The parity-switcher machinery from [6] is adapted with care, especially Lemma 3.9, which avoids exhausting the neighbourhoods of small-degree vertices. The random graph estimates in Lemma 3.3 look standard and, as far as I checked, correct. The overall argument in the f(n)-window hangs together.\n\nSoft spots: the theorem is stated for all p above the threshold, but the proof is written only for p=(log n + 2 log log n + f(n))/n with 1 ≪ f(n) ≪ log log n. The last paragraph delegates three other ranges. I agree with the stress-test: the claim that for (1+ε)log n/n ≤ p ≤ C log n/n one can replace properties (P1)–(P3) by δ,Δ = Θ(log n) is false. For p = 1.1 log n/n the minimum degree is o(log n) — more precisely Θ(log n / log log n) — so vertices of degree ≤ 0.1 log n exist a.a.s. That regime needs a real argument, not a two-sentence sketch. The intermediate range between the f-window and (1+ε)log n/n is also asserted with “minor technical changes”; that might be true, but it is not automatic because Cn(G)=C(G) is not monotone increasing.\n\nThe dependence on Lemma 2.2 of [6] is not a new weakness; that is a published structural result, and using it as a black box is acceptable. My concern is the missing rigor for larger p, not the core recipe.\n\nWho it’s for: random graph theorists, and anyone interested in cycle space generation. The core proof is valuable; the gap is in the packaging. I would bring it to a reading group and would cite it for the f(n)-window result. It deserves serious refereeing — send it to a referee who can check the missing ranges, not a desk reject.","headline":"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.","tokens_in":16710,"tokens_out":6391,"would_cite":true,"duration_ms":59766,"reading_group":"yes","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":"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.","keywords":["cycle space","Hamilton cycles","random graphs","F2 vector space","minimum degree","parity switcher","phase transition","Hamilton-connected expanders"],"falsifier":"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.","tokens_in":15661,"feed_emoji":"🔄","tokens_out":8280,"duration_ms":86248,"temperature":0.7,"pith_summary":"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.\"","feed_headline":"Hamilton cycles generate every cycle at min-degree-3 threshold","feed_subtitle":"For n odd and p=(log n+2 log log n)/n, degree-3 vertices force all cycles to be F2-sums of Hamilton cycles.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the structural dichotomy (Lemma 2.2), the parity-switcher recipe, and the previously known result for large constant times log n/n.","marker":"[6]"},{"why":"Provides the textbook theorems used as Theorem 3.1 (a.a.s. Hamiltonicity) and Theorem 3.2 (a.a.s. minimum degree at least 3).","marker":"[13]"},{"why":"Supplies Theorem 2.8, the vertex-disjoint path-linking lemma used to build the paths inside the parity switcher.","marker":"[9]"},{"why":"Supplies Theorem 2.6, the expander Hamilton-connectivity result used to find the Hamilton path in the remainder step.","marker":"[10]"},{"why":"Supplies Lemma 3.5, the partition lemma used to split vertex sets into parts with controlled internal degrees for the random-graph proof.","marker":"[15]"},{"why":"Supplies the Chernoff-type bounds used throughout the probabilistic estimates for the random graph lemmas.","marker":"[19]"},{"why":"Is the source of the observed necessity that δ(G) ≥ 3 for the equality to hold a.a.s. in non-forest random graphs.","marker":"[18]"}],"fun_headline_variants":["Min-degree-3 forces Hamilton cycles to span all cycles in G(n,p)","At degree-3 threshold, Hamilton cycles span the cycle space of random graphs","For odd n, Hamilton cycles span every cycle once minimum degree hits 3","Hamilton cycles become a basis of cycle space in random graphs with min degree 3","Hamilton cycles span all cycles in random graphs at min-degree 3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Min-degree-3 forces Hamilton cycles to span all cycles in G(n,p)","At degree-3 threshold, Hamilton cycles span the cycle space of random graphs","For odd n, Hamilton cycles span every cycle once minimum degree hits 3","Hamilton cycles become a basis of cycle space in random graphs with min degree 3","Hamilton cycles span all cycles in random graphs at min-degree 3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000606,"raw_usage":{"total_tokens":2828,"prompt_tokens":950,"completion_tokens":1878,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":1778}},"tokens_in":566,"tokens_out":1878,"duration_ms":11237,"temperature":1.0,"reasoning_tokens":1778,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:27:52.820942+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Frieze and M","cited_arxiv_id":null,"evidence_quote":"Provides the textbook theorems used as Theorem 3.1 (a.a.s. Hamiltonicity) and Theorem 3.2 (a.a.s. minimum degree at least 3)."}],"review_version":2}