László Lovász: The many facets of the Regularity Lemma @AbelPrize
László Lovász: The many facets of the Regularity Lemma  @AbelPrize
Uploaded February 2020 | Updated November 2026, 1 day ago
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
László Lovász: The many facets of the Regularity LemmaThe Norwegian Prime Minister and the Minister of Education congratulates Michel Talagrand (2024)Interview with Hillel Furstenberg and Gregory Margulis - Abel Prize Laureates 2020Endre Szemerédi - The Abel Prize interview 2012The Abel Prize Interview: Michel Talagrand (2024) with Dundas & SkauJohn Christian Ottem: Advice to Young Mathematicians (2025)Gerd Faltings - Official Abel Prize laureate portrait 2026Hee Oh: A Eucledian travelers journey in a hyperbolic worldEveryone else understood. I didnt. | Hee Oh - Advice to young mathematicians - Abel Prize 2026Hillel Furstenberg: Why I went into mathematics (2022)アーベル賞の歴史 (History of the Abel Prize)Stephanos Venakides: Rigorous semiclassical asymptotics for integrable systems
The Abel Prize |

László Lovász: The many facets of the Regularity Lemma

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER