Back to Search Start Over

Spread blow-up lemma with an application to perturbed random graphs

Authors :
Nenadov, Rajko
Pham, Huy Tuan
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