ラムゼー理論：無秩序の中に必ず現れる構造を扱う組合せ論

基本概念

ラムゼー理論の中心にはラムゼーの定理がある。これは、十分に大きな完全グラフの辺を固定された有限個の色でどのように彩色しても、任意に指定した大きさの単色完全部分グラフが含まれる、という定理である。有限の場合の定式化からはラムゼー数 R(m,n) が導かれる。これは、一方または他方の色の単色クリークを強制するために必要な最小の大きさを表す。この理論には有限版と無限版があり、無限定理は、無限集合の k 要素部分集合を有限個の色で彩色すると、無限の単色族が必ず存在すると述べる。これは論理学においても基本的な関心をもつ結果である。

例と説明

• 古典的な「パーティー問題」では、6人の中には、互いに知り合いである3人組か、互いに見知らぬ3人組が必ず存在する。これは R(3,3)=6 と同値の主張である。
• 整数の彩色からも、別の状況では単色の等差的パターンが生じる。関連する結果は、数列や配置の中で規則性がどのように現れるかを示している。

歴史と発展

フランク・ラムゼーは20世紀初頭、論理学と決定理論の問題に取り組む中で最初の定理を定式化した。その後、とりわけポール・エルデシュらがこの分野を大きく発展させ、確率的方法を導入してラムゼー数の下界を与え、超グラフや構造的変種への一般化を探究した。時とともにこの分野は、集合論、位相幾何学、理論計算機科学とのつながりを深めてきた。

応用、変種、未解決問題

ラムゼー型の議論は多分野に現れる。グラフ理論と極値組合せ論では存在証明を導き、論理学と集合論では独立性の結果に示唆を与え、計算機科学では特定のアルゴリズムやデータ構造の限界を示す。定量的な問題の多くは未解決のままであり、たとえば大部分のラムゼー数の正確な値は未知で、計算も困難である。また、標準的ラムゼー理論、構造的ラムゼー理論、幾何学的ラムゼー理論などへも分かれ、それぞれ不可避な秩序について異なる概念を研究する。

注目すべき点：ラムゼー理論は、見かけ上の混沌から何らかの秩序が必ず生じる条件を形式化し、大規模または無限の系における避けられない構造を明らかにする手法と印象的な定理を提供する。入門的な資料については、組合せ論およびグラフ理論の標準的な概説や教科書を参照されたい（概説、基礎文献）。