Kovari-Sos-Turan Theorem

This theorem discusses extremal graphs for $\text{ex}(n,K_{r,s})$. In particular, we explore when $F$ is bipartite, as an extension of Bipartite Dichotomy.

Lemma (Discrete Jensen’s Inequality)

Let $a_1,a_2,\dots ,a_n,r\in {\mathbb{Z}}_{+}$ and let

$$a=\frac{1}{n}\sum _{i=1}^n{a}_i$$

If $a\ge r-1$ then

$$n\left(\genfrac{}{}{0ex}{}{a}{r}\right)\le \sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{a_i}{n}\right)$$

Proof: This is a special case of Jensen’s Inequality. Note that in Verstraete, the lemma is written wrong. Source: Kane.

Kovari-Sos-Turan Theorem

The theorem states that

$$\text{ex}(n,K_{r,s})\le {\left(\frac{s-1}{2}\right)}^{1/r}{n}^{2-\frac{1}{r}}+\frac{(r-1)n}{2}$$

for complete bipartite graph $K_{r,s}$ and $r,s\in {\mathbb{Z}}_{+}$. As $n\to \infty$, then the left term will increase more than the right term. Then approximately it will be $n^{2-\frac{1}{r}}$. In particular, this is $<<n^2$.

Proof:

Let $G$ be an $n-$vertex graph not containing $K_{r,s}$. If $|E(G)|\le (r-1)n/2$ then we are done, so assume otherwise. For $n$ vertices, we have $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ total $r-$tuples. If we named the vertices ${\mathbb{Z}}_{1\to n}$, and let $a_v=\mathrm{deg}(v)$, then there are exactly $\left(\genfrac{}{}{0ex}{}{a_v}{r}\right)$ sets of size $r$ in $N(v)$.

Thus, the total number of sets of size $r$ in the neighborhood of some vertex is

$$\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{a_v}{r}\right)$$

In particular, we have counted up the total number of star graphs in $G$. We may have counted some sets of size $r$ more than once. However, no set of size $r$ could have been counted at least $s$ times. Otherwise, that particular set of size $r$ would be in the neighborhood of $s$ vertices in $V(G)$, and that would resolve $K_{r,s}$. Thus,

$$\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{a_v}{r}\right)\le (s-1)\left(\genfrac{}{}{0ex}{}{n}{r}\right)$$

The RHS represents our “forbidden subgraph”. By applying Lemma (Discrete Jensen’s Inequality), with

$$a=\frac{2|E(G)|}{n}\ge r-1$$

by Handshake Lemma, we get

$$n\left(\genfrac{}{}{0ex}{}{a}{r}\right)\le (s-1)\left(\genfrac{}{}{0ex}{}{n}{r}\right)$$

The goal now is to separate $a$ from the binomial, where $|E(G)|$ is trapped in. Unfortunate!

We use the fact that for $x\ge r$,

$$\frac{(x-r{)}^r}{r!}\ge \left(\genfrac{}{}{0ex}{}{x}{r}\right)=\frac{x(x-1)\dots (x-r+1)}{r!}\ge \frac{(x-r+1{)}^r}{r!}$$

In Verstraete, the inequalities are flipped, which I’m pretty sure is not correct. In particular, let $x=5,r=2$.

and that

$$\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le \frac{n^r}{r!}$$

so that

$$n\frac{(a-r+1{)}^r}{r!}\le (s-1)\frac{n^r}{r!}$$

This tells us that

$$(an-(r-1)n{)}^r\le (s-1)n^{2r-1}$$

and since $an=2|E(G)|$, then

$$|E(G)|\le {\left(\frac{s-1}{2}\right)}^{1/r}{n}^{2-\frac{1}{r}}+\frac{(r-1)n}{2}$$

and the proof is complete.