A Wowzer‐type lower bound for the strong regularity lemma. Issue 3 (8th October 2012)

• Record Type: Journal Article
• Authors: Kalyanasundaram, Subrahmanyam; Shapira, Asaf
• Is Part Of: Proceedings of the London Mathematical Society. Volume 106:Issue 3(2012:Mar.)
• Page Start: 621
• Page End: 649
• Publication Date: 2012-10-08
• Subjects: Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms/pds045
• Languages: English
• ISSNs: 0024-6115

Abstract

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 et al. ('Efficient testing of large graphs', Combinatorica 20 (2000) 451–476) 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.