Blow-up lemma for cycles in sparse random graphs

Abstract

In a recent work, Allen, Böttcher, Hàn, Kohayakawa, and Person provided a first general analogue of the blow-up lemma applicable to sparse (pseudo)random graphs thus generalising the classic tool of Komlós, Sárközy, and Szemerédi. Roughly speaking, they showed that with high probability in the random graph $G_{n,p}$ for $p\ge C(\log n/n{)}^{1/\Delta }$, sparse regular pairs behave similarly as complete bipartite graphs with respect to embedding a spanning graph $H$ with $\Delta (H)\le \Delta$. However, this is typically only optimal when $\Delta \in \{2,3\}$ and $H$ either contains a triangle ($\Delta =2$) or many copies of $K_4$ ($\Delta =3$). We go beyond this barrier for the first time and present a sparse blow-up lemma for cycles $C_{2k-1},C_{2k}$, for all $k\ge 2$, and densities $p\ge C{n}^{-(k-1)/k}$, which is in a way best possible. As an application of our blow-up lemma we fully resolve a question of Nenadov and Škorić regarding resilience of cycle factors in sparse random graphs.

arXiv comment31 pages and 7 pages appendix, 5 figures