Regularity inheritance in pseudorandom graphs

Allen, Peter

; and Stein, Maya (2020) Regularity inheritance in pseudorandom graphs Random Structures and Algorithms, 56 (2). 306 - 338. ISSN 1042-9832

Copy

Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved H-counting lemmas for subgraphs of bijumbled graphs, for some H.

Item Type	Article
Keywords	counting lemma,pseudorandom graphs,regularity inheritance,sparse regularity lemma,Szemerédi’s regularity lemma,UKRI fund,Wiley prepayment account
Departments	Mathematics
DOI	10.1002/rsa.20851
Date Deposited	07 Feb 2019 09:12
URI	https://researchonline.lse.ac.uk/id/eprint/100044

Explore Further

QA Mathematics

http://www.lse.ac.uk/Mathematics/people/Peter-Allen?from_serp=1 (Author)
http://www.lse.ac.uk/Mathematics/people/Julia-Boettcher?from_serp=1 (Author)
http://www.lse.ac.uk/Mathematics/people/Jozef-Skokan?from_serp=1 (Author)
https://onlinelibrary.wiley.com/journal/10982418 (Official URL)

picture_as_pdf

picture_as_pdf
subject: Published Version
: Available under Creative Commons: Attribution 4.0

Download

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