Blow-up lemmas for sparse graphs

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 $\hat{I}”$ in subgraphs of $G(n,p)$ with $p=C(\log n/n{)}^{1/\hat{I}”}$; one for embedding spanning graphs with maximum degree $\hat{I}”$ and degeneracy $D$ in subgraphs of $G(n,p)$ with $p=C_{\hat{I}}”(\log n/n{)}^{1/(2D+1)}$; and one for embedding spanning graphs with maximum degree $\hat{I}”$ in $(p,c{p}^{\max (4,(3\hat{I}”+1)/2)}n)$-bijumbled graphs. We also consider various applications of these lemmas.

141 pages, 3 figures, final version for Discrete Analysis