![School of Mathematics Event](/sites/default/files/styles/two_column_medium/public/2019-09/sm_default.jpg?itok=gMvWynkh)
Computer Science/Discrete Mathematics Seminar I
The Graph Removal Lemma
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.
Date & Time
November 08, 2010 | 11:15am – 12:15pm
Location
S-101Speakers
Jacob Fox
Affiliation
Massachusetts Institute of Technology