|COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I|
|Topic:||The Graph Removal Lemma|
|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.