次: エルディシュ問題 上: ラムゼー型定理 前: 存在定理

漸化不等式

南海　 $N\ge R$ならその中に一定の構造が存在する，これが成り立つ$R$の存在は示せた． 次の問題は$R$の上限と下限を求めるということだ． しかし一般にこれはたいへん難しい． とくに下限はほとんどの場合わからない．

太郎　 そうなのですね．色の数を$n$にした場合，三角形ができるための上限公式は先に導けました．

南海　 ここで，$r=2$つまり2点を結ぶ線分を$n$色で塗り分ける場合に一般化しよう．

定理 4        漸化不等式

$$\begin{array}{l} q_i=2\ (i \ne k)\Rightarrow R(q_1,\ q_2... ...^nR(q_1,\ \cdots,\ q_i-1,\ \cdots,\ q_n\ ;\ 2) \end{array}$$

が成り立つ．■

$n=2$のときは

$$\begin{array}{l} R(p,\ 2\ ;\ 2)=p,\ R(2,\ q\ ;\ 2)=q\\ ... ...\ q\ ;\ 2)\le R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2) \end{array}$$

が成立する．まずこれを考えてみよう．

太郎　 $R(p,\ q\ ;\ 2)$は何を意味していたか再確認します．

自然数 $N\ge R(p,\ q\ ;\ 2)$をとる．$N$個の点の集合を$S$とする． $S$の2点を結ぶ線分を赤色と青色で塗り分ける． $S$の$p$個からなる部分集合$V_p$でその線分がすべて赤色か， $q$個からなる部分集合$V_q$でその線分がすべて青色であるものが存在する．

$R(p,\ 2\ ;\ 2)=p$を示します． $p$個以上の点の集合を$S$とする． $S$の2点を結ぶ線分を赤色と青色で塗り分ける． すべてが赤色で塗られていれば$V_p=S$とする． 青色の線分が存在すれば，その2点を$V_2$とする．

この部分はこれでいいでしょうか．

南海　 いや，$p-1$以下ではできない反例を示すことが必要だ．

太郎　 $p-1$以下の場合，すべてを赤でぬれば， $S$の$p$個からなる部分集合$V_p$でその線分がすべて赤色のものも， $2$個からなる部分集合$V_q$でその線分がすべて青色であるものも存在しません．

南海　 そう．これ自体は難しくないが，このように下の限界を示すことが大切なのだ．

太郎　 つぎに不等式を示すためには， $N\ge R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2)$であれば， 先の命題が成り立つことを示せばよい．

不等式

$$R(p,\ q\ ;\ 2)\le R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2)$$

は

$$R(p,\ q\ ;\ 2)-1\le R(p-1,\ q\ ;\ 2)-1+R(p,\ q-1\ ;\ 2)-1+1$$

を意味します．

右辺は，$N$個の集合の各2点を結ぶ線分を2色で着色すれば， 赤の線分が $R(p-1,\ q\ ;\ 2)$あるか， 青の線分が $R(p,\ q-1\ ;\ 2)$あるかを意味します．

いずれもがなければ，その合計は $R(p-1,\ q\ ;\ 2)-1+R(p,\ q-1\ ;\ 2)-$より小さいはずだからです．

$N$個の点の一つを固定し，そこから残る$N-1$個の点を赤か青の線分で結ぶ． このとき，赤の線分の端点が $R(p-1,\ q\ ;\ 2)$以上あるか， 青の線分の端点が $R(p,\ q-1\ ;\ 2)$以上あるか，その少なくとも一方は成り立つ．

赤の線分の端点が $R(p-1,\ q\ ;\ 2)$以上あるとする． それらの端点の$q$個からなる部分集合$V_q$でその線分がすべて青色であるものが存在するなら，それでよい． それらの端点の$p-1$個からなる部分集合$V_{p-1}$でその線分がすべて赤色であるものが存在するなら， それにはじめの1点を加えた$p$個からなる部分集合$V_p$はその線分がすべて赤色である．

青の線分の端点が $R(p,\ q-1\ ;\ 2)$以上ある場合も同様である．

したがって，$N$が $R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2)$以上であることは， $S$の$p$個からなる部分集合$V_p$でその線分がすべて赤色か， $q$個からなる部分集合$V_q$でその線分がすべて青色であるものが存在するための十分条件である．

