Endre Szemerédi: In every chaos there is an order

Abstract:
The chaos and order will be defined relative to three problems.
1. Arithmetic progressions
This part is connected to a problem of Erdős and Turán from the 1930’s. Related to the van der Waerden theorem, they asked if the density version of that result also holds:
Is it true that an infinite sequence of integers of positive (lower) density contains arbitrary long arithmetic progressions?
The first result in this direction was due to K. F. Roth, who proved that any sequence of integers of positive (lower) density contains a three-term arithmetic progression.
I will give a short history of the generalization of Roth’s result and explain some ideas about the “easiest” proof.
2. Long arithmetic progression in subset sums
I will give exact bound for the size of longest arithmetic progression in subset sums. In addition, I shall describe the structure of the subset sums, and give applications in number theory and probability theory.
3. Embedding sparse graphs into large graphs
I am going to describe and illustrate a method to embed relatively sparse graphs into large graphs. This will include the cases of Pósa‘s conjecture, El Zahar’s conjecture, and tree embedding under different conditions. Among others, I shall give several generalizations of the central Dirac Theorem, both for graphs and hypergraphs.
The methods are elementary.
This lecture was held by Abel Laureate Endre Szemerédi 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
Thumbnail photo: Erlend Aas/Scanpix