An approximate blow-up lemma for sparse pseudorandom graphs

Allen, Peter

; Hàn, Hiệp; Kohayakawa, Yoshiharu; and Person, Yury (2013) An approximate blow-up lemma for sparse pseudorandom graphs. Electronic Notes in Discrete Mathematics, 44. pp. 393-398. ISSN 1571-0653

Copy

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/δ

Item Type	Article
Keywords	Blow-up lemma; Pseudorandom graphs; Random graphs; Sparse regularity lemma
Departments	Mathematics
DOI	10.1016/j.endm.2013.10.061
Date Deposited	16 Dec 2013 14:13
URI	https://researchonline.lse.ac.uk/id/eprint/54939

Explore Further

QA Mathematics

http://www.lse.ac.uk/Mathematics/people/Peter-Allen.aspx (Author)
http://www.lse.ac.uk/Mathematics/people/Julia-Boettcher.aspx (Author)
10.1016/j.endm.2013.10.061 (DOI)

Full text not available from this repository.

Atom

BibTeX

OpenURL ContextObject in Span

OpenURL ContextObject

Dublin Core

MPEG-21 DIDL

Data Cite XML

EndNote

HTML Citation

METS

MODS

RIOXX2 XML

Reference Manager

Refer

ASCII Citation

Export

Downloads