Cycle factors in randomly perturbed graphs

We study the problem of finding pairwise vertex-disjoint copies of the l-vertex cycle Ce 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 l >= 3 we prove that asymptotically almost surely G boolean OR G(n, p) contains min{delta(G), [n/l]) pairwise vertex-disjoint cycles C-l, provided p >= C log n/n for C sufficiently large. Moreover, when delta(G) >= an with 0 < a <= 1/l and G and is not 'close' to the complete bipartite graph K-alpha n,K-(1-alpha)n, then p >= C/n suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that p >= C/n suffices when alpha > n/l for finding [n/l] cycles C-l. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson-Kahn-Vu Theorem for C-l-factors and the resolution of the El-Zahar Conjecture for C-l-factors by Abbasi. (C) 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) Peer-review under responsibility of the scientific committee of the XI Latin and American Algorithms, Graphs and Optimization Symposium