# 極値グラフ理論と Ramsey 理論：Turán の定理・Ramsey の定理・確率的方法 > 禁止された部分グラフをもたないグラフの辺数の最大値（Mantel・Turán・Kővári–Sós–Turán）、彩色に必ず現れる単色の構造（Ramsey・Schur）、数え上げによる存在証明（Erdős の下界、内周も彩色数も大きいグラフ）を証明する。 > https://rikai.mugen-giken.com/mathematics/graph-theory/extremal-and-ramsey ## 0. この記事の要点 この章は、点と線でできた図（グラフ）について、次の 2 つの素朴な問いを扱います。「ある形を作らないように線を引くと、何本まで引けるか」と「点の間の線を何色かで塗り分けても、同じ色だけでできた決まった形がどうしても現れてしまうのはいつか」です。6 人が集まれば、互いに知り合いの 3 人か、互いに知らない 3 人が必ずいる、という話が後者の入口です。読み終えると、この 2 つの問いに答える定理を証明でき、さらに「作り方は分からないが、数え上げれば存在は言える」という考え方（確率的方法）を使えるようになります。 - $K_{r+1}$ を含まない $n$ 頂点グラフの辺の数は、頂点を $r$ 個のほぼ同じ大きさの組に分け、異なる組の頂点をすべて結んだ **Turán グラフ** $T_r(n)$ で最大になり、最大を達成するのはこのグラフだけです（**Turán の定理**）。$r=2$ の場合が「三角形を含まなければ辺は $n^2/4$ 本以下」という **Mantel の定理**です。 - 禁止するグラフが二部グラフのときは、最大の辺数の桁が下がります。$K_{s,t}$ を含まないグラフの辺は $O(n^{2-1/s})$ 本です（**Kővári–Sós–Turán の定理**）。$C_4$ の場合の $n^{3/2}$ という桁は、有限体上の平面の点と直線の接続グラフで達成されます。 - 十分大きな完全グラフの辺を 2 色でどう塗っても、単色の $K_s$ か $K_t$ が現れます（**Ramsey の定理**）。色の数を増やしても、辺の代わりに $k$ 元部分集合を塗っても、無限集合の上でも成り立ちます。 - 小さい場合の正確な値は $R(3,3)=6$、$R(3,4)=9$、$R(4,4)=18$ です。18 の下界は、位数 17 の Paley グラフが与えます。 - 「条件を満たさない対象の個数を数えると全体より少ない」ことから存在を示す**確率的方法**で、$R(k,k)>2^{k/2}$（Erdős の下界）と、「どんな $g,k$ に対しても、長さ $g$ 以下の閉路をもたず彩色数が $k$ より大きいグラフがある」こと（Erdős の定理）を証明します。 - Ramsey の定理から、整数の有限彩色には $x+y=z$ の単色解があること（**Schur の定理**）と、平面上の十分多くの点は凸 $n$ 角形の頂点を含むこと（**Erdős–Szekeres の定理**）が従います。 ## 1. 動機 この章の 2 つの主題は、同じ問いの表と裏です。 **極値問題**は「ある構造を避け続けるには、どこまで疎でなければならないか」を問います。三角形を含まないグラフは、辺を何本までもてるか。答えは、頂点を 2 組に分けて組の間だけを結ぶ、という単純な構成が最良だというものです。 **Ramsey 理論**は「どう分けても、ある構造は避けられない」ことを主張します。6 人が集まれば、互いに知り合いの 3 人か、互いに知らない 3 人が必ずいます。完全な無秩序はありえず、十分大きな対象は必ず秩序だった部分を含みます。 どちらの主題でも、上からの評価（これ以上は無理）と下からの評価（ここまではできる）の両方が要ります。下からの評価には具体的な構成が必要ですが、Ramsey 数については、よい構成を作るのが極端に難しいことが知られています。ここで登場するのが確率的方法です。対象をでたらめに選んだとき、条件を満たす確率が正であれば、条件を満たす対象は存在します。存在だけを主張し、作り方は教えてくれませんが、多くの問題で、知られている最良の評価を与えます。 この章では、確率を有限集合の上の重み付きの数え上げとして扱います。測度論は使いません。必要な事実は、期待値の線形性と Markov の不等式だけです。 ## 2. 準備：記法と、有限集合の上の確率 グラフは有限・単純・無向とし、記法は[道・閉路・木の章](/mathematics/graph-theory/paths-cycles-trees)に従います。$n=|V(G)|$、$m=|E(G)|$ です。独立数 $\alpha(G)$（）、クリーク数 $\omega(G)$ と彩色数 $\chi(G)$（）を使います。集合 $X$ の $k$ 元部分集合の全体を $[X]^k$、$[N]=\{1,\dots,N\}$ と書きます。二項係数 $\binom nk$ は $[n]$ の $k$ 元部分集合の個数です（）。 有限集合 $\Omega$ と、$w(\omega)\ge0$、$\sum_{\omega\in\Omega}w(\omega)=1$ を満たす重み $w$ の組を**有限確率空間**という。$A\subseteq\Omega$（**事象**）の**確率**を $\mathbb{P}(A)=\sum_{\omega\in A}w(\omega)$、関数 $X:\Omega\to\mathbb{R}$（**確率変数**）の**期待値**を $\mathbb{E}[X]=\sum_{\omega\in\Omega}X(\omega)w(\omega)$ と定める。すべての重みが $1/|\Omega|$ のとき**一様**であるといい、このとき $\mathbb{P}(A)=|A|/|\Omega|$ である。 これは、すべての部分集合を事象とする確率空間（）で、期待値は一般の定義（）の有限和の場合です。この章で使う性質は、有限和の計算だけで確かめられます。 有限確率空間 $(\Omega,w)$ について、次が成り立つ。 1. 事象 $A_1,\dots,A_r$ について $\mathbb{P}(A_1\cup\dots\cup A_r)\le\sum_i\mathbb{P}(A_i)$。 2. **（期待値の線形性）** 確率変数 $X_1,\dots,X_r$ について $\mathbb{E}[X_1+\dots+X_r]=\sum_i\mathbb{E}[X_i]$。事象 $A$ の指示関数 $\mathbf{1}_A$ について $\mathbb{E}[\mathbf{1}_A]=\mathbb{P}(A)$。 3. **（Markov の不等式）** $X\ge0$、$a>0$ ならば $\mathbb{P}(X\ge a)\le\mathbb{E}[X]/a$。 4. **（平均の原理）** $w(\omega)>0$ かつ $X(\omega)\ge\mathbb{E}[X]$ となる $\omega$ が存在する。 1: $\omega\in\bigcup_iA_i$ の重みは、右辺の和で 1 回以上数えられます。 2: $\sum_\omega\bigl(\sum_iX_i(\omega)\bigr)w(\omega)=\sum_i\sum_\omega X_i(\omega)w(\omega)$ は有限和の順序交換です。$\sum_\omega\mathbf{1}_A(\omega)w(\omega)=\sum_{\omega\in A}w(\omega)$ です。 3: $X\ge0$ なので $\mathbb{E}[X]\ge\sum_{\omega:X(\omega)\ge a}X(\omega)w(\omega)\ge a\,\mathbb{P}(X\ge a)$ です（一般の場合は ）。 4: 重みが正のすべての $\omega$ で $X(\omega)<\mathbb{E}[X]$ なら、$\mathbb{E}[X]=\sum_\omega X(\omega)w(\omega)<\mathbb{E}[X]\sum_\omega w(\omega)=\mathbb{E}[X]$ となって矛盾です。 $n\ge1$、$0\le p\le1$ とする。頂点集合 $[n]$ の上のグラフの全体（$2^{\binom n2}$ 個）を $\Omega$ とし、グラフ $G$ の重みを $$ w(G)=p^{|E(G)|}(1-p)^{\binom n2-|E(G)|} $$ と定めた有限確率空間を $G(n,p)$ と書く。$p=1/2$ のときは一様である。 $G(n,p)$ は有限確率空間である。さらに、$[n]$ の 2 元部分集合からなる互いに交わらない集合 $F_1,F_0$ について、「$F_1$ の組はすべて辺で、$F_0$ の組はどれも辺でない」という事象の確率は $p^{|F_1|}(1-p)^{|F_0|}$ である。 $F_1\cup F_0$ に入らない組の全体を $Q$、$q=|Q|$ とします。事象に属するグラフは、$Q$ の部分集合 $S$ によって $E(G)=F_1\cup S$ と一意に表せ、その重みは $p^{|F_1|}(1-p)^{|F_0|}\cdot p^{|S|}(1-p)^{q-|S|}$ です。$|S|=j$ の $S$ は $\binom qj$ 個あるので、二項定理（）から $$ \sum_{S\subseteq Q}p^{|S|}(1-p)^{q-|S|}=\sum_{j=0}^q\binom qjp^j(1-p)^{q-j}=(p+1-p)^q=1 $$ で、事象の確率は $p^{|F_1|}(1-p)^{|F_0|}$ です。$F_1=F_0=\varnothing$ とすれば、重みの総和が 1 であることが分かります。 補題は、異なる組が辺になるかどうかが独立（）であることを述べています。「各組について、確率 $p$ で表の出る硬貨を投げて辺にするかどうかを決める」という言い方を、重み付きの数え上げとして書いたものです。 ## 3. Mantel の定理と Turán の定理 ### 3.1. 極値数 グラフ $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)$ と書く。 $n=qr+s$（$0\le s $n$ 頂点の $r$ 部グラフの辺の数は $t_r(n)$ 以下で、等号が成り立つのは $T_r(n)$ と同型なときに限る。また $$ t_r(n)\le\Bigl(1-\frac1r\Bigr)\frac{n^2}{2} $$ であり、$n\ge r$ のとき $t_r(n)=t_r(n-r)+(n-r)(r-1)+\binom r2$ である。 組の大きさを $n_1,\dots,n_r$（和は $n$）とすると、辺の数は $e(n_1,\dots,n_r)=\sum_{i）から $n^2=\bigl(\sum_in_i\cdot1\bigr)^2\le r\sum_in_i^2$ なので、$t_r(n)\le\frac12(n^2-n^2/r)$ です。 漸化式を示します。$n\ge r$ なら $T_r(n)$ の組はどれも空でないので、各組から 1 頂点ずつ選んだ $r$ 頂点の集合 $A$ が取れます。$A$ はクリークで辺は $\binom r2$ 本、$A$ の外の $n-r$ 個の各頂点は $A$ のうち自分の組以外の $r-1$ 頂点と隣接し、$T_r(n)-A$ は組の大きさが 1 ずつ減った完全 $r$ 部グラフ、すなわち $T_r(n-r)$ です。 ### 3.2. Mantel の定理 三角形を含まない $n$ 頂点グラフの辺の数 $m$ は $m\le n^2/4$ を満たす。 辺 $uv$ を取ります。$u$ と $v$ に共通の隣接点があれば三角形ができるので、$N(u)$ と $N(v)$ は交わらず、$d(u)+d(v)\le n$ です。すべての辺について足すと、各頂点 $v$ の次数 $d(v)$ は $v$ に接続する $d(v)$ 本の辺で 1 回ずつ数えられるので $$ \sum_{v}d(v)^2=\sum_{uv\in E(G)}\bigl(d(u)+d(v)\bigr)\le mn $$ です。握手補題（）と Cauchy–Schwarz の不等式（）から $$ 4m^2=\Bigl(\sum_vd(v)\Bigr)^2\le n\sum_vd(v)^2\le mn^2 $$ で、$m>0$ なら $m\le n^2/4$ です。 ### 3.3. Turán の定理 $r\ge1$、$n\ge1$ とする。$K_{r+1}$ を含まない $n$ 頂点グラフ $G$ の辺の数は $t_r(n)$ 以下である。すなわち $\operatorname{ex}(n,K_{r+1})=t_r(n)$ である。等号が成り立つのは、$G$ が $T_r(n)$ と同型なときに限る。 2 通りの証明を与えます。第 1 の証明のねらいは、辺の数が最大のグラフを取り、頂点の「複製」で辺を増やせる状況をすべて排除していくと、完全多部グラフ（異なる組の頂点がすべて結ばれた形）しか残らない、と示すことです。「隣接しない」が推移的でないと複製で辺が増えるので、場合分けはその状況を一つずつ潰すためのものです。第 1 の証明は等号の場合まで扱い、第 2 の証明は不等式だけを帰納法で示します。 **第 1 の証明（Zykov の対称化）.** $K_{r+1}$ を含まない $n$ 頂点グラフのうち、辺の数が最大のものを $G$ とします。$G$ が完全 $r$ 部グラフであることを示せば、 から $|E(G)|\le t_r(n)$ で、等号は $G\cong T_r(n)$ のときに限ります。$T_r(n)$ 自身が $K_{r+1}$ を含まないので最大値は $t_r(n)$ であり、定理が従います。 *複製.* 頂点 $u$ の**複製**を足すとは、新しい頂点 $u'$ を足して、$u$ の隣接点のすべてと（そしてそれらだけと）結ぶことです。$u'$ と $u$ は隣接しません。複製を足しても $K_{r+1}$ はできません。$u'$ を含むクリークは $u$ を含まず、$u'$ を $u$ に取り替えてもクリークだからです。 *隣接しないという関係は推移的.* 相異なる 3 頂点 $u,v,w$ で、$u$ と $v$、$v$ と $w$ は隣接せず、$u$ と $w$ は隣接するものがあると仮定します。 - $d(v)|E(G)|$ となり、$G$ の最大性に反します。 - $d(v)）で $|E(G)|\le t_r(n)$ を示します。$n\le r$ なら $|E(G)|\le\binom n2=t_r(n)$ です。$n>r$ とし、$K_{r+1}$ を含まない $n$ 頂点グラフのうち辺の数が最大のものを $G$ とします。$G$ は $K_r$ を含みます。含まなければ、$G$ は完全グラフではない（$n>r$）ので隣接しない 2 頂点があり、それらを結ぶ辺を足しても $K_{r+1}$ はできず（できるなら、もとのグラフがその辺を除いた $K_{r+1}$、とくに $K_r$ を含みます）、最大性に反するからです。 $K_r$ をなす頂点集合 $A$ を取ります。$A$ の外の各頂点は、$A$ の頂点のうち高々 $r-1$ 個としか隣接しません（$r$ 個すべてと隣接すれば $K_{r+1}$ ができます）。$G-A$ は $K_{r+1}$ を含まない $n-r$ 頂点グラフなので、帰納法の仮定から辺は $t_r(n-r)$ 本以下です。よって、 の漸化式から $$ |E(G)|\le\binom r2+(n-r)(r-1)+t_r(n-r)=t_r(n) $$ です。 $T_3(10)$ の組の大きさは $4,3,3$ で、辺の数は $4\cdot3+4\cdot3+3\cdot3=33$ です。$K_4$ を含まない 10 頂点グラフの辺は 33 本以下で、34 本あれば必ず $K_4$ を含みます。 の式で確かめると、$\frac12(100-16-9-9)=33$ です。上界 $(1-\frac13)\cdot\frac{100}{2}=33.3\dots$ とも合っています。 $r=2$ では $T_2(n)$ は完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ で、$t_2(n)=\lfloor n^2/4\rfloor$ です。 は、 に「等号は均等な完全二部グラフだけ」という情報を付け加えます。 ### 3.4. 独立数の下界から どのグラフ $G$ についても $$ \alpha(G)\ge\sum_{v\in V(G)}\frac{1}{d(v)+1} $$ が成り立つ。 $\Omega$ を頂点の並べ方（全順序）$n!$ 通りの全体とし、一様な有限確率空間とします。並べ方 $\sigma$ に対し、自分のどの隣接点よりも前に並んでいる頂点の集合を $I_\sigma$ とします。$I_\sigma$ は独立集合です。隣接する $u,v$ がともに $I_\sigma$ に属せば、$u$ は $v$ より前で、$v$ は $u$ より前でなければならないからです。 頂点 $v$ を固定します。$v$ と隣接点を合わせた $d(v)+1$ 個の頂点のうち、どれがいちばん前に来るかは、対称性からどれも同じ個数の並べ方で起こります（$v$ と隣接点 $u$ の位置を入れ替える写像は、「$v$ がいちばん前」の並べ方と「$u$ がいちばん前」の並べ方の間の全単射です）。よって $\mathbb{P}(v\in I_\sigma)=1/(d(v)+1)$ です。$|I_\sigma|=\sum_v\mathbf{1}_{\{v\in I_\sigma\}}$ なので、 の 2 から $$ \mathbb{E}\bigl[|I_\sigma|\bigr]=\sum_v\frac1{d(v)+1} $$ で、同じ補題の 4 から、$|I_\sigma|$ がこの値以上になる $\sigma$ があります。 $K_{r+1}$ を含まない $n$ 頂点グラフの辺の数 $m$ は $m\le\bigl(1-\frac1r\bigr)\frac{n^2}{2}$ を満たす。 補グラフ $\overline G$ に を使います。$\overline G$ での $v$ の次数は $n-1-d(v)$ で、$\alpha(\overline G)=\omega(G)\le r$ なので $$ r\ge\sum_v\frac1{n-d(v)} $$ です。Cauchy–Schwarz の不等式（）を $a_v=\sqrt{n-d(v)}$、$b_v=1/\sqrt{n-d(v)}$ に使うと $$ n^2\le\Bigl(\sum_v(n-d(v))\Bigr)\Bigl(\sum_v\frac1{n-d(v)}\Bigr)\le(n^2-2m)\,r $$ で、$2m\le n^2-n^2/r$ です。 ## 4. 二部グラフを禁止する $K_{r+1}$ を禁止したときの極値数は $n^2$ の定数倍でした。禁止するグラフが二部グラフだと、事情が変わります。完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ はどの奇閉路も含まないので、二部グラフでない $H$ では $\operatorname{ex}(n,H)\ge\lfloor n^2/4\rfloor$ ですが、$H$ が二部グラフのときは、辺が $n^2$ の定数倍あると必ず $H$ が現れます。完全二部グラフ $K_{s,t}$ を含まないグラフの辺の数の最大値を求める問題は、行列の言葉での定式化から **Zarankiewicz の問題**と呼ばれます。 次の補題で現れる関数 $h_s$ は、定理の証明の中で「次数から数えた組の個数」を下から評価するための道具です。凸関数であることが分かれば、次数が不ぞろいな場合より全頂点の次数が平均に等しい場合のほうが個数が少ない、という Jensen の不等式が使え、本題の二重の数え上げに戻れます。補題は少し長いですが、凸性の確認だけが目的です。 整数 $s\ge1$ に対し、$h_s(x)=\bigl(\max(x-s+1,\,0)\bigr)^s$ とおく。 1. $h_s$ は $\mathbb{R}$ 上の凸関数である（）。 2. 整数 $d\ge0$ について $\binom ds\ge h_s(d)/s!$ である。 1: まず、$\varphi(u)=u^s$ が $[0,\infty)$ で単調増加かつ凸であることを、$s$ についての帰納法で示します。単調性は明らかです。$s=1$ では凸性の不等式は等号です。$u,w\ge0$、$0\le\lambda\le1$、$\mu=1-\lambda$ とし、$s$ で成り立つとすると $$ (\lambda u+\mu w)^{s+1}\le(\lambda u^s+\mu w^s)(\lambda u+\mu w)=\lambda^2u^{s+1}+\mu^2w^{s+1}+\lambda\mu(u^sw+w^su) $$ で、 $$ \lambda u^{s+1}+\mu w^{s+1}-\bigl(\lambda^2u^{s+1}+\mu^2w^{s+1}+\lambda\mu(u^sw+w^su)\bigr)=\lambda\mu\,(u^s-w^s)(u-w)\ge0 $$ です（$\lambda-\lambda^2=\mu-\mu^2=\lambda\mu$ を使いました）。よって $s+1$ でも凸です。 次に、$\psi(x)=\max(x-s+1,0)$ は凸です。$\ell(x)=x-s+1$ と $0$ はどちらも 1 次関数で $\psi$ 以下なので、$\ell(\lambda x+\mu y)=\lambda\ell(x)+\mu\ell(y)\le\lambda\psi(x)+\mu\psi(y)$、$0\le\lambda\psi(x)+\mu\psi(y)$ となり、大きいほうを取って $\psi(\lambda x+\mu y)\le\lambda\psi(x)+\mu\psi(y)$ です。 $h_s=\varphi\circ\psi$ について、$\varphi$ の単調性と凸性から $$ h_s(\lambda x+\mu y)\le\varphi\bigl(\lambda\psi(x)+\mu\psi(y)\bigr)\le\lambda h_s(x)+\mu h_s(y) $$ です。 2: $d\le s-1$ なら $h_s(d)=0$ です。$d\ge s$ なら、 から $\binom ds=\frac{d(d-1)\cdots(d-s+1)}{s!}$ で、分子の $s$ 個の因子はどれも $d-s+1>0$ 以上です。 $2\le s\le t$ とする。$K_{s,t}$ を含まない $n$ 頂点グラフの辺の数 $m$ は $$ m\le\frac12\Bigl((t-1)^{1/s}\,n^{2-1/s}+(s-1)\,n\Bigr) $$ を満たす。とくに $\operatorname{ex}(n,K_{s,t})=O(n^{2-1/s})$ である。 頂点 $v$ と $s$ 元集合 $S\subseteq N(v)$ の組 $(v,S)$ の個数 $M$ を 2 通りに数えます。 $v$ ごとに数えると $M=\sum_v\binom{d(v)}s$ です。$S$ ごとに数えると、$S$ のすべての頂点と隣接する頂点（$S$ の外にあります）は $t-1$ 個以下です。$t$ 個あれば、$S$ とそれらが $K_{s,t}$ をなすからです。よって $M\le(t-1)\binom ns\le(t-1)\,n^s/s!$ です。 平均次数を $\bar d=2m/n$ とします。 の 2 と、凸関数 $h_s$ に対する Jensen の不等式（。重みはすべて $1/n$）から $$ M\ge\frac1{s!}\sum_vh_s(d(v))\ge\frac n{s!}\,h_s(\bar d) $$ です。2 つの評価を合わせて $h_s(\bar d)\le(t-1)\,n^{s-1}$ を得ます。$\bar d\le s-1$ なら $m\le(s-1)n/2$ で、主張は成り立ちます。$\bar d>s-1$ なら $(\bar d-s+1)^s\le(t-1)n^{s-1}$ から $$ \bar d\le(t-1)^{1/s}\,n^{1-1/s}+s-1 $$ で、$m=n\bar d/2$ に代入すれば主張の不等式です。 $s=t=2$ のとき $K_{2,2}=C_4$ で、定理は $\operatorname{ex}(n,C_4)\le\frac12(n^{3/2}+n)$ を与えます。この場合は、少していねいに数えるともう少しよい評価が得られ、しかも桁 $n^{3/2}$ は実際に達成されます。 1. $C_4$ を含まない $n$ 頂点グラフの辺の数 $m$ は $m\le\dfrac n4\bigl(1+\sqrt{4n-3}\bigr)$ を満たす。 2. 素数 $p$ に対し、頂点 $2p^2$ 個、辺 $p^3$ 本の、$C_4$ を含まない二部グラフが存在する。したがって $\operatorname{ex}(2p^2,C_4)\ge p^3$ である。 1: 頂点 $v$ と、$v$ の相異なる 2 つの隣接点の組 $\{u,w\}$ の対の個数を数えます。$C_4$ を含まないので、2 頂点 $u,w$ の共通の隣接点は高々 1 個です（2 個あれば、それらと $u,w$ で $C_4$ ができます）。よって $$ \sum_v\binom{d(v)}2\le\binom n2,\qquad\text{すなわち}\qquad\sum_vd(v)^2-2m\le n(n-1) $$ です。 の証明と同じく Cauchy–Schwarz の不等式（）から $\sum_vd(v)^2\ge4m^2/n$ なので、$4m^2-2mn-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) $$ です。 2: $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ は体です（）。一方の側の頂点を「点」$(x,y)\in\mathbb{F}_p^2$、他方の側の頂点を「直線」$L_{a,b}=\{(x,y):y=ax+b\}$（$(a,b)\in\mathbb{F}_p^2$）とし、点が直線の上にあるとき結びます。頂点は $p^2+p^2$ 個です。各直線の上には、$x$ を決めるごとに 1 点、合わせて $p$ 点があるので、辺は $p^2\cdot p=p^3$ 本です。 二部グラフの長さ 4 の閉路は、相異なる 2 点と、その両方を通る相異なる 2 直線からなります。相異なる 2 直線 $L_{a,b},L_{a',b'}$ の共有点は $ax+b=a'x+b'$、すなわち $(a-a')x=b'-b$ の解から決まります。$a\ne a'$ なら、体では $a-a'$ で割れるので $x$ はただ 1 つで、共有点は 1 個です。$a=a'$ なら $b\ne b'$ で解はなく、共有点はありません。どちらにしても共有点は高々 1 個なので、$C_4$ は含まれません。 $n=2p^2$ のとき、2 の下界 $p^3=(n/2)^{3/2}\approx0.35\,n^{3/2}$ と 1 の上界 $\approx0.5\,n^{3/2}$ は、定数倍を除いて一致します。無限遠の点と直線を補った射影平面を使い、点と直線を同一視する工夫（極性）をすると、定数も $1/2$ に合わせられます。有限体上の射影平面は[有限幾何とデザインの章](/mathematics/finite-fields-coding/finite-geometry-designs)で扱います。 一般のグラフ $H$ に対する極値数の主要項は、彩色数だけで決まります。$\chi(H)=r+1\ge2$ ならば $$ \lim_{n\to\infty}\frac{\operatorname{ex}(n,H)}{\binom n2}=1-\frac1r $$ です（Erdős–Stone の定理、1946 年。この形に述べたのは Erdős と Simonovits です）。$H=K_{r+1}$ の場合が と の評価で、$r=1$（$H$ が二部グラフ）の場合が「$\operatorname{ex}(n,H)$ は $n^2$ より小さい桁」という の内容です。二部グラフの極値数の正確な桁は、$C_8$ や $K_{4,4}$ のような基本的な場合でも分かっていません。 Erdős–Stone の定理の現代的な証明は、**Szemerédi の正則化補題**を使います。これは、「どんな大きなグラフも、頂点を有界個の組に分ければ、ほとんどの組の間で辺がランダムグラフのように一様に分布する」という主張で、極値グラフ理論と加法的組合せ論の基本的な道具です。どちらの証明もこの章の分量を超えるので、主張だけを紹介します。本章の定理の証明には使いません。出典は参考文献の Diestel の教科書の第 7 章です。 ## 5. Ramsey の定理 ### 5.1. 2 色の場合 完全グラフ $K_N$ の辺を赤と青で塗ることは、$N$ 頂点のグラフ $G$ を 1 つ決めること（赤い辺を $G$ の辺とする）と同じです。赤い $K_s$ は $G$ のクリーク、青い $K_t$ は $G$ の独立集合です。 $s,t\ge1$ に対し、「$N$ 頂点のどんなグラフも、$s$ 頂点のクリークか $t$ 頂点の独立集合を含む」ような最小の $N$ を **Ramsey 数** $R(s,t)$ という（そのような $N$ が存在することは で示す）。 性質をもつ $N$ より大きい $N'$ も同じ性質をもちます（$N'$ 頂点のグラフの $N$ 頂点を取り出せばよい）。補グラフを考えれば $R(s,t)=R(t,s)$ です。1 頂点はクリークでも独立集合でもあるので $R(1,t)=R(s,1)=1$ です。$R(2,t)=t$ です（$t$ 頂点のグラフは、辺があれば 2 頂点のクリークを、なければ $t$ 頂点の独立集合を含み、$t-1$ 頂点の辺のないグラフはどちらも含みません）。 すべての $s,t\ge1$ について $R(s,t)$ は存在する。$s,t\ge2$ のとき $$ R(s,t)\le R(s-1,t)+R(s,t-1) $$ で、右辺の 2 項がともに偶数なら、不等号は真に成り立つ。また $$ R(s,t)\le\binom{s+t-2}{s-1} $$ である。 $s+t$ についての帰納法（）で、存在と 2 つの不等式を同時に示します。$s=1$ または $t=1$ のときは $R=1=\binom{s+t-2}{s-1}$ です。 $s,t\ge2$ とし、$a=R(s-1,t)$、$b=R(s,t-1)$ が存在するとします。$N=a+b$ 頂点のグラフ $G$ と頂点 $v$ を取ります。$v$ の隣接点の集合を $A$、$v$ 以外で $v$ と隣接しない頂点の集合を $B$ とすると、$|A|+|B|=a+b-1$ なので、$|A|\ge a$ か $|B|\ge b$ のどちらかが成り立ちます（どちらも成り立たなければ $|A|+|B|\le a+b-2$）。 - $|A|\ge a$ のとき、$G[A]$ は $s-1$ 頂点のクリークか $t$ 頂点の独立集合を含みます。前者なら $v$ を加えて $s$ 頂点のクリークです。 - $|B|\ge b$ のとき、$G[B]$ は $s$ 頂点のクリークか $t-1$ 頂点の独立集合を含みます。後者なら $v$ を加えて $t$ 頂点の独立集合です。 よって $R(s,t)$ は存在して $a+b$ 以下です。 $a,b$ がともに偶数のとき、$N=a+b-1$ 頂点のグラフ $G$ が、$s$ 頂点のクリークも $t$ 頂点の独立集合も含まないと仮定します。上の議論から、どの頂点 $v$ でも $|A|\le a-1$ かつ $|B|\le b-1$ で、$|A|+|B|=a+b-2$ なので、$d(v)=|A|=a-1$ です。次数の和は $(a+b-1)(a-1)$ で、奇数どうしの積なので奇数です。これは握手補題（）に反します。よって $R(s,t)\le a+b-1$ です。 二項係数による評価は、帰納法の仮定と Pascal の漸化式（）から $$ R(s,t)\le\binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}=\binom{s+t-2}{s-1} $$ です。 $R(3,3)\le R(2,3)+R(3,2)=3+3=6$ です。6 人が集まると、互いに知り合いの 3 人か、互いに知らない 3 人が必ずいます。証明をこの場合に書き下すと次のとおりです。1 人 $v$ に注目すると、残りの 5 人のうち、知り合いが 3 人以上いるか、知らない人が 3 人以上います。知り合いが 3 人いるとして、その 3 人の中に知り合いどうしの 2 人がいれば、$v$ と合わせて互いに知り合いの 3 人です。いなければ、その 3 人が互いに知らない 3 人です。 5 人では足りません。5 人を円卓に座らせ、隣の席の人とだけ知り合いだとすると（グラフ $C_5$）、知り合いの 3 人組（三角形）はなく、互いに知らない 3 人組もありません（円周上の 5 点から、どの 2 つも隣り合わない 3 点は選べません）。完全グラフ $K_5$ の辺の塗り分けとしては、五角形の辺を赤、対角線（星形）を青に塗ったものです。
### 5.2. 小さい Ramsey 数 下界には、クリークも独立集合も小さいグラフを具体的に作る必要があります。対称性の高い例が、有限体の[平方剰余](/mathematics/number-theory/quadratic-reciprocity#def-qr)（平方数として表せる数）から得られます。 $p$ を $p\equiv1\pmod4$ である素数とする。頂点集合を $\mathbb{Z}/p\mathbb{Z}$ とし、$x-y$ が $p$ を法として $0$ でない平方剰余であるとき $x$ と $y$ を結んだグラフを **Paley グラフ** $P_p$ という。 $p\equiv1\pmod4$ を素数とする。 1. $P_p$ の隣接関係は対称で、$P_p$ はグラフとして定まる。 2. $a\in\mathbb{Z}/p\mathbb{Z}$ と、$0$ でない平方剰余 $s$ に対し、$x\mapsto x+a$ と $x\mapsto sx$ は $P_p$ の自己同型である。 3. 平方非剰余 $t$ に対し、$x\mapsto tx$ は $P_p$ から補グラフ $\overline{P_p}$ への同型である。とくに $\omega(P_p)=\alpha(P_p)$ である。 Legendre 記号 $\bigl(\frac ap\bigr)$ は乗法的で、$p\equiv1\pmod4$ のとき $\bigl(\frac{-1}p\bigr)=1$ です（ の 1 と 3）。 1: $\bigl(\frac{y-x}p\bigr)=\bigl(\frac{-1}p\bigr)\bigl(\frac{x-y}p\bigr)=\bigl(\frac{x-y}p\bigr)$ なので、$x-y$ が平方剰余であることと $y-x$ が平方剰余であることは同値です。 2: $(x+a)-(y+a)=x-y$ です。また $\bigl(\frac{sx-sy}p\bigr)=\bigl(\frac sp\bigr)\bigl(\frac{x-y}p\bigr)=\bigl(\frac{x-y}p\bigr)$ です。どちらの写像も全単射（$s\not\equiv0$ は $p$ を法として可逆）で、隣接関係を保ちます。 3: $\bigl(\frac{tx-ty}p\bigr)=-\bigl(\frac{x-y}p\bigr)$ なので、$x\ne y$ について、$x,y$ が隣接することと $tx,ty$ が隣接しないことは同値です。この全単射でクリークは独立集合に、独立集合はクリークに写ります。 $R(3,3)=6$、$R(3,4)=9$、$R(4,4)=18$ である。 **上界.** から、$R(3,3)\le R(2,3)+R(3,2)=6$ です。$R(2,4)=4$ と $R(3,3)\le6$ について、$R(3,3)=6$（下で示す）なら 2 項とも偶数なので $R(3,4)\le4+6-1=9$ です。$R(4,4)\le R(3,4)+R(4,3)\le18$ です。 **$R(3,3)>5$.** 閉路 $C_5=v_1v_2v_3v_4v_5$ は長さ 5 の閉路だけからなるので三角形を含みません。3 頂点を選ぶと、選ばなかった 2 頂点を除いた残りは高々 2 本の道に分かれ、選んだ 3 頂点のうち 2 つは同じ道に入ります。その道の頂点はすべて選んだ頂点なので、道の上で隣り合う 2 頂点がともに選ばれていて、独立集合ではありません。よって $\alpha(C_5)\le2$ です。 **$R(3,4)>8$.** 頂点集合を $\mathbb{Z}/8\mathbb{Z}$ とし、差が $\pm1$ か $4$ の 2 頂点を結んだグラフ $G$ を考えます。三角形 $\{i,j,l\}$ があれば、差 $j-i$、$l-j$、$i-l$ は $\{1,4,7\}$ の元で、和は $8$ を法として $0$ です。$\{1,4,7\}$ から重複を許して 3 つ選んだ和は $3,6,9,9,12,15,12,15,18,21$ のどれかで、$8$ の倍数はありません。よって三角形はありません。独立集合 $I$ が 4 頂点をもつとします。差が $\pm1$ の 2 頂点を含まないので、$I$ の元を巡回順に並べたときの隣どうしの間隔はどれも 2 以上で、4 つの間隔の和は 8 なので、すべて 2 です。つまり $I$ は偶数全体 $\{0,2,4,6\}$ か奇数全体 $\{1,3,5,7\}$ ですが、前者は差が 4 の $0,4$ を、後者は $1,5$ を含みます。よって $\alpha(G)\le3$ です。 **$R(4,4)>17$.** Paley グラフ $P_{17}$ を考えます。$17$ を法とする $0$ でない平方剰余は、$1^2,\dots,8^2$ を計算して $$ Q=\{1,\ 2,\ 4,\ 8,\ 9,\ 13,\ 15,\ 16\} $$ です（$5^2=25\equiv8$、$6^2=36\equiv2$、$7^2=49\equiv15$、$8^2=64\equiv13$）。 $P_{17}$ が 4 頂点のクリーク $\{a,b,c,d\}$ をもつと仮定します。 の 2 の自己同型 $x\mapsto x-a$ で写すと、$0$ を含むクリーク $\{0,b',c',d'\}$ になります。$b'$ は $0$ と隣接するので平方剰余で、その逆元も平方剰余です（Legendre 記号の乗法性から $\bigl(\frac{b'}p\bigr)\bigl(\frac{b'^{-1}}p\bigr)=\bigl(\frac1p\bigr)=1$）。自己同型 $x\mapsto b'^{-1}x$ で写すと、$0$ と $1$ を含むクリーク $\{0,1,c'',d''\}$ になります。$c'',d''$ は $0$ とも $1$ とも隣接するので、$x\in Q$ かつ $x-1\in Q$ を満たします。$Q$ の元を順に調べると、$x-1$ は $0,1,3,7,8,12,14,15$ で、$Q$ に入るのは $x=2,9,16$ のときだけです。ところが、この 3 つの差 $9-2=7$、$16-2=14$、$16-9=7$ はどれも $Q$ に入らず、$c''$ と $d''$ は隣接できません。矛盾です。よって $\omega(P_{17})\le3$ で、 の 3 から $\alpha(P_{17})\le3$ です（$3$ は $17$ を法とする平方非剰余なので、$x\mapsto3x$ が補グラフへの同型です）。 $3$ が平方非剰余であることは、$Q$ に入っていないことから分かりますが、Euler の規準（）でも確かめられます。$3^2=9$、$3^4=81\equiv13$、$3^8\equiv169\equiv16\equiv-1\pmod{17}$ です。 知られている Ramsey 数はごくわずかです。$R(4,5)=25$ までは決定されていますが、$R(5,5)$ は、$43$ 以上であること（Exoo、1989 年）と、$46$ 以下であること（Angeltveit と McKay、2024 年のプレプリント。それ以前の上界は同じ著者による 2018 年の $48$）が示されたあとも、正確な値は分かっていません。 ## 6. 多色・超グラフ・無限への拡張と応用 ### 6.1. 超グラフ版 辺（2 元部分集合）の代わりに $k$ 元部分集合を、2 色の代わりに $c$ 色で塗ります。 次の証明のねらいは、$k-1$ の場合に帰着することです。点を小さい順に $a_1,a_2,\dots$ と選びながら、それより後ろの点を「$a_i$ を含む組の色の付き方が同じ」ものどうしにまとめて絞っていきます。すると、$(k-1)$ 元の組 $B$ に後ろの点を 1 つ足した $k$ 元の組の色が、足す点の選び方（$B$ の最大元より後ろなら何でもよい）によらなくなり、$k$ 元の組の塗り分けが $(k-1)$ 元の組の塗り分けとして読み直せます。$k=2$ なら、$a_i$ から後ろの点への辺の色が、絞り込んだあとはすべて同じ色になる、ということです。 $\chi:[X]^k\to[c]$ に対し、$Y\subseteq X$ が**単色**であるとは、$\chi$ が $[Y]^k$ の上で定数であることをいいます。 $k,c,n\ge1$ とする。ある $N$ が存在して、どんな写像 $\chi:[\,[N]\,]^k\to[c]$ に対しても、$n$ 元の単色な部分集合 $Y\subseteq[N]$ がある。そのような最小の $N$ を $R_k(n;c)$ と書く。 $k$ についての帰納法です。 **$k=1$.** $N=c(n-1)+1$ とします。$[N]$ の元の $c$ 色塗りでは、鳩の巣原理（ の 1）から、ある色の元が $n$ 個以上あります。 **$k\ge2$.** $k-1$ で成り立つとします。$ni$ なら $a_j\in S_{j-1}\subseteq S_i$ で、$a_j>a_i$ です。また、$(k-1)$ 元集合 $B\subseteq\{a_1,\dots,a_{T-1}\}$ の最大元が $a_i$ のとき、$\chi(B\cup\{a_j\})$ は $j>i$ によらず同じ値です（$a_j$ はすべて同値類 $S_i$ に属します）。この値を $\chi^*(B)$ と書きます（$i\le T-1$ なので、$j=T$ が取れます）。 *手順 2（帰納法の仮定を使う）.* $\chi^*$ は、$M=T-1$ 元集合 $\{a_1,\dots,a_{T-1}\}$ の $(k-1)$ 元部分集合の $c$ 色塗りです。$M=R_{k-1}(n;c)$ なので、$\chi^*$ について単色な $n$ 元集合 $Y\subseteq\{a_1,\dots,a_{T-1}\}$ があります。$Y$ の $k$ 元部分集合 $A$ を取り、その最大元を $a_j$、$B=A\setminus\{a_j\}$ とすると、$B$ の最大元は $a_j$ より前の $a_i$ なので $\chi(A)=\chi^*(B)$ で、これは $B$ によらない定数です。よって $Y$ は $\chi$ について単色です。 $k=2$、$c=2$ が前節の定理で、$R_2(n;2)=R(n,n)$ です。 $k,c\ge1$ とする。自然数全体 $\mathbb{N}$ の $k$ 元部分集合の $c$ 色塗り $\chi:[\mathbb{N}]^k\to[c]$ に対し、無限集合 $Y\subseteq\mathbb{N}$ で単色なものが存在する。 $k$ についての帰納法です。$k=1$ は、無限集合を有限個に分けるとどれかが無限集合である、という鳩の巣原理（ の 2）です。 $k\ge2$ とします。 の証明の手順 1 を、個数の勘定を「無限集合である」に替えて行います。$S_0=\mathbb{N}$ とし、無限集合 $S_{i-1}$ が決まったら、$a_i=\min S_{i-1}$ とし（）、$S_{i-1}\setminus\{a_i\}$ を同じ同値関係で分けます。同値類は有限個なので、無限集合である同値類があり、それを $S_i$ とします。こうして無限列 $a_1i$ によらない値 $\chi^*(B)$ です。 $a_i\mapsto i$ で $\{a_1,a_2,\dots\}$ を $\mathbb{N}$ と同一視すれば、$\chi^*$ は $[\mathbb{N}]^{k-1}$ の $c$ 色塗りです。帰納法の仮定から、$\chi^*$ について単色な無限集合 $Y\subseteq\{a_1,a_2,\dots\}$ があります。手順 2 と同じ理由で、$Y$ は $\chi$ について単色です。 無限版には数の評価が要らないので、証明は有限版より短くなります。逆に、有限版は「どれだけ大きければよいか」という量的な情報をもっています。 ### 6.2. Schur の定理 どの $c\ge1$ に対しても、ある $S$ が存在して、$[S]$ のどんな $c$ 色塗りにも、$x+y=z$ を満たす同じ色の $x,y,z\in[S]$（$x=y$ でもよい）がある。 $N=R_2(3;c)$（）、$S=N-1$ とします。$f:[S]\to[c]$ を任意の色塗りとし、$[N]$ の 2 元部分集合 $\{i,j\}$（$i Schur はこの定理を、「どんな $q$ に対しても、十分大きい素数 $p$ を法として $x^q+y^q\equiv z^q$ は $xyz\not\equiv0$ の解をもつ」ことを示すために使いました（1916 年）。Fermat の方程式を合同式で調べても矛盾は出ない、ということです。 ### 6.3. 凸位置にある点 平面の有限個の点が**一般の位置**にあるとは、どの 3 点も一直線上にないことをいいます。一般の位置にある点の集合 $S$ が**凸位置**にあるとは、どの点 $p\in S$ も残りの点の凸包 $\operatorname{conv}(S\setminus\{p\})$ に属さないことをいいます。凸位置にある $n$ 点は、凸 $n$ 角形の頂点です。凸位置にある集合の部分集合は凸位置にあります。 次の補題のうち、証明がいちばん長い 3 は、5 点があればその中に凸位置の 4 点があることを示します。直感的には、5 点のうち外側の三角形 $ABC$ の頂点になる 3 点と、その内側にある 2 点 $D,E$ の配置に分けて考えます。$D,E$ を通る直線は三角形の 3 頂点を 2 点と 1 点に分けるので、2 点の側の頂点と $D,E$ の 4 点が凸位置になります。
A B C D E ℓ
$S$ を、平面の一般の位置にある有限個の点の集合とする。 1. 点 $q$ が $\operatorname{conv}(S)$ に属せば、$q$ は $S$ の 3 個以下の点の凸包に属する。 2. $|S|\ge4$ で、$S$ のどの 4 点も凸位置にあれば、$S$ は凸位置にある。 3. $|S|=5$ ならば、$S$ は凸位置にある 4 点を含む。 1: $q=\sum_i\lambda_ip_i$（$p_i\in S$ は相異なり、$\lambda_i>0$、$\sum_i\lambda_i=1$）という表示のうち、使う点の個数 $r$ が最小のものを取ります。$r\ge4$ と仮定します。$p_2-p_1,\dots,p_r-p_1$ は平面の 3 個以上のベクトルなので線形従属で（）、すべては $0$ でない実数 $\mu_2,\dots,\mu_r$ で $\sum_{i\ge2}\mu_i(p_i-p_1)=0$ となるものがあります。$\mu_1=-\sum_{i\ge2}\mu_i$ とおくと、$\sum_i\mu_ip_i=0$、$\sum_i\mu_i=0$ で、$\mu_i$ のどれかは正です。$\tau=\min\{\lambda_i/\mu_i:\mu_i>0\}$ とし、$\lambda_i'=\lambda_i-\tau\mu_i$ とおくと、$\lambda_i'\ge0$、$\sum_i\lambda_i'=1$、$\sum_i\lambda_i'p_i=q$ で、少なくとも 1 つの $\lambda_i'$ は $0$ です。これは $r$ の最小性に反します。 2: $S$ が凸位置にないとすると、ある $p\in S$ が $\operatorname{conv}(S\setminus\{p\})$ に属します。1 から、$p$ は $S\setminus\{p\}$ の 3 個以下の点の凸包に属します。2 個以下の点の凸包（線分）に属せば 3 点が一直線上に並ぶので、ちょうど 3 点 $q_1,q_2,q_3$ の凸包に属します。このとき 4 点 $\{p,q_1,q_2,q_3\}$ は凸位置にありません。 3: $S$ の部分集合 $S'$ で $\operatorname{conv}(S')=\operatorname{conv}(S)$ となるもののうち、包含関係について極小なものを取ります。$S'$ は凸位置にあります（$p\in\operatorname{conv}(S'\setminus\{p\})$ なら $\operatorname{conv}(S'\setminus\{p\})=\operatorname{conv}(S')$ となって極小性に反します）。$|S'|\le2$ なら $S$ 全体が 1 本の線分に含まれて一般の位置に反するので、$|S'|\ge3$ です。$|S'|\ge4$ なら、$S'$ の 4 点が求めるものです。 $S'=\{A,B,C\}$ とします。残りの 2 点 $D,E$ は三角形 $T=\operatorname{conv}\{A,B,C\}$ に属します。$D$ と $E$ を通る直線を $\ell$ とします。一般の位置にあるので、$A,B,C$ は $\ell$ の上にありません。3 点がすべて $\ell$ の同じ側にあれば、$T$ は $\ell$ と交わらず、$D\in T\cap\ell$ に反します。よって、$\ell$ の一方の側にちょうど 2 点があります。それを $B,C$ とします。4 点 $B,C,D,E$ が凸位置にあることを示します。 - $D\notin\operatorname{conv}\{B,C,E\}$: $\ell$ からの符号付き距離を $\sigma$ とします（$\sigma$ は 1 次関数）。$\sigma(B),\sigma(C)$ は同符号で $0$ でなく、$\sigma(E)=0$ です。$\lambda B+\mu C+\nu E$（$\lambda,\mu,\nu\ge0$、和は 1）が $\ell$ の上にあるのは $\lambda\sigma(B)+\mu\sigma(C)=0$、すなわち $\lambda=\mu=0$ のときだけで、その点は $E$ です。$D$ は $\ell$ の上の $E$ と異なる点なので、この凸包に属しません。$E\notin\operatorname{conv}\{B,C,D\}$ も同様です。 - $B\notin\operatorname{conv}\{C,D,E\}$: $A,B,C$ は一直線上にないので、$T$ の点は $aA+bB+cC$（$a,b,c\ge0$、和は 1）とただ 1 通りに書けます（$B-A$ と $C-A$ が線形独立だからです）。この $b$ を「$B$ 座標」と呼びます。$B$ 座標は、$C$ では $0$、$D,E$ では 1 未満（$D,E\ne B$）です。$\lambda C+\mu D+\nu E$ の $B$ 座標は $\mu b_D+\nu b_E$ で、$\mu+\nu>0$ なら $\mu+\nu\le1$ より真に小さく、$\mu=\nu=0$ なら $0$ です。どちらにしても 1 ではないので、$B$ 座標が 1 である点 $B$ はこの凸包に属しません。$C\notin\operatorname{conv}\{B,D,E\}$ も同様です。 どの $n\ge3$ に対しても、ある $N$ が存在して、平面の一般の位置にあるどんな $N$ 点も、凸位置にある $n$ 点を含む。 $n\ge5$ としてよい（$n=3,4$ の場合は $n=5$ の場合から従います）。$N=R_4(n;2)$（）とし、一般の位置にある $N$ 点に $1,\dots,N$ の番号を付けます。4 点の組を、凸位置にあれば色 1、なければ色 2 で塗ります。$N$ の選び方から、単色な $n$ 点の集合 $Y$ があります。$n\ge5$ なので $Y$ から 5 点を選ぶと、 の 3 から凸位置にある 4 点を含みます。よって $Y$ の色は 2 ではなく 1 で、$Y$ のどの 4 点も凸位置にあります。 の 2 から、$Y$ は凸位置にあります。 「十分大きな対象は、どう分けても、決まった構造を単色でもつ」という形の定理を Ramsey 型の定理といいます。等差数列についての van der Waerden の定理（）、単調な部分列についての Erdős–Szekeres の定理（）がその例です。後者は、添字の組 $i からも（ずっと悪い評価で）従いますが、半順序集合の議論のほうが正確な値 $rs+1$ を与えます。 も同様で、Ramsey の定理による $N$ は実際に必要な数よりはるかに大きく、凸位置にある $n$ 点を保証する最小の $N$ は $2^{n-2}+1$ だろうと予想されています（$n\le6$ では正しいことが確かめられています）。この定理は、発見のいきさつから happy ending problem とも呼ばれます。 ## 7. 確率的方法 ### 7.1. Ramsey 数の下界 から $R(k,k)\le\binom{2k-2}{k-1}<4^k$ です。下からはどうでしょうか。Turán グラフのような素直な構成では、$k$ の多項式程度の頂点数しか達成できません。Erdős は 1947 年に、**構成せずに**指数関数的な下界を示しました。 $k\ge3$ のとき $R(k,k)>2^{k/2}$ である。 $n=\lfloor2^{k/2}\rfloor$ とし、一様な有限確率空間 $G(n,1/2)$（）を考えます。$[n]$ の $k$ 元部分集合 $K$ を固定すると、$K$ がクリークである確率は、$\binom k2$ 個の組がすべて辺である確率で、 から $2^{-\binom k2}$ です。$K$ が独立集合である確率も同じです。$k$ 元部分集合は $\binom nk$ 個あるので、 の 1 から $$ \mathbb{P}\bigl(k\text{ 頂点のクリークか独立集合がある}\bigr)\le2\binom nk2^{-\binom k2} $$ です。$\binom nk\le n^k/k!$、$n^k\le2^{k^2/2}$、$\binom k2=k^2/2-k/2$ なので、右辺は $$ \frac{2\cdot2^{k^2/2}\cdot2^{-k^2/2+k/2}}{k!}=\frac{2^{1+k/2}}{k!} $$ 以下です。この値は $k=3$ で $2^{5/2}/6=5.65\ldots/6<1$ で、$k$ を 1 増やすと $2^{1/2}/(k+1)<1$ 倍になるので、$k\ge3$ でつねに 1 未満です。 したがって、$k$ 頂点のクリークも独立集合もないグラフの集合は、確率が正で、空ではありません。$n$ 頂点のそのようなグラフがあるので、$R(k,k)\ge n+1>2^{k/2}$ です。 数え上げとして読めば、証明は次のことを言っています。$[n]$ 上のグラフ $2^{\binom n2}$ 個のうち、指定した $k$ 頂点がクリークか独立集合であるものは $2\cdot2^{\binom n2-\binom k2}$ 個で、$k$ 頂点の選び方すべてについて足しても全体の個数に届かない。だから、どの $k$ 頂点もクリークでも独立集合でもないグラフが残っている、ということです。 上界と合わせると $\sqrt2^{\,k} 同じ計算は、もっと強いことを示しています。$n\ge2$ とし、$x=\lceil2\log_2n\rceil+1$ とおきます。$G(n,1/2)$ で $x$ 頂点のクリークか独立集合がある確率は $$ 2\binom nx2^{-\binom x2}\le\frac2{x!}\bigl(n\,2^{-(x-1)/2}\bigr)^x\le\frac2{x!} $$ 以下です（$(x-1)/2\ge\log_2n$ なので $n2^{-(x-1)/2}\le1$）。$n=1024$ なら $x=21$ で、この確率は $2/21!<10^{-19}$ です。1024 頂点のグラフのほとんどすべては、21 頂点のクリークも独立集合ももちません。それなのに、そのようなグラフを 1 つ具体的に書き下すことは難しいのです。 ### 7.2. 内周も彩色数も大きいグラフ [彩色の章](/mathematics/graph-theory/graph-colouring)で、三角形を含まず彩色数がいくらでも大きいグラフを作りました（）。あの構成は長さ 4 の閉路を大量に含みます。短い閉路をまったく含まない（[内周](/mathematics/graph-theory/paths-cycles-trees#def-connected)、つまり最短の閉路の長さが大きい）グラフは、どの頂点のまわりも木のように見えます。木は 2 色で塗れるので、局所的には彩色数が 2 のグラフと区別がつきません。それでも全体の彩色数はいくらでも大きくできる、というのが次の定理です。彩色数は局所的な性質ではありません。 どの整数 $g\ge3$、$k\ge1$ に対しても、長さ $g$ 以下の閉路を含まず（すなわち内周が $g$ より大きく）、彩色数が $k$ より大きいグラフが存在する。 方針は次のとおりです。辺の少ないランダムグラフでは、短い閉路は頂点数に比べて少ししかなく、独立数も小さい。短い閉路から 1 頂点ずつ除けば、閉路は消え、頂点は半分以上残り、独立数は増えない。独立数が小さければ、彩色数は大きい（$\chi\ge n/\alpha$）。 **パラメータ.** $\theta=1/(2g)$ とし、整数 $n\ge(32gk)^{4g}$ を取ります（とくに $n\ge g^2$、$n\ge11$）。$p=n^{\theta-1}$ とおくと、$0 から $p^i$ です。$X$ は「その閉路が $G$ に含まれる」という事象の指示関数の和なので、 の 2 から $$ \mathbb{E}[X]\le\sum_{i=3}^g\frac{(np)^i}{6}=\sum_{i=3}^g\frac{n^{\theta i}}6\le\frac{g\,n^{\theta g}}6=\frac{g\sqrt n}6 $$ です（$n^\theta\ge1$ なので $n^{\theta i}\le n^{\theta g}$、$\theta g=1/2$）。Markov の不等式（同じ補題の 3）と $n\ge g^2$ から $$ \mathbb{P}\Bigl(X\ge\frac n2\Bigr)\le\frac{2\,\mathbb{E}[X]}n\le\frac g{3\sqrt n}\le\frac13 $$ です。 **手順 2（独立数は小さい）.** $x=\lceil3\ln n/p\rceil$ とおきます。$[n]$ の $x$ 元部分集合が独立集合である確率は、 から $(1-p)^{\binom x2}$ です。$e^u\ge1+u$（指数関数は凸で、$u=0$ での接線が $1+u$。、）に $u=-p$ を入れると $1-p\le e^{-p}$ です。よって $$ \mathbb{P}\bigl(\alpha(G)\ge x\bigr)\le\binom nx(1-p)^{\binom x2}\le n^x\,e^{-px(x-1)/2}=\bigl(n\,e^{-p(x-1)/2}\bigr)^x $$ です。$p(x-1)\ge3\ln n-p\ge3\ln n-1$ なので $$ n\,e^{-p(x-1)/2}\le n\cdot n^{-3/2}\cdot e^{1/2}=\frac{e^{1/2}}{\sqrt n}<\frac12 $$ です（$n\ge11$ のとき $\sqrt n>3.31$、$e^{1/2}<1.65$）。$x\ge1$ なので $\mathbb{P}(\alpha(G)\ge x)<1/2$ です。 **手順 3（両方を満たすグラフ）.** の 1 から、「$X\ge n/2$ または $\alpha\ge x$」の確率は $1/3+1/2<1$ 未満です。よって、$X(G)n/2$ です。$G^*$ は $G$ の誘導部分グラフなので、その閉路は $G$ の閉路で、長さ $g$ 以下のものは頂点を 1 つ失っているので残っていません。$G^*$ の独立集合は $G$ の独立集合なので $\alpha(G^*)\le\alpha(G)\le x-1$ です。 **手順 5（彩色数）.** の $\chi\ge n/\alpha$ から $$ \chi(G^*)\ge\frac{|G^*|}{\alpha(G^*)}>\frac{n}{2x} $$ です。$x\le3\ln n/p+1=3n^{1-\theta}\ln n+1\le4n^{1-\theta}\ln n$（$n^{1-\theta}\ln n\ge1$）なので、$\chi(G^*)>n^\theta/(8\ln n)$ です。$y>0$ について $\ln yu$ に $u=\ln y$ を入れる）なので、$\ln n=(2/\theta)\ln(n^{\theta/2})<(2/\theta)\,n^{\theta/2}$ で、 $$ \chi(G^*)>\frac{\theta\,n^{\theta/2}}{16}=\frac{n^{1/(4g)}}{32g}\ge k $$ です。最後の不等式は $n\ge(32gk)^{4g}$ によります。$G^*$ が求めるグラフです。 証明は、条件を 1 つずつ満たすのではなく、「ほぼ満たす」対象をまず取って、あとから手で直しています（手順 4）。この**改変法**は確率的方法の標準的な技法です。なお、この定理のグラフを具体的に構成することもできます（Lovász, 1968。のちに Ramanujan グラフによる構成も得られました）が、どれも証明はずっと長くなります。 ## 8. この先へ この章の 3 つの主題は、それぞれ大きな分野の入口です。 - **極値グラフ理論.** Turán の定理は「辺の密度が $1-1/r$ を超えれば $K_{r+1}$ が現れる」と読めます。一般のグラフ $H$ についての Erdős–Stone の定理、正則化補題とそこから従う除去補題（「三角形が少ないグラフは、少数の辺を除けば三角形がなくなる」）が次の段階です（）。 - **加法的組合せ論.** van der Waerden の定理（）は、整数を有限色に塗ると単色の長い等差数列が現れることを主張します。「どれかの色に」ではなく「密度が正の集合ならどれでも」長い等差数列を含むという Szemerédi の定理は、ちょうど Ramsey の定理に対する Turán の定理のような位置にあり、3 項の場合は三角形の除去補題から導けます。 - **ランダムグラフ.** $G(n,p)$ で $p$ を $n$ とともに動かすと、「三角形を含む」「連結である」といった性質が、ある $p$ の付近で急に成り立つようになります（しきい値）。この章で使ったのは期待値と Markov の不等式（1 次のモーメント）だけですが、分散を使う 2 次のモーメントの方法で、しきい値の反対側が調べられます。 ## 9. 演習 (1) $R(3,5)\le14$ を示せ。(2) $K_{17}$ の辺を 3 色でどう塗っても、単色の三角形があることを示せ。 (1) の漸化不等式と から $R(3,5)\le R(2,5)+R(3,4)=5+9=14$ です（実際には $R(3,5)=14$ であることが知られています）。 (2) 頂点 $v$ を取ります。$v$ から出る 16 本の辺は 3 色で塗られているので、鳩の巣原理から、ある色（赤とします）の辺が 6 本以上あります（どの色も 5 本以下なら合わせて 15 本以下です）。赤い辺で $v$ と結ばれた 6 頂点の集合を $A$ とします。$A$ の中に赤い辺 $ab$ があれば、$v,a,b$ が赤い三角形です。なければ、$A$ の 6 頂点の間の辺は残りの 2 色で塗られていて、$R(3,3)=6$（）からその 2 色のどちらかの単色三角形があります。 これは $R_2(3;3)\le17$ を示しています。実際には等号が成り立ちます（16 頂点で単色三角形のない 3 色塗りが、位数 16 の有限体を使って作れます）。 $\{1,2,3,4\}$ は、$x+y=z$ の単色解（$x=y$ も許す）がないように 2 色で塗れるが、$\{1,2,3,4,5\}$ は塗れないことを示せ。 $\{1,4\}$ を赤、$\{2,3\}$ を青に塗ります。赤の和は $1+1=2$、$1+4=5$、$4+4=8$ で、どれも赤い数（$1,4$）ではありません。青の和は $2+2=4$、$2+3=5$、$3+3=6$ で、どれも青い数（$2,3$）ではありません。 $\{1,\dots,5\}$ の 2 色塗りに単色解がないとします。$1$ を赤とします。$1+1=2$ なので $2$ は青です。$2+2=4$ なので $4$ は赤です。$1+3=4$ で $1,4$ が赤なので $3$ は青です。$5$ が赤なら $1+4=5$ が、青なら $2+3=5$ が単色解になります。矛盾です。 の $S$ として、$c=2$ では $5$ が最小です。 $G$ を三角形を含まないグラフとする。頂点に重み $x_v\ge0$（$\sum_vx_v=1$）を与え、$f(x)=\sum_{uv\in E(G)}x_ux_v$ とおく。$f(x)\le1/4$ を示し、そこから を導け。 重みが正の頂点の集合を $x$ の台と呼びます。 **台をクリークにできる.** 台が隣接しない 2 頂点 $u,v$ を含むとします。$s_u=\sum_{w\in N(u)}x_w$、$s_v=\sum_{w\in N(v)}x_w$ とおき、必要なら名前を入れ替えて $s_u\ge s_v$ とします。$u$ と $v$ は隣接しないので、$f$ の中で $x_u$ を含む項の和は $x_us_u$、$x_v$ を含む項の和は $x_vs_v$ で、この 2 つに共通の項はなく、$s_u,s_v$ は $x_u,x_v$ を含みません。$v$ の重みをすべて $u$ に移した重み $x'$（$x'_u=x_u+x_v$、$x'_v=0$、他は同じ）では、この部分が $(x_u+x_v)s_u$ になるので $$ f(x')-f(x)=(x_u+x_v)s_u-x_us_u-x_vs_v=x_v(s_u-s_v)\ge0 $$ です。台は 1 頂点減ります。これをくり返すと、有限回で、台がクリークで $f$ の値が減っていない重みに達します。 **クリークの上での値.** $G$ は三角形を含まないので、台は 2 頂点以下です。1 頂点なら $f=0$、隣接する 2 頂点 $u,v$ なら $f=x_ux_v\le\bigl(\tfrac{x_u+x_v}2\bigr)^2=\tfrac14$ です。よって、もとの $x$ についても $f(x)\le1/4$ です。 **Mantel の定理.** すべての頂点に重み $1/n$ を与えると $f=m/n^2$ なので、$m\le n^2/4$ です。 同じ議論を $K_{r+1}$ を含まないグラフに行うと、台は $r$ 頂点以下のクリークになり、$f\le\frac12\bigl(1-\frac1r\bigr)$、したがって $m\le\bigl(1-\frac1r\bigr)\frac{n^2}2$（）が得られます。 辺を 1 本以上もつ $n$ 頂点、$m$ 辺のグラフ $G$ は、最小次数が $m/n$（平均次数の半分）より大きい部分グラフを含むことを示せ。 次数が $m/n$ 以下の頂点がある限り、それを 1 つ除く、という操作をくり返します。1 回の操作で除かれる辺は $m/n$ 本以下です。 操作が頂点がなくなるまで続いたと仮定します。除いた頂点は $n$ 個で、最後に除いた頂点は、その時点で 1 頂点だけのグラフにあったので、除かれた辺は $0$ 本です。したがって除かれた辺の総数は $(n-1)\cdot m/n）で長い道や閉路が見つかるからです。たとえば、$m\ge(k-1)n$ ならば、最小次数が $k$ 以上の部分グラフがあり、$G$ は長さ $k$ 以上の道を含みます。 ## 参考文献 - R. Diestel, *Graph Theory*, 5th ed., Graduate Texts in Mathematics 173, Springer, 2017 — 第 7 章（極値グラフ理論、正則化補題）、第 9 章（Ramsey 理論）、第 11 章（ランダムグラフ）。 - N. Alon and J. H. Spencer, *The Probabilistic Method*, 4th ed., Wiley, 2016 — 第 1〜3 章（基本的な方法、期待値の線形性、改変法）。 - F. P. Ramsey, "On a problem of formal logic", *Proceedings of the London Mathematical Society* (2) 30 (1930), 264–286. - P. Erdős and G. Szekeres, "A combinatorial problem in geometry", *Compositio Mathematica* 2 (1935), 463–470. - P. Erdős, "Some remarks on the theory of graphs", *Bulletin of the American Mathematical Society* 53 (1947), 292–294 — $R(k,k)>2^{k/2}$ の証明。 - P. Erdős, "Graph theory and probability", *Canadian Journal of Mathematics* 11 (1959), 34–38 — 内周も彩色数も大きいグラフの存在。