An approximate blow-up lemma for sparse pseudorandom graphs

We state a sparse approximate version of the blow-up lemma, showing that regular partitions in sufficiently pseudorandom graphs behave almost like complete partite graphs for embedding graphs with maximum degree Δ. We show that (p,γ)-jumbled graphs, with γ=o(pmax(2Δ,Δ+3/2)n), are “sufficiently pseudorandom”.The approach extends to random graphs Gn,p with .