In Szemerédi's Regularity Lemma, how many blocks are in the partition?

Question

Suppose $G = (V,E)$ is a directed graph. For sets $A$ and $B$ of vertices of $G$, let $d(A,B) = |(A \times B) \cap E| / (|A||B|)$ denote the edge density between $A$ and $B$, and say that the pair $A,B$ is $\epsilon$-regular if $$ |d(X,Y) - d(A,B)| \lt \epsilon $$ whenever $X \subseteq A, Y \subseteq B$, $X$ contains more than an $\epsilon$-fraction of the vertices of $A$, and $Y$ contains more than an $\epsilon$-fraction of the vertices of $B$. An equipartition is a partition with the sizes of blocks of the partition differing pairwise by at most 1.

Szemerédi's Regularity Lemma can then be stated as:

For any $\epsilon > 0$, there exists $M(\epsilon)$ such that for every graph $G=(V,E)$ there is some $k\le M(\epsilon)$ and an equipartition $V = V_1 \cup \ldots \cup V_k$ in which each block $V_i$ contains at most $\lceil \epsilon |V|\rceil$ vertices, and having the property that for all but at most $\epsilon k^2$ of the pairs $(i,j)$, the pair $V_i, V_j$ is $\epsilon$-regular.

Do we have any bounds or asymptotics for how $M(\epsilon)$ behaves as a function of $\epsilon$?

I vaguely recall having read a comment that $M(\epsilon)$ is likely to be extremely large, making the Regularity Lemma only useful for truly large graphs. But I have not been able to find this assessment again, so a pointer would be appreciated. (I did check Terence Tao's exposition again, and some of the more obvious references.)

Answer 1

In addition to Gowers' breakthrough paper, a recent paper addressing the bounds in Szemerédi's regularity lemma, and its weak and strong variants is:

D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), 1191-1256.

It is shown that the bound on the number of parts for Szemer\'edi's regularity lemma grows as at least a tower of $2$'s of height $\Omega(\epsilon^{-1})$, for the Frieze-Kannan weak regularity it grows as $2^{\Theta(\epsilon^{-2})}$, and for the strong regularity lemma of Alon, Fischer, Krivelevich, and Szegedy it grows as a wowzer in a power of $1/\epsilon$. The wowzer function is the next function in the Ackermann hierarchy after the tower function.

Update (April 2014): Moshkovitz and Shapira recently gave a simple proof of a bound which is a tower of height a power of $1/\epsilon$ in the paper entitled:

A Short Proof of Gowers' Lower Bound for the Regularity Lemma.

Laszlo Miklos Lovasz and I recently give a bound on the tower height in a version of Szemer\'edi's regularity lemma which is tight up to an absolute constant factor in the paper entitled:

A tight lower bound for Szemerédi's regularity lemma.

Answer 2

This is addressed in Gowers' paper:

T. Gowers, Lower bounds of tower type for Szemerédi's uniformity lemma. Geom. Funct. Anal. 7 (1997), no. 2, 322–337.

In particular, the $k$ is a tower of 2's of height proportional to $\epsilon^{-5}$.

Answer 3

As Mark Lewko points out, the bound on the original lemma is so huge as to be impractical. However, if we weaken the conditions of the lemma slightly, to produce the Weak Regularity Lemma, we get a much more practical number of classes-- merely exponential in epsilon. This was introduced by Frieze and Kannan in 1996. In that original paper, the lemma is just a lemma, and hard to extract from the context of the (very interesting) algorithmic work the authors are doing. Instead, I would look at "Large Networks and Graph Limits" by Lovasz. The description of the Weak Regularity Lemma is in section 9.1.2. This book also contains descriptions of large special classes of graphs for which the bound is merely polynomial in epsilon. Look in section 13.4 for one of these.

I don't know if the weak version suffices for your problem, of course.