ラムゼーの定理 （ラムゼーのていり）とは、数学 の組合せ論 における次の二つの定理のことである(フランク・ラムゼイ , 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 k i N の部分集合で、その中のどの相異なるs 個の元からなる部分集合も類C i 以下、これを満たす最小のR をR r s ; k 1 , k 2 , ..., k r
有限ラムゼーの定理は無限ラムゼーの定理から従う。その証明は英語版を参照のこと。
鳩の巣原理 から、s =1のとき、R r k , k , ..., k )=(k -1)r +1ととれる。つまり、ラムゼーの定理は鳩の巣原理 の一般化といえる。また、R 2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。
単色のK3 を含まないK5 の2色彩色 s =2 とするとき、次の結果が得られる。この結果がラムゼーの定理として言及されることも多い。
r , k 1 , k 2 , ..., k r 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 3
ラムゼー数の性質については、特に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 )≤ 4R (k , k -2)+2.R r k 1 , k 2 , ..., k r R r -1R 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 ラムゼー数が確定している例を、以下の表に示す。
ラムゼー数 / ラムゼー数の下界・上界 R (r , s )オンライン整数列大辞典 の数列 A212954
r\s
1
2
3
4
5
6
7
8
9
10
1
1
1
1
1
1
1
1
1
1
1
2
2
3
4
5
6
7
8
9
10
3
6
9
14
18
23
28
36
40–42
4
18
25[ 1]
36–41
49–61
59[ 2]
73–115
92–149
5
43–48
58–87
80–143
101–216
133–316
149[ 2]
6
102–165
115[ 2]
134[ 2]
183–780
204–1171
7
205–540
217–1031
252–1713
292–2826
8
282–1870
329–3583
343–6090
9
565–6588
581–12677
10
798–23556
r ≥ 3のときにラムゼー数が確定しているのはR 3 (3, 3, 3)=17が知られているに過ぎない。
K16 を単色のK3 を含まないように3色で彩色する方法はこの2通りしかない The untwisted colouring (top) and the twisted colouring (bottom). 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 r (R r -1r R r -1v を選び、そこから残りの頂点への辺をr 色に彩色する。鳩の巣原理 から、i をうまく選べばv との間の辺がすべて色i に塗られているR r -1W が存在する。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.
