ラムゼーの定理

ラムゼーの定理とは、数学の組合せ論における次の二つの定理のことである。

無限ラムゼーの定理//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//=1のとき、//R////r// =//r// +1ととれる。つまり、ラムゼーの定理は鳩の巣原理の一般化といえる。また、//R//2 =6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。

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

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

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

1. 例://R//2 =6
--------------------

上にもあるが、//R//2 =6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。これを示す。なお、上の図より、//R//2 >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つの点の組で、辺xyの色と辺yzの色が異なるものの個数をNとする。ただし、において、xとzの順番は区別しないものとする。y=Aのとき、そのような組の個数は、0×5=0、1×4=4、2×3=6のいずれかである。よって、y=Aのとき、そのような組の個数は最大でも6である。yが他の点である場合も同様なので、Nは6×6=36以下である。一方、一つの一色でない三角形はそのような組を2つ含む。よって、一色でない三角形の個数は36/2=18以下である。三角形は//6//C//3//=20個あるので、一色の三角形は20-18=2個以上ある。

2. 性質
-----

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

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

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

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

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

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

51≤ //R//4 ≤ 62
162≤ //R//5 ≤ 307
538≤ //R//6 ≤ 1838
1682≤ //R//7 ≤ 12861
//R////r// ≤ //r// -1)+2.
//r// //R////r// -1 +1個の点からなる完全グラフから1点//v//を選び、そこから残りの頂点への辺を//r// 色に彩色する。鳩の巣原理から、//i//をうまく選べば//v//との間の辺がすべて色//i//に塗られている//R////r// -1 個の頂点からなるグラフ //W// が存在する。//W// の頂点の間の辺の一つ //x// //y// が色//i// に塗られていれば、//x// //y// //v// は色//i// のみからなる3点のグラフとなる。そのような辺が存在しないなら、//W// の辺は//r// -1色で彩色されるので、色//j// のみからなる3点のグラフが存在する。このようにラムゼー数については多くの性質が知られているものの、ラムゼー数が確定している場合は非常に少なく、特定のパラメータに対してさえ、ラムゼー数を決定するのは非常に難しい問題である。

3. 脚注
-----

4. 参考文献
-------

F. P. Ramsey, On a problem of formal logic, //Proc. London Math. Soc.// ser. 2, 30 , 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.

5. 関連項目
-------

組合せ数学

6. 外部リンク
--------

[1]