Blow-Up Lemmas for Sparse Graphs

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 triangle in subgraphs of G(n, p) with p = C(logn/n)(1/triangle); one for embedding spanning graphs with maximum degree triangle and degeneracy D in subgraphs of G(n, p) with p = C(logn/n)(1/(2D+1)); and one for embedding spanning graphs with maximum degree triangle in (p, cp(max(4,(3 triangle+1)/2))n)-bijumbled graphs. We also consider various applications of these lemmas.