極値グラフ理論

同義語：extremal graph theory

概要

極値グラフ理論（extremal graph theory）とは、あるグラフ $H$ を部分グラフとして含まないなどの条件のもとで、グラフの辺の本数などの量がどこまで大きく（小さく）なれるかを調べる分野である。基本の量は $H$ を含まない $n$ 頂点のグラフの辺の本数の最大値 $\operatorname{ex}(n,H)$ で、これを $\binom n2$ で割った比はTurán密度 $\pi(H)$ に収束する。完全グラフではTuránの定理が正確な値を与え、一般には $\pi(H)=1-1/(\chi(H)-1)$ と彩色数で決まる（Erdős–Stone–Simonovitsの定理）。二部グラフでは $\pi(H)=0$ となり、Kővári–Sós–Turánの定理や有限体を使った構成で増え方を調べる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 部分グラフ, Mantelの定理, Turánの定理, 彩色数

$n$ 頂点のグラフに辺を引いていくと、いつかは三角形ができる。三角形を作らずに引ける辺の本数の最大値は $\lfloor n^2/4\rfloor$ である（Mantelの定理）。三角形の代わりに長さ 4 の閉路を禁止すると、最大値は $n^{3/2}$ 程度まで下がる。「あるグラフを含まない」という条件のもとで辺の本数の最大値を求めるこの種の問いと、そこから広がる「ある性質をもつグラフの中で、ある量はどこまで大きく（小さく）なれるか」という問いを調べる分野を 極値グラフ理論（extremal graph theory）という。
この分野の基本の量は、グラフ $H$ を部分グラフとして含まない $n$ 頂点のグラフの辺の本数の最大値 $\operatorname{ex}(n,H)$ である。$H$ が完全グラフなら Turánの定理 が $\operatorname{ex}(n,H)$ を正確に与える。一般の $H$ では、$\operatorname{ex}(n,H)$ の $n^2$ の係数は $H$ の彩色数だけで決まる（Erdős–Stone–Simonovits の定理。Erdős–Stoneの定理 から導かれる）。この記事では、$\operatorname{ex}(n,H)/\binom n2$ が単調に減ることから極限（Turán 密度）を定め、彩色数による下界を示す。次に、二部グラフを禁止したときの上界（Kővári–Sós–Turánの定理）を述べ、Turán 密度は $0$ か $1/2$ 以上のどちらかであることを導く。長さ 4 の閉路については、上界と、有限体の直線を使った構成で、最大値が $n^{3/2}$ の定数倍であることを示す。

定義

この記事では、グラフはループも平行辺ももたない有限の無向の単純グラフとする。$e(G)$ を $G$ の辺の本数、$v(G)$ を頂点の個数、$d(v)$ を頂点 $v$ の次数(グラフ)、$N(v)$ を $v$ に隣接する頂点の集合とする。$K_n$ は $n$ 頂点の完全グラフ、$K_{s,t}$ は部の大きさが $s,t$ の完全二部グラフ、$C_\ell$ は長さ $\ell$ の閉路である。

禁止部分グラフと極値数

$H$ を辺を 1 本以上もつグラフとする。グラフ $G$ のある部分グラフが $H$ とグラフ同型であるとき、$G$ は $H$ を 含む という。含まないとき $H$ を含まない（$H$-free）という。$n\ge1$ に対し
$$ \operatorname{ex}(n,H):=\max\{e(G)\mid G\text{ は }H\text{ を含まない }n\text{ 頂点のグラフ}\} $$
を $H$ の 極値数（extremal number、Turán 数）といい、最大値を与えるグラフを 極値グラフ という。グラフの集まり $\mathcal F$ についても、$\mathcal F$ のどのグラフも含まないグラフの辺の本数の最大値を $\operatorname{ex}(n,\mathcal F)$ と書く。

辺のない $n$ 頂点のグラフは辺をもつ $H$ を含まないので、最大値をとる集合は空でない。$H$ が辺をもたない場合は、$v(H)\le n$ ならどの $n$ 頂点のグラフも $H$ を含むので、この定義からは除いておく。また、以下では $H$ は 孤立した頂点（次数 $0$ の頂点）をもたない とする。$n\ge v(H)$ なら、$H$ から孤立した頂点を取り除いても「含む」かどうかは変わらない（余った頂点を孤立した頂点に充てればよい）ので、極値数を調べるうえでこの仮定は制限にならない。

