Abstract:
The Regularity Lemma of Szemerédi, first obtained in the context of his theorem on arithmetic progressions in dense sequences, has become one of the most important and most powerful tools in graph theory. It is basic in extremal graph theory and in the theory of property testing. Weaker versions with better bounds (Frieze and Kannan) and stronger versions (Alon, Fisher, Krivelevich and Szegedy) have been proved and used. However, the significance of it goes way beyond graph theory: it can be viewed as statement in approximation theory, as a compactness result for the completion of the space of finite graphs, as a result about the dimensionality of a metric space associated with a graph, as a statement in information theory. It serves as the archetypal example of the dichotomy between structure and randomness as pointed out by Tao. Its extensions to hypergraphs, a difficult problem solved by Gowers and by Rodl, Skokan and Schacht, connects with higher order Fourier analysis.
This lecture was held at The University of Oslo, May 23, 2012 and was part of the Abel Prize Lectures in connection with the Abel Prize Week celebrations.
Program for the Abel Lectures 2012:
1. "In every chaos there is an order" by Abel Laureate Endre Szemerédi
2. "The many facets of the Regularity Lemma" by professor László Lovász
3. "The afterlife of Szemerédi's theorem" by professor Timothy Gowers
4. "Randomness and pseudorandomness" a science lecture by professor Avi Wigderson
