REVIEW 1 minor 12 references
Sharp threshold for Hamilton cycles in randomly perturbed sparse graphs
T0 review · 0 major / 1 minor · reviewed 2026-06-29 · grok-4.3
Pith's one-line read 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→∞.
desk verdict 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 → ∞. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Robust random expansion lemma applied to the union graph, together with Pósa's booster lemma and sprinkling.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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.
minor comments (1)
- 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.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending acceptance.
Circularity Check
No significant circularity in derivation chain
full rationale
The paper derives the sharp threshold p ≥ (1+ε) log(1/α)/n for Hamiltonicity of G_α ∪ G(n,p) via direct application of the robust random expansion lemma, Pósa's booster lemma, and sprinkling to the union graph. These are standard external tools from random graph theory, not self-citations or fitted inputs; the matching lower bound when αn → ∞ follows from a standard first-moment argument on the random graph component. No equation reduces to a prior definition or self-citation by construction, and the central claim remains independent of the authors' prior work.
Assumptions & free parameters
assumptions (2)
- standard math Pósa's booster lemma holds for the perturbed graph
- domain assumption A robust random expansion lemma applies in the sparse regime
Cite this review
Pith. "Pith review of Sharp threshold for Hamilton cycles in randomly perturbed sparse graphs." pith.science (2026). https://pith.science/paper/X7QHZZGE
@misc{pith2026260529553,
author = {Pith},
title = {Pith review of: Sharp threshold for Hamilton cycles in randomly perturbed sparse graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/X7QHZZGE}},
note = {Machine review of arXiv:2605.29553}
}
abstract
We determine the sharp threshold for Hamilton cycles in randomly perturbed sparse graphs. For any $\alpha=\alpha(n)=o(1)$, let $G_{\alpha}$ be an $n$-vertex graph with minimum degree $\delta(G_{\alpha})\ge\alpha n$. We prove that if $$p\ge(1+\varepsilon)\frac{\log(1/\alpha)}{n},$$ then the union $G_{\alpha}\cup G(n,p)$ is Hamiltonian asymptotically almost surely. This significantly strengthens a recent result of Hahn-Klimroth, Maesaka, Mogge, Mohr, and Parczyk by improving the leading constant from 6 to the optimal value of 1. Crucially, we show that this bound on $p$ is best possible when $\alpha n\rightarrow\infty$, thereby establishing the exact probability threshold for Hamiltonicity in this sparse regime. Our proof relies on a robust random expansion lemma, P\'{o}sa's booster lemma, and a sprinkling argument.
Reference graph
Works this paper leans on
-
[1]
S. Antoniuk, N. Kam c ev, C. Reiher, and T. P. Tukara. The complete picture for clique factors in randomly perturbed graphs. arxiv:2603.22081 , 2026
-
[2]
Bohman, A
T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph H amiltonian? Random Structures Algorithms , 22(1):33--42, 2003
2003
-
[3]
B\" o ttcher, R
J. B\" o ttcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika , 66(2):422--447, 2020
2020
-
[4]
Balogh, A
J. Balogh, A. Treglown, and A. Z. Wagner. Tilings in randomly perturbed dense graphs. Combin. Probab. Comput. , 28(2):159--176, 2019
2019
-
[5]
Triangle packings in randomly perturbed graphs
X. Cheng, H. Liu, L. Wang, and Z. Yan. Triangle packings in randomly perturbed graphs. arxiv:2604.25250 , 2026
work page Pith review arXiv 2026
-
[6]
Das and A
S. Das and A. Treglown. Ramsey properties of randomly perturbed graphs: cliques and cycles. Combin. Probab. Comput. , 29(6):830--867, 2020
2020
-
[7]
Espuny D\' az and R.V
A. Espuny D\' az and R.V. Razafindravola. How many random edges make an almost- D irac graph H amiltonian? Electron. J. Combin. , 32(4):Paper No. 4.47, 15, 2025
2025
-
[8]
Hahn-Klimroth, G
M. Hahn-Klimroth, G. S. Maesaka, Y. Mogge, S. Mohr, and O. Parczyk. Random perturbation of sparse graphs. Electron. J. Combin. , 28(2):Paper No. 2.26, 12, 2021
2021
Show all 12 references
-
[9]
J. Han, P. Morris, and A. Treglown. Tilings in randomly perturbed graphs: bridging the gap between H ajnal- S zemer\' e di and J ohansson- K ahn- V u. Random Structures Algorithms , 58(3):480--516, 2021
2021
-
[10]
Joos and J
F. Joos and J. Kim. Spanning trees in randomly perturbed graphs. Random Structures Algorithms , 56(1):169--219, 2020
2020
-
[11]
Krivelevich, M
M. Krivelevich, M. Kwan, and B. Sudakov. Bounded-degree spanning trees in randomly perturbed graphs. SIAM J. Discrete Math. , 31(1):155--171, 2017
2017
-
[12]
P\' o sa
L. P\' o sa. Hamiltonian circuits in random graphs. Discrete Math. , 14(4):359--364, 1976
1976
Reviewed June 29, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.