Ramseyの定理

1. 赤と青を入れ替えると、$K_n$ の 2 色塗り分けの全体はそれ自身に全単射で移り、赤い $K_s$ か青い $K_t$ があることは、入れ替えた塗り分けに青い $K_s$ か赤い $K_t$ があることに移る。よって $n$ が $(s,t)$ 性質をもつことと $(t,s)$ 性質をもつことは同値である。
2. 1 点は赤い $K_1$ なので、$n=1$ は $(1,t)$ 性質をもち、$R(1,t)=1$ である。1 と同様に $R(s,1)=1$ である。
3. $K_t$ の塗り分けで赤い辺が 1 本でもあれば、その両端が赤い $K_2$ であり、赤い辺がなければ全体が青い $K_t$ である。よって $t$ は $(2,t)$ 性質をもつ。$t\geq2$ のとき、$K_{t-1}$ の辺をすべて青に塗ると赤い $K_2$ も青い $K_t$（頂点が $t-1$ 個しかない）もないので、$t-1$ は $(2,t)$ 性質をもたない。$t=1$ のときは 2 により $R(2,1)=1$ である。以上で $R(2,t)=t$ である。$\square$

$N:=R(s-1,t)+R(s,t-1)$ とし、$K_N$ の辺の 2 色塗り分けを任意にとる。頂点 $v$ を 1 つ固定し、残りの $N-1$ 個の頂点を、$v$ と赤い辺で結ばれるものの集合 $A$ と青い辺で結ばれるものの集合 $B$ に分ける。$|A|\leq R(s-1,t)-1$ かつ $|B|\leq R(s,t-1)-1$ とすると $|A|+|B|\leq N-2$ となり、$|A|+|B|=N-1$ に反する（鳩の巣原理）。よって $|A|\geq R(s-1,t)$ か $|B|\geq R(s,t-1)$ である。
$|A|\geq R(s-1,t)$ の場合、$A$ に制限した塗り分けには赤い $K_{s-1}$ か青い $K_t$ がある。青い $K_t$ ならそれが求めるものである。赤い $K_{s-1}$ なら、その頂点はすべて $v$ と赤い辺で結ばれているので、$v$ を加えると赤い $K_s$ になる。$|B|\geq R(s,t-1)$ の場合も同様に、$B$ の中の赤い $K_s$ はそのまま求めるものであり、青い $K_{t-1}$ に $v$ を加えると青い $K_t$ になる。
いずれの場合も赤い $K_s$ か青い $K_t$ があるので、$N$ は $(s,t)$ 性質をもつ。よって $R(s,t)$ が存在して $R(s,t)\leq N$ である。$\square$

$s+t$ に関する帰納法で示す。$s=1$ または $t=1$ なら、prop-ramsey-theorem-basic の 2 により $R(s,t)=1$ であり、右辺は $\binom{t-1}{0}=1$ または $\binom{s-1}{s-1}=1$ なので成り立つ。$s,t\geq2$ とし、和が $s+t-1$ の組について主張が成り立つとする。帰納法の仮定により $R(s-1,t)$ と $R(s,t-1)$ が存在するので、lem-ramsey-theorem-recursion と二項係数の漸化式（Pascal の三角形の関係）により
$$ R(s,t)\leq R(s-1,t)+R(s,t-1)\leq\binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}=\binom{s+t-2}{s-1} $$
である。$\square$

thm-ramsey-theorem-graph により $R(3,3)\leq\binom{4}{2}=6$ である（これは導入の議論そのものである）。$K_5$ の頂点を $0,1,2,3,4$ とし、差が $\pm1\pmod 5$ の 2 頂点を結ぶ辺（五角形の辺）を赤、差が $\pm2\pmod 5$ の辺（五角形の対角線）を青に塗る。3 頂点 $x,y,z$ が赤い $K_3$ なら、差 $y-x$、$z-y$、$x-z$ はどれも $\pm1$ で、和は $0$ である。しかし $\pm1$ を 3 つ足した和は $\pm1$ か $\pm3$ であり、$5$ の倍数にならないので矛盾する。青い $K_3$ についても、$\pm2$ を 3 つ足した和は $\pm2$ か $\pm6$ で、$5$ の倍数にならない。よってこの塗り分けには赤い $K_3$ も青い $K_3$ もなく、$R(3,3)>5$ である。$\square$

