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.