ラムゼーの定理

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

無限ラムゼーの定理

r, sを正の整数とする。相異なるs 個の整数からなる集合全体をどのようにr 個の類に類別しても、ある整数の無限部分集合S が存在し、S に属する相異なる整数s個の集合は全て同一の類に属する。

有限ラムゼーの定理

s , r , k₁, k₂, ..., k_r をk_i ≥ s となる非負の整数とする。このとき、次の性質を満たすRが存在する：n≥ Rならば、n 個の元からなる集合Nの s 個の元からなる部分集合全体をr個の類 C₁, C₂, ..., C_rに類別したとき、あるiが存在して、k_i個の元からなるNの部分集合で、その中のどの相異なるs 個の元からなる部分集合も類C_iに属するものが存在する。

以下、これを満たす最小のR をR_r (s; k₁, k₂, ..., k_r)とおく。

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

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

単色のK₃を含まないK₅の2色彩色

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

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

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

例:R₂ (3, 3)=6

上にもあるが、R₂ (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。これを示す。なお、上の図より、R₂ (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以下である。三角形は₆C₃=20個あるので、一色の三角形は20-18=2個以上ある。

性質

ラムゼー数の性質については、特にr=s=2としたときのラムゼー数R (k , l )=R₂ (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₁, k₂, ..., k_r)≤ R_{r -1}(R_s (k₁-1, k₂, ..., k_r), R_r (k₁, k₂-1, ..., k_r), ..., R_r (k₁, k₂-1, ..., k_r-1)).

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

ラムゼー数 / ラムゼー数の下界・上界 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	36–41	49–61	59–84	73–115	92–149
5					43–48	58–87	80–143	101–216	133–316	149–442
6						102–165	115–298	134–495	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)=17が知られているに過ぎない。

K₁₆を単色のK₃を含まないように3色で彩色する方法はこの2通りしかない The untwisted colouring (top) and the twisted colouring (bottom).

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

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

• 51≤ R₄ (3, 3, 3, 3)≤ 62
• 162≤ R₅ (3, 3, 3, 3, 3)≤ 307
• 538≤ R₆ (3, 3, 3, 3, 3, 3)≤ 1838
• 1682≤ R₇ (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