ラムジー理論

ラムゼー理論は、イギリスの数学者で哲学者のフランク・P・ラムゼーにちなんで名付けられた組み合わせ論の数学分野の一分野で、既知のサイズの構造が与えられた場合に部分構造に秩序が現れることに焦点を当てています。ラムゼー理論の問題は、通常、「特定の性質が成り立つことを保証するには、ある構造はどのくらいの大きさでなければならないか？」という形式の質問をします。^{[ 1 ]}

ラムゼー理論における典型的な結果は、まず何らかの数学的構造が提示され、それが分割されるというものです。分割された構造のうち少なくとも1つが特定の興味深い性質を持つことを保証するためには、元の構造はどの程度の大きさでなければならないのでしょうか？この考え方は、分割規則性として定義できます。

例えば、次数nの完全グラフを考えてみましょう。つまり、n個の頂点があり、各頂点は他のすべての頂点と辺で結ばれています。次数 3 の完全グラフは三角形と呼ばれます。ここで、各辺を赤または青に塗り分けます。青い三角形か赤い三角形のどちらかが存在するためには、n はどれくらい大きくなければならないでしょうか。答えは 6 です。厳密な証明については、ラムゼーの定理に関する記事を参照してください。

この結果を別の言い方で表現すると次のようになります。6人以上のパーティーでは、必ず3人が互いに知り合い（それぞれが他の2人を知っている）か、互いに見知らぬ人（誰も他の2人を知らない）のいずれかになります。友人と見知らぬ人に関する定理を参照してください。

これもラムゼーの定理の特殊なケースです。ラムゼーの定理は、任意の整数cと任意の整数n ₁ ,..., n _cに対して、次数 R ( n ₁ ,..., n _c ) の完全グラフの辺をc種類の異なる色で着色した場合、1 からcまでの間のiに対して、辺がすべて色iである次数n _iの完全部分グラフが含まれるような数R ( n ₁ ,..., n _c ) が存在することを示しています。上記の特殊なケースでは、c = 2 でn ₁ = n ₂ = 3 です。

ラムゼー理論の2つの重要な定理は以下のとおりです。

• ファン・デル・ヴェルデンの定理：任意のcとnに対して、連続する V 個の数をc種類の異なる色で着色すると、その数には長さnの等差数列が含まれ、その要素はすべて同じ色でなければならない。
• ヘイルズ・ジュエットの定理：任意のnとcに対して、ある数Hが存在し、 n × n × n ×... × n次元の立方体のセルをc色で着色した場合、長さnの行、列などが必ず存在し、そのセルはすべて同じ色になります。つまり、 n がどれだけ大きくても、何人がプレイしていても、十分な次元を持つ盤面上でプレイする場合、マルチプレイヤーのn列三目並べは引き分けで終わることはありません。ヘイルズ・ジュエットの定理は、ファン・デル・ヴェルデンの定理を導きます。

ファン・デル・ヴェルデンの定理に似た定理として、シューアの定理があります。任意のcに対して、1, 2, ..., Nの数をc種類の異なる色で着色すると、 x、y、およびx + yがすべて同じ色になるような整数の組x、y が存在するような数Nが存在します。この定理には、ラドの定理、ラド・フォークマン・サンダースの定理、ヒンドマンの定理、ミリケン・テイラーの定理など、多くの一般化が存在します。ラムゼー理論におけるこれらの結果やその他の多くの結果に関する古典的な参考文献は、25 年ぶりの新版として 2015 年に更新および拡張された Graham、Rothschild、Spencer、および Solymosi です。^{[ 2 ]}

ラムゼー理論の結果には、通常、主に2つの特徴があります。第一に、それらは非構成的です。つまり、何らかの構造が存在することを示すことはできますが、その構造を見つけるための手順（総当たり探索以外）は示しません。例えば、鳩の巣原理はこの形式です。第二に、ラムゼー理論の結果は、十分に大きなオブジェクトには必ず特定の構造が含まれると述べていますが、これらの結果の証明には、多くの場合、これらのオブジェクトが非常に大きいことが求められます。指数関数的に、あるいはアッカーマン関数と同じ速さで増加する境界は珍しくありません。ごく一部の特殊なケースでは、上限と下限が改善されますが、一般的にはそうではありません。多くの場合、これらの境界は証明の産物であり、大幅に改善できるかどうかは不明です。また、他のケースでは、境界は非常に大きくなければならず、場合によっては、あらゆる原始的な再帰関数よりも大きくなることが知られています。例として、パリス・ハリントンの定理を参照してください。グラハム数は、真剣な数学的証明で使用された最大の数の 1 つであり、ラムゼー理論に関連する問題の上限です。もう 1 つの大きな例は、ブールピタゴラス トリプル問題です。^{[ 3 ]}

ラムゼー理論の定理は、一般的に次の 2 種類の 1 つに分類されます。ラムゼーの定理自体をモデルにした多くの定理は、大きな構造化オブジェクトのすべての分割において、クラスの 1 つが必ずその構造化オブジェクトを含むと主張しますが、どのクラスであるかについては情報を提供しません。その他の場合、ラムゼー型の結果の根拠は、最大の分割クラスが常に目的のサブ構造を含むことです。この後者の種類の結果は、トゥランの定理にちなんで、密度結果またはトゥラン型結果と呼ばれます。注目すべき例としては、ファン・デル・ヴェルデンの定理の強化であるセメレディの定理や、ヘイルズ・ジュエットの定理の密度バージョンなどがあります。^{[ 4 ]}

• エルゴード的ラムゼイ理論
• 極値グラフ理論
• グッドスタインの定理
• バーテル・レンデルト・ファン・デル・ワールデン
• 不一致理論
• ヒマワリの推測

• Landman, BM & Robertson, A. (2004), Ramsey Theory on the Integers , Student Mathematical Library, vol.  24, Providence, RI: AMS, ISBN 0-8218-3199-2。
• Ramsey, FP (1930)、「形式論理の問題について」、ロンドン数学会紀要、s2-30 (1): 264–286、doi : 10.1112/plms/s2-30.1.264（有料コンテンツ）
• ポール・エルデシュ; Szekeres、George (2008) [1935]、「幾​​何学の組み合わせ問題」、Compositio Mathematica、vol.  2、463–470ページ、土井： 10.1007 /978-0-8176-4842-8_3、ISBN  978-0-8176-4841-1、Zbl 0012.27010 。
• Boolos, G.; Burgess, JP; Jeffrey, R. (2007), Computability and Logic (5th  ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-87752-7。
• マシュー・カッツ、ヤン・ライマン著『ラムゼー理論入門：高速関数、無限大、メタ数学』学生数学ライブラリー第87巻、2018年、207ページ、ISBN 978-1-4704-4290-3