極値数の例
  1. $K_2$（1 本の辺）を含まないグラフは辺をもたないので $\operatorname{ex}(n,K_2)=0$ である。
  2. 辺を 2 本もつ道 $P_3$ を含まないことは、どの頂点の次数も $1$ 以下であることと同じである。このとき辺は互いに端点を共有しないので $\operatorname{ex}(n,P_3)=\lfloor n/2\rfloor$ であり、極値グラフは $\lfloor n/2\rfloor$ 本の互いに交わらない辺からなる。
  3. すべての閉路の集まり $\mathcal C$ について、$\mathcal C$ のどれも含まないグラフは森であり、$\operatorname{ex}(n,\mathcal C)=n-1$ である（閉路 の系「辺の本数と閉路」と、$n$ 頂点の木が $n-1$ 本の辺をもつこと）。
  4. $\operatorname{ex}(n,K_3)=\lfloor n^2/4\rfloor$ である（Mantelの定理）。
  5. $r\ge1$ のとき、$\operatorname{ex}(n,K_{r+1})=t(n,r)$ である。ここで $t(n,r)$ は頂点をほぼ均等に $r$ 個の部に分けた完全 $r$ 部グラフ（Turán グラフ）$T(n,r)$ の辺の本数である（Turánの定理）。

単調性と Turán 密度

極値数の単調性

$H$ を辺をもち孤立した頂点をもたないグラフとする。

  1. $H'$ が辺をもち孤立した頂点をもたない $H$ の部分グラフなら $\operatorname{ex}(n,H')\le\operatorname{ex}(n,H)$ である。
  2. $\operatorname{ex}(n,H)\le\operatorname{ex}(n+1,H)$ である。
  3. $n\ge2$ なら
    $$ \frac{\operatorname{ex}(n+1,H)}{\binom{n+1}2}\le\frac{\operatorname{ex}(n,H)}{\binom n2} $$
    である。
部分集合の上で平均をとる
  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$

数列 $\operatorname{ex}(n,H)/\binom n2$（$n\ge2$）は単調に減少し、$0$ 以上 $1$ 以下なので収束する。

Turán密度

辺をもつグラフ $H$ に対し
$$ \pi(H):=\lim_{n\to\infty}\frac{\operatorname{ex}(n,H)}{\binom n2} $$
を $H$ の Turán 密度 という。

$\binom n2$ は頂点の組の個数なので、$\pi(H)$ は「$H$ を含まない大きなグラフが、頂点の組のうちどれだけの割合を辺にできるか」の極限である。

彩色数による下界

$H$ を辺をもつグラフとし、彩色数を $\chi(H)=r+1$（$r\ge1$）とする。このとき $\operatorname{ex}(n,H)\ge t(n,r)$ であり、
$$ \pi(H)\ge1-\frac1r,\qquad\pi(K_{r+1})=1-\frac1r $$
である。

Turán グラフは $H$ を含まない

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$

逆向きの不等式も成り立つ。これが極値グラフ理論の基本定理である。

Erdős–Stone–Simonovitsの定理

辺をもつグラフ $H$ について
$$ \pi(H)=1-\frac1{\chi(H)-1} $$
である。すなわち $\operatorname{ex}(n,H)=\Bigl(1-\frac1{\chi(H)-1}+o(1)\Bigr)\frac{n^2}2$（$n\to\infty$）である。

証明の所在

証明は Erdős–Stoneの定理 の記事にあり、この定理はそこで系「Erdős–Simonovitsの式」として導かれる。その記事では、辺の本数が $\bigl(1-\frac1r+\varepsilon\bigr)\frac{n^2}2$ 以上の大きなグラフは、$K_{r+1}$ の各頂点を $s$ 個ずつにふくらませた完全 $(r+1)$ 部グラフを含むこと（Erdős–Stone の定理）を、$K_{r+1}$ の超飽和と、超グラフへの Kővári–Sós–Turán の定理の拡張によって証明している（Zha23 定理 1.5.1、p. 27 も参照）。下からの不等式は prop-ext-chromatic である。

$\chi(H)\ge3$ なら、$\operatorname{ex}(n,H)$ の主要項 $\bigl(1-\frac1{\chi(H)-1}\bigr)\frac{n^2}2$ は $H$ の形によらず彩色数だけで決まる。たとえば Petersenグラフ（彩色数 3）の Turán 密度は三角形と同じ $1/2$ である（Zha23 例 1.5.4）。一方、$\chi(H)=2$、すなわち $H$ が辺をもつ二部グラフのときは $\pi(H)=0$ となり、$\operatorname{ex}(n,H)$ の増え方はこの定理からは分からない。次節でこの場合を調べる。

