# 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"

** 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.

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

List of talks, 2004-05

Archive of lists of talks