Date & Time: Tuesday, February 02, 2016, 14:00-15:30
Venue: Ramanujan Hall
Title: The number of parts in an $\epsilon$-regular partition grows as a tower of 2's of height $\Omega(1/epsilon^c)$ for some absolute constant c.
Speaker: Niranjan Balachandran, Mathematics Department, IIT Bombay
Abstract: The regularity lemma (due to E. Szemeredi) states that for a given $\epsilon>0$ every graph can be partitioned into $k< M(\epsilon)$ equitable parts {V_1,V_2,..,V_k} such that except for at most $\epsilon k^2$ of these pairs, the rest are $\epsilon$-regular. The proof of the regularity lemma obtains a $k$ which grows as a tower of 2's of height $\Omega(1/\epsilon^5)$. Gowers however showed that this type of tower growth is unavoidable, and simpler proofs were later given by Conlon and Fox. We shall look at another one which is considerably simpler, due to Shapira and Moschovitz.