§E16.10有限 Ramsey の定理

(1)を示す。定理 3.1により$R(s,t)$は定まる正の整数である。$s=1$または$t=1$のとき、右辺は$1$であるから主張は成り立つ。

$s\ge2$かつ$t\ge2$とし、$N=(s-1)(t-1)\ge1$と置く。$K_N$の頂点集合$V$を、それぞれ$s-1$個の元をもつ$t-1$個の互いに素な部分集合$B_1,\dots,B_{t-1}$へ分ける。辺$xy$を、$x$と$y$が同じ$B_j$に属するとき赤に、異なる$B_j$に属するとき青に塗る。この塗り分けを$\varphi$とする。

内部のすべての辺が赤である$s$元集合$S$が存在すると仮定する。$S$の相異なる二頂点が異なる$B_j$に属すれば、それらを結ぶ辺は青であるから、$S$の頂点はすべて一つの$B_j$に属する。しかし$\lvert B_j\rvert=s-1<s=\lvert S\rvert$であるから、これは起こらない。

内部のすべての辺が青である$t$元集合$T$が存在すると仮定する。$T$の各頂点をそれが属する$B_j$へ対応させると、$t=(t-1)+1$個の対象を$t-1$個の箱へ入れることになる。$t-1\ge1$であるから、§D2.3 系 4.3より同じ$B_j$に属する$T$の相異なる二頂点が存在し、それらを結ぶ辺は赤である。これは$T$の内部のすべての辺が青であることに反する。

ゆえに$\varphi$は求める塗り分けであり、$Q_{s,t}(N)$は成り立たない。命題 1.3の対偶より、$n\le N$を満たす正の整数$n$について$Q_{s,t}(n)$は成り立たない。$Q_{s,t}(R(s,t))$は成り立つから$R(s,t)>N$であり、$R(s,t)\ge(s-1)(t-1)+1$を得る。$t=2$のとき下界は$s$であり、例 4.1の$R(2,s)=s$と命題 1.4 (2)により等号が成り立つ。$s=t=3$のとき下界は$5$であり、同じ例の$R(3,3)=6$より小さい。

(2)を示す。定理 3.1により、以下に現れる Ramsey 数はすべて定まる。

$t=1$のとき、命題 1.4 (1)より$R(s,1)=1$であり、命題 1.4 (2)と例 4.1の$R(2,s)=s$より$R(s,2)=s\ge2=R(s,1)+1$である。

$t\ge2$とする。$K_1$の頂点集合は一元集合であり、$s\ge2$かつ$t\ge2$であるから$s$元部分集合も$t$元部分集合ももたない。ゆえに$Q_{s,t}(1)$は成り立たず、$R(s,t)\ge2$である。$N=R(s,t)-1$と置くと$N\ge1$であり、$R(s,t)$の最小性より$Q_{s,t}(N)$は成り立たない。すなわち、$K_N$の頂点集合$V$の上の辺の塗り分け$\varphi$であって、内部のすべての辺が赤である$s$元集合も、内部のすべての辺が青である$t$元集合も存在しないものがある。$z\notin V$を取り、$V'=V\cup\{z\}$上の完全グラフ$K_{N+1}$の辺を、両端点が$V$に属する辺は$\varphi$と同じ色に、$z$を端点とする辺はすべて青に塗る。この塗り分けを$\varphi'$とする。

内部のすべての辺が赤である$s$元集合$S\subseteq V'$が存在すると仮定する。$z\in S$ならば、$s\ge2$より$S$は$z$と異なる頂点$y$を含み、内部の辺$zy$は青であるから矛盾する。ゆえに$S\subseteq V$であり、$S$の内部の辺の色は$\varphi$と$\varphi'$で等しいので、$S$は$\varphi$について内部のすべての辺が赤である$s$元集合となって矛盾する。

内部のすべての辺が青である$(t+1)$元集合$T\subseteq V'$が存在すると仮定する。$T\cap V$は$t$個以上の元をもつので、その$t$元部分集合$T'$を取ることができる。$T'$の内部の辺は$T$の内部の辺であって両端点が$V$に属するから、$\varphi$についても青である。これは$\varphi$の取り方に反する。

ゆえに$Q_{s,t+1}(N+1)$は成り立たず、命題 1.3の対偶より$n\le N+1$を満たす正の整数$n$について$Q_{s,t+1}(n)$は成り立たない。したがって$R(s,t+1)\ge N+2=R(s,t)+1$である。

後半を示す。$s\ge1$、$t\ge2$とする。前半を$t$と$s$の役割を入れ替えて適用すると$R(t,s+1)\ge R(t,s)+1$であり、命題 1.4 (2)より$R(s+1,t)=R(t,s+1)\ge R(t,s)+1=R(s,t)+1$を得る。

(3)を示す。$K_6$の頂点集合を$V$とし、塗り分け$\varphi$を任意に取る。内部のすべての辺が同じ色である$3$元集合を単色であるという。頂点$v$を端点とする赤い辺の本数を$r_v$とすると、青い辺の本数は$5-r_v$である。

と置く。$v$を固定したとき、条件を満たす対$\{x,y\}$は、$vx$が赤で$vy$が青である頂点の組$(x,y)$と一対一に対応するから、§D2.2 定理 2.3よりその個数は$r_v(5-r_v)$である。$r_v\in\{0,1,\dots,5\}$に対する$r_v(5-r_v)$の値は$0,4,6,6,4,0$であるから、各項は$6$以下である。§D2.2 定理 2.1より

である。

