Computer Science/Discrete Mathematics Seminar II
Topic: Graph removal lemmas
Speaker: Fan Wei
Affiliation: Member, School of Mathematics
Date & Time: Tuesday December 10th, 2019, 10:30am - 12:30pm
Location: Simonyi Hall 101
Continuing last week's lecture, among the numerous applications of the regularity lemma, a classical one is the graph removal lemma. It has applications in fields such as number theory and theoretical computer science. For every fixed graph H, the H-removal lemma gives a highly nontrivial equivalence between the density of H in G and the L1 distance between a graph G to the set of H-free graphs. The quantitative estimates remains a big open question in graph theory. In this talk, I will cover the standard proof of the graph removal lemma, and discuss some recent works on a strengthening of the usual graph removal lemma.