ラムゼーの定理

ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 1930)。
以下、これを満たす最小の"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"2 (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" ≥ 3のときにラムゼー数が確定しているのは"R"3 (3, 3, 3)=17が知られているに過ぎない。
"R"3 (3, 3, 3)=17から、1から17までの整数をどのように3つの集合に分割しても、そのうちの一つの集合で、"x" +"y" ="z" が解を持つことが示される。これは辺 "x" "y" を "x" -"y" の絶対値の属する類によって彩色することにより得られる。
このほか、次の評価が知られている。
このようにラムゼー数については多くの性質が知られているものの、ラムゼー数が確定している場合は非常に少なく、特定のパラメータに対してさえ、ラムゼー数を決定するのは非常に難しい問題である。