Blow-up lemmas for sparse graphs

MaRDI QIDQ6280403zbMATH OpenFDO

Authors Peter Allen, Julia Böttcher, Hiệp Hàn, Yoshiharu Kohayakawa, Yury Person

Publication date 2 December 2016

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

This page was built for publication: Blow-up lemmas for sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280403)