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.