Blow-up lemma for cycles in sparse random graphs

2021/11/17 by Trujić, Miloš
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2111.09236

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 ≥ C(log n/n)^1/Δ, sparse regular pairs behave similarly as complete bipartite graphs with respect to embedding a spanning graph H with Δ(H) ≤ Δ. However, this is typically only optimal when Δ∈ \2,3\ and H either contains a triangle (Δ= 2) or many copies of K₄ (Δ= 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 ≥ 2, and densities p ≥ Cn^-(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.

Related

• Blow-up lemmas for sparse graphs
• Spread blow-up lemma with an application to perturbed random graphs
• Covering cycles in sparse graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Local resilience for squares of almost spanning cycles in sparse random graphs