Graph regularity and removal lemmas
Graph regularity and removal lemmas
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.