### Theorem 3.4.1. Kővari–Sós–Turán Theorem [151].

For any natural numbers \(s\) and \(t\) such that \(s\leq t\text{,}\)

\begin{equation*}
\ex(n,K_{s,t})\leq (1+o(1))\frac{1}{2}(t-1)^{\frac{1}{s}}n^{2-\frac{1}{s}}\text{.}
\end{equation*}

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{.}\)

“Projective plane.”

For any natural numbers \(s\) and \(t\) such that \(s\leq t\text{,}\)

\begin{equation*}
\ex(n,K_{s,t})\leq (1+o(1))\frac{1}{2}(t-1)^{\frac{1}{s}}n^{2-\frac{1}{s}}\text{.}
\end{equation*}

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.

For any bipartite graph \(H\text{,}\)

\begin{equation*}
\ex(n,H)=O\left(n^{2-\frac{2}{|V(H)|}}\right)
\end{equation*}

where the constant factor depends on \(H\text{.}\)

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.

For any \(n\text{,}\)

\begin{equation*}
\ex(n,C_4)\leq \frac{1}{4}\left(\sqrt{4n-3} + 1\right)n\text{.}
\end{equation*}

This bound turns out to be sharp. Some of the standard examples include “incidence graphs” of points and lines of finite projective planes.^{ 1 }

Let’s consider the following somewhat simpler example, borrowed from these notes [117].

Finite projective places are discussed in Math 322 at UVic \cite[Chapter 4]{322}.

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 \(x'\text{,}\) there is a unique \(y'\) 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: