Kővári–Sós–Turánの定理

$g(x):=x(x-1)\cdots(x-s+1)$ とおく。$x\ge s-1$ では $s$ 個の因数 $x-j$（$0\le j\le s-1$）はどれも $0$ 以上なので、積の微分により
$$ g'(x)=\sum_{j}\prod_{k\ne j}(x-k)\ge0,\qquad g''(x)=\sum_{j\ne k}\ \prod_{l\ne j,k}(x-l)\ge0 $$
であり、$f_s$ は $[s-1,\infty)$ で非減少かつ凸である（$s=1$ なら $f_1(x)=x$ である）。$(-\infty,s-1]$ では $f_s$ は定数 $0$ である（$f_s(s-1)=0$）。$f_s$ は連続で、点 $s-1$ での右微分係数 $g'(s-1)/s!\ge0$ が左微分係数 $0$ 以上なので、$f_s$ の右微分係数は $\mathbb R$ 全体で非減少であり、$f_s$ は $\mathbb R$ 上で非減少かつ凸である。整数 $d$ については、$d\le s-2$ なら $f_s(d)=0=\binom ds$、$d\ge s-1$ なら定義から $f_s(d)=\binom ds$ である。最後の不等式は、$x\ge s-1$ のとき各因数が $x-j\ge x-s+1\ge0$ をみたすことによる。$\square$

1. $A$ を $s\times t$ の全 $1$ 部分行列をもたない $m\times n$ 行列とし、$1$ の個数を $Z$、第 $j$ 列の $1$ の個数を $d_j$ とする。$s$ 個の行の集合 $S$ と列 $j$ の組 $(S,j)$ で、$S$ のすべての行で第 $j$ 列の成分が $1$ であるものの個数を $X$ とし、これを 2 通りに数える。

行の組から数える．$S$ を決めると、条件をみたす列は $t-1$ 個以下である（$t$ 個あれば、$S$ とそれらの列が全 $1$ 部分行列をなす）。よって
$$ X\le(t-1)\binom ms\le\frac{(t-1)m^s}{s!} $$
である。
列から数える．列 $j$ を決めると、$S$ はその列で $1$ である $d_j$ 個の行から $s$ 個を選ぶので、$X=\sum_{j=1}^n\binom{d_j}s=\sum_jf_s(d_j)$ である。lem-kst-convex により $f_s$ は凸なので、Jensenの不等式（$n$ 個の列の上の一様な確率測度に当てる）により $\sum_jf_s(d_j)\ge n\,f_s(Z/n)$ である。
合わせる．$Z\le(s-1)n$ なら主張は明らかなので、$Z/n>s-1$ とする。lem-kst-convex の最後の不等式とあわせて
$$ \frac n{s!}\Bigl(\frac Zn-s+1\Bigr)^s\le n\,f_s\Bigl(\frac Zn\Bigr)\le X\le\frac{(t-1)m^s}{s!} $$
であり、$s$ 乗根をとると $Z/n-s+1\le(t-1)^{1/s}mn^{-1/s}$、すなわち $Z\le(t-1)^{1/s}mn^{1-1/s}+(s-1)n$ である。
2. $G$ の頂点を $1,\dots,n$ と番号づけ、隣接行列 $A$（$i$ と $j$ が隣接するとき $a_{ij}=1$、そうでないとき $a_{ij}=0$。特に $a_{ii}=0$）を考える。$A$ の $1$ の個数は $2e(G)$ である。行の集合 $S$（$s$ 個）と列の集合 $T$（$t$ 個）の交わりの成分がすべて $1$ なら、$a_{ii}=0$ なので $S\cap T=\emptyset$ であり、$S$ と $T$ は $G$ の中で $K_{s,t}$ をなす。よって $A$ は $s\times t$ の全 $1$ 部分行列をもたず、1 から
$$ 2e(G)\le z(n,n;s,t)\le(t-1)^{1/s}n^{2-1/s}+(s-1)n $$
である。$\square$

$H$ の辺はすべて 2 つの部を結ぶので、$H$ はその 2 つの部を部とする $K_{s,t}$ の部分グラフである。したがって $K_{s,t}$ を含むグラフは $H$ も含み、対偶をとると、$H$ を含まないグラフは $K_{s,t}$ も含まない。よって $\operatorname{ex}(n,H)\le\operatorname{ex}(n,K_{s,t})$ であり、あとは thm-kst-main の 2 と、$n^{2-1/s}/\binom n2\to0$ による。$\square$

$x\ne0$ なら $y\mapsto x\cdot y$ は $\mathbb F_q^3$ 上の $0$ でない線形汎関数なので、その核は 2 次元部分空間、すなわち直線 $L(x)$ である。

