ラムゼーの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

以下、これを満たす最小のR をRr (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)が存在する：n≥ R (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 (k1, k2, ..., kr)≤ Rr -1(Rs (k1-1, k2, ..., kr), Rr (k1, k2-1, ..., kr), ..., Rr (k1, k2-1, ..., kr-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[1] 36–41 49–61 59[2]–84 73–115 92–149
5 43–48 58–87 80–143 101–216 133–316 149[2]–442
6 102–165 115[2]–298 134[2]–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のときにラムゼー数が確定しているのは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 y を x -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. ^ “Ramsey Graphs”. 2019年3月2日閲覧。
  2. ^ a b c d Exoo, Geoffrey; Tatarevic, Milos (2015). “New Lower Bounds for 28 Classical Ramsey Numbers”. The Electronic Journal of Combinatorics 22 (3): 3. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p11. 

参考文献[編集]

  • 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.

関連項目[編集]

外部リンク[編集]

「https://ja.wikipedia.org/w/index.php?title=ラムゼーの定理&oldid=95104631」から取得