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