Combinatorics Seminar
When: Sunday, October 27, 10am
Where: Schreiber 309
Speaker: Asaf Shapira, Tel Aviv University
Title: A Short Proof of Gowers' Lower Bound for the
Regularity Lemma
Abstract:
A celebrated result of Gowers states that for every \eps > 0 there
is a graph G so that every \eps-regular partition of G (in the sense
of Szemeredi's regularity lemma) has order given by a tower of
exponents of height polynomial in 1/\eps. I will describe a new proof
of this result that uses a construction and proof of correctness that
are significantly simpler and shorter.
Joint work with G. Moshkovitz.