§E13.10有限 Ramsey の定理

証明.$K_{n'}$の頂点集合を$V'$とし、辺集合の赤と青への塗り分け$\varphi'$を任意に取る。$n\le n'$であるから$\lvert W\rvert=n$を満たす$W\subseteq V'$を取ることができる。$W$を頂点集合とし、両端点が$W$に属する$K_{n'}$の辺の全体を辺集合とするグラフは、$W$の相異なる二頂点がすべて隣接するので$K_n$と同型である。このグラフの辺への$\varphi'$の制限は、$K_n$の辺集合の赤と青への塗り分けを与える。

$Q_{s,t}(n)$より、$W$の部分集合であって内部のすべての辺が赤である$s$元集合、または内部のすべての辺が青である$t$元集合が存在する。この集合は$V'$の部分集合でもあり、内部の辺と塗り分けは制限の前後で変わらないから、$\varphi'$についても同じ条件を満たす。$\varphi'$は任意であったから$Q_{s,t}(n')$が成り立つ。▨

証明.(1)を示す。$K_1$は辺をもたないから、辺集合の塗り分けは空写像ただ一つである。$K_1$の唯一の頂点からなる一元集合$S$を取ると、$\lvert S\rvert=1$であり内部の辺は存在しないから、「内部のすべての辺が赤である」という条件は空虚に成り立つ。ゆえに$S$は$Q_{1,t}(1)$の要求する$1$元集合であり、$Q_{1,t}(1)$が成り立つ。$1$は最小の正の整数であるから$R(1,t)=1$である。$Q_{t,1}(1)$については、同じ$S$が「内部のすべての辺が青である$1$元集合」の条件を空虚に満たすので、同様に$R(t,1)=1$である。

(2)を示す。$K_n$の辺集合の塗り分け$\varphi$に対し、赤と青を入れ替えた塗り分けを$\bar\varphi$と書く。$\varphi\mapsto\bar\varphi$は塗り分けの全体からそれ自身への全単射であり、$\bar{\bar\varphi}=\varphi$である。定義より、$S$が$\varphi$について内部のすべての辺が赤である集合であることと、$S$が$\bar\varphi$について内部のすべての辺が青である集合であることは同値である。

したがって、$\bar\varphi$について「赤い$t$元集合または青い$s$元集合が存在する」ことと、$\varphi$について「青い$t$元集合または赤い$s$元集合が存在する」ことは同値である。$\varphi\mapsto\bar\varphi$が全単射であることから、「すべての塗り分けについて前者が成り立つ」ことと「すべての塗り分けについて後者が成り立つ」ことも同値であり、これは$Q_{t,s}(n)\iff Q_{s,t}(n)$にほかならない。二つの性質を満たす正の整数の集合が一致するので、最小元も一致する。▨

証明.$R(s-1,t)\ge1$かつ$R(s,t-1)\ge1$であるから$N\ge2$である。$K_N$の頂点集合を$V$とし、辺集合の赤と青への塗り分け$\varphi$を任意に取る。頂点$v\in V$を一つ固定し$A=\{x\in V\setminus\{v\}:\ \varphi(vx)=\text{赤}\},\qquad B=\{x\in V\setminus\{v\}:\ \varphi(vx)=\text{青}\}$と置く。$A$と$B$は互いに素で合併が$V\setminus\{v\}$であるから、§D2.2 定理 2.1より$\lvert A\rvert+\lvert B\rvert=N-1=R(s-1,t)+R(s,t-1)-1$である。もし$\lvert A\rvert\le R(s-1,t)-1$かつ$\lvert B\rvert\le R(s,t-1)-1$であるとすると、和は$N-2$以下となって上の等式に反する。ゆえに$\lvert A\rvert\ge R(s-1,t)$または$\lvert B\rvert\ge R(s,t-1)$が成り立つ。

場合 1：$\lvert A\rvert\ge R(s-1,t)$のとき.$A$を頂点集合とし、両端点が$A$に属する$K_N$の辺の全体を辺集合とするグラフは$K_{\lvert A\rvert}$と同型であり、$\varphi$の制限がその辺の塗り分けを与える。$R(s-1,t)$の定義より$Q_{s-1,t}(R(s-1,t))$が成り立つから、命題 1.2より$Q_{s-1,t}(\lvert A\rvert)$が成り立つ。ゆえに、$A$の部分集合であって内部のすべての辺が赤である$s-1$元集合$S$、または内部のすべての辺が青である$t$元集合$T$が存在する。

