{"id":"baa886e1-e721-4ea3-b438-b4e9cd3f7c5e","arxiv_id":"2502.00489","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimum degree threshold for a graph perturbed by a random 2-factor to become Hamiltonian is asymptotically sqrt(n log n / 2).","lead":"A graph whose minimum degree is just above sqrt(n log n / 2) becomes Hamiltonian when combined with a random 2-factor, and this is the exact threshold. This settles an open problem in randomly perturbed graphs, a model connecting extremal and probabilistic graph theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uniform-order property in Phase 2 needs M to be separated: adjacent M-edges break the transposition invariance that justifies the binomial success count.","rationale":"The reader correctly identified the uniform-order property in Phase 2 as the most load-bearing step, but did not pinpoint why the stated transposition invariance can fail. The good-pair relation itself (i-goodness) is label-based and order-independent, so transposing endpoints of an isolated pair preserves that pair's membership in M_i. However, if another M-edge is separated by only one vertex, its surrounding four-vertex window changes when the first pair is transposed, potentially changing its isolation status. Therefore M as a whole is not invariant, and the claimed uniform distribution over the 2^{|M|} orientations may fail for non-twin pairs. This gap is likely repairable because the expected number of close M-pairs is O(log^4 n / n) = o(1), so a simple union bound should restore the argument. The rest of the proof, including the lower bound construction and the approximately regular case, appears internally consistent. Hence the paper's central result is probably correct, but the proof as written needs an additional whp separation step before acceptance.","tokens_in":12734,"tokens_out":55627,"duration_ms":525660,"concrete_test":"Bound the expected number of unordered pairs {e1,e2} in M whose endpoints are at vertex-distance one along P0. If this expectation is o(1), add a union bound conditioning on a separated matching (no two M-edges within distance one), after which the transposition argument is valid. If the expectation is not o(1), construct a small configuration where a non-twin pair xy in M has P(x precedes y | M) != 1/2, disproving the uniform-order claim as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In 'Preparation for Phase 2', the proof asserts that for any xy in the unordered matching M, transposing x and y in π leaves every M_i unchanged, so conditional on M all 2^{|M|} orders of the pairs on P0 are equally likely. This is true only if no other edge of M lies at vertex-distance one from xy on P0. If e1=xy occupies positions (j,j+1) and e2=zw occupies positions (j+2,j+3), then the four-vertex window surrounding e2 contains y, while after transposing x and y it contains x instead. Since i-goodness is label-dependent, e2 may enter or leave M, so the conditioning event M is not invariant under the transposition. The paper only proves M is a matching, which does not exclude such adjacent pairs. Without the invariance, a non-twin pair's orientation on P0 need not be uniformly distributed conditional on M, and the binomial model for the number of successful exposures in Phase 2 is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper determines the asymptotic minimum-degree threshold for Hamiltonicity of the union of an n-vertex graph G and a random 2-factor F on the same vertex set: the threshold is (1+o(1))√(n log n / 2). Theorem 1.1 gives a positive result for δ(G) ≥ (1+ε)√(n log n/2), Theorem 1.2 gives a matching lower-bound construction, and Theorem 1.3 shows that for nearly regular G, a polylogarithmic minimum degree suffices. The proofs use the random-permutation representation of F, a two-phase Pósa-rotation argument with multiple exposure, and concentration inequalities including Chernoff, McDiarmid, and Talagrand-type bounds for permutations.","tokens_in":12880,"tokens_out":33965,"duration_ms":317487,"significance":"If correct, this resolves the problem posed by Girão and Espuny Díaz, improving the previous interval [log n / 5, n^{3/4+o(1)}] to the sharp threshold. The lower-bound construction is simple and exact, and the upper bound introduces a multiphase exposure framework that is likely to be useful in other randomly perturbed graph problems. The paper is largely self-contained, proving the needed random-permutation facts and concentration lemmas. The main caveat is a gap in the uniform-order property in Phase 2 of Theorem 1.1, which appears repairable but requires restructuring the proof.","major_comments":[{"comment":"The assertion that for any xy ∈ M, transposing x and y in π does not affect any Mi is not a consequence of the stated definition. If M contains two edges xy and zq at consecutive positions (j,j+1) and (j+2,j+3) of P0, then the four-vertex window surrounding zq is {y,z,q,r}; after transposing x and y it becomes {x,z,q,r}. Because i-goodness depends on the labels of the vertices, the set of i′-good ordered pairs in that window can change, so membership of zq in M can change; the matching property only excludes shared vertices, not edges at distance two. The later whp claim that all Yi = 0 does rule out such adjacent M-edges, since the endpoint z of zq would be an unexposed neighbour of b_{i′−1} or a_{i′} in the window of xy, but this is proved after the invariance assertion is used. To make the binomial model for X in Phase 2 rigorous, the proof should first define and condition on the whp event from the Yi calculation, then prove that M is 2-separated on that event, and only then derive the transposition invariance and the uniform-order property for pairs in M.","section":"Section 4, 'Preparation for Phase 2'"}],"minor_comments":[{"comment":"The displayed estimate '∼ d(√n log n)/n = Ω(log^{3/2} n)' is arithmetically incorrect; the quantity is Θ(log n). The argument still works with a union bound over the O(log n) long cycles, but the exponent should be corrected.","section":"Section 4, Phase 1"},{"comment":"In the sentence 'the conditional distribution of π given M1, . . . , Mk', the list should run to M_{k+1}, since the final Hamilton-cycle step is included in the argument.","section":"Section 4, Preparation for Phase 2"},{"comment":"The phrase 'the only ordered pairs that are i′-good for some i′ ∈ [k+1]' is ambiguous: it should be stated explicitly whether the local-uniqueness witness i′ may depend on the edge, and the later argument should use the same index for the adjacent-edge exclusion.","section":"Section 4, Preparation for Phase 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is strong and likely correct after a moderately involved repair of the Phase 2 conditioning argument. The reader's report's ACCEPT seems optimistic; the gap in the uniform-order property is in the core of the proof, although the materials to fix it (the Yi=0 claim) are already present. I recommend major_revision rather than accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the paper pins down the asymptotic minimum-degree threshold: δ(G) = (1+o(1)) sqrt(n log n/2) guarantees whp Hamiltonicity in G ∪ F with F a random 2-factor, and this is sharp. That is a genuine resolution of an open problem, and the near-regular polylog result is a nice bonus. The proofs are mostly self-contained and use standard concentration machinery; the lower bound construction is clean and the writing is honest about relying on random permutation theory.\n\nWhat is new: the sharp threshold, improving the prior interval [log n/5, n^{3/4+o(1)}], and the randomized Pósa rotation adapted to multiple exposure. The paper deserves credit for these ideas.\n\nNow the soft spot. The Phase 2 argument claims that transposing the endpoints of any pair xy in the matching M leaves every M_i unchanged, which justifies that all 2^{|M|} orders of the pairs on P0 are equally likely conditional on M. That is only true if no other M-edge lies within the four-vertex window of xy. The definition of M_i only excludes pairs that are i'-good within that window, so two M-edges can sit at positions (j,j+1) and (j+2,j+3): the second pair's window includes the vertex at j+1, which changes label when the first pair is transposed. That changes whether the second pair remains in M. So the conditioning event is not invariant, and the uniform-order property—and with it the binomial model for successes—is not established. This is not a minor typo; it is a load-bearing step in the proof of Theorem 1.1. I suspect it can be repaired, perhaps by strengthening the isolation condition in the definition of M_i or by a more careful orientation-counting argument, but as written the proof has a genuine gap.\n\nElsewhere the paper is solid: the lower bound, the concentration lemmas, and the near-regular theorem all check out. The self-citation for 'special vertices' is appropriate. The minor typo in Lemma 3.2 doesn't affect the conclusion.\n\nMy take: this is an important paper with a credible main theorem, but the Phase 2 gap means it is not ready as-is. A serious referee should see it, and the authors should be asked to tighten that step. If the gap is closable, this will be a strong contribution; if not, the lower bound and the near-regular result may still stand alone.","headline":"Resolves the asymptotic threshold for Hamiltonicity with a random 2-factor, but the Phase 2 uniform-order claim has a real gap that needs fixing.","tokens_in":13446,"tokens_out":5265,"would_cite":true,"duration_ms":49909,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding a random 2-factor makes any sufficiently large graph Hamiltonian once the minimum degree is at least $(1+\\varepsilon)\\sqrt{n \\log n/2}$, and this value is asymptotically best possible.","keywords":["Hamilton cycles","random 2-factor","randomly perturbed graphs","minimum degree threshold","Pósa rotation","random permutations","concentration inequalities","nearly regular graphs"],"falsifier":"Run the two-phase process on a large instance, say $n = 10^5$ with $d = 1.1\\sqrt{n \\log n / 2}$, and count how often Phase 2 exhausts all available good pairs before every short cycle is absorbed; the proof predicts a failure probability of $o(1)$ from a binomial bound, so any non-vanishing failure rate would contradict the upper bound.","tokens_in":12509,"feed_emoji":"🎲","tokens_out":17107,"duration_ms":152401,"temperature":0.7,"pith_summary":"This paper asks how large the minimum degree of a graph $G$ must be before adding a random 2-factor $F$ on the same $n$ vertices almost surely creates a Hamiltonian cycle, a cycle that visits every vertex exactly once. It proves the asymptotic threshold is $(1+o(1))\\sqrt{n \\log n / 2}$: every graph with minimum degree at least $(1+\\varepsilon)\\sqrt{n \\log n/2}$ becomes Hamiltonian with high probability after adding $F$, while some graph just below that degree fails with high probability. This settles the gap between the earlier lower and upper bounds, $\\tfrac{1}{5} \\log n$ and $n^{3/4+o(1)}$. If $G$ is nearly regular, the paper shows that a minimum degree of only $\\omega(\\log^3 n)$ already suffices. The proofs develop a randomised version of classical Pósa rotation adapted to progressive exposure of the random permutation that the 2-factor represents.","feed_headline":"Random 2-factor Hamiltonicity threshold is √(n log n / 2)","feed_subtitle":"At minimum degree (1+ε)√(n log n / 2), a Hamilton cycle appears with high probability; just below it, it fails.","key_machinery":"The engine is a randomised form of Pósa rotation, the classical technique that extends a path by rotating its endpoint along unused edges, run in multiple exposure rounds on the random permutation underlying $F$. A random 2-factor is written as $\\pi(F^*)$, with $F^*$ a fixed 2-factor with the exposed cycle lengths and $\\pi$ uniform. Long cycles are absorbed into the growing path by exposing a short random segment that with high probability contains a neighbour of the current endpoint in $G$. Short cycles are absorbed through 'i-good' ordered pairs $xy$ on the current path, where $x$ is a neighbour in $G$ of the previous endpoint and $y$ is a neighbour in $G$ of the cycle's attachment vertex. The delicate part is the matching $M$ of such pairs: the proof shows that transposing the endpoints of any good pair does not change the set of good pairs, so conditionally all $2^{|M|}$ orders of the pairs along the path are equally likely; this turns the greedy search for correctly ordered pairs into a binomial process with success probability $1/2$. In the nearly regular case the same exposure scheme is powered by 'special vertex sequences', chains of edges of $G$ that respect the order of random intervals, produced by expansion and concentration lemmas.","core_discovery":"The central claim is that the minimum degree needed for random 2-factor completion is asymptotically $\\sqrt{n \\log n / 2}$. For every $\\varepsilon>0$ and all sufficiently large $n$, if $G$ has $n$ vertices and minimum degree at least $(1+\\varepsilon)\\sqrt{n \\log n/2}$, then the union $G \\cup F$, with $F$ a uniformly random 2-regular graph on the same vertex set, is with high probability Hamiltonian. Conversely, for every $\\varepsilon>0$ there is an $n$-vertex graph with minimum degree $(1-\\varepsilon)\\sqrt{n \\log n/2}$ for which $G \\cup F$ is with high probability not Hamiltonian, so the constant $\\sqrt{1/2}$ is sharp. Under the additional condition that $G$ is nearly regular, meaning $\\Delta(G)=O(\\delta(G))$, the paper proves that minimum degree $\\omega(\\log^3 n)$ suffices. It also shows that for random $C_\\ell$-factors with $\\ell$ at least a large constant depending on $\\alpha$, minimum degree $\\alpha n$ suffices for every $\\alpha>0$.","pith_inferences":["The transposition-uniformity mechanism is a general switching principle: any edge-acceptability predicate that depends only on vertex labels and exposed vertices inherits the same all-orderings-equally-likely property, so the multiple-exposure architecture should transfer to other spanning structures such as powers of cycles or $\\ell$-factors.","The lower-bound construction suggests the real obstruction is component structure rather than raw edge count: a random 2-factor typically has many short cycles trapped inside the large side of a bipartite split, and the small side cannot connect them. One testable extension is that random $d$-regular perturbations with constant $d>2$ might still have threshold of order $\\sqrt{n \\log n}$, with a $d","A small computational experiment could test the proof's pivotal step directly: simulate the first exposure phase for moderate $n$, tally the conditional distribution of the $2^{|M|}$ orderings of matched good pairs, and check that it is uniform; any measurable bias would locate a flaw in the binomial step."],"forward_implications":["For every $\\varepsilon>0$ and all large $n$, every $n$-vertex graph with minimum degree at least $(1+\\varepsilon)\\sqrt{n \\log n/2}$ becomes Hamiltonian with high probability after adding a random 2-factor.","The threshold is asymptotically exact: there are graphs of minimum degree $(1-\\varepsilon)\\sqrt{n \\log n/2}$ whose union with a random 2-factor is with high probability non-Hamiltonian.","The same conclusions hold if the random perturbation is the graph of a uniformly random permutation instead of a random 2-factor, because loops and parallel edges cannot help in forming a Hamiltonian cycle.","Nearly regular graphs need only a polylogarithmic minimum degree, $\\omega(\\log^3 n)$, to become Hamiltonian after a random 2-factor.","For random $C_\\ell$-factors with $\\ell$ large, minimum degree $\\alpha n$ suffices for every fixed $\\alpha>0$, so the required linear density can be made arbitrarily small."],"supporting_citations":[{"why":"Establishes the previous interval for the minimum degree threshold, which Theorems 1.1 and 1.2 tighten to $\\sqrt{n \\log n/2}$.","marker":"[15]"},{"why":"Supplies the classical Pósa rotation technique whose randomised multiple-exposure variant is the paper's main method.","marker":"[32]"},{"why":"Supplies the concentration inequality for random permutations used to control the number of available good pairs.","marker":"[30]"},{"why":"Introduces the special vertex sequence tool that powers the nearly regular result.","marker":"[12]"},{"why":"Supplies the concentration inequalities and random graph facts used throughout the proofs.","marker":"[21]"},{"why":"Frames the randomly perturbed graph question that the paper answers.","marker":"[2]"}],"fun_headline_variants":["Sharp Hamiltonicity threshold: sqrt(n log n / 2) for random 2-factor","Random 2-factor threshold: sqrt(n log n / 2) is exact","Minimum degree for Hamiltonicity with random 2-factor: sqrt(n log n / 2)","Exact threshold: sqrt(n log n / 2) for random 2-factor","Sharp bound for Hamiltonicity via random 2-factor: sqrt(n log n / 2)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a vertex pair's usefulness as a connection depends only on the two labelled vertices and the set of vertices already exposed, not on their order along the growing path; if path order ever mattered, the equally-likely-order step would fail and the final count would not be a binomial variable.","fun_headline_variants_meta":{"raw":{"variants":["Sharp Hamiltonicity threshold: sqrt(n log n / 2) for random 2-factor","Random 2-factor threshold: sqrt(n log n / 2) is exact","Minimum degree for Hamiltonicity with random 2-factor: sqrt(n log n / 2)","Exact threshold: sqrt(n log n / 2) for random 2-factor","Sharp bound for Hamiltonicity via random 2-factor: sqrt(n log n / 2)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001087,"raw_usage":{"total_tokens":4546,"prompt_tokens":952,"completion_tokens":3594,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":3481}},"tokens_in":568,"tokens_out":3594,"duration_ms":25485,"temperature":1.0,"reasoning_tokens":3481,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T18:49:26.504633+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-phase process on a large instance, say $n = 10^5$ with $d = 1.1\\sqrt{n \\log n / 2}$, and count how often Phase 2 exhausts all available good pairs before every short cycle is absorbed; the proof predicts a failure probability of $o(1)$ from a binomial bound, so any non-vanishing failure rate would contradict the upper bound.","supporting_citations":[{"cited_title":"Hamiltonicity of graphs perturbed by a random regular graph","cited_arxiv_id":null,"evidence_quote":"Establishes the previous interval for the minimum degree threshold, which Theorems 1.1 and 1.2 tighten to $\\sqrt{n \\log n/2}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical Pósa rotation technique whose randomised multiple-exposure variant is the paper's main method."},{"cited_title":"Concentration for independent permu tations","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration inequality for random permutations used to control the number of available good pairs."},{"cited_title":"Pancyclicity of Hamiltonian graphs","cited_arxiv_id":"2209.03325","evidence_quote":"Introduces the special vertex sequence tool that powers the nearly regular result."},{"cited_title":"Bohman, A","cited_arxiv_id":null,"evidence_quote":"Frames the randomly perturbed graph question that the paper answers."}],"review_version":1}