OpenAlex ·
Thinning and sprinkling: from robust sampling to almost Hamiltonicity
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.30165
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Boolean threshold functions, neuron capacity, and memory retrieval
Fast factorization in diagram monoids
Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
Odd Cycle Transversal on $H$-free graphs
Construction of Partial Join Graphs with Perfect State Transfer in Shunt Decomposition-Based Quantum Walks
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.