Jacob Fox : The Graph Removal Lemma

Posted by , part of the Departmental Colloquium.

At

Dec. 3, 2010, 3 p.m.

In

SEO 636

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.