一方、$P$の元$(v,\{x,y\})$に$3$元集合$\{v,x,y\}$を対応させ、$3$元集合ごとに$P$の元を数える。$3$元集合$\{a,b,c\}$が単色ならば、どの頂点においても二本の内部の辺の色は等しいので、対応する$P$の元は存在しない。単色でないならば、三本の内部の辺のうち二本が同じ色で残る一本が他の色である。同じ色の二本に共通の端点では二本の色が等しく、残る二つの頂点ではそれぞれ色の異なる二本が出る。ゆえに対応する$P$の元はちょうど二つである。単色でない$3$元集合の個数を$u$とすると、§D2.2 定理 2.1より$\lvert P\rvert=2u$であり、$u\le18$である。$3$元集合は§D2.2 命題 3.1より$\binom63=20$個あるから、単色の$3$元集合は$20-u\ge2$個以上ある。

例を与える。$V=\{1,\dots,6\}$とし、両端点がともに$\{1,2,3\}$に属する辺と、両端点がともに$\{4,5,6\}$に属する辺を赤に、その他の辺を青に塗る。$\{1,2,3\}$と$\{4,5,6\}$は単色である。その他の$3$元集合は$\{1,2,3\}$と$\{4,5,6\}$の両方と交わる。$3$個の頂点を二つの集合へ入れることになるので、§D2.3 系 4.3より同じ集合に属する二頂点があり、それらを結ぶ辺は赤である。また、異なる集合に属する二頂点を結ぶ辺は青である。ゆえにその他の$3$元集合は単色でなく、単色の$3$元集合はちょうど二つである。

(4)を示す。$s\ge s_0$、$t\ge t_0$を満たす組$(s,t)$についての主張$R(s,t)\le\binom{s+t-2}{s-1}-1$を、$s+t$についての累積帰納法（§D2.1 命題 1.2）で示す。定理 3.1により、以下に現れる Ramsey 数はすべて定まる。

$(s,t)=(s_0,t_0)$のときは仮定そのものである。$(s,t)\ne(s_0,t_0)$とすると、$s>s_0$と$t>t_0$の少なくとも一方が成り立つ。$s\ge2$かつ$t\ge2$であるから、定理 2.1より$R(s,t)\le R(s-1,t)+R(s,t-1)$である。

$s>s_0$のとき、組$(s-1,t)$は$s-1\ge s_0$、$t\ge t_0$を満たし、成分の和は$s+t-1$であるから、帰納法の仮定より$R(s-1,t)\le\binom{s+t-3}{s-2}-1$である。$s=s_0$のときは、定理 3.1より$R(s-1,t)\le\binom{s+t-3}{s-2}$である。同様に、$t>t_0$のときは帰納法の仮定より$R(s,t-1)\le\binom{s+t-3}{s-1}-1$であり、$t=t_0$のときは定理 3.1より$R(s,t-1)\le\binom{s+t-3}{s-1}$である。少なくとも一方の評価で$1$が引かれるから

である。§D2.2 命題 5.2を$n=s+t-2$、$k=s-1$に適用する。$s\ge2$より$k\ge1$であり、$t\ge2$より$k\le n-1$であるから適用の条件が満たされ、右辺は$\binom{s+t-2}{s-1}-1$に等しい。これで主張が示された。

後半を示す。(6)より$R(3,4)\le9=\binom52-1$であるから、前半を$(s_0,t_0)=(3,4)$に適用すると、$s\ge3$、$t\ge4$のすべてで主張が成り立つ。命題 1.4 (2)より$R(4,3)=R(3,4)\le9=\binom53-1$であるから、前半を$(s_0,t_0)=(4,3)$に適用すると、$s\ge4$、$t\ge3$のすべてで主張が成り立つ。$s\ge3$、$t\ge3$、$(s,t)\ne(3,3)$を満たす組は、$t\ge4$を満たすか、$t=3$かつ$s\ge4$を満たすので、いずれかに含まれる。なお、例 4.1の$R(3,3)=6=\binom42$により、$(3,3)$ではこの評価は成り立たない。

(5)を示す。$a=R(s-1,t)$、$b=R(s,t-1)$、$N=a+b-1$と置く。$a$と$b$は偶数の正の整数であるから$a\ge2$かつ$b\ge2$であり、$N\ge3$である。$K_N$の頂点集合を$V$とし、辺集合の赤と青への塗り分け$\varphi$を任意に取る。各頂点$v\in V$に対して、定理 2.1の証明と同じく

と置く。§D2.2 定理 2.1より$\lvert A_v\rvert+\lvert B_v\rvert=N-1=a+b-2$である。

$\lvert A_v\rvert\ge a$または$\lvert B_v\rvert\ge b$を満たす頂点$v$が存在することを、背理法で示す。すべての頂点$v$について$\lvert A_v\rvert\le a-1$かつ$\lvert B_v\rvert\le b-1$が成り立つと仮定する。ある$v$で$\lvert A_v\rvert<a-1$ならば$\lvert B_v\rvert=a+b-2-\lvert A_v\rvert>b-1$となって仮定に反するので、すべての頂点$v$について$\lvert A_v\rvert=a-1$である。赤い辺の全体を$E_{\text{赤}}$とし、グラフ$G_{\text{赤}}=(V,E_{\text{赤}})$を考える。$x\mapsto vx$は$A_v$から$v$に接続する赤い辺の集合への全単射であるから、§D2.2 命題 1.5より$\deg_{G_{\text{赤}}}(v)=\lvert A_v\rvert=a-1$である。§D2.7 定理 1.2より

であるから、$N(a-1)$は偶数である。一方、$a$と$b$は偶数であるから$N=a+b-1$は奇数であり、$a-1$も奇数であるので、$N(a-1)$は奇数である。$N(a-1)$が偶数であることと奇数であることは両立しないので、仮定は誤りである。ゆえに、$\lvert A_v\rvert\ge a$または$\lvert B_v\rvert\ge b$を満たす頂点$v$が存在する。