Title: The Graph Removal Lemma
Speaker: Jacob Fox, MIT
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. It has many applications in theoretical computer
science, extremal graph theory, additive combinatorics, and discrete
geometry. We give a new proof of the graph removal lemma which avoids
Szemeredi'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.