Combinatorics Seminar
When: Sunday, April 15, 10am
Where: Schreiber 309
Speaker: Asaf Shapira, Tel Aviv University
Title: A Wowzer Type Lower Bound for the Strong Regularity
Lemma
Abstract:
The regularity lemma of Szemeredi 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 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 any such partition of H must have a number of parts given by a
Wowzer-type function.
Joint work with S. Kalyanasundaram.