二部グラフを禁止する場合

$G$ が $K_{s,t}$ を含むことは、$s$ 個の頂点の集合 $S$ で、$S$ のすべての頂点と隣接する頂点（共通の隣接頂点）が $t$ 個以上あるものが存在することと同じである。共通の隣接頂点は $S$ に属さない（頂点は自分自身と隣接しない）ので、$S$ と $t$ 個の共通の隣接頂点が $K_{s,t}$ をなす。

完全二部グラフを含まないグラフの辺の本数

$s,t\ge1$ を整数とする。$K_{s,t}$ を含まない $n$ 頂点のグラフ $G$ について
$$ e(G)\le\frac12(t-1)^{1/s}n^{2-1/s}+\frac12(s-1)n $$
である。特に $\operatorname{ex}(n,K_{s,t})=O(n^{2-1/s})$ である。

名前と証明の所在

この上界は Kővári–Sós–Turán の定理 とよばれる（Zha23 定理 1.4.2、p. 22）。証明は Kővári–Sós–Turánの定理 の記事にある。頂点 $v$ と、$N(v)$ の $s$ 個の頂点からなる部分集合の組を 2 通りに数え、「$s$ 個の頂点の共通の隣接頂点は $t-1$ 個以下」という条件を、二項係数 $\binom ds$ を $d$ の凸関数に延ばして Jensenの不等式 を当てることで辺の本数の上界に変える（その記事では、成分が $0$ か $1$ の行列で $1$ だけからなる $s\times t$ の部分行列をもたないものの $1$ の個数の上界をまず示し、グラフの形は隣接行列に当てて導いている）。

$K_{s,t}$ と $K_{t,s}$ は同型なので、$s\le t$ として使うと指数 $2-1/s$ が小さくなる。この上界の指数が最良かどうかは一般には分かっていない。$\operatorname{ex}(n,K_{s,t})\ge cn^{2-1/s}$ となる定数 $c>0$ があるという予想は、$K_{2,t}$・$K_{3,t}$ と、$t$ が $s$ に比べて十分大きい場合に正しいことが知られており、最初の未解決の場合は $K_{4,4}$ である（Zha23 予想 1.4.4、p. 24）。

Turán密度は0か1/2以上

辺をもち孤立した頂点をもたないグラフ $H$ について、次が成り立つ。

  1. $H$ が二部グラフで、二部分割の部の大きさが $s\le t$ なら、$\operatorname{ex}(n,H)\le\frac12(t-1)^{1/s}n^{2-1/s}+\frac12(s-1)n$ であり、$\pi(H)=0$ である。
  2. $H$ が二部グラフでなければ $\pi(H)\ge1/2$ である。
    したがって $0<\pi(H)<1/2$ となる $H$ は存在しない。
完全二部グラフに埋め込む
  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$

thm-ext-ess まで使えば、Turán 密度のとりうる値はちょうど $0,\frac12,\frac23,\frac34,\dots$ である。

長さ 4 の閉路

$C_4=K_{2,2}$ の場合は、上界と同じ次数 $n^{3/2}$ の構成がある。

長さ4の閉路を含まないグラフの辺の本数

$C_4$ を含まない $n$ 頂点のグラフ $G$ について
$$ e(G)\le\frac n4\bigl(1+\sqrt{4n-3}\bigr) $$
である。

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

詳細

頂点 $v$ と、$N(v)$ の相異なる 2 頂点からなる部分集合 $\{u,w\}$ の組 $(v,\{u,w\})$ の個数を $X$ とする。$v$ を先に決めると $X=\sum_v\binom{d(v)}2$ である。$\{u,w\}$ を先に決めると $v$ は $u,w$ の共通の隣接頂点であり、共通の隣接頂点が 2 個 $v,v'$ あれば $u,v,w,v'$ が $C_4$ をなすので、$v$ は高々 1 個である。よって $X\le\binom n2$ である。Cauchy–Schwarzの不等式により $\sum_vd(v)^2\ge(2m)^2/n$ なので、$X=\frac12\bigl(\sum_vd(v)^2-2m\bigr)\ge\frac12\bigl(\frac{4m^2}n-2m\bigr)$ である。よって $\frac{4m^2}n-2m\le n(n-1)$、すなわち $4m^2-2nm-n^2(n-1)\le0$ であり、$m$ についての 2 次不等式を解くと $m\le\frac{2n+\sqrt{4n^2+16n^2(n-1)}}8=\frac n4\bigl(1+\sqrt{4n-3}\bigr)$ である。$\square$

