$$

Szemerédi’s regularity lemma tells us that we can split a graph into $O(1)$ equal parts $V=V_1\cup \dots \cup V_M$ such that the subgraphs between (almost) each pair of parts $(V_i,V_j)$ are “homogenous”: the edge densities between any two large subsets $A\subseteq V_i$ and $B\subseteq V_j$ are all roughly the same.

In other words, for each such pair $(V_i,V_j)$, it’s a bit as if each edge $e\in V_i\times V_j$ were included at random with some fixed probability $d(V_i,V_j)$, the edge density between $V_i$ and $V_j$. If the edges were actually drawn at random in this way (and ignoring the fact that this is only true for almost all pairs), then we could say lots of cool things about the graph!

For example, we could easily get an estimate on the number of triangles: for every triple $(V_i,V_j,V_k)$ of parts (not necessarily distinct), the fraction of triples $(u,v,w)\in V_i\times V_j\times V_k$ that are triangles would be very close to the product of the densities $d(V_i,V_j)d(V_i,V_k)d(V_j,V_k)$. And in particular, whenever this product of densities is $\ne 0$, you’d get $\mathrm{\Omega }(n^3)$ triangles, because the parts all have size $\mathrm{\Omega }(n)$. So either the graph has no triangles at all, or it has lots of them; there’s no in-between!

The graph counting lemma and the reduced graph realize those two dreams.

Graph counting lemma

We’ll first show that regularity allows us to find many triangles, then generalize to counting the occurrences of any constant-size graph.

Finding triangles

Above, we argued that if the edges between three parts $X,Y,Z$ were drawn at random, then there should be roughly $d(X,Y)d(X,Z)d(Y,Z)|X||Y||Z|$ triangles. Let’s show that we get roughly that many triangles as long as $(X,Y)$, $(X,Z)$ and $(Y,Z)$ are $ϵ$-regular: as long as the densities $d(X,Y),d(X,Z)$ are $\ge 2ϵ$, then we have

$$\ge (1-2ϵ)(d(X,Y)-ϵ)(d(X,Z)-ϵ)(d(Y,Z)-ϵ)|X||Y||Z|$$

triangles.

We’ll first start by finding a bunch of wedges starting from $X$: vertices $x\in X$ that have edges $(x,y)$ and $(x,z)$ for many $y\in Y$ and $z\in Z$. Then we’ll complete those wedges to triangles by finding edges $(y,z)$ for many of those wedges.

Formally, at most an $ϵ$ fraction of vertices $x\in X$ can be linked to less than a $d(X,Y)-ϵ$ fraction of $Y$ (and similarly for $Z$): otherwise, those poorly-connected vertices $x$ would form a large subset $X^{\prime }\subseteq X$ for which the density $d(X^{\prime },Y)$ is abnormally low. By a union bound, this means that a $1-2ϵ$ fraction of vertices $x\in X$ are connected to both a $d(X,Y)-ϵ$ fraction of $Y$ and a $d(X,Z)-ϵ$ fraction of $Z$.

Let’s name those fractions $Y_x$ and $Z_x$. Since $d(X,Y),d(X,Z)\ge 2ϵ$ these fractions $Y_x,Z_x$ are big enough for regularity between $Y$ and $Z$ to apply, so the density between $Y_x,Z_x$ is at least $d(Y,Z)-ϵ$, and each edge between $Y_x$ and $Z_x$ gives us a triangle. So in total, we have

$$\ge \underset{\text{\# good }x}{\underbrace{(1-2ϵ)|X|}}\cdot \underset{|Y_x|}{\underbrace{(d(X,Y)-ϵ)|Y|}}\cdot \underset{|Z_x|}{\underbrace{(d(X,Z)-ϵ)|Z|}}\cdot \underset{d(Y_x,Z_x)}{\underbrace{(d(Y,Z)-ϵ)}}$$

triangles.

General case

Informally, for any fixed graph $H$, the number of copies of $H$ within $G$ that “lie within the regular parts” is roughly the number we’d expect given the densities between the parts.

Lemma

Let $H$ be a graph over $[k]$ and let $ϵ>0$. Let $V_1,\dots ,V_k$ be a partition such that $(V_i,V_j)$ is $ϵ$-regular whenever $(i,j)$ is an edge in $H$. Then, the number of labeled copies¹ of $H$ is

$$(\prod _{(i,j)\in E(H)}d(V_i,V_j)\pm ϵ\cdot e(H))\prod _{i=1}^k|V_k|.$$

Note: the factor $e(H)$ in the error comes from the fact that the $ϵ$-regularity is applied $e(H)$ times.

Proof

TODO (it was a beautiful telescoping sum)

Reduced graph

TODO: rewrite

For any $ϵ$, Szemerédi’s regularity lemma can split any graph into $O_{ϵ}(1)$ equal parts $V=V_1,\dots ,V_K$ such that for all but an $ϵ$ fraction of the pairs $(i,j)\in [K{]}^2$, $(V_i,V_j)$ is $ϵ$-regular: the density between large enough subsets of them is roughly what we would expect it to be.

The idea of the “reduced graph” is to make a graph over the parts $[K]$: we will connect $(i,j)$ iff $(V_i,V_j)$ is $ϵ$-regular and the density $d(V_i,V_j)$ is above some threshold $\alpha$.

Applications

This technique allows us (among other things) to reprove some known results very easily.

Theorem (Erdős-Stone-Simonovits)

Any $H$-free graph over $n$ vertices has at most $(1-\frac{1}{\chi (H)-1}+o(1))\frac{n^2}{2}$ edges.²

Proof (sketch)

Let $t:=|H|$. Let $H^{\prime }$ be the complete $\chi (H)$-bipartite graph with parts of size $t$. Clearly, $H^{\prime }$ contains $H$. We will show that if $G$ has too many edges, it must contain a copy of $H^{\prime }$.

Suppose $G$ has $\ge (1-\frac{1}{\chi (H)-1}+2\alpha )\frac{n^2}{2}$ edges. Apply Szemerédi’s regularity lemma to $G$ with small enough $ϵ$ (to be set later). Consider the reduced graph $R$ with threshold $\alpha$. As long as $ϵ$ is small enough as a function of $\alpha$, this reduced graph will have at least $(1-\frac{1}{\chi (H)-1}+\mathrm{\Omega }(1))\frac{K^2}{2}$ edges. So by Turán’s theorem, $R$ must contain a copy of $K_{\chi (H)}$. Then, apply the graph counting lemma to the corresponding parts of $G$ to find ${\mathrm{\Omega }}_{ϵ}(n^{\chi (H)t})$ copies of $H^{\prime }$ in $G$.³ We only needed one.

1. This means copies are ordered, and I think that technically, mapping two nodes of $H$ to the same node in $G$ is allowed (but this is usually not a problem since such mappings are comparatively rare). ↩

2. Here, $\chi (H)$ is the coloring number of $H$, i.e. the least $k$ such that it can be embedded into a $k$-partite graph. ↩

3. For this to work, we needed $ϵ$ to be enough to survivec the $e(H^{\prime })$ factor blow up coming from the $e(H^{\prime })$ applications of regularity in the proof of the counting lemma. ↩