Erdős–Stone theorem

Statement for arbitrary non-bipartite graphs

If H is an arbitrary graph whose chromatic number is r > 2, then H is contained in K_r(t) whenever t is at least as large as the largest color class in an r-coloring of H, but it is not contained in the Turán graph T(n,r − 1), as this graph and therefore each of its subgraphs can be colored with r − 1 colors. It follows that the extremal number for H is at least as large as the number of edges in T(n,r − 1), and at most equal to the extremal function for K_r(t); that is,

${\displaystyle \text{ex}(n;H)=\left(\frac{r-2}{r-1}+o(1)\right)(\genfrac{}{}{0ex}{}{n}{2}).}$

For bipartite graphs H, however, the theorem does not give a tight bound on the extremal function. It is known that, when H is bipartite, ex(n; H) = o(n²), and for general bipartite graphs little more is known. See Zarankiewicz problem for more on the extremal functions of bipartite graphs.

Turán density

Another way of describing the Erdős–Stone theorem is using the Turán density of a graph ${\displaystyle H}$, which is defined by ${\displaystyle \pi (H)=\underset{n\to \mathrm{\infty }}{lim}\frac{\text{ex}(n;H)}{(\genfrac{}{}{0ex}{}{n}{2})}}$. This determines the extremal number ${\displaystyle \text{ex}(n;H)}$ up to an additive ${\displaystyle o(n^2)}$ error term. It can also be thought of as follows: given a sequence of graphs ${\displaystyle G_1,G_2,\dots }$, each not containing ${\displaystyle H}$, such that the number of vertices goes to infinity, the Turán density is the maximum possible limit of their edge densities. The Erdős–Stone theorem determines the Turán density for all graphs, showing that any graph ${\displaystyle H}$ with chromatic number ${\displaystyle r>2}$ has a Turán density of

${\displaystyle \pi (H)=\frac{r-2}{r-1}.}$

Proofs

Saturation

One proof of the Erdős–Stone theorem uses an extension of the Kővári–Sós–Turán theorem to hypergraphs, as well as the supersaturation theorem, by creating a corresponding hypergraph for every graph that is ${\displaystyle K_r(t)}$-free and showing that the hypergraph has some bounded number of edges. The Kővári–Sós–Turán says, among other things, that the extremal number of ${\displaystyle K_2(t)}$, the complete bipartite graph with ${\displaystyle t}$ vertices in each part, is at most ${\displaystyle \text{ex}(K_2(t);n)\le C{n}^{2-1/t}}$ for a constant ${\displaystyle C}$. This can be extended to hypergraphs: defining ${\displaystyle K_{s,\dots ,s}^{(r)}}$ to be the ${\displaystyle r}$-partite ${\displaystyle r}$-graph with ${\displaystyle s}$ vertices in each part, then ${\displaystyle \text{ex}(K_{s,\dots ,s}^{(r)},n)\le C{n}^{r-s^{1-r}}}$ for some constant ${\displaystyle C}$.

Now, for a given graph ${\displaystyle H=K_r(t)}$ with ${\displaystyle r>1,s\ge 1}$, and some graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices that does not contain a subgraph isomorphic to ${\displaystyle H}$, we define the ${\displaystyle r}$-graph ${\displaystyle F}$ with the same vertices as ${\displaystyle G}$ and a hyperedge between vertices in ${\displaystyle F}$ if they form a clique in ${\displaystyle G}$. Note that if ${\displaystyle F}$ contains a copy of ${\displaystyle K_{s,\dots ,s}^{(r)}}$, then the original graph ${\displaystyle G}$ contains a copy of ${\displaystyle H}$, as every pair of vertices in distinct parts must have an edge. Thus, ${\displaystyle F}$ contains no copies of ${\displaystyle K_{s,\dots ,s}^{(r)}}$, and so it has ${\displaystyle o(n^r)}$ hyperedges, indicating that there are ${\displaystyle o(n^r)}$ copies of ${\displaystyle K_r}$ in ${\displaystyle G}$. By supersaturation, this means that the edge density of ${\displaystyle G}$ is within ${\displaystyle o(1)}$ of the Turán density of ${\displaystyle K_r}$, which is ${\displaystyle \frac{r-2}{r-1}}$ by Turán's theorem; thus, the edge density is bounded above by ${\displaystyle \frac{r-2}{r-1}+o(1)}$.

