Szemerédi's regularity lemma revisited

Terry Tao
UCLA

In 1975, Szemerédi introduced a remarkable regularity lemma for arge dense graphs, as a key component of his proof of a long-standing conjecture of Erdös and Turán on arithmetic progressions. Roughly speaking, this lemma asserts that any large dense graph can be modeled accurately by a bounded number of random graphs between a bounded number of cells in a vertex partition. This lemma has since proven to be of major importance in graph theory, computer science, and combinatorial number theory. In recent years, the regularity lemma (and its generalisation to hypergraphs) has been revisited using several new perspectives, including functional analysis, measure theory, non-standard analysis, information theory, and ergodic theory; for instance, these approaches to the regularity lemma played an important guiding role in my work with Ben Green on establishing arbitrarily long arithmetic progressions in the primes. We discuss some of these new developments and insights in this talk.