Turan and Erdos-Stone

Today we discuss Turan's theorem and its extension the Erdos-Stone theorem, which are fundamental results in extremal combinatorics, from the perspective of Szemeredi regularity.

The extremal number $\text{ex}(n,H)$ is defined to be the maximum number of edges in a graph with $n$ vertices not containing a subgraph isomorphic to $H$. The Erdos-Stone theorem is the following:
\[
\text{ex}(n,H) = \left(1- \frac{1}{\chi(H)-1} \pm o(1)\right) \frac{n^2}{2}.
\]

In other words, for every $H, r$ and $\varepsilon$, such that $\chi(H) = r +1$, there exists $n_0 = n_0(r,H,\varepsilon)$ such that for every $n > n_0$,

\[
\left(1 - \frac{1}{\chi(H)-1} -\varepsilon\right) \frac{n^2}{2} \leq \text{ex}(n,H) \leq \left(1- \frac{1}{\chi(H)-1} +\varepsilon\right) \frac{n^2}{2}.
\]

Turan's theorem is the special case that $H$ is some complete graph. There are many proofs of Erdos-Stone, but I want to show the one using the regularity ideas because it puts the theorem into a wider context and illustrates the power of the regularity lemma and the consequences mentioned above. Additionally, I don't like most of the proofs of Erdos-Stone, but I do like many of the proofs of the special case of Erdos-Stone which goes by the name of Turan's theorem. Regularity will let us bootstrap Turan to Erdos-Stone.

First, let's do Turan. This has so many beautiful proofs that we are spoiled for choice. We will mention the Turan graph $T_r(n)$, which is the graph formed by partition $n$ vertices into $r$ subsets with sizes as equal as possible and connecting two vertices by an edge if and only if they belong to different subsets.

Proof 1: (Erdos)
Take the vertex $v$ of largest degree. Consider the set $A$ of vertices not adjacent to $v$ and the set $B$ of vertices adjacent to $v$.

Now, delete all edges within $A$ and draw all edges between $A$ and $B$. This increases the number of edges by our maximality assumption and keeps the graph $K_{r+1}$-free. Now, $B$ is $K_r$-free, so the same argument can be repeated on $B$.

Repeating this argument eventually produces a graph in the same form as a Turán graph, which is a collection of independent sets, with edges between each two vertices from different independent sets. A simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible. $\blacksquare$

Proof 2: Given a $K_{r+1}$-free graph, apply the following steps:
 

• If $u, v$ are non-adjacent vertices and $u$ has a higher degree than $v$, replace $v$ with a copy of $u$. Repeat this until all non-adjacent vertices have the same degree.
• If $u, v, w$ are vertices with $u, v$ and $v, w$ non-adjacent but $u, w$ adjacent, then replace both $u$ and $w$ with copies of $v$.

All of these steps keep the graph $K_{r+1}$-free while increasing the number of edges.

Now, non-adjacency forms an equivalence relation. The equivalence classes imply that any maximal graph has the same form as a Turán graph. As in the maximal degree vertex proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible. $\blacksquare$

We now prove Erdos-Stone:

The lower bound is very easy; the Turán graph $T_r(n)$ is $r$-colorable, hence it is $H$-free (recall that we assume $\chi(H) = r+1$). It is now easy to check (do this) that
\[
e(T_r(n)) = t_r(n) \geq \left(1- \frac{1}{r} -o(1)\right) \frac{n^2}{2},
\]
so we are just left with proving the upper bound.

We note that it is clearly enough to prove the upper bound only for $K^v_{r+1}$ (which is the $v$-blowup\footnote{The $v$-blowup means replacing each vertex of $K_{r+1}$ by $v$ vertices, and connecting all possible edges between different parts.} of $K_{r+1}$) as if $\chi(H) = r +1$, then $H$ is a subgraph of $K^v_{r+1}$ for $|v| = |V(H)|$.

Theorem For every $b,r$ and $\delta > 0$ there exists $n_0(\delta,r,b)$ so that if $G$ is a graph on at least $n_0$ vertices with
\[
\left(1- \frac{1}{r} +\delta\right) \frac{n^2}{2}
\]
edges, then $G$ contains a copy of $K^b_{r+1}$ (a $b$-blowup of $K_{r+1}$).


Proof Define $\varepsilon = \varepsilon(\delta/8,rb)$ and $c = c(\delta/8,rb)$ and apply the Regularity Lemma with parameter $\min(\varepsilon, \delta/8)$. We get an $\varepsilon$-regular partition into $k$ sets $V_1,\dots, V_k$ where $\frac{1}{\varepsilon} \leq k \leq T(\varepsilon)$ and therefore $|V_i| \geq \frac{n}{T(\varepsilon)}$.

Remove the following edges from the graph:
 

• Edges within $V_i$. There are at most $\frac{\delta n^2}{8}$ such edges.
• Edges connecting $V_i$ to $V_j$ where $d(V_i,V_j) < \delta/8$. There are at most $\frac{\delta n^2}{4}$ such edges.
•  Edges connecting $V_i$ to $V_j$ where $(V_i,V_j)$ is not $\varepsilon$-regular. There are at most $\frac{\delta n^2}{8}$ such edges.

All in all, we removed fewer than $\frac{\delta n^2}{2}$ edges.

Therefore, $G$ still has at least
\[
\left(1 - \frac{1}{r}\right) \frac{n^2}{2}
\]
edges, so by Turán’s Theorem, $G$ contains a copy of $K_{r+1}$.

This $K_{r+1}$ must have a single vertex in each of $r+1$ sets $V_1, \dots, V_{r+1}$ such that all pairs $(V_i, V_j)$ are $\varepsilon$-regular and satisfy $d(V_i,V_j) \geq \delta/8$.

We have $r+1$ sets of size at least $\frac{n}{T(\varepsilon)}$ where the density between them is at least $\delta/8$, and every one of them is $\varepsilon(\delta/8,rb)$-regular.

The graph $K^b_{r+1}$ is an $(r + 1)$-colorable graph with maximum degree $rb$. Hence, the Embedding Lemma implies that $V_1, \dots, V_{r+1}$ contain a copy of $K^b_{r+1}$ if
\[
|V_i| \geq c(\delta/8, rb) \cdot (r+1)b.
\]
So to conclude the proof, we set
\[
n_0 = c(\delta/8,rb) \cdot b(r+1) \cdot T\left(\min\left\{\delta/8, \varepsilon(\delta/8,rb)\right\}\right).
\]
Since $n_0$ depends only on $\delta$, $r$, and $b$, the proof is complete. $blacksquare$