Lower bounds of tower type for Szemerédi's uniformity lemma

Abstract.

It is known that the size of the partition obtained in Szemerédi's Uniformity Lemma can be bounded above by a number given by a tower of 2s of height proportional to $\epsilon^{-5}$, where $\epsilon$ is the desired accuracy. In this paper, we first show that the bound is necessarily of tower type, obtaining a lower bound given by a tower of 2s of height proportional to $\log{(1/ \epsilon)}$). We then give a different construction which improves the bound, even for certain weaker versions of the statement.