Loading article…
ラムゼー理論は、イギリスの数学者で哲学者のフランク・P・ラムゼーにちなんで名付けられ、既知の大きさの構造を与えられた部分構造における秩序の出現に焦点を当てた数学の分野である。ラムゼー理論の問題は、典型的には「特定の特性が保たれることを保証するには、ある構造はどのくらいの大きさでなければならないか？」という形式の質問をする。[1]
例
ラムゼー理論の典型的な結果は、ある数学的構造から始まり、それを断片に分割することです。断片の少なくとも 1 つが特定の興味深い特性を持つことを保証するには、元の構造はどのくらいの大きさである必要がありますか? この考え方は、分割規則性として定義できます。
たとえば、n次元の完全グラフを考えてみましょう。つまり、 n 個の頂点があり、各頂点は辺によって他のすべての頂点と接続されています。 次元 3 の完全グラフは三角形と呼ばれます。次に、各辺を赤または青で色付けします。青い三角形または赤い三角形のいずれかが存在するようにするには、 n をどのくらい大きくする必要がありますか? 答えは 6 です。厳密な証明については、ラムゼーの定理に関する記事を参照してください。
この結果を別の方法で表現すると、次のようになります。6 人以上の人が集まるパーティーでは、全員が知り合い (それぞれが他の 2 人のことを知っている) か、全員が他人 (誰も他の 2 人のことを知らない) である人が 3 人います。友人と他人に関する定理を参照してください。
これは、ラムゼーの定理の特殊なケースでもあります。ラムゼーの定理は、任意の整数c、任意の整数n 1、...、n cに対して、 R ( n 1、...、n c )という数が存在し、 R ( n 1、...、n c )の完全グラフの辺がc つの異なる色で着色されている場合、 1 とcの間のあるiに対して、辺がすべて色iであるn i次完全サブグラフが必ず含まれるというものです。上記の特殊なケースでは、 c = 2 かつn 1 = n 2 = 3 です。
結果
ラムゼー理論の 2 つの重要な定理は次のとおりです。
- ファンデルワールデンの定理: 任意のcとnに対して、 V 個の連続する数が c 個の異なる色で着色されている場合、その数Vには、要素がすべて同じ色である長さ n の等差数列が含まれている必要があります。
- ヘイルズ・ジュエットの定理: 任意のnとcに対して、H次元のn × n × n ×...× n立方体のセルがc色で色付けされている場合、長さnの行、列などが 1 つ存在し、そのセルはすべて同じ色になります。つまり、十分な次元数を持つボードでプレイする場合、n がどれだけ大きくても、何人の人がプレイしていても、複数人でn列の三目並べをプレイすると引き分けに終わることはありません。ヘイルズ・ジュエットの定理から、ファンデルワールデンの定理が導かれます。
ファンデルワールデンの定理に似た定理に、シューアの定理がある。任意のcに対して、ある数Nが存在し、数 1、2、...、Nがc つの異なる色で着色されている場合、 x、y、x + yがすべて同じ色になるような整数のペアx、yが存在するというものである。この定理には、ラドーの定理、ラドー–フォークマン–サンダースの定理、ハインドマンの定理、ミリケン–テイラーの定理など、多くの一般化が存在する。これらやラムゼー理論の他の多くの結果に関する古典的な参考文献は、グラハム、ロスチャイルド、スペンサー、ソリモシの著書で、2015年に更新・拡張され、25年ぶりの新版となった。[2]
ラムゼー理論の結果には、通常、2 つの主な特徴があります。第 1 に、それらは非構成的であるということです。つまり、何らかの構造が存在することを示すことはできますが、その構造を見つけるためのプロセスは示されません (総当たり検索以外)。たとえば、鳩の巣原理はこの形式です。第 2 に、ラムゼー理論の結果では、十分に大きなオブジェクトには特定の構造が必ず含まれているとは述べていますが、これらの結果の証明では、これらのオブジェクトが非常に大きいことが求められることがよくあります。境界が指数関数的に増加したり、アッカーマン関数と同じ速さで増加することも珍しくありません。一部の小さなニッチなケースでは、上限と下限が改善されますが、一般的にはそうではありません。多くの場合、これらの境界は証明の産物であり、大幅に改善できるかどうかはわかっていません。他の場合には、境界は非常に大きく、場合によっては原始的な再帰関数よりも大きいことがわかっています。例としては、パリス-ハリントンの定理を参照してください。グラハム数は、本格的な数学的証明で使用された最大の数の一つであり、ラムゼー理論に関連する問題の上限である。もう一つの大きな例は、ブールピタゴラス数問題である。[3]
ラムゼー理論の定理は、一般的に次の 2 つのタイプのいずれかです。ラムゼーの定理自体をモデルにしたこのような定理の多くは、大きな構造化オブジェクトのすべての分割において、クラスの 1 つが必ずそれ自身の構造化オブジェクトを含むと主張しますが、それがどのクラスであるかについての情報は提供しません。他のケースでは、ラムゼー型の結果の背後にある理由は、最大の分割クラスが常に目的のサブ構造を含むことです。この後者の種類の結果は、密度結果またはトゥランの定理にちなんでトゥラン型結果と呼ばれます。注目すべき例としては、ファンデルワールデンの定理を強化したセメレディの定理や、ヘイルズ-ジューエットの定理の密度バージョンがあります。 [4]
参照
参考文献
- ^ グラハム、ロン;バトラー、スティーブ(2015)。ラムゼー理論の基礎(第2版)。アメリカ数学会。p. 1。ISBN 978-0-8218-4156-3。
- ^ グラハム、ロナルド L. ;ロスチャイルド、ブルース L. ;スペンサー、ジョエル H. ;ソリモシ、ヨーゼフ(2015)、『ラムゼイ理論』（第 3 版）、ニューヨーク：ジョン ワイリー アンド サンズ、ISBN 978-0470391853。
- ^ Lamb, Evelyn (2016-06-02). 「200テラバイトの数学証明は史上最大」. Nature . 534 (7605): 17–18. doi : 10.1038/nature.2016.19990 . PMID 27251254.
- ^ ヒレル、ファステンバーグ; Katznelson、Yitzhak (1991)、「Hales–Jewett 定理の密度バージョン」、Journal d'Analyse Mathématique、57 (1): 64–119、doi :10.1007/BF03041066。
さらに読む
- ランドマン、BM & ロバートソン、A. (2004)、「整数に関するラムゼー理論」、学生数学図書館、第24巻、プロビデンス、RI：AMS、ISBN 0-8218-3199-2。
- ラムゼー、FP（1930）、「形式論理の問題について」、ロンドン数学会誌、s2-30（1）：264–286、doi：10.1112/plms/s2-30.1.264（有料です）。
- ポール・エルデシュ;ジョージ セーケレス(1935)、「幾何学における組み合わせの問題」、Compositio Mathematica、2 : 463–470、doi :10.1007/978-0-8176-4842-8_3、ISBN 978-0-8176-4841-1、ZBL0012.27010 。
- Boolos, G.; Burgess, JP; Jeffrey, R. (2007)、Computability and Logic (第 5 版)、ケンブリッジ: Cambridge University Press、ISBN 978-0-521-87752-7。
- マシュー・カッツとヤン・ライマン『ラムゼー理論入門：高速関数、無限大、メタ数学』学生数学図書館 巻：87; 2018; 207 ページ; ISBN 978-1-4704-4290-3