Skip to main content

Section 3.4 Bounding Extremal Numbers of Bipartite Graphs

One important thing to notice about the Erdős–Stone Theorem is that it tells us very little about the precise asymptotics of \(\ex(n,H)\) when \(H\) is bipartite (i.e. when \(\chi(H)=2\)). That is, all that it tells us is that \(\ex(n,H)\) grows slower than \(n^2\text{,}\) but it does not tell us what the actual growth rate is. The well-known Kővari–Sós–Turán Theorem tells us that it is at least a polynomial factor away from \(n^2\text{.}\)
described in detail following the image
“Projective plane.”

Proof.

The proof has a similar flavour to the proof of Mantel’s Theorem given earlier. Let \(G\) be a graph which does not contain a copy of \(K_{s,t}\text{.}\) We count the pairs \((v,S)\) such that \(v\in V(G)\) and \(S\) is a set of cardinality \(s\) contained in the neighbourhood of \(v\text{.}\) On one hand, this is clearly equal to
\begin{equation*} \sum_{v\in V(G)} \binom{d(v)}{s}\text{.} \end{equation*}
On the other hand, for each set \(S\) of cardinality \(s\) there are at most \(t-1\) such vertices \(v\) for, if not, then \(G\) would contain a \(K_{s,t}\text{.}\) Therefore,
\begin{equation*} \sum_{v\in V(G)} \binom{d(v)}{s}\leq (t-1)\binom{n}{s}\text{.} \end{equation*}
Now, given the constraint that \(\sum_{v\in V(G)}d(v)=2|E(G)|\text{,}\) the sum \(\sum_{v\in V(G)} \binom{d(v)}{s}\) is minimized when the degrees are as similar as possible; this is because, by Pascal’s Formula,
\begin{equation*} \binom{a+1}{s}+\binom{b-1}{s} -\binom{a}{s}-\binom{b}{s} = \binom{a}{s-1}-\binom{b-1}{s-1} \end{equation*}
which is non-negative whenever \(a\geq b-1\text{.}\) Thus,
\begin{equation*} n\cdot \frac{\left(2|E(G)|/n - s\right)^s}{s!}\leq\sum_{v\in V(G)} \binom{d(v)}{s}\leq (t-1)\binom{n}{s}\leq (t-1)\frac{n^s}{s!}\text{.} \end{equation*}
The result now follows from a bit of algebra.
Since any bipartite graph \(H\) is contained in a complete bipartite graph, we get the following.
Consider the proof of Theorem 3.4.1 specialized to the case that \(s=t=2\text{.}\) Note that \(K_{2,2}\) is the same as the \(4\)-cycle \(C_4\text{.}\) If we fast forward to the middle of the proof, we have that, in any \(C_4\)-free graph \(G\) on \(n\) vertices,
\begin{equation*} \binom{n}{2}\geq \sum_{v\in V(G)}\binom{d(v)}{2} = \sum_{v\in V(G)}\frac{d(v)^2}{2} - \sum_{v\in V(G)}\frac{d(v)}{2}\text{.} \end{equation*}
Recall that, by handshaking, \(\sum_{v\in V(G)}d(v)=2|E(G)|\text{.}\) So, applying Corollary C.0.6, we have
\begin{equation*} \binom{n}{2} \geq \frac{\left(2|E(G)|\right)^2}{2n}-|E(G)| \end{equation*}
\begin{equation*} \Longrightarrow 4|E(G)|^2 -2n|E(G)| - n^2(n-1)\leq 0\text{.} \end{equation*}
Solving this quadratic yields the following bound.
This bound turns out to be sharp. Some of the standard examples include “incidence graphs” of points and lines of finite projective planes.
 1 
Finite projective places are discussed in Math 322 at UVic \cite[Chapter 4]{322}.
Let’s consider the following somewhat simpler example, borrowed from these notes [117].

Example 3.4.4.

Given a prime \(p\text{,}\) let \(G_p\) be the graph with vertex set \(\mathbb{Z}_p\times \mathbb{Z}_p\) where \((x,y)\) is adjacent to \((x',y')\) if \(x+x'=yy'\) and \((x,y)\neq (x',y')\text{.}\) For any \((x,y)\) and any choice of \(y'\text{,}\) there is a unique \(x'\) for which the equation is satisfied. Thus, each \((x,y)\) has degree either \(p-1\) or \(p\text{,}\) depending on whether or not the equation is satisfied with \((x',y')=(x,y)\text{.}\) Therefore, the number of edges is at least
\begin{equation*} \frac{1}{2}p^2(p-1) = \Theta(n^{3/2}) \end{equation*}
where \(n=p^2\) is the number of vertices.
Now, let us show that \(G_p\) does not have any \(4\)-cycles. Let \((x,y)\) be a vertex and let \((x_1,y_1)\) and \((x_2,y_2)\) be two distinct neighbours of it. Then
\begin{equation*} x+x_1 = yy_1 \end{equation*}
and
\begin{equation*} x+x_2=yy_2\text{.} \end{equation*}
Subtracting these equations, we get
\begin{equation*} x_1-x_2 = y(y_1-y_2)\text{.} \end{equation*}
Thus, given the choice of \(x_1,x_2,y_1\) and \(y_2\text{,}\) provided that \((x_1,y_1)\neq (x_2,y_2)\text{,}\) the value of \(y\) is uniquely determined from this equation. Taking the equation \(x+x_1=yy_1\) then uniquely determines \(x\text{.}\) Therefore, \((x,y)\) is the unique common neighbour of \((x_1,y_1)\) and \((x_2,y_2)\text{,}\) and so \(G_p\) does not contain a \(4\)-cycle.
Here is a YouTube video related to the Kővari–Sós–Turán Theorem: