The Graph Removal Lemma

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:	The Graph Removal Lemma
Speaker:	Jacob Fox
Affiliation:	Massachusetts Institute of Technology
Date:	Monday, November 8
Time/Room:	11:15am - 12:15pm/S-101

---

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 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.