Turán's theorem

Turán's theorem はグラフに関する定理であり、Turán number $T(n,r+1,2)$ と $\text{ex}(n,K_{r+1})$ の値を与える。

Turán graph

定理の主張に重要な役割を果たすグラフを先に定義しておく。

定義$(V,E)$ をグラフとする。$V$ の分割 $V_1,\dots,V_r$ が存在して、この分割によって定まる $V$ 上の同値関係 $\sim$ に対して\[v\sim w \Rightarrow \{v,w\}\not\in E\]であるとき $(V,E)$ は$r$ 部グラフである。

定義$(V,E)$ をグラフとする。$V$ の分割 $V_1,\dots,V_r$ が存在して、この分割によって定まる $V$ 上の同値関係 $\sim$ に対して\[v\sim w \Leftrightarrow \{v,w\}\not\in E\tag{1}\]であるとき $(V,E)$ は完全 $r$ 部グラフである。このときの同値関係 $\sim$ を、この完全 $r$ 部グラフに付随する同値関係とよぶ。

ここで完全 $r$ 部グラフの特徴づけについて述べておく。完全 $r$ 部グラフ $(V,E)$ が与えられたとき、式1より付随する同値関係と分割は一意に定まる。また分割の要素数 $n_1,\dots,n_r$ が与えられると、式1を満たす分割をもつ完全 $r$ 部グラフが同型の違いを除いて一意に定まるので、そのグラフを $K_{n_1,\dots,n_r}$ と書く。

ここまではグラフ理論の各所で目にする対象の定義であるが、次に定義する Turán graph が今回の議論に特有なグラフである。

定義$n$, $r$ を正の整数とし、$V$ を $n$-元集合とし、$E$ を $\binom{V}{2}$ の部分集合とする。$V$ の分割 $V_1,\dots,V_r$ が存在して、任意の $i\in\{1,\dots,r\}$ に対して $\lfloor n/r\rfloor \leq |V_i| \leq \lceil n/r\rceil$ であって、任意の $v\in V_i$, $w\in V_j$ に対して\[i=j \Leftrightarrow \{v_i, v_j\} \not\in E\]であるとき、グラフ $(V,E)$ を Turán graph と呼び、$T_{n,r}$ と書く。

つまり $n$ 頂点の完全 $r$ 部グラフ $K_{\lfloor n/r\rfloor,\dots,\lfloor n/r\rfloor,\lceil n/r\rceil,\dots,\lceil n/r\rceil}$ が Turán graph であり、これは $n$, $r$ に対して (同型の違いを除いて) 一意に定まるので固有の表記として $T_{n,r}$ を与える。

この Turán graph の辺の個数があとあと大事になるので、その概数を得ておく。

補題Turán graph $T_{n,r}$ の辺の個数は高々\[\left(1-\frac{1}{r}\right)\frac{n^2}{2}\]である。