1. $\mathbb F_q^3$ の $0$ でないベクトルは $q^3-1$ 個あり、各点はそのうち $q-1$ 個（$0$ でないスカラー倍）で張られるので、点は $(q^3-1)/(q-1)=q^2+q+1$ 個ある。同じく、2 次元部分空間 $L(x)$ の上の点は $(q^2-1)/(q-1)=q+1$ 個ある。$[x]$ の隣接頂点は、$L(x)$ の上の点から、$x\cdot x=0$（すなわち $[x]\in L(x)$）のときに限り $[x]$ 自身を除いたものなので、次数は $q+1$ か $q$ である。握手補題により $2e(\mathrm{ER}_q)\ge q(q^2+q+1)$ である。
2. 相異なる 2 点 $[x],[y]$ の共通の隣接頂点は $L(x)\cap L(y)$ の上にある。$x,y$ は 1 次独立なので、2 つの線形汎関数 $x\cdot{-}$ と $y\cdot{-}$ も 1 次独立であり、核の共通部分は $3-2=1$ 次元である。よって $L(x)\cap L(y)$ はただ 1 点で、共通の隣接頂点は高々 1 個である。ex-kst-small の 2 により、$\mathrm{ER}_q$ は $K_{2,2}$ を含まない。$\square$

$K_{2,2}$ は $K_{2,t}$ の部分グラフなので、$K_{2,2}$ を含まないグラフは $K_{2,t}$ も含まず（prf-kst-bipartite と同じ対偶）、真ん中の不等式が成り立つ。右の不等式は thm-kst-main の 2 を $s=2$ で使った $\operatorname{ex}(n,K_{2,t})\le\frac12\sqrt{t-1}\,n^{3/2}+\frac12n$ による。
左の不等式を示す。素数 $p$ が $p\le\sqrt n-1$ をみたせば、$p^2+p+1\le(\sqrt n-1)^2+(\sqrt n-1)+1=n-\sqrt n+1\le n$ である。$\mathrm{ER}_p$ に孤立した頂点を $n-(p^2+p+1)$ 個加えた $n$ 頂点のグラフは $K_{2,2}$ を含まない（$K_{2,2}$ の頂点はどれも次数 $2$ なので、孤立した頂点は使えない）。prop-kst-polarity により
$$ \operatorname{ex}(n,K_{2,2})\ge\frac12p(p^2+p+1)>\frac{p^3}2 $$
である。$\varepsilon>0$ を任意にとる。素数定理 の系「短い区間の素数」により、$n$ が十分大きければ $\frac{\sqrt n-1}{1+\varepsilon}< p\le\sqrt n-1$ となる素数 $p$ があるので、
$$ \frac{\operatorname{ex}(n,K_{2,2})}{n^{3/2}}>\frac1{2(1+\varepsilon)^3}\Bigl(1-\frac1{\sqrt n}\Bigr)^3 $$
である。右辺は $n\to\infty$ で $\frac1{2(1+\varepsilon)^3}$ に近づき、$\varepsilon$ は任意なので、左の不等式が従う。
最後の主張は、素数定理の代わりに Bertrandの仮説 で $p$ を選べば得られる。

1. $A$ を $2\times2$ の全 $1$ 部分行列をもたない $n\times n$ 行列とし、$1$ の個数を $Z$、第 $j$ 列の $1$ の個数を $d_j$ とする。相異なる 2 つの行が両方 $1$ である列は 1 個以下なので、prf-kst-main の $X$（$s=t=2$）は $X=\sum_j\binom{d_j}2\le\binom n2$ をみたす。Cauchy–Schwarzの不等式により $\sum_jd_j^2\ge Z^2/n$ なので、
   $$ \frac12\Bigl(\frac{Z^2}n-Z\Bigr)\le\sum_j\binom{d_j}2\le\frac{n(n-1)}2 $$
   であり、$Z^2-nZ-n^2(n-1)\le0$ である。この 2 次不等式を解くと $Z\le\frac{n+\sqrt{n^2+4n^2(n-1)}}2=\frac n2\bigl(1+\sqrt{4n-3}\bigr)$ である。
2. $4N-3=(2q+1)^2$ なので、1 の上界は $\frac N2(2q+2)=(q+1)N$ である。逆向きの不等式のために、$\mathbb P^2(\mathbb F_q)$ の点を行、直線を列とし、点が直線の上にあるとき $1$ とする行列を考える。直線は $0$ でない線形汎関数の核で、汎関数はスカラー倍を除いて核で決まるので、直線も $(q^3-1)/(q-1)=N$ 本あり、行列は $N\times N$ である。各直線の上に $q+1$ 個の点があるので、$1$ は $(q+1)N$ 個ある。相異なる 2 点 $[x],[y]$ の両方を含む 2 次元部分空間は $x,y$ の張る空間ただ 1 つなので、2 つの行が両方 $1$ である列は 1 個しかなく、この行列は $2\times2$ の全 $1$ 部分行列をもたない。$\square$

要点：各辺を確率 $p=\frac12n^{-\alpha}$ で独立に選んだランダムグラフ（Erdős–Rényiのランダムグラフ の $G(n,p)$）では、$K_{s,t}$ の個数の期待値が辺の本数の期待値の半分以下になるので、$K_{s,t}$ ごとに辺を 1 本除いても多くの辺が残る。