Published July 2013
| Submitted
Book Section - Chapter
Open
Graph removal lemmas
- Creators
-
Conlon, David
- Fox, Jacob
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.
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.Attached Files
Submitted - 1211.3487.pdf
Files
1211.3487.pdf
Files
(440.8 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:4df8c3bc90a2b3cce68b96b24bb9ecce
|
440.8 kB | Preview Download |
Additional details
- Eprint ID
- 97850
- Resolver ID
- CaltechAUTHORS:20190812-163001516
- Royal Society
- Simons Foundation
- DMS-1069197
- NSF
- Created
-
2019-08-19Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Series Name
- London Mathematical Society Lecture Note Series
- Series Volume or Issue Number
- 409