An approximate blow-up lemma for sparse pseudorandom graphs
Allen, P.
, Böttcher, J., Hàn, H., Kohayakawa, Y. & Person, Y.
(2013).
An approximate blow-up lemma for sparse pseudorandom graphs.
Electronic Notes in Discrete Mathematics,
44, 393-398.
https://doi.org/10.1016/j.endm.2013.10.061
, Böttcher, J., Hàn, H., Kohayakawa, Y. & Person, Y.
(2013).
An approximate blow-up lemma for sparse pseudorandom graphs.
Electronic Notes in Discrete Mathematics,
44, 393-398.
https://doi.org/10.1016/j.endm.2013.10.061
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 p≫(lognn)1/δ