A Wowzer Type Lower Bound for the Strong Regularity Lemma

Details A Wowzer Type Lower Bound for the Strong Regularity Lemma A Wowzer Type Lower Bound for the Strong Regularity Lemma

2011-07-25

arxiv.org/abs/1107.4896v1

Mathematics

Combinatorics

Scientific paper

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 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 any such partition of H must have a number of parts given by a Wowzer-type function.

Affiliated with

Also associated with

No associations

Rating

A Wowzer Type Lower Bound for the Strong Regularity Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Wowzer Type Lower Bound for the Strong Regularity Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Wowzer Type Lower Bound for the Strong Regularity Lemma will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-572351