CaltechAUTHORS
  A Caltech Library Service

Extremal results in sparse pseudorandom graphs

Conlon, David and Fox, Jacob and Zhao, Yufei (2014) Extremal results in sparse pseudorandom graphs. Advances in Mathematics, 256 . pp. 206-290. ISSN 0001-8708. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957263

[img] PDF - Submitted Version
See Usage Policy.

742Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957263

Abstract

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and Rödl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős–Stone–Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.aim.2013.12.004DOIArticle
https://www.sciencedirect.com/science/article/pii/S0001870813004507PublisherArticle
https://arxiv.org/abs/1204.6645arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 2014 Elsevier. Under an Elsevier user license. Received 4 June 2012; accepted 14 December 2013; available online 25 February 2014. Conlon research supported by a Royal Society University Research Fellowship. Fox research supported by a Simons Fellowship, a Packard Fellowship, an Alfred P. Sloan Fellowship, an MIT NEC Corporation Award, and NSF grant DMS-1069197. Zhao research supported by an Akamai Presidential Fellowship and a Microsoft Research PhD Fellowship. We thank the referees for a number of helpful comments which improved the manuscript.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
Simons FoundationUNSPECIFIED
David and Lucile Packard FoundationUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
MIT NEC CorporationUNSPECIFIED
NSFDMS-1069197
Akamai Presidential Graduate FellowshipUNSPECIFIED
Microsoft Research Graduate FellowshipUNSPECIFIED
Subject Keywords:Szemerédi’s regularity lemma; Sparse regularity lemma; Counting lemma; Graph removal lemma; Extremal combinatorics; Sparse graphs
Record Number:CaltechAUTHORS:20190812-162957263
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957263
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97808
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 18:00
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page