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.