Szemerédi strikes back

Host Institution:

La Trobe University

Title of Seminar:

Szemerédi strikes back

Speaker's Name:

Prof János Pach

Speaker's Institution:

Budapest and Lausanne

Time and Date:

Wednesday 29 August 2012, 4.00pm (EST)

Seminar Abstract:

By an argument reminiscent of Furstenberg's original ergodic theoretic proof for Szemerédi's Theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following result. For every k and l, there exists an integer n(k,l) such that no matter how we color the vertices of a complete binary tree of depth n>n(k,l) with k colors, it always contains a monochromatic equispaced complete binary subtree T' of depth l; that is, a complete binary subtree T' of depth l which has the property that all of its vertices are of the same color and every vertex at level i of T' lies at level j+id in T. (Here j and d are suitable integers and 0 ≤ j ≤l.) Moreover, the two children of any vertex v of T' are descendants of different children of v in T. Furstenberg and Weiss also established several density versions of the above results, generalizing Szemerédi's Theorem.

We show that all of these results can be obtained by a simple combinatorial argument, using Szemerédi's classical theorem itself. Joint work with J. Solymosi and G. Tardos. The talk will be completely elementary and self-contained.

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support:

This email address is being protected from spambots. You need JavaScript enabled to view it.