ラムゼー理論

ラムゼー理論は、完全な無秩序がいかに不可能であるかを研究します。すなわち、十分に大きな構造は、高度に組織化された部分構造を必ず含むというものです。

Definition

組合せ論の一分野であり、ある構造の任意の分割または彩色が、単色またはその他の所定の部分構造を生み出すことを保証するために、その構造がどれほど大きくなければならないかを問うものです。

Scope

この分野は、グラフおよびハイパーグラフに対するラムゼーの定理とその定量的ラムゼー数、Schurの定理、van der Waerdenの定理、Hales-Jewettの定理といった整数の分割に関する結果、そしてパラメーター集合の抽象的な構造的ラムゼー理論を扱います。これは、十分に大きなシステムは秩序を避けられないという極値組合せ論的原理を例証するものです。

Sub-topics

• Ramsey's Theorem and Ramsey Numbers
• Partition Regularity and Structural Ramsey Theory

Core questions

• 不可避な秩序ある部分構造を強制するために、構造はどれほど大きくなければならないか？
• これらの保証に対する正確な、または近似的な閾値であるラムゼー数は何か？
• 整数の分割定理はどのように算術的パターンを保証するか？
• どの抽象的な構造の族がラムゼー特性を満たすか？

Key concepts

• ラムゼーの定理
• ラムゼー数
• 単色部分構造
• ファン・デル・ヴェルデンの定理
• シューアの定理
• ヘールズ-ジェウェットの定理

Clinical relevance

ラムゼー型の不可避な構造の保証は、理論計算機科学における下限の議論、大規模ネットワークの分析、および加法的数論に情報を提供し、既知の境界間のギャップは確率論的方法を推進します。

History

フランク・ラムゼーによる1930年の分割に関する定理は、元々は論理学の問いのために証明されましたが、ErdosとSzekeresによって、20世紀を通じて発展した不可避な構造に関する広範な理論の種として認識されました。

Key figures

• Frank Ramsey
• Paul Erdos
• Bartel van der Waerden

Seminal works

• graham1990
• landman2003

Frequently asked questions

ラムゼー理論のスローガンは何ですか？

完全な無秩序は不可能です。すなわち、いかに配置されていようとも、十分に大きなシステムは必ずかなりの秩序ある部分を含みます。

ラムゼー数の計算が難しいのはなぜですか？

確認すべき彩色の数が天文学的に増加するため、R(5,5)のような小さなラムゼー数でさえ、多大な努力にもかかわらず未だ不明です。