Jerusalem Mathematics Colloquium

Thursday, 17th March 2005, 4:00 pm
Mathematics Building, Lecture Hall 2

Ehud Friedgut
(Hebrew University)

"New proofs of the multidimensional Szemeredi theorem via hypergraph regularity"


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.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2004-05
Archive of lists of talks