極値グラフ理論

1. $H'$ を含まないグラフは $H$ も含まない（$H$ と同型な部分グラフがあれば、その中に $H'$ と同型な部分グラフがある）。
2. $H$ を含まない $n$ 頂点のグラフに孤立した頂点 $w$ を 1 つ加えても、$H$ を含むようにはならない。$H$ と同型な部分グラフの頂点はその部分グラフの中で次数 $1$ 以上なので、次数 $0$ の $w$ を使えず、もとのグラフの部分グラフになるからである。
3. $G$ を $H$ を含まない $n+1$ 頂点のグラフとする。$n$ 個の頂点からなる部分集合 $S$（$n+1$ 通り）について誘導部分グラフ $G[S]$ も $H$ を含まないので、$e(G[S])\le\operatorname{ex}(n,H)$ である。各辺は、その両端を含む $S$、すなわち残りの $n-1$ 個の頂点のどれか 1 つを除いた $S$ に属するので、$n-1$ 個の $S$ で数えられる。よって
   $$ (n-1)\,e(G)=\sum_Se(G[S])\le(n+1)\operatorname{ex}(n,H) $$
   であり、両辺を $(n-1)\binom{n+1}2=(n+1)\binom n2$ で割ると、$e(G)/\binom{n+1}2\le\operatorname{ex}(n,H)/\binom n2$ である。$G$ は任意なので主張が従う。$\square$

Turán グラフ $T(n,r)$ は部ごとに色を変えれば $r$ 色で塗り分けられるので $\chi(T(n,r))\le r$ である。$T(n,r)$ が $H$ を含めば、彩色数 の命題「部分グラフと連結成分」により $\chi(H)\le r$ となって矛盾する。よって $\operatorname{ex}(n,H)\ge e(T(n,r))=t(n,r)$ である。
$T(n,r)$ の部の大きさを $n_1,\dots,n_r$ とすると、各 $n_i\le n/r+1$ なので $\sum_in_i^2\le(n/r+1)\sum_in_i=n^2/r+n$ であり、
$$ t(n,r)=\frac12\Bigl(n^2-\sum_in_i^2\Bigr)\ge\Bigl(1-\frac1r\Bigr)\frac{n^2}2-\frac n2 $$
である。両辺を $\binom n2=n(n-1)/2$ で割って $n\to\infty$ とすると $\pi(H)\ge1-1/r$ を得る。一方、Turánの定理 の系「辺の密度による形」により $\operatorname{ex}(n,K_{r+1})=t(n,r)\le(1-1/r)n^2/2$ なので、$\operatorname{ex}(n,K_{r+1})/\binom n2\le(1-1/r)\,n/(n-1)$ であり、$\pi(K_{r+1})\le1-1/r$ である。$\square$

$y^s-a^s=(y-a)\sum_{j=0}^{s-1}y^ja^{s-1-j}$ である。$y\ge a$ なら和の各項は $a^{s-1}$ 以上で $y-a\ge0$、$y< a$ なら各項は $a^{s-1}$ 以下で $y-a< 0$ なので、どちらの場合も $y^s-a^s\ge sa^{s-1}(y-a)$ である。後半は $y=y_i$ として $i$ について足すと、$\sum_i(y_i-a)=0$ から従う。$\square$

$m:=e(G)$ とし、頂点 $v$ と、$N(v)$ の $s$ 個の頂点からなる部分集合 $S$ の組 $(v,S)$ の個数を $X$ とする。
上から。 $S$ を先に決めると、$v$ は $S$ の共通の隣接頂点である。$G$ は $K_{s,t}$ を含まないので、共通の隣接頂点は $t-1$ 個以下である。よって
$$ X\le(t-1)\binom ns\le(t-1)\frac{n^s}{s!} $$
である。
下から。 $v$ を先に決めると $X=\sum_v\binom{d(v)}s$ である。整数 $d\ge0$ に対し $y:=\max(d-s+1,0)$ とおくと $s!\binom ds\ge y^s$ である。実際、$d\ge s$ なら $s!\binom ds=d(d-1)\cdots(d-s+1)$ の $s$ 個の因数はどれも $d-s+1>0$ 以上であり、$d\le s-1$ なら両辺とも $0$ である。$y_v:=\max(d(v)-s+1,0)$ とおくと、握手補題（次数(グラフ) の記事）により
$$ \sum_vy_v\ge\sum_v\bigl(d(v)-s+1\bigr)=2m-(s-1)n $$
である。$2m\le(s-1)n$ なら主張は明らかなので、$2m>(s-1)n$ とする。$y_v$ の平均 $a$ は $a\ge2m/n-(s-1)>0$ を満たし、lem-ext-tangent により
$$ s!\,X\ge\sum_vy_v^s\ge na^s\ge n\Bigl(\frac{2m}n-s+1\Bigr)^s $$
である。
合わせる。 $n(2m/n-s+1)^s\le(t-1)n^s$ から $2m/n-s+1\le(t-1)^{1/s}n^{1-1/s}$ であり、両辺に $n/2$ を掛けて整理すると主張を得る。$\square$

1. $H$ の二部分割を $A,B$（$\lvert A\rvert=s$、$\lvert B\rvert=t$）とする。$H$ は辺をもつので $s,t\ge1$ であり、$H$ の辺はすべて $A$ と $B$ を結ぶので、$H$ は部 $A,B$ の完全二部グラフ $K_{s,t}$ の部分グラフである。prop-ext-monotone の 1 と thm-ext-kst から上界が従い、$n^{2-1/s}/\binom n2\to0$ なので $\pi(H)=0$ である。
2. 二部グラフであることは 2 色で塗り分けられることと同じである（彩色数 の命題「2 色で彩色できるグラフ」）ので、$\chi(H)\ge3$ である。prop-ext-chromatic を $r=\chi(H)-1\ge2$ で使うと $\pi(H)\ge1-1/r\ge1/2$ である。$\square$

要点：相異なる 2 頂点の共通の隣接頂点は高々 1 個なので $\sum_v\binom{d(v)}2\le\binom n2$ であり、Cauchy–Schwarz の不等式で左辺を $m:=e(G)$ で下から評価する。

各直線 $(a,b)$ は、$x\in\mathbb F_p$ を自由に選び $y:=ax+b$ と定めた $p$ 個の点と結ばれるので、辺は $p^2\cdot p=p^3$ 本である。$I_p$ は二部グラフなので、$C_4$ は 2 点 $(x_1,y_1)\ne(x_2,y_2)$ と、その両方を通る 2 本の直線からなる。両方を通る直線 $(a,b)$ について、$x_1=x_2$ なら $y_1=ax_1+b=y_2$ となって 2 点が一致するので、$x_1\ne x_2$ である。$\mathbb F_p$ は体なので $a=(y_1-y_2)/(x_1-x_2)$、$b=y_1-ax_1$ と一意に決まり、両方を通る直線は 1 本しかない。よって $C_4$ はない。$\square$

上界は prop-ext-c4-upper と $\sqrt{4n-3}<2\sqrt n$ による。下界：要点は、$2p^2\le n$ で $p$ が $\sqrt{n/2}$ の定数倍以上の素数を Bertrandの仮説 で選び、prop-ext-incidence と prop-ext-monotone の 2 を使うことである。