後者の場合、$T$は$V$の部分集合として、内部のすべての辺が青である$t$元集合であり、求めるものである。

前者の場合、$v\notin A$かつ$S\subseteq A$であるから$\lvert S\cup\{v\}\rvert=s$である。$S\cup\{v\}$の内部の辺は、$S$の内部の辺と、$v$と$S$の各頂点を結ぶ辺である。前者はすべて赤であり、後者は$S\subseteq A$と$A$の定義よりすべて赤である。ゆえに$S\cup\{v\}$は内部のすべての辺が赤である$s$元集合であり、求めるものである。

場合 2：$\lvert B\rvert\ge R(s,t-1)$のとき. 同じ議論により$Q_{s,t-1}(\lvert B\rvert)$が成り立つから、$B$の部分集合であって内部のすべての辺が赤である$s$元集合、または内部のすべての辺が青である$t-1$元集合$T$が存在する。前者はそのまま求めるものである。後者の場合、$T\cup\{v\}$は$t$元集合であり、その内部の辺は$T$の内部の辺（すべて青）と$v$と$T$の各頂点を結ぶ辺（$T\subseteq B$よりすべて青）であるから、求めるものである。

いずれの場合も条件を満たす頂点部分集合が存在し、$\varphi$は任意であったから$Q_{s,t}(N)$が成り立つ。したがって$Q_{s,t}$を満たす正の整数の集合は空でないので$R(s,t)$が定まり、$N$がこの集合に属することから$R(s,t)\le N$である。▨

証明.$s+t$についての累積帰納法（§D2.1 命題 1.2）による。$s,t\ge1$より$s+t\ge2$である。

$s=1$の場合.命題 1.3より$Q_{1,t}(1)$が成り立ち$R(1,t)=1$である。また$\binom{1+t-2}{0}=1$であるから、主張の不等式は等号として成り立つ。

$t=1$の場合.命題 1.3より$R(s,1)=1$である。また$\binom{s+1-2}{s-1}=\binom{s-1}{s-1}=1$であるから、主張の不等式は等号として成り立つ。

$s\ge2$かつ$t\ge2$の場合.$(s-1)+t=s+t-1<s+t$かつ$s+(t-1)=s+t-1<s+t$であり、$s-1\ge1$かつ$t-1\ge1$であるから、帰納法の仮定を組$(s-1,t)$と$(s,t-1)$へ適用することができる。すなわち$R(s-1,t)$と$R(s,t-1)$は定まり$R(s-1,t)\le\binom{(s-1)+t-2}{(s-1)-1}=\binom{s+t-3}{s-2},\qquad R(s,t-1)\le\binom{s+(t-1)-2}{s-1}=\binom{s+t-3}{s-1}$が成り立つ。定理 2.1より$R(s,t)$は定まり$R(s,t)\le R(s-1,t)+R(s,t-1)\le\binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}$である。ここで§D2.2 命題 5.2を$n=s+t-2$、$k=s-1$に対して適用する。$s\ge2$より$k=s-1\ge1$であり、$t\ge2$より$k=s-1\le s+t-3=n-1$であるから、適用の条件が満たされる。ゆえに$\binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}=\binom{s+t-2}{s-1}$であり、$R(s,t)\le\binom{s+t-2}{s-1}$を得る。▨

証明.定理 3.1を$t=s$に対して適用すると$R(s,s)\le\binom{s+s-2}{s-1}=\binom{2s-2}{s-1}$を得る。

$m=s-1$と置くと$m\ge1$である。§D2.2 定理 5.1を$x=y=1$、$n=2m$に対して適用すると$4^{m}=2^{2m}=(1+1)^{2m}=\sum_{j=0}^{2m}\binom{2m}{j}$である。右辺は$2m+1$個の項の和であり、各項は正の整数である。$m\ge1$より$2m+1\ge3$であるから、$j=m$の項$\binom{2m}{m}$のほかに正の項が少なくとも二つある。ゆえに$\binom{2m}{m}<\sum_{j=0}^{2m}\binom{2m}{j}=4^{m}$であり、$\binom{2s-2}{s-1}<4^{s-1}$を得る。▨