$R(3,4)\leq9$。$K_9$ の 2 色塗り分けで、赤い $K_3$ も青い $K_4$ もないものがあると仮定する。頂点 $v$ を 1 つとり、$v$ と赤い辺で結ばれる頂点の集合を $A$、青い辺で結ばれる頂点の集合を $B$ とする。$A$ の 2 点を結ぶ辺が赤なら、その 2 点と $v$ が赤い $K_3$ になるので、$A$ の中の辺はすべて青である。青い $K_4$ はないので $|A|\leq3$ である。また $|B|\geq6$ なら、prop-ramsey-theorem-r33 により $B$ の中に赤い $K_3$ か青い $K_3$ があり、前者は仮定に反し、後者は $v$ を加えて青い $K_4$ になって仮定に反する。よって $|B|\leq5$ である。$|A|+|B|=8$ だから $|A|=3$ である。つまり、どの頂点からも赤い辺がちょうど 3 本出ている。赤い辺だけからなるグラフを考えると、9 個の頂点の次数がすべて $3$ で、次数の総和 $27$ は奇数になる。これは次数の総和が辺の本数の 2 倍に等しいこと（次数(グラフ) の定理「次数の総和と辺数」）に反する。よって $9$ は $(3,4)$ 性質をもつ。
$R(3,4)>8$。$K_8$ の頂点を $0,1,\dots,7$ とし、差が $\pm1$ または $4\pmod 8$ の辺を赤、差が $\pm2$ または $\pm3\pmod 8$ の辺を青に塗る。赤い $K_3$ の頂点を $x,y,z$ とすると、3 つの差 $y-x$、$z-y$、$x-z$ は $8$ を法として $1,-1,4$ のいずれかで、和は $0$ である。$1,-1,4$ から重複を許して 3 つ選んだ和は、$4$ を使わなければ $\pm1,\pm3$、$4$ を 1 つ使えば $4\pm2$ か $4$、$4$ を 2 つ使えば $8\pm1$、3 つ使えば $12$ であり、どれも $8$ の倍数でない。よって赤い $K_3$ はない。
青い $K_4$ があるとし、その頂点集合を $S$ とする。4 つの組 $\{i,i+4\}$（$i=0,1,2,3$）はどれも赤い辺で結ばれるので、$S$ は各組からちょうど 1 点 $x_i$ を含む。$x_i$ が $i$ のとき「下」、$i+4$ のとき「上」とよぶ。$i=0,1,2$ について、$x_i$ と $x_{i+1}$ がともに下かともに上なら差が $1$ で赤い辺で結ばれるので、$x_0,x_1,x_2,x_3$ は下と上が交互に並ぶ。すると $x_0$ と $x_3$ は一方が下で他方が上であり、$(x_0,x_3)=(0,7)$ または $(4,3)$ となって、どちらも差が $\pm1$ で赤い辺で結ばれる。これは $S$ が青い $K_4$ であることに反する。よってこの塗り分けには赤い $K_3$ も青い $K_4$ もなく、$R(3,4)>8$ である。$\square$

最初の不等式は thm-ramsey-theorem-graph による。二項定理により $4^{k-1}=(1+1)^{2k-2}=\sum_{j=0}^{2k-2}\binom{2k-2}{j}$ であり、$k\geq2$ なら右辺には $\binom{2k-2}{k-1}$ 以外に正の項 $\binom{2k-2}{0}=1$ があるので、$\binom{2k-2}{k-1}<4^{k-1}$ である。$\square$

$n:=\lfloor2^{k/2}\rfloor$ とし（$\lfloor x\rfloor$ は $x$ 以下の最大の整数）、$K_n$ の辺の赤青の塗り分けで、赤い $K_k$ も青い $K_k$ もないものが存在することを示す。$n< k$ なら $K_n$ には $k$ 個の頂点がないので、どの塗り分けでもよい。$n\geq k$ とする。$K_n$ の辺は $\binom n2$ 本なので、塗り分けは全部で $2^{\binom n2}$ 通りある。$k$ 個の頂点の集合 $S$ を 1 つ固定すると、$S$ が赤い $K_k$ になる塗り分けは、$S$ の中の $\binom k2$ 本の辺を赤に決め、残りの辺を自由に塗るので $2^{\binom n2-\binom k2}$ 通りあり、青い $K_k$ になるものも同数ある。$S$ の選び方は $\binom nk$ 通りだから、赤い $K_k$ か青い $K_k$ を含む塗り分けの個数は多くとも
$$ M:=\binom nk\cdot2\cdot2^{\binom n2-\binom k2} $$
である。$\binom nk\leq n^k/k!$ と $n^k\leq2^{k^2/2}$ を使うと
$$ \frac{M}{2^{\binom n2}}=\binom nk2^{1-\binom k2}\leq\frac{2^{k^2/2}}{k!}\,2^{1-\frac{k(k-1)}2}=\frac{2^{1+k/2}}{k!} $$
である。$f(k):=2^{1+k/2}/k!$ とおくと $f(3)=2^{5/2}/6=\sqrt{32}/6<1$ であり、$f(k+1)/f(k)=\sqrt2/(k+1)<1$ だから、$k\geq3$ で $f(k)<1$ である。よって $M<2^{\binom n2}$ であり、赤い $K_k$ も青い $K_k$ も含まない塗り分けが存在する。したがって $n$ は $(k,k)$ 性質をもたず、$R(k,k)\geq n+1>2^{k/2}$ である。$\square$

無限集合 $A_0:=\mathbb{N}$ から始めて、数 $x_1< x_2<\cdots$、色 $\chi_1,\chi_2,\dots$、無限集合 $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\}$ の元 $y$ を色 $c(\{x_i,y\})$ で $r$ 個の集合に分けると、鳩の巣原理 の記事の命題「無限集合の鳩の巣原理」により、少なくとも 1 つの色 $\chi$ について $\{y\in A_{i-1}\setminus\{x_i\}\mid c(\{x_i,y\})=\chi\}$ は無限集合である。そのような色のうち最小のものを $\chi_i$ とし、この無限集合を $A_i$ とする。
構成から $A_i$ の元はすべて $x_i$ より大きいので $x_i< x_{i+1}$ であり、$j>i$ なら $x_j\in A_{j-1}\subset A_i$ だから $c(\{x_i,x_j\})=\chi_i$ である。つまり $\{x_i,x_j\}$（$i< j$）の色は小さいほうの添字 $i$ だけで決まる。色の列 $\chi_1,\chi_2,\dots$ は $r$ 個の値しかとらないので、再び無限集合の鳩の巣原理により、ある色 $\chi$ について $I:=\{i\mid\chi_i=\chi\}$ は無限集合である。$H:=\{x_i\mid i\in I\}$ とおくと、$H$ は無限集合であり、$H$ の 2 元 $x_i,x_j$（$i< j$、$i,j\in I$）について $c(\{x_i,x_j\})=\chi_i=\chi$ である。$\square$