Ramsey理論
概要
Ramsey理論（Ramsey theory）とは、十分大きな構造を有限個の組に分けると、どれか 1 つの組に規則的な部分構造が必ず残るという型の定理と、そこに現れる数の大きさを調べる分野である。中心にあるのは、自然数の無限集合の $m$ 元部分集合を有限個の色で塗ると無限の単色集合があるという無限Ramseyの定理で、$m$ に関する帰納法で示され、そこから塗り分けの列の極限をとる議論で有限版とRamsey数の存在が従う。整数の塗り分けについてのSchurの定理・van der Waerdenの定理・Hales–Jewettの定理、平面の点の凸多角形についてのErdős–Szekeresの定理もこの型に属する。塗り分けの代わりに割合を仮定する密度版や、Peano算術で証明できない Paris–Harrington の命題との関係もある。
6 人いれば、互いに知り合いの 3 人か互いに知り合いでない 3 人が必ずいる（Ramsey数 R(3,3)=6）。$1,2,\dots,9$ を 2 色に塗れば、同じ色の 3 項の等差数列が必ずある（van der Waerdenの定理）。$1,2,3,4,5$ を 2 色に塗れば、同じ色の $x,y$ と $x+y$（$x=y$ でもよい）が必ずある（Schurの定理(和のない集合)）。どれも「十分大きな構造をどう有限個の組に分けても、どれか 1 つの組に規則的な部分構造が残る」という形をしている。この型の定理を集め、その証明法と、定理に現れる数の大きさを調べる分野を Ramsey 理論（Ramsey theory）という。標語的には「完全な無秩序は存在しない」と言い表される。
この記事では、Ramsey 理論の中心にある集合の塗り分けの定理を、塗る部分集合の大きさ $m$ と色の個数 $r$ が一般の場合に証明する。無限集合の場合を $m$ に関する帰納法で示し、有限の場合を、塗り分けの列から極限の塗り分けを取り出す議論（コンパクト性の議論）で導く。2 元部分集合を 2 色で塗る場合と Ramsey 数の評価は Ramseyの定理 の記事で扱っている。次に、単調な部分列の存在や「大きな」単色集合の存在などの帰結を示し、整数の加法構造・幾何・密度・論理に広がる Ramsey 型の定理を見渡す。最後に、結論を強めると成り立たなくなる例を挙げる。
定義
集合 $X$ と正の整数 $m$ について、$X$ の $m$ 元部分集合全体を $\binom{X}{m}$ と書く（$[X]^m$ と書く文献も多い）。$[N]:=\{1,2,\dots,N\}$、$\mathbb N:=\{1,2,3,\dots\}$ とする。写像 $c\colon\binom{X}{m}\to\{1,\dots,r\}$ を $\binom{X}{m}$ の $r$ 色の塗り分け という。$m=1$ なら $X$ の元の塗り分け、$m=2$ なら $X$ を頂点とする完全グラフの辺の塗り分けである。
$c\colon\binom{X}{m}\to\{1,\dots,r\}$ を塗り分けとする。$H\subset X$ について、$c$ が $\binom{H}{m}$ の上で一定の値 $i$ をとるとき、$H$ を 色 $i$ の単色集合（homogeneous set）という。
正の整数 $N$、$m$、$h_1,\dots,h_r$ について、$\binom{[N]}{m}$ のどの $r$ 色の塗り分けにも、ある色 $i$ と、大きさ $h_i$ の色 $i$ の単色集合が存在することを
$$
N\to(h_1,\dots,h_r)^m
$$
と書く。$h_1=\cdots=h_r=h$ のときは $N\to(h)^m_r$ とも書く。$N\to(h_1,\dots,h_r)^m$ となる最小の $N$ が存在するとき、それを Ramsey 数 $R^{(m)}(h_1,\dots,h_r)$ という。
$N\to(h_1,\dots,h_r)^m$ なら $N+1\to(h_1,\dots,h_r)^m$ である。$\binom{[N+1]}{m}$ の塗り分けを $\binom{[N]}{m}$ に制限すればよい。また単色集合の部分集合は同じ色の単色集合なので、$h:=\max_ih_i$ について $N\to(h)^m_r$ なら $N\to(h_1,\dots,h_r)^m$ である。
$h_i< m$ となる $i$ があると、大きさ $h_i$ の集合は $m$ 元部分集合をもたないので色 $i$ の単色集合とみなされ、問題は自明になる。興味があるのは $h_i\ge m$ の場合である。
主定理
$m,r\ge1$ とし、$A\subset\mathbb N$ を無限集合、$c\colon\binom{A}{m}\to\{1,\dots,r\}$ を塗り分けとする。このとき、無限集合 $H\subset A$ で $c$ について単色なものが存在する。
$m$ に関する帰納法で示す。$m=1$ のとき、$c\colon A\to\{1,\dots,r\}$ について、鳩の巣原理 の命題「無限集合の鳩の巣原理」により、ある色 $i$ で $c^{-1}(i)$ は無限集合であり、これが求める $H$ である。
$m\ge1$ で主張が成り立つとし、$c\colon\binom{A}{m+1}\to\{1,\dots,r\}$ を塗り分けとする。数 $x_1< x_2<\cdots$、色 $\chi_1,\chi_2,\dots$、無限集合 $A=A_0\supset A_1\supset A_2\supset\cdots$ を順に次のように定める。$A_{i-1}$ が無限集合として定まったとき、$x_i:=\min A_{i-1}$ とし、$A_{i-1}\setminus\{x_i\}$ の $m$ 元部分集合 $F$ を
$$
c_i(F):=c\bigl(\{x_i\}\cup F\bigr)
$$
で塗る。帰納法の仮定により、無限集合 $A_i\subset A_{i-1}\setminus\{x_i\}$ で $c_i$ について単色なものがある。その色を $\chi_i$ とする。
$A_i$ の元はすべて $x_i=\min A_{i-1}$ より大きいので $x_i< x_{i+1}$ である。$i< j_1<\cdots< j_m$ のとき、各 $x_{j_k}$ は $A_{j_k-1}\subset A_i$ に属するので、$F:=\{x_{j_1},\dots,x_{j_m}\}\subset A_i$ であり、
$$
c\bigl(\{x_i,x_{j_1},\dots,x_{j_m}\}\bigr)=c_i(F)=\chi_i
$$
である。つまり $\{x_1,x_2,\dots\}$ の $m+1$ 元部分集合の色は、その最小元の添字 $i$ だけで決まる。色の列 $\chi_1,\chi_2,\dots$ に再び $m=1$ の場合を使うと、無限集合 $I\subset\mathbb N$ と色 $\chi$ で、$i\in I$ なら $\chi_i=\chi$ となるものがある。$H:=\{x_i\mid i\in I\}$ は無限集合であり、その $m+1$ 元部分集合の最小元を $x_i$（$i\in I$）とすると色は $\chi_i=\chi$ なので、$H$ は色 $\chi$ の単色集合である。$\square$
$m=2$ の場合は Ramseyの定理 の定理「無限 Ramsey の定理」で、上の証明はその議論を $m$ について繰り返したものである。
正の整数 $m,r$ と $h_1,\dots,h_r$ について、ある $N$ が存在して $N\to(h_1,\dots,h_r)^m$ が成り立つ。したがって Ramsey 数 $R^{(m)}(h_1,\dots,h_r)$ は存在する。
$h:=\max(h_1,\dots,h_r,m)$ について $N\to(h)^m_r$ となる $N$ があることを示せばよい（上の注意）。そのような $N$ がないと仮定する。各 $N\ge h$ について、大きさ $h$ の単色集合をもたない塗り分け $c_N\colon\binom{[N]}{m}\to\{1,\dots,r\}$ がある。
段 1（列の選び出し）。 $\binom{[k]}{m}$ の塗り分けは有限個しかない。無限集合 $M_0:=\{N\mid N\ge h\}$ から始めて、無限集合 $M_0\supset M_1\supset M_2\supset\cdots$ を次のように選ぶ。$M_{k-1}$ が定まったとき、$N\in M_{k-1}$、$N\ge k$ の $c_N$ を $\binom{[k]}{m}$ に制限したものは有限個の値しかとらないので、無限集合の鳩の巣原理により、同じ制限をもつ $N\ge k$ が無限個ある。それらの全体を $M_k$ とする。
段 2（極限の塗り分け）。 $F\in\binom{\mathbb N}{m}$ について $k:=\max F$ とし、$c(F):=c_N(F)$（$N\in M_k$）と定める。$M_k$ の $c_N$ は $\binom{[k]}{m}$ の上で一致するので、$c(F)$ は $N$ の選び方によらない。さらに $k\le k'$ なら $M_{k'}\subset M_k$ なので、$N\in M_{k'}$ について、$c_N$ と $c$ は $\binom{[k']}{m}$ の上で一致する。
段 3（矛盾）。 thm-rt-infinite により、$c$ について単色な無限集合 $H\subset\mathbb N$ がある。$H$ の小さいほうから $h$ 個の元の集合を $H'$、$k:=\max H'$ とし、$N\in M_k$ をとる。$c_N$ と $c$ は $\binom{[k]}{m}\supset\binom{H'}{m}$ の上で一致するので、$H'$ は $c_N$ について大きさ $h$ の単色集合である。これは $c_N$ の選び方に反する。$\square$
この証明は Ramsey 数の大きさについて何も教えない。$m=2$、$r=2$ では、Ramseyの定理 の記事が帰納法で $R(s,t)\le\binom{s+t-2}{s-1}$ を示し、数え上げで $R(k,k)>2^{k/2}$ を示している。
$r$ 色で $K_N$ の辺を塗るとき、単色の三角形が必ず現れる最小の $N$ を $R_r(3)$ とする（$=R^{(2)}(3,\dots,3)$）。Schurの定理(和のない集合) の補題「多色の単色三角形」により $R_r(3)\le\lfloor r!\,e\rfloor+1$ である。一方 $R_r(3)>2^r$ である。実際、$\{0,1\}^r$ の $2^r$ 個の 0-1 列を頂点とし、相異なる 2 列を、2 つが初めて異なる座標の番号 $i$ の色で塗る。3 辺が色 $i$ の三角形 $x,y,z$ があれば、3 つの列は最初の $i-1$ 個の座標が等しく、$i$ 番目の座標が互いに異なるが、$\{0,1\}$ に相異なる 3 つの値はないので矛盾する（Zha23 命題 0.1.12、p. 3）。$R_r(3)$ が $C^r$ 程度の上界をもつかどうかは未解決である（同書 未解決問題 0.1.13、p. 4）。
帰結
実数列 $(a_n)_{n\in\mathbb N}$ は、単調非減少な無限部分列か、狭義単調減少な無限部分列をもつ。
$i< j$ について、$\{i,j\}$ を $a_i\le a_j$ なら色 1、$a_i>a_j$ なら色 2 で塗る。thm-rt-infinite（$m=2$、$r=2$）により無限の単色集合 $H=\{i_1< i_2<\cdots\}$ がある。色 1 なら $a_{i_1}\le a_{i_2}\le\cdots$、色 2 なら $a_{i_1}>a_{i_2}>\cdots$ である。$\square$
有界な実数列に使えば、単調で有界な部分列は収束するので、Bolzano–Weierstrassの定理の別証明になる。有限の列についての量的な形が 鳩の巣原理 の定理「Erdős–Szekeres の定理」（$n^2+1$ 項の相異なる実数の列は長さ $n+1$ の単調部分列をもつ）である。
有限 Ramsey の定理の証明は、無限の場合からコンパクト性の議論で有限の主張を取り出した。同じ方法で、次の少し強い主張も示せる。集合 $S\subset\mathbb N$ が $\lvert S\rvert>\min S$ を満たすとき 大きい（large）という。
正の整数 $m,r$ と $n\ge m$ について、ある $N$ が存在して、$\{n,n+1,\dots,N\}$ の $m$ 元部分集合のどの $r$ 色の塗り分けにも、大きい単色集合がある。
要点：無限集合 $\{n,n+1,\dots\}$ の塗り分けには無限の単色集合 $H$ があり、その小さいほうから $\min H+1$ 個の元は大きい単色集合である。あとは prf-rt-finite と同じく、そのような $N$ がないとして悪い塗り分けの列から極限の塗り分けを作り、矛盾を導く。
詳細
主張が成り立たないとすると、各 $N\ge n$ について、$\{n,\dots,N\}$ の $m$ 元部分集合の塗り分け $c_N$ で大きい単色集合をもたないものがある。prf-rt-finite の段 1・段 2 と同じく、$c_N$ の列から、$\{n,n+1,\dots\}$ の $m$ 元部分集合の塗り分け $c$ で、各 $k$ について無限個の $N$ の $c_N$ と $\{n,\dots,k\}$ の上で一致するものを作る。thm-rt-infinite により $c$ の無限の単色集合 $H$ がある。$a:=\min H\ge n$ とし、$H$ の小さいほうから $a+1$ 個の元の集合を $S$、$k:=\max S$ とする。$\lvert S\rvert=a+1>\min S$ なので $S$ は大きく、$k$ について一致する $c_N$ についても $S$ は単色である。これは $c_N$ の選び方に反する。$\square$
cor-rt-large は有限の対象についての主張で、自然数の言葉で書けるが、Peano 算術からは証明できないことが知られている（Paris–Harrington。Hal12 p. 16 の系 2.6 と p. 22 の注。この記事では証明しない）。Peano算術で証明できない「自然な」組合せ論の命題の最初の例として知られる。上の証明は無限集合についての thm-rt-infinite を経由している。
Ramsey 型の定理の広がり
Ramsey 理論の定理は、塗り分ける対象と、探す部分構造によって分類できる。
| 対象 | 探す部分構造 | 定理 |
|---|---|---|
| 集合の $m$ 元部分集合 | 単色の部分集合 | thm-rt-infinite・thm-rt-finite、Ramseyの定理 |
| 平面の点（一般の位置） | 凸多角形をなす点 | Erdős–Szekeresの定理(凸多角形) |
| $1,\dots,N$ | $x+y=z$ | Schurの定理(和のない集合) |
| $1,\dots,N$ | 等差数列 | van der Waerdenの定理 |
| $\{1,\dots,n\}^\ell$ の点 | 組合せ論的な直線 | Hales–Jewett の定理 |
| $\mathbb N$ | 有限部分和がすべて同色の無限集合 | Hindman の定理 |
Hales–Jewett の定理（Hal12 定理 11.2、p. 246、証明 pp. 247–249）は、長さ $\ell$ の語の集合 $\{1,\dots,n\}^\ell$ を $r$ 色に塗ると、$\ell$ が十分大きければ、一部の座標を変数とし残りを定数とした語の族（変数に $1,\dots,n$ を代入した $n$ 個の語）が単色になることを述べ、van der Waerdenの定理はその系である（同書 p. 246）。Hindman の定理（同書 p. 23 の関連する結果 3。この記事では証明しない）は、$\mathbb N$ を有限個の色で塗ると、無限集合 $X$ で、$X$ の空でない有限部分集合の元の和がすべて同じ色になるものが存在することを述べる。
塗り分けの代わりに「大きい割合」を仮定する 密度版 もある。van der Waerdenの定理に対しては、正の上密度をもつ整数の部分集合は任意の長さの等差数列を含むという Szemerédi の定理がある（Zha23 定理 0.2.4、p. 6。3 項の場合が Roth の定理 0.2.3）。ただし、どんな構造にも密度版があるわけではない。三角形については、頂点の組の約半分を辺にしても三角形のないグラフがある（Mantelの定理）。辺の割合と部分構造の関係は極値グラフ理論で調べる。
例と反例
次の表の各行は、この記事の定理の仮定を 1 つだけ変えると結論が成り立たなくなる例である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-rt-infinite の「色が有限個」 | $\{x,y\}$ を $\max\{x,y\}$ で塗る | 3 元以上の単色集合がある |
| thm-rt-infinite の結論の「無限集合」を「順序が有理数と同じ集合」に強める | 下の $\mathbb Q$ の塗り分け | そのような単色集合がある |
| van der Waerdenの定理の「任意の長さ」を「無限の長さ」に強める | 下の区間ごとの塗り分け | 単色の無限等差数列がある |
| thm-rt-finite の「$N$ が十分大きい」 | $N=5$、$K_5$ の五角形の塗り分け | $5\to(3,3)^2$ |
| ex-rt-multicolor-triangle の「色の数 $r$ を固定」 | $2^r$ 頂点の塗り分け | $N$ が $r$ によらずに選べる |
1 行目は Ramseyの定理 の例「反例：色が無限にある場合」、4 行目は同じ記事の命題「6 人の問題」の証明、5 行目は ex-rt-multicolor-triangle による。
2 行目：$\mathbb Q$ の元を $q_1,q_2,\dots$ と番号付ける。$i< j$ について $\{q_i,q_j\}$ を、$q_i< q_j$ なら色 1、$q_i>q_j$ なら色 2 で塗る。色 1 の単色集合 $H$ では、番号の大小と値の大小が一致する。$H$ の順序が $\mathbb Q$ と同じなら、$H$ の元 $x$ より小さい $H$ の元の狭義減少列 $y_1>y_2>\cdots$ がとれるが、その番号は狭義に減少する自然数の無限列になり、矛盾する。色 2 では番号の大小と値の大小が逆なので、狭義増加列 $y_1< y_2<\cdots$ について同じ矛盾が出る（Hal12 p. 23 の関連する結果 5）。
3 行目：$\mathbb N$ を区間 $[k^2,(k+1)^2)$（$k=1,2,\dots$）に分け、$k$ が奇数の区間を色 1、偶数の区間を色 2 で塗る（$\mathbb Z$ についての Zha23 演習 0.2.2 の $\mathbb N$ 版）。初項 $a$、公差 $d\ge1$ の無限等差数列を考える。$k\ge d$ かつ $k^2>a$ なら、区間 $[k^2,(k+1)^2)$ は長さ $2k+1>d$ で初項より後ろにあるので、数列の項を少なくとも 1 つ含む。隣り合う 2 つのそのような区間は色が異なるので、数列は両方の色の項をもち、単色でない。
補足
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
