Frühlingssemester 2015
Jacob Fox
(Stanford University)
Regularity Methods in Combinatorics


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.

Time:              tba
Auditorium:   tba
Begins:          tba

M. Struwe