A Wowzer-type lower bound for the strong regularity lemma

Author： Kalyanasundaram Subrahmanyam Shapira Asaf

ISSN： 0024-6115

Source： Proceedings of the London Mathematical Society, Vol.106, Iss.3, 2013-03, pp. : 621-649

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The regularity lemma of Szemerdi 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 et al. (Efficient testing of large graphs, Combinatorica 20 (2000) 451476) 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 guaranteed only 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.