| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652067 | Electronic Notes in Discrete Mathematics | 2013 | 6 Pages |
Abstract
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 .
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
