ラムゼー理論とは? わかりやすく解説

ラムゼー理論

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/07/17 04:26 UTC 版)

ラムゼー理論(ラムゼーりろん、: Ramsey theory)は、一定の秩序がどのような条件の下で必ず現れるかを研究する数学の一分野である。

名前はイギリスの数学者・哲学者であるフランク・ラムゼイ (Frank P. Ramsey) に因んでいる。ラムゼー理論の問題は、典型的には「ある構造がある性質を持つことを保証するには、その構造にはどのくらいが必要か」という形のものである。

ラムゼー理論における典型的な結果では、まず何らかの数学的構造が与えられ、次いでその構造がいくつかの断片へと分割される。その断片の少なくとも1つが所与の興味深い性質を持つためには、元の構造がどれだけ大きければよいのだろうか。この考えは分割の正則性英語版として定義される。

例えば、位数が n完全グラフを考える。すなわち、そのグラフには n 個の頂点があり、全ての頂点が互いに辺により結ばれている。位数が3の完全グラフは三角形と呼ばれる。今、各辺の色を赤または青とする。赤または青一色の三角形があることを保証するには、n はどれだけ大きければよいか。答えは6である。厳密な証明ラムゼーの定理英語版に書かれている。

この結果は次のようにも表現できる。すなわち、少なくとも6人いれば、その中に、互いに知り合い(それぞれが他の二人を知っている)、もしくは互いに他人(それぞれが他の二人を知らない)であるような3人がいる。詳しくはパーティ問題英語版を参照のこと。

この結果はラムゼーの定理の特別な場合でもある。その定理は、任意の自然数 c と任意の自然数 n1, ..., nc に対し、ある数 R(n1, ..., nc) が存在して、位数 R(n1, ..., nc) の完全グラフの辺が c 種類の色に塗られているならば、1 以上 c 以下のある自然数 i に対して、全ての辺が i 番目の色で塗られている位数 ni の完全部分グラフが必ず含まれるというものである。

結果

ラムゼー理論の鍵となる二つの定理は以下のものである:

  • ファン・デル・ヴェルデンの定理: 任意に cn が与えられたとき、ある自然数 V が存在して、以下の条件を満たす: V 個の連続する自然数が c 色に塗り分けられているならば、どの元も同じ色で塗られている、長さ n等差数列が含まれている。
  • ヘイルズ–ジュエットの定理英語版: 任意に cn が与えられたとき、ある自然数 H が存在して、以下の条件を満たす: n×n×...×nH 次元超立方体のセルを c 色で塗り分けると、ある長さnの行や列などが存在して、それに属する全てのセルが同じ色で塗り分けられている。すなわち、一列に n マスある多人数まるばつは、どれほど n が大きくても、どれほど多人数で遊んだとしても、十分次元の大きい盤面で遊ぶ際、引き分けに終わることがない。ヘイルズ–ジュエットの定理はファン・デル・ヴェルデンの定理を含む。

ファン・デル・ヴェルデンの定理に似た定理にシューアの定理英語版があり、これは次のような定理である。これは、任意に c が与えられたとき、ある自然数 N が存在して、以下の条件を満たす: 1, 2, ..., N という数が c 色で塗り分けられているならば、x, y, x + y が全て同じ色となるような自然数 x, y の組が存在する。この定理の一般化はラドの定理英語版Rado-Folkman-Sandersの定理英語版Hindmanの定理英語版Milliken-Taylorの定理英語版など多数ある。これらの定理やその他多くの結果の古典的な参考文献として、Graham, Rothschild and Spencer[1]がある。

ラムゼー理論の結果は二つの主要な特徴がある。第一に、構成的ではない英語版ことである。結果は、ある構造が存在することは示しているが、(力まかせ探索を除いて)この構造を見つけるための手段は与えていない。例えば、鳩の巣原理はこの形式に属する。第二に、ラムゼー理論の結果は十分大きな対象がある与えられた構造を必ず持つことを示す一方、この結果の証明にはその大きさが莫大であることがしばしば要求される。その大きさの上界は、指数関数的に、あるいは、アッカーマン関数と同じくらいの速さで増大することさえ珍しくはない。多くの場合このような上界は証明に用いられる人為的なものであり、その上界を十分に改善できるかどうかは知られていない。またある場合にはどのような上界も莫大でなければならず、ときにはどのような原始再帰関数よりさえも大きい。例はパリス–ハーリントンの定理を参照。グラハム数は、正式な数学の証明において使われた最大の数であり、ラムゼー理論に関する問題の上界である。

ラムゼー理論における定理は一般的に2種類に分けられる。多くの定理は、ラムゼーの定理そのものをモデルとしており、大きな構造を持つ対象の任意の分割において、類の1つが必ず大きな構造を持つ部分対象を持つことを主張するが、それがどの類なのかに関する情報は一切与えない。いくつかの場合において、そのようなラムゼー型の結果が成り立つ理由は、最大の分割類がつねに所望の部分構造を含むからである。この種の結果は、density results, あるいはトゥラーンの定理英語版に因んで、トゥラーン型の結果と呼ばれる。代表的な例として、ファン・デル・ヴェルデンの定理をそのように強めたものであるセメレディの定理英語版や、ヘイルズ-ジュエットの定理の密度版がある[2]

関連項目

注釈

  1. ^ Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory (2nd ed.), New York: John Wiley and Sons, ISBN 0-4715-0046-1 .
  2. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1991), “A density version of the Hales–Jewett theorem”, Journal d'Analyse Mathématique 57 (1): 64–119, doi:10.1007/BF03041066 .

参考文献


ラムゼー理論

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/20 09:41 UTC 版)

組合せ数学」の記事における「ラムゼー理論」の解説

フランク・ラムゼイどのような6人が集まっても、その中には常に互いに知り合いの3人か、互いに全く知らない3人が見つけられるということ証明した証明背理法による短いものである。この主張正しくない仮定する。これは、どの3人を見てもその中の2人知り合いで、2人知り合いではない、ということ意味している。ここで、この6人の中の1人を"A"としよう残りの5人の中には"A"と知り合いである3人か、知り合いでない3人が存在する。これは、片方否定がもう片方になることから明らかである。では、始めの方の条件をまず仮定する。このとき3人中2人以上は互いに知り合いである。なぜなら、そうでないとすると、互いに知り合いでない3人がいることになり仮定反するからである。しかし、そうするとその2人はAも知っているので、この3人が互いに知り合いになってしまう。これは最初仮定矛盾する。もう一方条件 (残りの5人には"A"と知り合いでない3人が存在すること) を仮定する場合同様な矛盾導かれる。 これはラムゼーの定理特殊な場合である。 無秩序な配置秩序見出すという考えからラムゼー理論は生まれた一言で言うと、この理論任意に大きな配置にはある別の種類配置少なくとも1つは含むことを主張している。

※この「ラムゼー理論」の解説は、「組合せ数学」の解説の一部です。
「ラムゼー理論」を含む「組合せ数学」の記事については、「組合せ数学」の概要を参照ください。

ウィキペディア小見出し辞書の「ラムゼー理論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ラムゼー理論」の関連用語

ラムゼー理論のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ラムゼー理論のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのラムゼー理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの組合せ数学 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS