Skip to main content

Math 426/529: Extremal Combinatorics

Jonathan A. Noel

Section 3.3 Turán Density of General Graphs

So far, we have only considered extremal numbers of complete graphs, which begs the question of how extremal numbers behave for graphs in general. In this section, we will see that, for most graphs, it is possible to pin down the extremal number, up to some “lower order fluctuations.”
described in detail following the image
“Erdős stone.”
An independent set in a graph \(G\) is a set \(S\subseteq V(G)\) such that there does not exist \(u,v\in S\) such that \(uv\in E(G)\text{.}\) One of the keys to computing the extremal numbers of complete graphs in the previous section was that a complete graph on \(r\) vertices cannot be decomposed into fewer than \(r\) independent sets. This property turns out to be important for estimating extremal numbers in general. Given a graph \(H\text{,}\) the chromatic number of \(H\text{,}\) denoted \(\chi(H)\text{,}\) is the minimum \(k\) such that \(V(H)\) can be partitioned into \(k\) independent sets; in other words, it is the smallest \(k\) such that the vertices of \(H\) can be coloured with \(k\) colours such that the endpoints of each edge are coloured differently. See Figure 3.3.11 for an example.

Example 3.3.1.

For any graph \(H\text{,}\) a complete \((\chi(H)-1)\)-partite graph \(G\) cannot contain a copy of \(H\text{.}\) Therefore,
\begin{equation*} \ex(n,H) \geq \ex\left(n,K_{\chi(H)}\right) \end{equation*}
for all \(n\text{.}\) Asymptotically speaking, this tells us that
\begin{equation*} \ex(n,H)\geq \left(\frac{\chi(H)-2}{\chi(H)-1} + o(1)\right)\frac{n^2}{2}\text{.} \end{equation*}

Definition 3.3.2.

For \(k\geq1\text{,}\) the \(k\)-vertex path is the graph Pk with \(k\) vertices \(v_1,\dots,v_k\) such that \(v_iv_{i+1}\in E(P_k)\) for \(1\leq i\leq k-1\text{.}\)

Definition 3.3.3.

For \(k\geq3\text{,}\) the \(k\)-cycle is the graph Ck with \(k\) vertices \(v_1,\dots,v_k\) such that \(E(P_k)\subseteq E(C_k)\) and \(v_1v_k\in E(C_k)\text{.}\) That is, the vertices are joined in a “cyclic” fashion.
Figure 3.3.4. The graphs \(P_1,P_2,P_3\) and \(P_4\text{.}\)
Figure 3.3.5. The graphs \(C_3,C_4,C_5\) and \(C_6\text{.}\)

Example 3.3.6.

Consider \(C_5\text{.}\) It is easy to see that \(\chi(C_5)=3\text{.}\) For \(n=3\text{,}\) it is clear that \(\ex(3,C_5)=3 > 2= \ex(3,K_3)\text{;}\) see Exercise 16 in Section 3.6. Thus, the bound in Example 3.3.1 may not be tight, at least for small values of \(n\text{.}\)

Example 3.3.7.

Let \(H\) be a graph with the property that \(\chi(H-e) = \chi(H)\) for every edge \(e\) of \(H\text{.}\) For a concrete example, one could take \(H\) to be a complete \(k\)-partite graph in which every part has at least two elements. Let \(G\) be a graph obtained from a complete \((\chi(H)-1)\)-partite graph by adding a single edge within one of the parts. Then the vertices of the graph \(G\) can be coloured with \(\chi(H)-1\) colours in such a way that only one edge is monochromatic; thus, \(G\) cannot contain any copy of \(H\text{.}\) Therefore, for any \(n\text{,}\) we have that
\begin{equation*} \ex(n,H) \geq \ex\left(n,K_{\chi(H)}\right)+1\text{.} \end{equation*}
So, for any graph \(H\) of this type, the lower bound in Example 3.3.6 is never tight.
Examples 3.3.6 and Example 3.3.7 suggest that it may be tricky to determine the exact extremal number of \(H\) for all values of \(n\text{.}\) For each value of \(n\text{,}\) the exact structure of the extremal graphs \(G\) on \(n\) vertices may depend on the idiosyncrasies of the graph \(H\) that we are forbidding. However, what we will show is that, if all that we want to determine is the “rough” asymptotics of \(\ex(n,H)\) (relative to \(n^2\)), then the fine details of the extremal constructions do not make a significant difference.

Definition 3.3.8.

For each graph \(H\text{,}\) define the Turan density of \(H\) to be
\begin{equation*} \pi(H):=\lim_{n\to\infty} \frac{\ex(n,H)}{\binom{n}{2}}\text{.} \end{equation*}
Of course, if we are defining \(\pi(H)\) in terms of a limit, then the definition only makes sense if that limit exists.

Proof.

Remarkably, Erdős and Stone [103] exactly determined the Turán density of every graph.
Figure 3.3.11. The Petersen graph \(P\) has chromatic number three. By the Erdős–Stone Theorem, \(\ex(n,P) = (1+o(1))\frac{n^2}{4}\text{.}\)
We divide the proof of this theorem into two lemmas. The first is a simple statement for converting a graph with large average degree into a graph with large minimum degree without deleting too many vertices.

Proof.

Initialize \(G_0:=G\text{.}\) For \(i\geq1\text{,}\) let \(v_i\) be a vertex of \(V(G_{i-1})\) of minimum degree in \(G_i\) and define \(G_i\) to be \(G_{i-1} - v_i\text{.}\) We terminate this process at the first index \(i\) such that
\begin{equation*} \delta(G_i)\geq \left(\alpha-\gamma\right)(|V(G_i)|-1)\text{.} \end{equation*}
Note that this condition is eventually satisfied since the graph \(G_{n-1}\) has only one vertex, and so both sides of the above inequality are zero. Therefore, the termination condition is well-defined.
Now, by construction, for any \(i\geq1\) for which \(G_i\) is defined, it holds that
\begin{equation*} |E(G_{i-1})| = |E(G_i)|+\delta(G_{i-1})\text{.} \end{equation*}
Thus,
\begin{equation*} |E(G)| = |E(G_i)| + \sum_{j=0}^{i-1}\delta(G_j)\text{.} \end{equation*}
If the process does not terminate before constructing \(G_i\text{,}\) then we must have \(\delta(G_j) \lt (\alpha - \gamma)(|V(G_j)|-1)\) for all \(0\leq j\leq i-1\text{.}\) Therefore,
\begin{equation*} |E(G)|\lt |E(G_i)| + \sum_{j=0}^{i-1}(\alpha - \gamma)(|V(G_j)|-1) \end{equation*}
\begin{equation*} \leq \binom{n-i}{2} + (\alpha-\gamma)\sum_{j=0}^{i-1}(n-1-j) = \binom{n-i}{2} + (\alpha - \gamma)\frac{i(2n-i-1)}{2} \end{equation*}
\begin{equation*} = \binom{n-i}{2}+ (\alpha-\gamma)\left(\binom{n}{2}-\binom{n-i}{2}\right)\text{.} \end{equation*}
Combining this with the hypothesis on \(G\) and doing a bit of re-arranging, we get that
\begin{equation*} \gamma\binom{n}{2}\leq (1-\alpha+\gamma)\binom{n-i}{2}\text{.} \end{equation*}
Therefore, for any \(i\) such that \(G_i\) is defined, we have
\begin{equation*} \gamma(n-1)^2\lt (1-\alpha+\gamma)(n-i)^2 \end{equation*}
\begin{equation*} \Longrightarrow i \lt n - \sqrt{\frac{\gamma}{1-\alpha+\gamma}}(n-1) \leq \left(1-\sqrt{\frac{\gamma}{1-\alpha+\gamma}}\right)n + 1\text{.} \end{equation*}
Thus, when the process terminates, the number of vertices remaining is at least \(n\cdot \sqrt{\frac{\gamma}{1-\alpha+\gamma}}\text{.}\) This completes the proof.
The next lemma says that any graph with sufficiently large minimum degree contains a complete \(r\)-partite graph in which every part has cardinality \(t\text{.}\)

Proof.