有限体の点と直線の接続グラフ

$p$ を素数とし、$\mathbb F_p$ を $p$ 元体とする。点の集合 $P:=\mathbb F_p^2$ と、直線 $y=ax+b$ を表す組の集合 $L:=\{(a,b)\mid a,b\in\mathbb F_p\}$ を頂点とし、点 $(x,y)$ と直線 $(a,b)$ を $y=ax+b$ のときに結んだ二部グラフ $I_p$ を考える。$I_p$ は $2p^2$ 個の頂点と $p^3$ 本の辺をもち、$C_4$ を含まない。

2 点を通る直線は 1 本

各直線 $(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$

長さ4の閉路の極値数の大きさ

$n\ge8$ のとき
$$ \frac1{64}\Bigl(\frac n2\Bigr)^{3/2}\le\operatorname{ex}(n,C_4)\le\frac12n^{3/2}+\frac n4 $$
である。

上界は 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 を使うことである。

詳細

$N:=\lfloor\sqrt{n/2}\rfloor$ とおくと、$n\ge8$ より $N\ge2$ なので $\lfloor N/2\rfloor\ge1$ である。Bertrand–Chebyshev の定理を $\lfloor N/2\rfloor$ に使うと、素数 $p$ で $\lfloor N/2\rfloor< p\le2\lfloor N/2\rfloor\le N$ となるものがある。$p\ge\lfloor N/2\rfloor+1>N/2$ であり、$N>\sqrt{n/2}-1\ge\frac12\sqrt{n/2}$（$\sqrt{n/2}\ge2$ による）なので $p>\frac14\sqrt{n/2}$ である。$2p^2\le2N^2\le n$ なので、$I_p$ に孤立した頂点を加えて $n$ 頂点にしたグラフは $C_4$ を含まず（prop-ext-monotone の 2 の証明）、$\operatorname{ex}(n,C_4)\ge p^3>\frac1{64}(n/2)^{3/2}$ である。$\square$

実際には $\operatorname{ex}(n,C_4)=\bigl(\frac12+o(1)\bigr)n^{3/2}$ である（Zha23 定理 1.10.1・系 1.10.2、p. 40）。上界は prop-ext-c4-upper から従い、下界は有限体の上の射影平面から作る極グラフによる。証明は Kővári–Sós–Turánの定理 の記事の定理「$K_{2,t}$ の極値数の大きさ」にある。

応用：平面の単位距離

平面上の相異なる $n$ 個の点のうち、距離がちょうど $1$ の点の組の個数は $\frac{\sqrt2}2n^{3/2}+\frac n2$ 以下である。点を頂点とし、距離 $1$ の 2 点を結んだグラフを考える。相異なる 2 点 $p,q$ の両方から距離 $1$ の点は、中心の異なる 2 つの単位円の共通部分にある。2 つの円の方程式の差をとると 1 次式になるので、共通部分は 1 本の直線と円の共通部分に含まれ、高々 2 点である。よってこのグラフは $K_{2,3}$ を含まず、thm-ext-kst を $s=2$、$t=3$ で使えばよい（Zha23 定理 1.4.8、p. 25 と同じ議論）。

例と反例

次の表の各行は、この記事の定理の仮定を 1 つだけ外したときに結論が成り立たなくなる例である。

外す条件反例成り立たなくなること
thm-ext-dichotomy の 1 の「$H$ が二部グラフ」$H=K_3$$\operatorname{ex}(n,H)=\lfloor n^2/4\rfloor$ で、$\pi(H)=0$ にならない
prop-ext-incidence の「$p$ が素数」$\mathbb Z/4\mathbb Z$ で同じように作ったグラフ$C_4$ を含まない
ex-ext-unit-distance の「平面上」4 次元空間の 2 つの直交する円の上の点単位距離の組が $\frac{\sqrt2}2n^{3/2}+\frac n2$ 以下
prop-ext-monotone の「孤立した頂点をもたない」1 本の辺と孤立した頂点 1 つからなる $H$$\operatorname{ex}(2,H)\le\operatorname{ex}(3,H)$
奇閉路の極値数が $\lfloor n^2/4\rfloor$ になるための「$n$ が十分大きい」$n=4$、$H=C_5$$\operatorname{ex}(4,C_5)=\lfloor16/4\rfloor$
反例の確かめ

1 行目：Mantelの定理。2 行目：$\mathbb Z/4\mathbb Z$ では $2\cdot2=0$ なので、2 点 $(0,0)$ と $(2,0)$ はどちらも直線 $y=0$ と直線 $y=2x$ の上にあり、この 2 点と 2 直線が $C_4$ をなす。$x_1-x_2=2$ で割れないことが prf-ext-incidence の破れる所である。3 行目：$a\ge1$ とし、相異なる角 $\theta_1,\dots,\theta_a$ と $\varphi_1,\dots,\varphi_a$ について、$\mathbb R^4$ の $2a$ 個の点 $\frac1{\sqrt2}(\cos\theta_j,\sin\theta_j,0,0)$ と $\frac1{\sqrt2}(0,0,\cos\varphi_k,\sin\varphi_k)$ をとる。前者と後者の点は直交する長さ $\frac1{\sqrt2}$ のベクトルなので、距離の 2 乗は $\frac12+\frac12=1$ である。よって $n=2a$ 個の点に $a^2=n^2/4$ 組の単位距離があり、$n\ge16$ では $\frac{\sqrt2}2n^{3/2}+\frac n2$ を超える（$n=16$ で $64>\frac{\sqrt2}2\cdot64+8$）。平面の議論が破れるのは、$\mathbb R^4$ では 2 つの単位球面の共通部分が無限集合になりうるためである。4 行目：$\operatorname{ex}(2,H)=1$（2 頂点のグラフは 3 頂点の $H$ を含まない）だが、3 頂点のグラフは辺を 1 本でももつとその辺と残りの頂点で $H$ を含むので $\operatorname{ex}(3,H)=0$ である。5 行目：$K_4$ は 4 頂点しかないので $C_5$ を含まず、$\operatorname{ex}(4,C_5)=6>4$ である。

補足

ほかの問いと方法
  • 偶数の長さの閉路：$k\ge2$ について $\operatorname{ex}(n,C_{2k})\le Cn^{1+1/k}$ となる定数 $C$ がある（Bondy–Simonovits。Zha23 定理 1.6.3、p. 32 に主張がある。この記事では証明しない）。$k=2$ では cor-ext-c4-order がこれに当たる。
  • 奇数の長さの閉路：$n$ が十分大きければ $\operatorname{ex}(n,C_{2k+1})=\lfloor n^2/4\rfloor$ である（Zha23 定理 1.6.1、p. 31。主張のみ）。
  • 超飽和と安定性：辺の本数が閾値 $(\pi(H)+\varepsilon)\binom n2$ を超えると $H$ が $n^{v(H)}$ の定数倍個現れる（Zha23 定理 1.3.4、p. 21）。三角形の場合の具体的な下界と、最大値に近いグラフが極値グラフに近いことは Mantelの定理 の記事で証明した。
  • 正則性の方法：Szemerédiの正則性補題（Zha23 定理 2.1.9、p. 56）は、大きなグラフの頂点を有限個の組に分け、ほとんどの組の間で辺がランダムのように分布するようにできることを述べる。ここから、三角形が少ないグラフは少数の辺を除いて三角形をなくせるという三角形除去補題（同書 定理 2.3.1、p. 65）が得られ、3 項の等差数列に関する Roth の定理（同書 定理 2.4.1、p. 67）が導かれる。三角形除去補題とこの Roth の定理は、どちらもその記事で証明している。
  • 超グラフ：$r$ 元集合を辺とする超グラフにも極値数と Turán 密度が同じように定まるが、4 頂点の完全 3 一様超グラフの Turán 密度すら決まっていない（Zha23 注意 1.3.3、pp. 20–21）。
Ramsey理論との関係

極値グラフ理論は「辺の割合がどれだけあれば部分構造が現れるか」を問い、Ramsey理論は「どう塗り分けてもどれかの色に部分構造が現れるか」を問う。$K_N$ の辺を $r$ 色に塗れば、ある色の辺は $\binom N2/r$ 本以上あるので、$\pi(H)<1/r$ なら $N$ が大きいときその色に $H$ が現れる。たとえば二部グラフ $H$ は $\pi(H)=0$ なので、何色で塗っても $N$ が大きければ単色の $H$ が現れる。三角形は $\pi(K_3)=1/2$ なので、この議論では 2 色の場合は扱えず、Ramseyの定理のような別の議論が要る。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
極値グラフ理論