ラムゼーの定理

**ラムゼーの定理**（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。

;無限ラムゼーの定理
:*r*, *s*を正の整数とする。相異なる*s* 個の整数からなる集合全体をどのように*r* 個の類に類別しても、ある整数の無限部分集合*S* が存在し、*S* に属する相異なる整数*s*個の集合は全て同一の類に属する。
;有限ラムゼーの定理
:*s* , *r* , *k*1, *k*2, ..., *k**r*  を*k**i* ≥ *s* となる非負の整数とする。このとき、次の性質を満たす*R*が存在する：*n*≥ *R*ならば、*n* 個の元からなる集合*N*の *s* 個の元からなる部分集合全体を*r*個の類 *C*1, *C*2, ..., *C**r*に類別したとき、あるiが存在して、*k**i*個の元からなる*N*の部分集合で、その中のどの相異なる*s* 個の元からなる部分集合も類*C**i*に属するものが存在する。

以下、これを満たす最小の*R* を*R**r* (*s*; *k*1, *k*2, ..., *k**r*)とおく。

有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。

鳩の巣原理から、*s*=1のとき、*R**r* (1; *k*, *k*, ..., *k* )=(*k* -1)*r* +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、*R*2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。

*s*=2 とするとき、次の結果が得られる。この結果がラムゼーの定理として言及されることも多い。

*r*, *k*1, *k*2, ..., *k**r*を2以上の整数とする。このとき、次の性質を満たす*R**r* (*k*1, *k*2, ..., *k**r*)が存在する：*n*≥ *R* (*k*1, *k*2, ..., *k**r*)ならば、*n* 個の点からなる完全グラフの辺をどの様に*r* 色に彩色してもある*i* に対して、*k**i*個の点からなる色*i* の完全グラフが存在する。

ラムゼーの定理に類似した定理として、ファン・デル・ヴェルデンの定理など多くの種類の定理が知られている。最近になって、これらの一般化であるHales-Jewettの定理が発見され、これにより、一連の類似した定理は一つの理論として確立した。

## 例:''R''<sub>2</sub> (3, 3)=6
上にもあるが、*R*2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。これを示す。なお、上の図より、*R*2 (3, 3)>5であり、5人いても互いに知り合いである3人組も互いに知り合いでない3人組も存在しない場合がある。

6つの点があり、その中のどの2つの点も赤い線か青い線で結ばれているとする。赤一色の三角形か青一色の三角形が存在することを示せばよい。6つの点のうち、どれでも良いので1つの点に着目し、その点をAとする。Aからは5本の線が出ているので、そのうちの3本以上は同じ色の線である筈である。Aから赤い線が3本以上出ている場合を考える。Aと赤い線でつながっている点は3つ以上あるが、そのうちの3点をB,C,Dとする。BとCが赤い線で結ばれている場合、三角形ABCはどの辺も赤い赤一色の三角形である。CとD、DとBが赤い線で結ばれている場合も同様に赤一色の三角形が存在する。よって、B,C,Dの中のいずれか2点が赤い線で結ばれている場合は赤一色の三角形が存在する。そうでない場合、即ち、B,C,Dのうちどの2点も青い線で結ばれている場合、三角形BCDはどの辺も青い青一色の三角形である。よってこの場合も一色の三角形が存在する。Aから青い線が3本以上出ている場合も同様である。

これとは別の方法で、一色の三角形が2個以上存在することを示すこともできる。相異なる3つの点の組(x,y,z)で、辺xyの色と辺yzの色が異なるものの個数をNとする。ただし、(x,y,z)において、xとzの順番は区別しないものとする。y=Aのとき、そのような組(x,y,z)の個数は、0×5=0(yから出ている線が全て同じ色である場合)、1×4=4(yから赤い線が1本だけ、または青い線が1本だけ出ている場合)、2×3=6(yからある色の線が2本出ており、他方の色の線は3本出ている場合)のいずれかである。よって、y=Aのとき、そのような組の個数は最大でも6である。yが他の点である場合も同様なので、Nは6×6=36以下である。一方、一つの一色でない三角形はそのような組(x,y,z)を2つ含む。よって、一色でない三角形の個数は36/2=18以下である。三角形は*6*C*3*=20個あるので、一色の三角形は20-18=2個以上ある。

