Kalyanasundaram, Subrahmanyam and Shapira, A
(2013)
A Wowzertype lower bound for the strong regularity lemma.
Proceedings of the London Mathematical Society, 106 (3).
pp. 621649.
ISSN 00246115
Full text not available from this repository.
(
Request a copy)
Abstract
he regularity lemma of Szemerédi asserts that one can partition every graph into a bounded number of quasirandom bipartite graphs. In some applications however, one would like to have a strong control on how quasirandom 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 quasirandomness. 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 quasirandomness of a regular partition, then the number of parts in any such partition of H must be given by a Wowzertype function.
[error in script]
Actions (login required)

View Item 