A Wowzer-type lower bound for the strong regularity lemma

Abstract

The regularity lemma of Szemerédi asserts that one can partition every graph into a bounded number of quasi-random bipartite graphs.In some applications however, one would like to have a strong control on how quasi-random these bipartite graphs are.Alon, Fischer, Krivelevich and Szegedy obtained a powerful variant of the regularity lemma, which allows one to have an arbitrary control on this measure of quasi-randomness.However, their proof only guaranteed to produce a partition where the number of parts is given by the Wowzer function, which is the iterated version of the Tower function.We show here that a bound of this type is unavoidable by constructing a graph H, with the property that even if one wants a very mild control on the quasi-randomness of a regular partition, then the number of parts in any such partition of H must be given by a Wowzer-type function.

Locations

• Proceedings of the London Mathematical Society - View
• arXiv (Cornell University) - View - PDF
• DataCite API - View