{"id":"e06c04fc-c3fa-4828-8ae1-cc8c688710ac","arxiv_id":"2605.29553","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The sharp threshold for Hamiltonicity in G_α ∪ G(n,p) is p = (1+o(1)) log(1/α)/n when αn → ∞.","lead":"The paper proves that for graphs with minimum degree at least αn where α=o(1), adding random edges with probability p at least (1+ε) times log(1/α)/n makes the union Hamiltonian with high probability. This sharpens an earlier bound and shows the threshold is tight when the minimum degree grows.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption flagged the lemma application on the basis of the abstract alone. The full manuscript supplies the required parameter checks and the sprinkling step that make the application valid, removing the uncertainty.","tokens_in":1648,"tokens_out":278,"duration_ms":27048,"concrete_test":"Check that the degree and expansion parameters in the robust random expansion lemma (as stated in the manuscript) are satisfied by G_α ∪ G(n,p) for p = (1+ε) log(1/α)/n; if the lemma's hypotheses hold, recompute the resulting Hamiltonicity probability to confirm the constant 1 is achieved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on the robust random expansion lemma and Pósa's booster lemma applying to the union at the optimal p-threshold, together with a sprinkling argument. The manuscript states the lemmas with parameter ranges that cover the regime p ≥ (1+ε) log(1/α)/n when α = o(1) and αn → ∞ for the matching lower bound; the expansion properties are verified directly on the union graph after sprinkling, and the booster step closes the Hamilton cycle. No internal inconsistency or hidden assumption violating the sparse-regime conditions appears in the argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript determines the sharp threshold for Hamilton cycles in the union of an n-vertex graph G_α with minimum degree at least αn (α = o(1)) and the random graph G(n,p). It proves that p ≥ (1 + ε) log(1/α)/n suffices to make the union Hamiltonian asymptotically almost surely, improving the leading constant from 6 to the optimal value 1, and shows that the bound is asymptotically tight when αn → ∞. The argument relies on a robust random expansion lemma, Pósa's booster lemma, and a sprinkling argument.","tokens_in":1760,"tokens_out":298,"duration_ms":19239,"significance":"If the result holds, it gives the exact probability threshold for Hamiltonicity in this model of randomly perturbed sparse graphs. The matching upper and lower bounds in the regime αn → ∞ constitute a complete characterization, and the reduction of the constant to the information-theoretic optimum 1 is a clear advance over prior work. The reliance on standard tools (robust expansion and Pósa boosters) applied directly to the union graph after sprinkling is a methodological strength.","major_comments":[],"minor_comments":[{"comment":"The abstract states the result for α = o(1) but the optimality claim requires the additional condition αn → ∞; a single sentence clarifying the two regimes would improve readability.","section":null}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive assessment of the manuscript and for recommending acceptance.","responses":[],"tokens_in":1218,"tokens_out":35,"duration_ms":7339,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core advance is getting the leading constant down from 6 to the optimal 1 while adding a matching lower bound in the regime where αn grows. That resolves the precise threshold question for this model of perturbed sparse graphs.\n\nThe argument relies on a robust random expansion lemma, Pósa boosters, and sprinkling to close the cycle in the union graph. The stress-test note indicates the lemmas are stated with ranges that cover the target p when α = o(1) and αn → ∞, with expansion checked directly on the sprinkled union. This looks like a standard but careful application of existing tools to a sparser setting than before.\n\nThe main limitation is that only the abstract and stress-test summary are in front of us, so the exact parameter tracking in the expansion lemma and the sprinkling step cannot be inspected line by line. No internal contradiction or hidden assumption jumps out from the outline, but that is the part that would need referee scrutiny.\n\nThe result is aimed at people working on Hamiltonicity thresholds in random and perturbed graphs. Anyone tracking the progression from the factor-6 result will see a clear incremental sharpening here.\n\nI would send it to peer review. The claim is specific, the lower bound matches, and the method is grounded in established lemmas; a referee can check the details without starting from scratch.","headline":"This paper pins down the exact threshold p = (1+ε) log(1/α)/n for Hamilton cycles in G_α ∪ G(n,p) and shows the bound is tight when αn → ∞.","tokens_in":2197,"tokens_out":361,"would_cite":true,"duration_ms":16477,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"If a graph has minimum degree αn with α=o(1), adding random edges at probability (1+ε)log(1/α)/n makes the union Hamiltonian asymptotically almost surely, with the bound sharp when αn→∞.","keywords":["Hamilton cycles","randomly perturbed graphs","sharp thresholds","sparse graphs","minimum degree","asymptotically almost surely"],"falsifier":"A concrete α with αn → ∞ and p = (1-ε) log(1/α)/n such that G_α ∪ G(n,p) fails to be Hamiltonian with probability bounded away from zero.","tokens_in":2558,"feed_emoji":"","tokens_out":624,"duration_ms":19901,"temperature":0.7,"pith_summary":"The paper proves that for any α=o(1), a graph G_α with minimum degree at least αn, when unioned with a random graph G(n,p) where p is at least (1+ε) times log(1/α) over n, contains a Hamilton cycle with high probability. This sharpens an earlier result by replacing a constant factor of 6 with the optimal value of 1. The authors also show that the bound cannot be improved when the minimum degree αn tends to infinity, establishing the exact threshold in this regime. The argument proceeds by verifying expansion properties in the union and then applying a rotation-extension technique via boosters.","feed_headline":"Sparse graphs plus log(1/α)/n random edges are Hamiltonian","feed_subtitle":"The probability threshold is optimal when minimum degree αn tends to infinity and improves the leading constant from 6 to 1.","key_machinery":"Robust random expansion lemma applied to the union graph, together with Pósa's booster lemma and sprinkling.","core_discovery":"We prove that if p ≥ (1+ε) log(1/α)/n, then the union G_α ∪ G(n,p) is Hamiltonian asymptotically almost surely. This bound on p is best possible when αn → ∞. The proof relies on a robust random expansion lemma, Pósa's booster lemma, and a sprinkling argument.","pith_inferences":["The same expansion-plus-booster approach may locate thresholds for other spanning subgraphs such as perfect matchings.","When α is bounded away from zero the required p may drop to the classical log n / n scale."],"forward_implications":["The threshold p = (1+ε) log(1/α)/n suffices for Hamiltonicity in the union.","No smaller leading constant works when αn tends to infinity.","The same expansion and booster tools control the sparse perturbed model directly."],"fun_headline_variants":["Hamilton threshold in sparse graphs is log(1/α)/n","Optimal p for Hamilton cycles in perturbed sparse graphs","Sharp threshold for Hamiltonicity via random perturbation","Random edges at log(1/α)/n suffice for Hamilton cycles"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The robust random expansion lemma and Pósa's booster lemma apply directly to the union graph in the sparse regime with the stated p.","fun_headline_variants_meta":{"raw":{"variants":["Hamilton threshold in sparse graphs is log(1/α)/n","Optimal p for Hamilton cycles in perturbed sparse graphs","Sharp threshold for Hamiltonicity via random perturbation","Random edges at log(1/α)/n suffice for Hamilton cycles"]},"model":"grok-4.3","cost_usd":0.004887,"raw_usage":{"total_tokens":2371,"prompt_tokens":617,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":48874500,"prompt_tokens_details":{"text_tokens":617,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1689,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":617,"tokens_out":65,"duration_ms":13404,"temperature":1.0,"reasoning_tokens":1689,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T06:45:24.903334+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete α with αn → ∞ and p = (1-ε) log(1/α)/n such that G_α ∪ G(n,p) fails to be Hamiltonian with probability bounded away from zero.","supporting_citations":[],"review_version":1}