2021/03/10 by Böttcher, Julia, Parczyk, Olaf, Sgueglia, Amedeo +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.06136
We study the problem of finding pairwise vertex-disjoint copies of the ℓ-vertex cycle C_ℓ 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 ℓ ≥ 3 we prove that asymptotically almost surely G ∪ G(n,p) contains min \δ(G), \lfloor n/ℓ \rfloor \ pairwise vertex-disjoint cycles C_ℓ, provided p ≥ C log n/n for C sufficiently large. Moreover, when δ(G) ≥αn with 01/ℓ for finding \lfloor n/ℓ \rfloor cycles C_ℓ. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson--Kahn--Vu Theorem for C_ℓ-factors and the resolution of the El-Zahar Conjecture for C_ℓ-factors by Abbasi.