On the other hand, we can achieve this bound by taking the Turán graph ${\displaystyle T(n,r-1)}$, which contains no copies of ${\displaystyle K_r(t)}$ but has ${\displaystyle \left(\frac{r-2}{r-1}-o(1)\right)(\genfrac{}{}{0ex}{}{n}{2})}$ edges, showing that this value is the maximum and concluding the proof.

Counting Paths

Another proof of the Erdős–Stone theorem works by generalising the proof of the Kővári–Sós–Turán theorem, counting paths of length two in a high minimum degree subgraph of the original graph ${\displaystyle G}$. This starts with a lemma to find a subgraph with high minimum degree, then a lemma that finds an ${\displaystyle r}$-partite Turán graph given a graph with high minimum degree, and finally the application of both lemmas to prove the Erdős–Stone theorem.

For purposes of notation, let ${\displaystyle V(G)}$ be the set of vertices of a graph ${\displaystyle G}$ and ${\displaystyle e(G)}$ be the number of edges of a graph ${\displaystyle G}$.

The first lemma states the following: consider some real number ${\displaystyle c\in (0,1)}$, let ${\displaystyle \epsilon >0}$ and let ${\displaystyle G}$ be a graph on ${\displaystyle n}$ vertices with ${\displaystyle e(G)}$ edges such that:

${\displaystyle e(G)\ge c\cdot (\genfrac{}{}{0ex}{}{n}{2})}$

Then there is a subgraph ${\displaystyle G^{\prime }}$ of ${\displaystyle G}$ with ${\displaystyle n^{\prime }}$ vertices such that ${\displaystyle n^{\prime }\ge \epsilon n}$ and the minimum degree of ${\displaystyle G^{\prime }}$ is greater than or equal to ${\displaystyle (c-\epsilon )n^{\prime }}$.

To prove this the idea is to continually remove vertices if they have a lower degree than what we want. Formally, consider a series of graphs ${\displaystyle G=G_n\supset G_{n-1}\supset \cdots \supset G_t}$ obtained by doing the following:

1. If there is a vertex ${\displaystyle v_i\in V(G_i)}$ that has degree ${\displaystyle d_{G_i}(v_i)<(c-\epsilon )v(G_i)}$, then define ${\displaystyle G_{i-1}=G_i-v_i}$ (in the case there are multiple, pick an arbitrary vertex).
2. Otherwise, the minimum degree of ${\displaystyle G_i}$ is greater than or equal to ${\displaystyle (c-\epsilon )v(G_i)}$, and therefore the process terminates at ${\displaystyle t=i}$.

To prove that this process ends at some ${\displaystyle t\ge \epsilon n}$, we will use contradiction. Assuming that ${\displaystyle t<\epsilon n}$ the following bounds can be obtained:

${\displaystyle e(G)<\sum _{i=t+1}^n(c-\epsilon )i+(\genfrac{}{}{0ex}{}{t}{2})\le (c-\epsilon )(\genfrac{}{}{0ex}{}{n}{2})+\epsilon (\genfrac{}{}{0ex}{}{n}{2})=c\cdot (\genfrac{}{}{0ex}{}{n}{2})}$

This means that ${\displaystyle e(G)<c\cdot (\genfrac{}{}{0ex}{}{n}{2})}$, which contradicts the initial assumption that ${\displaystyle e(G)\ge c\cdot (\genfrac{}{}{0ex}{}{n}{2})}$. Therefore, the process must terminate at some ${\displaystyle t\ge \epsilon n}$, and the subgraph ${\displaystyle G^{\prime }}$ can be found.

The second lemma states the following: for any ${\displaystyle r,t\in \mathbb{N}}$ and ${\displaystyle \epsilon >0}$, there exists some ${\displaystyle n_0\in \mathbb{N}}$ such that when given a graph ${\displaystyle G}$ with ${\displaystyle n\ge n_0}$ vertices and minimum degree greater than or equal to:

${\displaystyle \left(1-\frac{1}{r}+\epsilon \right)n}$

