CaltechAUTHORS
  A Caltech Library Service

Graph removal lemmas

Conlon, David and Fox, Jacob (2013) Graph removal lemmas. In: Surveys in Combinatorics 2013. London Mathematical Society Lecture Note Series. No.409. Cambridge University Press , Cambridge, United Kingdom, pp. 1-50. ISBN 9781139506748. https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001516

[img] PDF - Submitted Version
See Usage Policy.

440kB

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

Abstract

The graph removal lemma states that any graph on n vertices with o(n^h) copies of a fixed graph H on h vertices may be made H-free by removing o(n^2) edges. Despite its innocent appearance, this lemma and its extensions have several important consequences in number theory, discrete geometry, graph theory and computer science. In this survey we discuss these lemmas, focusing in particular on recent improvements to their quantitative aspects.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1017/cbo9781139506748.002DOIBook Section
https://arxiv.org/abs/1211.3487arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 2013 Cambridge University Press. Print publication year 2013; online publication date July 2013. Conlon supported by a Royal Society University Research Fellowship. Fox supported by a Simons Fellowship and NSF Grant DMS-1069197. The authors would like to thank Noga Alon, Zoltan Füredi, Vojta Rödl and Terry Tao for helpful comments regarding the history of the removal lemma.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
Simons FoundationUNSPECIFIED
NSFDMS-1069197
Series Name:London Mathematical Society Lecture Note Series
Issue or Number:409
DOI:10.1017/cbo9781139506748.002
Record Number:CaltechAUTHORS:20190812-163001516
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-163001516
Official Citation:Conlon, David, and Jacob Fox. “Graph Removal Lemmas.” Chapter. In Surveys in Combinatorics 2013, edited by Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, 1–50. London Mathematical Society Lecture Note Series. Cambridge: Cambridge University Press, 2013. doi:10.1017/CBO9781139506748.002.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97850
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:19 Aug 2019 21:29
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page