Computer Science/Discrete Mathematics Seminar II

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.