We can guarantee that the ${\displaystyle (r+1)}$-partite Turán graph with components of size ${\displaystyle t}$ (referred to as ${\displaystyle K_{r+1}(t)}$) is a subgraph of ${\displaystyle G}$.

This can be proved by induction on ${\displaystyle r}$. The base case is equivalent to the Kővári–Sós–Turán theorem. For the inductive step, first find a copy of ${\displaystyle K_r(q)}$ with ${\displaystyle q\ge \frac{t}{\epsilon }}$.

Now, define ${\displaystyle A_1,A_2,\cdots ,A_r}$ the ${\displaystyle r}$ components of ${\displaystyle K_r(q)}$, with the vertices of ${\displaystyle K_r(q)}$ being ${\displaystyle A}$, define ${\displaystyle B=V(G)/A}$ and additionally define:

${\displaystyle X=\bigcap _{i=1}^r\{v\in B:|N(v)\cap A_i|\ge t\}}$

Counting the number of edges between ${\displaystyle A}$ and ${\displaystyle B}$ it can be derived that:

${\displaystyle e(A,B)\le |X|\cdot qr+(|B|-|X|)(q(r-1)+t-1)}$

While the minimum degree condition will yield that:

${\displaystyle e(A,B)\ge \left(1-\frac{1}{r}+\epsilon \right)\cdot n\cdot qr-(qr{)}^2}$

After manipulating these two inequalities, using that ${\displaystyle |B|\le n}$ it can be concluded that:

${\displaystyle \epsilon qrn\le (t-1)n+|X|(q-t+1)+(qr{)}^2}$

Then, since ${\displaystyle q\ge \frac{t}{\epsilon }}$ we can conclude that ${\displaystyle |X|\to \mathrm{\infty }}$ as ${\displaystyle n\to \mathrm{\infty }}$. After this, using the infinite pigeonhole principle it can be concluded that there must be a ${\displaystyle K_{r+1}(t)}$, finishing the induction.

Now, the theorem can be proved with these lemmas. Consider a fixed graph ${\displaystyle H}$ with ${\displaystyle \chi (H)=r+1}$ and a graph ${\displaystyle G}$ with a large enough number of vertices ${\displaystyle n}$ such that:

${\displaystyle e(G)\ge \left(1-\frac{1}{r}+2\epsilon \right)(\genfrac{}{}{0ex}{}{n}{2})}$

Then, by Lemma 1 there exists some subgraph ${\displaystyle G^{\prime }}$ with ${\displaystyle n^{\prime }\ge ϵn}$ vertices with that has minimum degree of at least:

${\displaystyle \left(1-\frac{1}{r}+\epsilon \right)n^{\prime }}$

Now, let ${\displaystyle t}$ be the size of the largest independent set of vertices in ${\displaystyle H}$. By Lemma 2, given a large enough ${\displaystyle \epsilon n}$ (which we can guarantee by increasing ${\displaystyle n}$) we can find some ${\displaystyle K_{r+1}(t)}$ in ${\displaystyle G^{\prime }}$. But then, ${\displaystyle H\subseteq K_{r+1}(t)\subset G^{\prime }\subset G}$, proving the Erdős–Stone theorem.

Quantitative results

Several versions of the theorem have been proved that more precisely characterise the relation of n, r, t and the o(1) term. Define the notation s_r,ε(n) (for 0 < ε < 1/(2(r − 1))) to be the greatest t such that every graph of order n and size

${\displaystyle \left(\frac{r-2}{2(r-1)}+\epsilon \right)n^2}$

contains a K_r(t).

Erdős and Stone proved that

${\displaystyle s_{r,\epsilon }(n)\ge {\left(\underset{r-1}{\underbrace{\log \cdots \log }}n\right)}^{1/2}}$

for n sufficiently large. The correct order of s_r,ε(n) in terms of n was found by Bollobás and Erdős: for any given r and ε there are constants c₁(r, ε) and c₂(r, ε) such that c₁(r, ε) log n < s_r,ε(n) < c₂(r, ε) log n. Chvátal and Szemerédi then determined the nature of the dependence on r and ε, up to a constant:

${\displaystyle \frac{1}{500\log (1/\epsilon )}\log n<s_{r,\epsilon }(n)<\frac{5}{\log (1/\epsilon )}\log n}$ for sufficiently large n.