Cycle factors in randomly perturbed graphs

Abstract

We study the problem of finding pairwise vertex-disjoint copies of the $\ell$-vertex cycle $C_{\ell }$ in the randomly perturbed graph model, which is the union of a deterministic $n$-vertex graph $G$ and the binomial random graph $G(n,p)$. For $\ell \ge 3$ we prove that asymptotically almost surely $G\cup G(n,p)$ contains $\min \{\delta (G),\lfloor n/\ell \rfloor \}$ pairwise vertex-disjoint cycles $C_{\ell }$, provided $p\ge C\log n/n$ for $C$ sufficiently large. Moreover, when $\delta (G)\ge \alpha n$ with $0<\alpha \le 1/\ell$ and $G$ is not `close' to the complete bipartite graph $K_{\alpha n,(1-\alpha )n}$, then $p\ge C/n$ suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that $p\ge C/n$ suffices when $\alpha >1/\ell$ for finding $\lfloor n/\ell \rfloor$ cycles $C_{\ell }$. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for $C_{\ell }$-factors and the resolution of the El-Zahar Conjecture for $C_{\ell }$-factors by Abbasi.

12 pages. An extended abstract of this work will appear in the proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2021)