Departmental Colloquium
Jacob Fox
MIT
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. The graph removal lemma has many
applications in graph theory, additive combinatorics, discrete geometry,
and theoretical computer science.
We give a new proof which avoids Szemeredi's regularity lemma and gives a
better bound. This answers questions of Alon and Gowers.
Friday December 3, 2010 at 3:00 PM in SEO 636