Back to Search
Start Over
Spread blow-up lemma with an application to perturbed random graphs
- Publication Year :
- 2024
-
Abstract
- Combining ideas of Pham, Sah, Sawhney, and Simkin on spread perfect matchings in super-regular bipartite graphs with an algorithmic blow-up lemma, we prove a spread version of the blow-up lemma. Intuitively, this means that there exists a probability measure over copies of a desired spanning graph $H$ in a given system of super-regular pairs which does not heavily pin down any subset of vertices. This allows one to complement the use of the blow-up lemma with the recently resolved Kahn-Kalai conjecture. As an application, we prove an approximate version of a conjecture of B\"ottcher, Parczyk, Sgueglia, and Skokan on the threshold for appearance of powers of Hamilton cycles in perturbed random graphs.<br />Comment: 12 pages
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2410.06132
- Document Type :
- Working Paper