A Wowzer-type lower bound for the strong regularity lemma
A Wowzer-type lower bound for the strong regularity lemma
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, Fischer, Krivelevich and Szegedy obtained a powerful variant of the regularity lemma, …