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
Video Link:https://video.ias.edu/csdm/graphremovelemma

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.