Szemeredi’s Regularity Lemma

The goal is to partition a dense graph into few pseudorandom parts.

Edge density ${d(X,Y) =\frac{e(X,Y)}{|X||Y|}.}$

${\varepsilon}$ -regularity: For ${\varepsilon>0,}$ a pair of vertex sets ${X}$ and ${Y}$ is called ${\varepsilon}$ -regular, if for all subsets ${A \subseteq X, B \subseteq Y}$ satisfying ${|A| \geq \varepsilon|X|,|B| \geq \varepsilon|Y|,}$ we have ${|d(X, Y)-d(A, B)| \leq \varepsilon}$

Regular partition: A partition of ${V}$ into ${k}$ sets ${\mathcal{P}=\left\{V_{1}, \ldots, V_{k}\right\}}$ is called an ${\varepsilon}$ -regular partition if

$\displaystyle \sum_{\left(V_{i}, V_{j}\right) \text { not } \varepsilon \text { -regular }}\left|V_{i} \| V_{j}\right| \leq \varepsilon|V(G)|^{2}$

A way to achieve such partitions is to take: ${\mathcal{P}=\left\{V_0, V_{1}, \ldots, V_{k}\right\}}$ with
1. ${\left|V_{0}\right| \leq \epsilon|V| .}$ This set is called the exceptional set.
2. ${\left|V_{1}\right|=\left|V_{2}\right|=\cdots=\left|V_k\right|}$
3. All but at most ${\varepsilon k^2 }$ of the pairs ${\left(V_{i}, V_{j}\right), 1 \leq i, j \leq k}$ are ${\epsilon}$ -regular.

Szemeredi’s regularity lemma:

For every ${\varepsilon>0}$ and positive integer ${m}$ , there are integers ${M(\varepsilon, m), N(\varepsilon, m)}$ such that any graph ${G}$ with at least ${N(\varepsilon, m)}$ vertices, there is a ${k}$ in the range ${m \leq k \leq M(\varepsilon, m)}$ and an ${\varepsilon}$ -regular partition of the vertex set of ${G}$ into ${k}$ sets.

Proof (Energy Increment): Start with an arbitrary partition and if we find irregular subsets between a pair of vertex sets, we refine the partition further.

Consider the “energy” of a partition ${f\left(V_{0}, \ldots, V_{k}\right)=\frac{1}{|V|^2} \sum_{1 \leq i<j \leq k} |V_i||V_j|d\left(V_{i}, V_{j}\right)^{2}}$

A trivial bound on the this function is ${f\left(V_{0}, \ldots, V_{k}\right) \le 1}$ by noting that ${0\le d(X,Y) \le 1.}$

Find a pair of irregular subsets between for each pair ${V_i, V_i}$ . Refining the partition by using these irregular witnesses, we split each vertex set ${V_i}$ into atmost ${2^k}$ parts.

The resulting sets may not be of equal size- so we further split the sets into equal size sets and if any parts are left, we add them to the exceptional set.

Now we observe that
1. the energy increases with any refinement.
2. And infact, the above refinements increase the energy by atleast by some fixed amount.
So by the upper bound on the energy, in finite number of iterations, we reach a regular partition.

The fact that it increases can be seen by Cauchy’s inequality and that it increases by some fixed amount in out iterations (by ${\varepsilon^5}$ ) can be seen by the defect version of Cauchy Schwarz- (Basically amount to using that ${E(X^2) -(E(X))^2 = E((X-E(X))^2)}$ is the variance of ${X}$ ; and irregular pairs exactly corresponds to variation from expected value)

Energy Increment under refinements: Let ${X, Y \subseteq V}$ be two disjoint sets. If ${\mathcal{A}=\left\{X_{1}, X_{2}, \ldots, X_{h}\right\}}$ and ${\mathcal{B}=}$ ${\left\{Y_{1}, Y_{2}, \ldots, Y_{h^{\prime}}\right\}}$ are partitions of ${X}$ and ${Y}$ respectively, then:

$\displaystyle f(\mathcal{A}, \mathcal{B}) \geq f(X,Y)$

$\displaystyle \begin{aligned} f(\mathcal{A}, \mathcal{B}) &=\sum_{i, j} \frac{|X_i||Y_j|}{|V|^2}d\left(X_{i}, Y_{j}\right)^2 \\ &=\sum_{i, j} \frac{e\left(X_{i}, Y_{j}\right)^{2}}{|V|^{2}\left|X_{i} \| Y_{j}\right|} \\ & \geq \frac{\left(\sum_{i, j} e\left(X_{i}, Y_{j}\right)\right)^{2}}{|V|^{2} \sum_{i, j}\left|X_{i} \| Y_{j}\right|}\\ &=\frac{e(X, Y)^{2}}{|V|^{2}|X||Y|}\\ &=f(X, Y) \end{aligned}$

We used Cauchy-Schwarz in the form:

$\displaystyle \sum \frac{a_{i}^{2}}{b_{i}} \geq \frac{\left(\sum a_{i}\right)^{2}}{\sum b_{i}}$

Lower bounds on the increment: Let ${X, Y \subseteq V}$ be two disjoint sets such that ${(X, Y)}$ is not ${\epsilon}$ -regular, for a given ${\epsilon>0,}$ then there exists partitions ${\mathcal{X}=\left(X_{1}, X_{2}\right), \mathcal{Y}=\left(Y_{1}, Y_{2}\right)}$ of ${X}$ and ${Y}$ respectively such that: