Understanding Equitable Szemeredi regularity lemma

Question

I understand the proof for Szemeredi's Regularity lemma, but I'm not sure how to find an equitable partition of the vertex set of the graph so that most of the sets are $\epsilon$-regular. Finding an $\epsilon$-regular partition and then making it equitable seems to be the wrong approach since the former property need not be preserved. Can someone explain a way to make the partition equitable?

Answer 1

I don't know about the link provided in comment, but here is the argument in the original Szemerédi article.

For any given equitable partition $P$ into classes $C_0,C_1,\ldots,C_k$ ($C_0$ being the exceptional class, a.k.a the bin), we define the index of $P$ by $$\textrm{Ind}(P)=\frac{1}{k^2}\sum_{s=1}^{k} \sum_{t=s+1}^k d(C_s,C_t)^2$$

It is important to note that $Ind(P) \leq 1$ for any partition.

Then the main lemma goes as follow

Let $G = (V,E)$ be a graph with $n$ vertices. Let $P$ be an equitable partition of $V$ into classes $C_0,C_1,\ldots,C_k$ ($C_0$ being the exceptional class). Let $\varepsilon$ be a positive integer such that $4^k>600\varepsilon^{-5}$ . If more than $\varepsilon k^2$ pairs $(C_s,C_t)$ in $1 \leq s < t \leq k$ are s-irregular then there is an equitable partition $Q$ of $V$ into $1+k4^k$ classes, the cardinality of the exceptional class being at most $$\vert C_0\vert + \frac{n}{4^k}$$ and such that $$\textrm{Ind}(Q)>\textrm{Ind}(P)+\frac{\varepsilon^5}{20}$$

The point is that you don't really look for an $\varepsilon$-regular partition. But you prove that IF your partition is not regular, THEN you can refine the partition increasing the potential function. And each such refinement keep the equitable property because you have some control on the size of the exceptional class.

As long as your partition is not regular, you can iterate, every time increasing the index function by a fixed amount. But the index function is bounded by above by 1, so at one point the iteration must stop, meaning that you must have a regular partition.

Note that this means that the value of $M(\varepsilon)$ in the regularity lemma is quite huge as it is in the order of $4 \uparrow\uparrow\varepsilon^{-5}$, using Knuth's arrow notation, or $4^{4^{\ldots^{4}}}$ with a tower of size $\varepsilon^{-5}$.