{"id":"40e822ae-66c8-4bd2-bd05-13cb61b47e0a","arxiv_id":"2607.14881","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Random graphs with any edge probability have Hamilton covers of the smallest possible size, once Hamilton cycles exist.","lead":"The paper proves that random graphs can have every edge covered by the minimum possible number of Hamiltonian cycles, from the moment they become Hamiltonian up to almost complete graphs. It settles a conjecture about sparse random graphs and proves a classic decomposition conjecture for random graphs at every edge probability.","discovery_kind":"extension","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for edge probabilities p in the range (log n + log log n + omega(n))/n <= p <= 1 - omega(n)/n^2, the binomial random graph G(n,p) has with high probability a Hamilton cover of size ceil(Delta(G)/2), matching the trivial maximum-degree lower bound. This resolves a conjecture of Draganić, Glock, Munhá Correia and Sudakov for the sparse regime near the Hamiltonicity threshold. The paper also states a hitting-time version for the random graph process and uses the Hamilton-cover result to prove the linear arboricity conjecture for all p. The main technical contribution is a constructive proof for the sparse range: the graph is split into a typical middle part and exceptional high/low-degree parts, the typical part is decomposed into linear forests with slack, the exceptional vertices are handled by local gadgets, and an extendability method extends the resulting linear forests to Hamilton cycles. A separate argument handles the very dense range via a Hamilton decomposition theorem.","tokens_in":23777,"tokens_out":54143,"duration_ms":416113,"significance":"If the results are correct, they close the Hamilton-cover problem for random graphs essentially completely, answer the hitting-time question of Hefetz, Kühn, Lapinskas and Osthus, and prove the linear arboricity conjecture for all binomial random graphs. The sparse-range construction is novel and substantial, combining first-moment separation of exceptional vertices, forest-padding and merging mechanisms, and the Friedman–Pippenger extendability method. The paper also delivers a randomized polynomial-time algorithm for finding the cover. The proof of Theorem 1.1 is detailed and, in my reading, internally coherent. However, two advertised results have gaps: the hitting-time theorem is only sketched, and the linear arboricity proof contains a false statement in the dense case. These issues are fixable, but they currently prevent the paper from being fully established.","major_comments":[{"comment":"Theorem 1.2 is stated as a theorem in the abstract and introduction, but its proof is only a sketch. The assertion that 'the same estimates hold uniformly in the random graph process' is not proved. In particular, the exceptional sets B and S and their separation properties are not monotone, and the proof of Theorem 4.1 is written for a fixed binomial graph with a fixed p. A rigorous proof would need a coupling between the process and binomial graphs in the window, a union bound over m, or a direct verification of all deterministic hypotheses for every G_m with m in [m_-, m_+]. As written, Theorem 1.2 is not established.","section":"Section 7 (Theorem 1.2)"},{"comment":"The statement 'Then whp G has o(n) edges' is false. If 1-p=O(n^{-2}), the complement of G has O(1) edges whp, so G has C(n,2)-O(1) edges. The subsequent conclusion that G has a vertex of degree n-1 is correct (because the complement has O(1) edges), and the argument can be repaired by intersecting Walecki's linear-forest decomposition of K_n with E(G). However, the erroneous sentence must be corrected, as it is part of the proof of a stated theorem.","section":"Section 6 (Theorem 1.3, case 1-p=O(n^{-2}))"}],"minor_comments":[{"comment":"The proof uses 'P[v in B] <= n^{-0.59+o(1)}', but the Chernoff calculation in Item 1 gives n^{-0.56+o(1)}. The stronger bound is not justified. The weaker bound suffices for the first-moment argument, but the constants should be made consistent.","section":"Proposition 2.5, Item 2"},{"comment":"The line 'Let H:= G' should read 'Let H := \\bar G' (the complement), since the next equations use delta(H) and Delta(H) for the complement. The subsequent text writes 'H ~ G(n,q)', confirming the intended meaning.","section":"Lemma 5.3"},{"comment":"The definition 'm_\\pm = n^2 (\\log n + \\log\\log n \\pm \\xi)' appears dimensionally wrong: the number of edges in the process should be linear in n, i.e., m_\\pm = (n/2)(\\log n + \\log\\log n \\pm \\xi) (or the equivalent binomial-coefficient form). This is likely a typographical error.","section":"Section 7"},{"comment":"The manuscript refers to lemmas as 'Algorithm 2.4', 'Algorithm 3.2', 'Algorithm 4.1', etc. This is confusing and nonstandard. Use 'Lemma' for the statements and reserve 'Algorithm' for computational procedures.","section":"Throughout"},{"comment":"In the proof, the phrase 'The conditional distribution of e_G(v,R_i) given v not in R_i' is unnecessary: the number of neighbours of v in R_i is Bin(d_G(v)-d_W(v), 1/t) regardless of whether v itself lies in R_i, because neighbours are assigned independently. The argument is correct but the conditioning wording may mislead.","section":"Section 4, Lemma 4.2"}],"recommendation":"major_revision","confidential_remarks":"The main theorem (Theorem 1.1) appears sound and is a significant contribution. The revision should focus on (1) providing a complete proof of the hitting-time theorem rather than a sketch, and (2) correcting the false edge-count statement in the linear arboricity proof. Both are local in scope and do not undermine the central sparse-range construction, so rejection is not warranted. I recommend major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves the tight Hamilton-cover theorem for G(n,p) across the full range from the Hamiltonicity threshold to the dense endpoint, and deduces the linear arboricity conjecture for all p. The sparse regime near the threshold is the genuinely new part: the multi-stage construction with separated exceptional vertices, local gadgets for high/low degree vertices, and the extension to Hamilton cycles via reserved random sets is coherent and detailed. The dense range (complement with q = o(1/n^2)) is handled cleanly via regularisation and matchings, and the linear-arboricity deduction is standard once the cover theorem is in hand. The paper is honest about which parts are borrowed: the middle range is indeed [11] combined with [24], and the authors say so clearly.\n\nThe main soft spots are minor but real. First, in Section 6, the subcase 1-p = O(n^{-2}) says \"whp G has o(n) edges\" — that is plainly wrong; the complement has O(1) edges, not G. It reads like a typo, but it sits in a proof of Theorem 1.3, so it should be fixed before publication. Second, Theorem 1.2 (hitting time) is only sketched in the concluding remarks. The sketch is plausible and probably correct, but for a theorem stated in the abstract, a full proof or a precise reduction to the fixed-p case is expected. Third, the sparse argument uses the Hamilton-connectivity theorem from the preprint [14] as a black box. That is fine if the preprint is solid, but the referee should check it; a failure there would weaken the whole construction. The separation property in Proposition 2.5(2) is the kind of first-moment estimate that could worry a reader, but it is standard and the proof gives the right exponents; I do not see a hidden flaw.\n\nOverall, the central argument holds up. The paper is a capstone result for the Hamilton-cover and linear-arboricity questions in random graphs, and it deserves a serious referee. With the typo corrected and the hitting-time proof expanded (or explicitly deferred to a follow-up), it should be accepted. I would bring it to a reading group and cite it in my own work.","headline":"A substantial paper that plausibly closes the Hamilton-cover and linear-arboricity problems for random graphs; the sparse-range construction is the real new work, and the main results look correct, with a few rough edges that a careful referee should smooth out.","tokens_in":24202,"tokens_out":2748,"would_cite":true,"duration_ms":25276,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C45","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"With high probability, a binomial random graph whose edge probability ranges from the Hamiltonicity threshold to 1−ω(n)/n² has all its edges covered by exactly ⌈Δ(G)/2⌉ Hamilton cycles.","keywords":["Hamilton cover","random graph G(n,p)","tight cover","linear arboricity","Hamiltonicity threshold","linear forests","hitting time","expanders"],"falsifier":"Compute the expected number of length-6 paths in G(n, Clog n/n) with both endpoints in the top-degree set (degree at least (1−1/10)Δ). If for any fixed C this expectation is not o(1), the separation lemma fails and the cover construction loses control. A more direct falsifier is any graph in the stated range with an edge between two vertices whose degrees are close to the maximum, since the proof requires such high-degree stars to be disjoint.","tokens_in":23659,"feed_emoji":"🎲","tokens_out":5858,"duration_ms":56812,"temperature":0.7,"pith_summary":"This paper proves that the maximum-degree lower bound is the only obstruction to covering all edges of a random graph by Hamilton cycles: with high probability, G(n,p) has a cover by exactly ⌈Δ(G)/2⌉ Hamilton cycles for every p from the Hamiltonicity threshold up to the natural dense endpoint. The main new work is the sparse regime, where the degree spread is large; the proof isolates the exceptional very-high-degree and very-low-degree vertices, shows they are well separated, covers the typical part by controlled linear forests, and then extends each forest into a Hamilton cycle using reserved random structure. The same method gives a hitting-time result (the cover appears exactly when the minimum degree reaches two) and implies the linear arboricity conjecture for all binomial random graphs.","feed_headline":"Tight Hamilton covers proven across the full viable random-graph range","feed_subtitle":"The maximum-degree lower bound is always the only obstruction, from the Hamiltonicity threshold to near the complete graph.","key_machinery":"The key objects are linear forests (disjoint unions of paths): unlike arbitrary edge sets, any linear forest can be extended to a Hamilton cycle if enough unused random edges are reserved around its endpoints. The proof splits the graph into a constant number of subgraphs, covers the typical part by approximate linear forests with slack, builds cherry/path gadgets for the exceptional high-degree and low-degree vertices, and pairs typical with exceptional forests so that the leftover has bounded degree. A separation estimate (no short paths or cycles between exceptional vertices) keeps these local gadgets from interfering, and a bounded-degree merging lemma absorbs the leftover. Each final li","core_discovery":"The central claim is that tight Hamilton covers exist with high probability for G(n,p) throughout the range (log n + log log n + ω(n))/n ≤ p ≤ 1 − ω(n)/n². The proof's new engine is the sparse end: it identifies the small set of vertices whose degree is far from Δ(G), proves these exceptional vertices are separated by no short paths or cycles, covers the typical part by a family of linear forests with slack, merges explicit gadgets for high- and low-degree vertices, and then extends each merged linear forest to a Hamilton cycle via an expander-based tree-embedding (extendability) argument. As corollaries, the tight-cover property appears at the hitting time of minimum degree 2 in the random","pith_inferences":["The same forest-extension mechanism may transfer to pseudorandom (n,d,λ)-graphs with a degree gap, provided a separation lemma analogous to the one used here can be established for them.","The hitting-time result suggests tight-coverability does not lag behind Hamiltonicity; one could test whether the directed random graph analogue also holds at the analogous hitting time.","The linear arboricity corollary is nearly immediate for the dense regime, so the new content lies in the sparse regime; the proof indicates the separation estimate is the main obstacle to further weakening the degree-range assumptions.","One could computationally explore the constants (the split t and the slack α) to see whether the construction tolerates less separation; the paper does not optimize these constants."],"forward_implications":["For every p in the stated range, the edges of G(n,p) are covered by the theoretical minimum number of Hamilton cycles, matching the maximum-degree lower bound.","The hitting-time statement says the tight-cover property appears at the same moment the graph first has minimum degree at least two, so Hamiltonicity and tight-coverability share a threshold in the random graph process.","The linear arboricity conclusion gives a path-decomposition of all edges into at most ⌈(Δ+1)/2⌉ linear forests for every p, confirming the linear arboricity conjecture for random graphs.","The proof is constructive and yields a randomized polynomial-time algorithm to find the required cover.","The range of p is best possible up to the critical window 1−p ≍ n⁻², where no whp statement holds because the complement may consist of a single edge."],"fun_headline_variants":["Random graphs achieve the minimum Hamilton cover size","Tight Hamilton covers proven from sparse threshold to dense limit","Sparse random graphs now achieve exact Hamilton covers","Hamilton covers attain lower bound for all random-graph densities"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The construction depends on a first-moment separation estimate: with high probability no short path (length at most 6) joins two exceptional vertices, and no short cycle passes through the exceptional set or its neighbourhood, and if that estimate failed the local gadgets around different exceptional vertices could collide and the bounded-degree leftover argument would lose control.","fun_headline_variants_meta":{"raw":{"variants":["Random graphs achieve the minimum Hamilton cover size","Tight Hamilton covers proven from sparse threshold to dense limit","Sparse random graphs now achieve exact Hamilton covers","Hamilton covers attain lower bound for all random-graph densities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001423,"raw_usage":{"total_tokens":5613,"prompt_tokens":812,"completion_tokens":4801,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":4739}},"tokens_in":556,"tokens_out":4801,"duration_ms":32096,"temperature":1.0,"reasoning_tokens":4739,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T00:50:23.462241+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the expected number of length-6 paths in G(n, Clog n/n) with both endpoints in the top-degree set (degree at least (1−1/10)Δ). If for any fixed C this expectation is not o(1), the separation lemma fails and the cover construction loses control. A more direct falsifier is any graph in the stated range with an edge between two vertices whose degrees are close to the maximum, since the proof requires such high-degree stars to be disjoint.","supporting_citations":[],"review_version":1}