(証明) 除法の原理より $r$ 未満の非負整数 $b$ が一意に存在して\[n=a r+b,\\ a=\lfloor n/r \rfloor.\]$T_{n,r}$ の頂点集合を $V$ とし、辺集合を $E$ とすると、$V$ の分割 $V_1,\dots,V_r$ が存在して、任意の $i\in\{1,\dots,r\}$ に対して\[|V_i|=\left\{\begin{array}{ll} \lfloor n/r \rfloor+1 & \text{if $i\leq b$}\\\lfloor n/r \rfloor & \text{if $i\gt b$} \end{array}\right.\]であり、任意の $i,j\in\{1,\dots,r\}$, $v\in V_i$, $w\in V_j$ に対して\[i=j\Leftrightarrow \{v,w\}\not\in E.\]このとき、\begin{eqnarray}E&=& \{\{v,w\}\in \textstyle\binom{V}{2} \mid v\in V_i,w\in V_j,i\neq j\}\\ &=& \textstyle\binom{V}{2}\setminus \{\{v,w\}\in \textstyle\binom{V}{2} \mid v,w\in V_i\} \\ &=& \textstyle\binom{V}{2}\setminus(\binom{V_1}{2}\cup\dots\cup\binom{V_r}{2})\end{eqnarray}であり、$\binom{V_i}{2}$ 同士は共通元を持たず $\binom{V_1}{2}\cup\dots\cup\binom{V_r}{2}$ は $\binom{V}{2}$ の部分集合なので \begin{eqnarray}|E|&=& \textstyle|\binom{V}{2}|-(|\binom{V_1}{2}|+\dots+|\binom{V_r}{2}|)\\ &=&\textstyle \binom{n}{2}-b\binom{\lfloor n/r \rfloor+1}{2}-(r-b)\binom{\lfloor n/r \rfloor}{2} \\ &=& \frac{n(n-1)}{2}-b\frac{(a+1)(a+1-1)}{2}-(r-b)\frac{a(a-1)}{2} \\&=& \frac{n^2}{2}-\frac{b(a+1)^2}{2}-\frac{(r-b)a^2}{2}\\ &=&\left(1- \frac{a^2r+b+2ab}{n^2} \right)\frac{n^2}{2} \\ &\leq& \left(1- \frac{1}{r} \right)\frac{n^2}{2}\end{eqnarray}

Turán's theorem

証明は後にするとして、ひとまず定理の主張を述べておく。

定理頂点数が $n$ のグラフであって部分グラフとして完全グラフ $K_{r+1}$ を包含しないものの中で、辺の数が最大のものは $T_{n,r}$ である。

この定理で「グラフ $G$ が部分グラフとしてグラフ $H$ を包含しない」という表現があるが、今後はこれを「$G$ は $H$-free である」と言うことにする。

Turán's theorem から、以下の Turán number が得られる。\begin{eqnarray}\text{ex}(n,K_{r+1})&=& |E(T_{n,r})| \\ T(n,r+1,2)&=& {\textstyle \binom{n}{2}}-|E(T_{n,r})|\end{eqnarray}補題も使えばより単純な以下の不等式を得ることができる。\begin{eqnarray}\text{ex}(n,K_{r+1}) &\leq& \left(1-\frac{1}{r}\right)\frac{n^2}{2} \\ T(n,r+1,2)&\geq& \frac{n^2}{2r}-\frac{n}{2}\end{eqnarray}

Turán's theorem の証明

証明で利用するために、完全 $s$ 部グラフについて命題を得ておく。

命題$n$ を正の整数とし、$s$ を $n$ より小さい正の整数とする。任意の完全 $s$ 部グラフについて、それより辺の数が多い完全 $s+1$ 部グラフが存在する。

(証明) $G=(V,E)$ を完全 $s$ 部グラフとすると、$V$ のある分割 $V_1,\dots,V_s$ とそれを誘導する $V$ 上の同値関係 $\sim$ に対して、任意の $v,w\in V$ に対して\[\{v,w\}\in E \Leftrightarrow [v]_\sim\neq[w]_\sim\]である。ここで、$s\lt n$ から鳩の巣原理より、ある $i\in\{1,\dots,s\}$ について $|V_i|\geq 2$ である。そこである $a\in V_i$ を用いて、$E'$ を\[E'=E\cup\{\{a,x\} \mid x\in V_i\setminus\{a\}\}\]とすると、$(V,E')$ は独立集合列 $V_1\setminus\{a\},\dots,V_s\setminus\{a\}, \{a\}$ に分解できる完全 $s+1$ 部グラフとなり、この辺の個数 $|E'|$ は $|E|$ より大きい。

命題$G=(V,E)$ を $n$ 頂点の完全 $s$ 部グラフとし、それに付随する $V$ 上の同値関係を $\sim$ とする。$V_i,V_j\in V/\sim$ が存在して $|V_i|\leq |V_j|-2$ であるとき、$G$ より辺の数が多い $n$ 頂点完全 $s$ 部グラフが存在する。

(証明) 一般性を失うことなく $|V_1|\leq |V_2|-2$ であるとする。このとき $|V_2|\geq 3$ であるから、ある $a\in V_2$ を用いて\[E'=E\cup \{\{a,x\}\mid x\in V_2\setminus\{a\}\} \setminus \{\{a,x\} \mid x\in V_1 \} \]とすると、$(V,E')$ は独立集合列 $V_1\cup\{a\},V_2\setminus\{a\},V_3,\dots,V_s$ に分解できる完全 $s$ 部グラフとなり、この辺の個数 $|E'|$ は $|E|$ より大きい。

命題任意の $s$ 部グラフは $K_{s+1}$-free である。

(証明) $(V,E)$ を $s$ 部グラフとする。任意の $s+1$ 元部分集合 $S\subset V$ に対して、鳩の巣原理より異なる2つの頂点 $v,w\in S$ が存在して $\{v,w\}\not\in E$ であるので $(S,E\cap\binom{S}{2})$ は完全グラフにならない。したがって、$(V,E)$ は $K_{s+1}$ を部分グラフとして包含しない。

以上の命題を用いて、Turán's theorem を証明する。

(定理の証明) 頂点数 $n$ のグラフ $G=(V,E)$ が $K_{r+1}$-free な $n$ 頂点グラフの中で最大の辺の数をもつものと仮定して、$(V,E)$ について考察する。

まず、任意の $u,v,w\in V$ に対して $\{u,v\}\not\in E$, $\{v,w\}\not\in E$ であるとき $\{u,w\}\not\in E$ であることを背理法で示す。ある $u,v,w\in V$ に対して $\{u,v\}\not\in E$, $\{v,w\}\not\in E$, $\{u,w\}\in E$ と仮定する。ここで $d(v)\lt d(u)$ とすると $v$ を $u$ のコピーで置き換えることで、つまり新たな辺集合 $E''$ を任意の $e\in \binom{V}{2}$ に対して\begin{eqnarray}v\not\in e &\Rightarrow& [e\in E \Leftrightarrow e\in E''] \\ v\in e &\Rightarrow& [e\cup\{u\}\setminus\{v\}\in E \Leftrightarrow e\in E''] \\ \end{eqnarray}と定めることによって辺の数が $|E|$ より $d(u)-d(v)$ だけ多くて $K_{r+1}$-free なグラフ $(V,E'')$ を得られることになり $G$ の最大性に矛盾するので $d(v)\geq d(u)$。同様に $d(v)\geq d(w)$。このとき、$V'=V\setminus\{u,v,w\}$, $E'=E\cap\binom{V'}{2}$ として $G$ の部分グラフ $X=(V', E')$ を作ると\[|E|= |E'|+d(u)+d(v)+d(w)-1.\]ここで $G$ の $u$ と $w$ をそれぞれ $v$ のコピーで置き換えることで辺の数が $|E|$ より大きい\[|E'|+3d(v)\]である $K_{r+1}$-free なグラフを得られるので $G$ の最大性に矛盾する。したがって $\{u,v\}\not\in E$, $\{v,w\}\not\in E$, $\{u,w\}\in E$ を同時に満たす $u,v,w\in V$ は存在しない。

以上より $v,w\in V$ に対して二項関係 $v\sim w$ を $\{v,w\}\not\in E$ と定義するとこの二項関係は推移的である。反射律と対称律も明らかに満たすのでこの二項関係は同値関係であり、したがって $V$ は $\sim$ による同値類 $V_1,\dots,V_s$ に分割できて\[\{v,w\}\not\in E \Leftrightarrow v\sim w \]であるので、$(V,E)$ は完全 $s$ 部グラフである。$G$ が $K_{r+1}$-free であることから $s\leq r$ であり、これを満たす $n$ 頂点の完全 $s$ 部グラフの中で辺の数が最も多いのは命題, 命題, 命題より Turán graph $T_{n,r}$ である。

確率的手法を用いた Turán's theorem の証明

別の証明方法も記述しておく。ただしここで示す証明では $n$ が $r$ で割り切れるときについてのみ示され、$T_{n,r}$ と同数の辺を持つ $K_{r+1}$-free な $n$ 元グラフが $T_{n,r}$ しかないことは示されない。

ここでは補グラフに注目する。

命題$G=(V,E)$ が $K_{r+1}$-free であるとき、$G$ の補グラフ $(V, \binom{V}{2}\setminus E)$ は大きさが $r+1$ 以上の独立集合をもたない。

(証明) 対偶を示す。$G$ の補グラフ $(V, \binom{V}{2}\setminus E)$ が独立集合 $S$ を持ち $|S|=r+1$ であるとき、任意の異なる2頂点 $v,w\in S$ に対して\[\{v,w\}\not\in \textstyle\binom{V}{2}\setminus E\]であるから\[\{v,w\}\in E\]である。したがって $G$ の部分グラフ $(S,E\cap\binom{S}{2})$ は要素数が $r+1$ の完全グラフであり、$G$ は $K_{r+1}$-free ではない。

この命題から、ある程度の大きさの独立集合を持つかどうかが定理の主張に深くかかわることがわかる。そこで、どれくらいの大きさの独立集合を持つかどうかがわかる次の補題を確率的手法で証明する。実質的にこの補題が証明の主な部分である。

補題グラフ $G=(V,E)$ は大きさが少なくとも\[\frac{|V|}{2|E|/|V| + 1}\]である独立集合を持つ。

(証明) ランダムに独立集合 $S$ を構成したときの大きさ $|S|$ の平均値が $\frac{|V|}{2|E|/|V| + 1}$ 以上であることを示し、平均値の原理より平均値以上の大きさを持つ $S$ ができる確率が0でないと結論付ける。

全単射 $f:\{1,\dots,|V|\}\to V$ を一様ランダムに定め、$i$ を 1 から 1 ずつ増やしながら、$f(i)$ の近傍が1つも $S$ に属すると定められていないとき、$f(i)\in S$ と定め、すでに近傍が $S$ に属しているなら $f(i)\not\in S$ と定める操作を繰り返す。この方法でできあがる $S$ は明らかに独立集合である。

ここで任意の $v\in V$ に対して、$v\in S$ である事象は $f$ によって定められた全順序において $v=\min N(v)$ となる事象であり、最小値へのなりやすさに頂点毎の差異はないので、その確率は\[\Pr(v\in S)=\frac{1}{d(v)+1}\]である。確率変数 $X_v$ の値を\[X_v = \left\{\begin{array}{ll} 0 & \text{if $v\not\in S$} \\ 1 & \text{if $v\in S$} \end{array}\right.\]と定めると\[|S|=\sum_{v\in V} X_v\]だから期待値の線形性より\begin{eqnarray}\mathbb{E}(|S|)&=& \mathbb{E}\left(\sum_{v\in V} X_v\right)\\ &=& \sum_{v\in V} \mathbb{E}(X_v)\\ &=& \sum_{v\in V} \frac{1}{d(v)+1} \end{eqnarray}であり、関数 $x\mapsto \frac{1}{x+1}$ は凸関数だから $\sum d(v)=2|E|$ より \begin{eqnarray}\mathbb{E}(|S|)&\geq& \sum_{v\in V}\frac{1}{2|E|/|V|+1} \\ &=& \frac{|V|}{2|E|/|V|+1} \end{eqnarray}

これを用いて $T_{n,r}$ より多く辺を持つ $n$ 元グラフが $K_{r+1}$-free でないことを示す。$T_{n,r}$ が $K_{r+1}$-free であることは命題ですでに示されているので省略する。

(定理の証明) $r|n$ とし、$n$ を $r$ で割った商を $a$ とし、$G=(V,E)$ を頂点数 $n$ のグラフとし、$|E|$ が $T_{n,r}$ の辺の個数 $e(T_{n,r})$ より大きいとする。このとき $G$ の補グラフ $(V,\binom{V}{2}\setminus E)$ の辺の個数を $m$ とすると、補題の証明の中で明らかにした $e(T_{n,r})$ の値を用いて\begin{eqnarray}m &\leq& \textstyle\binom{n}{2} - e(T_{n,r})-1 \\ &=& \frac{n(n-1)}{2}-\left(1- \frac{a^2r}{n^2} \right)\frac{n^2}{2}-1\\ &=& \frac{a^2r-n}{2}-1 \end{eqnarray}となり、したがって\begin{eqnarray}\frac{n^2}{2m+n} &\geq& \frac{n^2}{a^2r-2}\\ &\gt& \frac{n^2}{a^2r} \\ &=& r\end{eqnarray}であるので補題より $G$ の補グラフは $r+1$ 以上の大きさを持つ独立集合を持つ。したがって命題より $G$ は $K_{r+1}$-free ではない。

本当は $n$ が $r$ で割り切れないときについても証明したいところだが、同じ方法で臨むと\begin{eqnarray}m &\leq& \textstyle\binom{n}{2} - e(T_{n,r})-1 \\ &=& \frac{n(n-1)}{2}-\left(1- \frac{a^2r+b+2ab}{n^2} \right)\frac{n^2}{2}-1\\ &=& \frac{a^2r+b+2ab-n}{2}-1 \end{eqnarray}より\begin{eqnarray}\frac{n^2}{2m+n} &\geq& \frac{n^2}{a^2r+b+2ab-2} \end{eqnarray}となるが、必ずしも $\frac{n^2}{a^2r+b+2ab-2}$ が $r$ を超えない ($n=23$, $r=10$ のときが反例) ので補題を使っても大きさ $r+1$ 以上の大きさの独立集合があると断言できない。

数学  2018/06/18  k.izumi