|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ラム ： [らむ] 【名詞】 1. (1) lamb 2. (2) rump 3. (3) rum 4. (4) RAM (random access memory) 5. (P), (n) (1) lamb/(2) rump/(3) rum/(4) RAM (random access memory) ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
ラムゼーの定理（ラムゼーのていり）とは、数学の組合せ論における次の二つの定理のことである(フランク・ラムゼイ, 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''に類別したとき、あるiが存在して、''k''''i''個の元からなる''N''の部分集合で、その中のどの相異なる''s'' 個の元からなる部分集合も類''C''''i''に属するものが存在する。 以下、これを満たす最小の''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個以上ある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ラムゼーの定理」の詳細全文を読む スポンサード リンク
|