Graph regularity and removal lemmas

-
Jacob Fox, MIT

Szemeredi's regularity lemma is one of the most powerful tools in graph theory. It was introduced by Szemeredi in his proof of the celebrated Erdos-Turan conjecture on long arithmetic progressions in dense subsets of the integers. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random-like. One of the most important applications is the graph removal lemma, which roughly says that every graph with few copies of a fixed graph H can be made H-free by removing few edges. It remains a significant problem to estimate the bounds in the regularity lemma and the removal lemma, and their variants. In this talk I discuss recent joint work with David Conlon which makes progress on this problem.