Abstract:

In 1975 Szemeredi, in a masterpiece of combinatorial reasoning, proved that every dense subset of the integers contains arbitrarily long arithmetic progressions. A key element in his proof was the Szemeredi Regularity Lemma, that eventually became a central tool in graph theory. Since then additional proofs have been found, by Furstenberg ('77), using ergodic theory, and by Gowers('98), using Fourier analysis. Last year Gowers, and, independently, Rodl came up with a generalization of the Regularity Lemma to hypergraphs. These generalizations, interesting in their own right, give a new and extremely simple proof (when used as a black box) of Szemeredi's theorem, and of the multidimensional version due to Furstenberg and Katznelson that previously had no combinatorial proof. I will attempt to describe their new ideas while keeping the talk self contained.