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

Szemerédi's well-known regularity lemma states that every graph allows a partition of its vertex set into \(K\) parts of almost equal size such that edges between most pairs of the partition are pseudorandomly distributed. The number \(K\) does not depend on the vertex number, but increases with increasing \(1/\varepsilon\), where \(\varepsilon\), the desired accuracy, is a number between 0 and 1. It is known that a tower of 2's of height proportional to \(\varepsilon^{-5}\) is an upper bound of this \(K\). In the present paper an example is given showing that a tower of 2's of height proportional to \(\log(1/\varepsilon)\) is a lower bound for \(K\). This result is improved and modified, even for certain weaker versions of the lemma, by a second example.