Define \(t_r:=t\) and, for \(1\leq s\leq r-1\text{,}\) let \(t_s:=\lceil (2/\varepsilon) t_{s+1}\rceil\text{.}\) What we will prove is that, for all \(1\leq s\leq r\text{,}\) the graph \(G\) contains a complete \(s\)-partite graph in which each part has cardinality at least \(t_s\text{.}\) The result will then follow by setting \(s=r\text{.}\) We proceed by induction on \(s\) where, in the base case \(s=1\text{,}\) we simply select any set of at least \(t_1\approx (2/\varepsilon)^{r-1} t\) vertices in \(G\text{.}\)
Now, for \(s\geq2\text{,}\) let \(B_1,\dots,B_{s-1}\) be the parts of a complete \((s-1)\)-partite graph in \(G\) with parts of size exactly \(t_{s-1}\text{.}\) Define \(B:=\bigcup_{i=1}^{s-1}B_i\) and \(U:=V(G)\setminus B\text{.}\) Define
\begin{equation*} W:=\left\{u\in U: |N(u)\cap B_i|\geq t_s\text{ for all } 1\leq i\leq s-1\right\}\text{.} \end{equation*}
We want to prove that the set \(W\) is rather large. The way that we will do this is by “double counting” the non-edges from \(U\) to \(B\text{.}\) First of all, each vertex of \(U\setminus W\) has more than
\begin{equation*} t_{s-1}-t_s \geq \left(1-\frac{\varepsilon}{2}\right)t_{s-1} \end{equation*}
non-neighbours in \(B\text{.}\) Thus, the number of non-edges between \(U\) and \(B\) is greater than
\begin{equation*} |U\setminus W|\left(1-\frac{\varepsilon}{2}\right)t_{s-1}= (|V(G)| - |B| - |W|)\left(1-\frac{\varepsilon}{2}\right)t_{s-1}\text{.} \end{equation*}
On the other hand, by the minimum degree condition, each vertex in \(B\) is only incident to at most \(\left(\frac{1}{r-1} -\varepsilon\right)(|V(G)|-1)\) non-edges. Thus, the number of non-edges between \(U\) and \(B\) is at most
\begin{equation*} |B|\left(\frac{1}{r-1} -\varepsilon\right)(|V(G)|-1) \lt t_{s-1}\left(1- \varepsilon(r-1)\right)|V(G)|\text{.} \end{equation*}
Putting this together, we get
\begin{equation*} (|V(G)| - |B| - |W|)\left(1-\frac{\varepsilon}{2}\right)t_{s-1} \lt t_{s-1}\left(1- \varepsilon(r-1)\right)|V(G)| \end{equation*}
which implies that
\begin{equation*} |W|\left(1-\frac{\varepsilon}{2}\right) > \varepsilon\cdot (r-(3/2))\cdot |V(G)| - (r-1)t_{s-1}\text{.} \end{equation*}
By letting \(|V(G)|\) be sufficiently large, we get that
\begin{equation*} |W| > \binom{t_{s-1}}{t_s}^{s-1}(t_s-1)\text{.} \end{equation*}
The number of ways to choose a set of size \(t_s\) from each of \(B_1,\dots,B_{s-1}\) is precisely \(\binom{t_{s-1}}{t_s}^{s-1}\text{.}\) Thus, by the Pigeonhole Principle,
 1 
See the course notes for Math 422 at UVic \cite[Chapter 5]{422}.
there must be a set \(A\) of \(t_s\) vertices of \(W\) and subsets \(B_i'\) of \(B_i\) for \(1\leq i\leq s-1\) such that every vertex in \(A\) is adjacent to every vertex in \(\bigcup_{i=1}^{s-1}B_i'\text{.}\) This completes the proof.
We now combine these two lemmas to prove the Erdős–Stone Theorem.

Proof of the Erdős–Stone Theorem .

Let \(H\) be any graph containing an edge, let \(r=\chi(H)\) and let \(t=|V(H)|\text{.}\) Let \(\varepsilon>0\) and let \(n\) be large with respect to \(r,t\) and \(\varepsilon\text{.}\) Let \(G\) be a graph with \(n\) vertices such that
\begin{equation*} |E(G)|\geq \left(\frac{r-2}{r-1}+\varepsilon\right)\binom{n}{2}\text{.} \end{equation*}
Using Lemma 3.3.12, we can find a subgraph \(G'\) of \(G\) such that
\begin{equation*} \delta(G')\geq \left(\frac{r-2}{r-1}+\frac{\varepsilon}{2}\right)(|V(G')|-1) \end{equation*}
and with the number of vertices in \(G'\) bounded below by \(n\sqrt{\frac{\varepsilon}{2-\varepsilon}}\text{.}\) Now, applying Lemma 3.3.13 to \(G'\text{,}\) we see that, if \(n\) is large enough, then it contains a complete \(r\)-partite graph in which every part has cardinality \(t\text{.}\) This clearly contains \(H\text{,}\) and so we are done.
Here are a few YouTube videos related to the Erdős–Stone Theorem:
PrevTopNext