Thinning and sprinkling: from robust sampling to almost Hamiltonicity
Abstract
We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgraphs of tough graphs, high-degree connected vertex-transitive graphs, and nearly regular sublinear expanders retain strong connectivity or expansion properties with very high probability. We also prove that every k-connected graph with k=ω(log n) contains a spanning bipartite subgraph that is Ω(k)-connected. Using these robustness results, we further develop a general framework for constructing almost Hamilton cycles from randomly sampled highly connected subgraphs. As a consequence, we show that tough graphs, connected vertex-transitive graphs and nearly regular expanders contain a cycle of length at least $(1-o(1))n$ whenever the toughness or degree is polylogarithmically large. This gives asymptotic solutions of longstanding conjectures of Chvátal and Lovász on Hamiltonicity of tough and vertex-transitive graphs.
Related
- On the Hamiltonicity of generating graphs of almost simple groups
- Random Sampling of Almost Periodic Stochastic Processes
- Fast Almost-Uniform Sampling of Random k-SAT Solutions
- Sprinkling for random regular graphs and Kim-Vu's sandwich conjecture
- SULA: Robust Langevin Sampling via Drift-Diffusion Saturation
BibTeX
@misc{christoph2026thinning,
title = {{Thinning and sprinkling: from robust sampling to almost Hamiltonicity}},
author = {Micha Christoph and Zach Hunter and Benny Sudakov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30165},
eprint = {2609.30165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30165},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Thinning and sprinkling: from robust sampling to almost Hamiltonicity
AU - Micha Christoph
AU - Zach Hunter
AU - Benny Sudakov
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30165
UR - https://arxiv.org/abs/2609.30165
AB - We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgraphs of tough graphs, high-degree connected vertex-transitive graphs, and nearly regular sublinear expanders retain strong connectivity or expansion properties with very high probability. We also prove that every k-connected graph with k=ω(log n) contains a spanning bipartite subgraph that is Ω(k)-connected. Using these robustness results, we further develop a general framework for constructing almost Hamilton cycles from randomly sampled highly connected subgraphs. As a consequence, we show that tough graphs, connected vertex-transitive graphs and nearly regular expanders contain a cycle of length at least $(1-o(1))n$ whenever the toughness or degree is polylogarithmically large. This gives asymptotic solutions of longstanding conjectures of Chvátal and Lovász on Hamiltonicity of tough and vertex-transitive graphs.
ER -