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

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.)

-

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}$.

-
Thanks! It seems I'd read a reference to this in the survey paper: János Komlós, Ali Shokoufandeh, Miklós Simonovits, Endre Szemerédi, The Regularity Lemma and Its Applications in Graph Theory, STACS 2002, LNCS 2292. dx.doi.org/10.1007/3-540-45878-6_3 –  András Salamon Apr 17 at 11:09

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.

-
Thanks, that is a useful set of pointers! –  András Salamon Apr 17 at 10:51
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.