ラムゼーの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ラムゼーの定理(ラムゼーのていり)とは、次の二つの定理である(フランク・ラムゼイ, 1930)。

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

以下、これを満たす最小のRRr (s; k1, k2, ..., kr)とおく。

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

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

単色のK3を含まないK5の2色彩色

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

r, k1, k2, ..., krを2以上の整数とする。このとき、次の性質を満たすRr (k1, k2, ..., kr)が存在する:nR (k1, k2, ..., kr)ならば、n 個の点からなる完全グラフの辺をどの様にr 色に彩色してもあるi に対して、ki個の点からなる色i の完全グラフが存在する。

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

例:R2 (3, 3)=6[編集]

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

性質[編集]

ラムゼー数の性質については、特にr=s=2としたときのラムゼー数R (k , l )=R2 (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.
  • Rr (k' 1, k2, ..., kr)≤ Rr -1(Rs (k' 1-1, k2, ..., kr), Rr (k' 1, k2-1, ..., kr), ..., Rr (k' 1, k2-1, ..., kr-1)).

ラムゼー数が確定している例として、r =2のときにはR (3, 3)=6, R (3, 4)=9, R (3, 5)=14, R (3, 6)=18, R (3, 7)=23, R (3, 8)=28, R (3, 9)=36, R (4, 4)=18, R (4, 5)=25が知られている。

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

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

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

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

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

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

参考文献[編集]

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

関連項目[編集]

外部リンク[編集]