Graph removal lemmas

2012/11/15 by Conlon, David, Fox, Jacob · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1211.3487

Abstract

The graph removal lemma states that any graph on n vertices with o(n^v(H)) copies of a fixed graph H may be made H-free by removing o(n²) 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.

Cited by

• A note on lower bounds for arithmetic regularity partitions

Related

• A new proof of the graph removal lemma
• The Minimum Degree Removal Lemma Thresholds
• Minimum degree and the graph removal lemma
• Efficient Removal without Efficient Regularity
• Parameterized lower bound and NP-completeness of some H-free Edge Deletion problems