極値数・Turán グラフ

グラフ $H$ に対し、$H$ と同型な部分グラフを含まない $n$ 頂点グラフの辺の数の最大値を極値数 $\operatorname{ex}(n,H)$ という。

$r\ge1$ とする。$n$ 個の頂点を、大きさが $\lfloor n/r\rfloor$ か $\lceil n/r\rceil$ の $r$ 個の組（空でもよい）に分け、異なる組に属する 2 頂点をすべて結んだグラフを Turán グラフ $T_r(n)$ といい、その辺の数を $t_r(n)$ と書く。