A new proof of the graph removal lemma


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.


Jacob Fox

Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA 02139-4307