よってその最小値 $R(p,\ q\ ;\ 2)$は

$$R(p,\ q\ ;\ 2)\le R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2)$$

をみたす．

太郎　 この考え方なら色の数$n$がの場合も同じことですね． ここで書いてみます．

定理4の証明      $q_i=2\ (i \ne k)$のとき． $R(q_1,\ q_2,\ \cdots,\ q_n\ ;\ 2)=q_k$を示す．

$q_k$個以上の点の集合を$S$とする． $S$の2点を結ぶ線分を$n$色で塗り分ける． すべてが$k$色で塗られていれば$V_{q_k}=S$とする． $k$色以外の線分が存在すれば，その色を$q_i$とするとき，その2点を$V_{q_i}$とする．

$q_{k-1}$以下の場合，すべてを$k$色でぬれば， $S$の$q_k$個からなる部分集合$V_{q_k}$でその線分がすべて$k$色のものも， $2$個からなる部分集合$V_{q_i}$でその線分がすべて$i$色であるものも存在しない．

次に不等式は

$$R(q_1,\ q_2,\ \cdots,\ q_n\ ;\ 2)-1 \le \sum_{i=1^n}\{R(q_1,\ \cdots,\ q_i-1,\ \cdots,\ q_n\ ;\ 2)-1\}+1$$

と変形できる．

$$N\ge \sum_{i=1^n}\{R(q_1,\ \cdots,\ q_i-1,\ \cdots,\ q_n\ ;\ 2)-1\}+2$$ をとり，$N$個の点の一つを固定する． そこから残る$N-1$個の点を$n$色で塗り分ける． このとき， $$N-1\ge \sum_{i=1^n}\{R(q_1,\ \cdots,\ q_i-1,\ \cdots,\ q_n\ ;\ 2)-1\}+1$$なので， $k$色の線分の端点が $R(q_1,\ \cdots,\ q_k-1,\ \cdots,\ q_n\ ;\ 2)$以上あるような$k$が存在する．

$i\ne k$に対し端点の$q_i$個からなる部分集合$V_{q_i}$でその線分がすべて$i$色であるものが存在するなら，それでよい． それらの端点の$q_k-1$個からなる部分集合$V_{q_k-1}$でその線分がすべて$k$色であるものが存在するなら， それにはじめの1点を加えた$q_k$個からなる部分集合$V_{q_k}$はその線分がすべて$k$色である． したがって，この$N$に対して$S$の$q_i$個からなる部分集合$V_{q_i}$でその線分がすべて$i$色であるものが存在した． □

太郎　 上限に関する漸化不等式ができたので，これから具体的に上限を表したいです．

南海　 定理4は$n=2$のときはきれいな形である．この場合は可能だ．

$$\dfrac{(p+q)!}{p!q!}=\dfrac{(p-1+q)!}{(p-1)!q!}+\dfrac{(p+q-1)!}{p!(q-1)!}$$

が成り立つ．これを用いると

$$R(p,\ q\ ;\ 2)\le \dfrac{(p-1+q-1)!}{(p-1)!(q-1)!}$$

が成り立つ．

太郎　 $q=2$のときは $R(p,\ 2\ ;\ 2)=p$でした．

$$\dfrac{(p-1+2-1)!}{(p-1)!(2-1)!}=p$$

なのでこの場合は成り立ちます．$p$か$q$のところが$p-1$か$q-1$までなら成立するとすると

\begin{eqnarray*} R(p,\ q\ ;\ 2)&\leqq& R(p-1,\ q\ ;\ 2)+R(p,\ q-1\ ;\ 2)\\ &\leqq& \dfrac{(p-2+q-1)!}{(p-2)!(q-1)!}+\dfrac{(p-1+q-2)!}{(p-1)!(q-2)!}\\ &=&\dfrac{(p-1)(p-2+q-1)!}{(p-1)!(q-1)!}+\dfrac{(q-1)(p-1+q-2)!}{(p-1)!(q-1)!}\\ &=&\dfrac{(p-1+q-1)(p-2+q-1)!}{(p-1)!(q-1)!}=\dfrac{(p-1+q-1)!}{(p-1)!(q-1)!} \end{eqnarray*}

より$p$と$q$のときも成立する． □

一般の場合は難しそうです．

南海　 さらに下限を確定することは難しい．

次: エルディシュ問題 上: ラムゼー型定理 前: 存在定理