Past lectures

Abstract

Szemerédi's regularity lemma provides a rough structural description of all large graphs. It shows that the vertices of any graph can be partitioned into a bounded number of parts such that the edges between almost every pair of parts behave in a random-like fashion. This result created a paradigm shift in how we view and study graphs, and it has become a central tool in combinatorics with diverse applications in mathematics and computer science. In these lectures, we introduce the regularity lemma, its applications, variants, and alternative methods. We conclude with a proof of the celebrated Green-Tao theorem that there are arbitrarily long arithmetic progressions in the primes based on developing the sparse regularity method.