Lower bounds of tower type for Szemerédi’s uniformity lemma. (English) Zbl 0876.05053
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.
Reviewer: E.Prisner (Clemson)
MSC:
05C35 | Extremal problems in graph theory |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05C80 | Random graphs (graph-theoretic aspects) |