A new proof of the graph removal lemma

Abstract

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemerédi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

arXiv comment17 pages

Cited by in corpus (2)

• Fast Distributed Algorithms for Testing Graph Properties
• Maximal antichains of minimum size