Blow-up lemmas for sparse graphs

2016/12/02 by Allen, Peter, Böttcher, Julia, Hàn, Hiep +2 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1612.00622

Abstract

The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three sparse versions of the blow-up lemma: one for embedding spanning graphs with maximum degree Δ in subgraphs of G(n,p) with p=C(log n/n)^1/Δ; one for embedding spanning graphs with maximum degree Δ and degeneracy D in subgraphs of G(n,p) with p=C_Δ(log n/n)^1/(2D+1); and one for embedding spanning graphs with maximum degree Δ in (p,cp^{max(4,(3Δ+1)/2)}n)-bijumbled graphs. We also consider various applications of these lemmas.

Cited by

• Robustness of the Sauer-Spencer Theorem

Related

• Blow-up lemma for cycles in sparse random graphs
• An Algorithmic Version of the Blow-up Lemma
• A blow-up lemma for approximate decompositions
• Spread blow-up lemma with an application to perturbed random graphs
• An Extension of the Blow-up Lemma to arrangeable graphs