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



In Szemerédi's Regularity Lemma, how many blocks are in the partition?
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.