## 性質
ラムゼー数の性質については、特に*r*=*s*=2としたときのラムゼー数*R* (*k* , *l* )=*R*2 (*k* , *l* )について多くの結果が知られている。

次の結果が知られている。

* *R* (*k* , *l* )≤ *R* (*k* -1, *l* )+*R* (*k* , *l* -1).
** *R* (*k* -1, *l* )+*R* (*k* , *l* -1)個の点からなる完全グラフから1点*v* を選び、そこから残りの点への辺を1と2に彩色する。このとき、色1に塗られている辺の個数が*R* (*k* -1, *l* )以上かまたは、色2に塗られている辺の個数が*R* (*k* , *l* -1)以上である。前者の場合（後者の場合も同じように議論できる）、色1に塗られている辺の向かう先の点の個数が*R* (*k* -1, *l* )以上だから、それらの点から*k* -1個の点の、色1のみからなる完全グラフか、*l*個の点の色2のみからなる完全グラフがある。前者の場合、*v* とあわせれば*k* 個の点の色1のみからなる完全グラフが得られる。ちなみに、この議論と*k*+*l*に関する数学的帰納法によって、*R* (*k* , *l* )の存在を示すことが出来る。
* *R* (*k* , *k* )≤ 4*R* (*k* , *k* -2)+2.
* *R**r* (*k*1, *k*2, ..., *k**r*)≤ *R**r* -1(*R**s* (*k*1-1, *k*2, ..., *k**r*), *R**r* (*k*1, *k*2-1, ..., *k**r*), ..., *R**r* (*k*1, *k*2-1, ..., *k**r*-1)).

ラムゼー数が確定している例を、以下の表に示す。

*r* ≥ 3のときにラムゼー数が確定しているのは*R*3 (3, 3, 3)=17が知られているに過ぎない。
 

*R*3 (3, 3, 3)=17から、1から17までの整数をどのように3つの集合に分割しても、そのうちの一つの集合で、*x* +*y* =*z* が解を持つことが示される。これは辺 *x* *y* を *x* -*y* の絶対値の属する類によって彩色することにより得られる。

このほか、次の評価が知られている。

*51≤ *R*4 (3, 3, 3, 3)≤ 62
*162≤ *R*5 (3, 3, 3, 3, 3)≤ 307
*538≤ *R*6 (3, 3, 3, 3, 3, 3)≤ 1838
*1682≤ *R*7 (3, 3, 3, 3, 3, 3, 3)≤ 12861
* *R**r* (3, 3, ..., 3)≤ *r* (*R**r* -1 (3, 3, ..., 3)-1)+2.
** *r* *R**r* -1 (3, 3, ..., 3)+1個の点からなる完全グラフから1点*v*を選び、そこから残りの頂点への辺を*r* 色に彩色する。鳩の巣原理から、*i*をうまく選べば*v*との間の辺がすべて色*i*に塗られている*R**r* -1 (3, 3, ..., 3)個の頂点からなるグラフ *W* が存在する。*W* の頂点の間の辺の一つ *x* *y* が色*i* に塗られていれば、*x* *y* *v* は色*i* のみからなる3点のグラフとなる。そのような辺が存在しないなら、*W* の辺は*r* -1色で彩色されるので、色*j* のみからなる3点のグラフが存在する。

このようにラムゼー数については多くの性質が知られているものの、ラムゼー数が確定している場合は非常に少なく、特定のパラメータに対してさえ、ラムゼー数を決定するのは非常に難しい問題である。

## 脚注

## 参考文献
* F. P. Ramsey, On a problem of formal logic, *Proc. London Math. Soc.* ser. 2, **30** (1930), 264--286.
* R. Graham, B. Rothschild, J. H. Spencer, *Ramsey Theory*, John Wiley and Sons, NY, 1990.
* Stanislaw Radziszowski, Small Ramsey Numbers, *The Electronic Journal of Combinatorics* , Dynamic Survey DS1.
* B. Bollobás, *Extremal Graph Theory*, Academic Press, London, 1978.  Dover edition, 2004, Section V.6.
* R. Diestel, *Graph Theory*, GTM 173, Springer-Verlag, 3rd edition, 2005, Chapter 9.

## 関連項目
* 組合せ数学

## 外部リンク
* 
* Ramsey@Home