ラムゼーの定理とラムゼー数

ラムゼーの定理は、十分に大きな2色に彩色された完全グラフには単色クリークが必ず存在することを保証し、ラムゼー数はその「十分に大きな」度合いを定量化します。

Definition

ラムゼー数 R(s,t) は、n 頂点の完全グラフの辺を赤と青でどのように彩色しても、s 頂点の赤のクリークまたは t 頂点の青のクリークのいずれかを含むような最小の整数 n です。

Scope

このトピックでは、グラフ形式のラムゼーの定理、ラムゼー数 R(s,t) の定義、R(3,3)=6 のような古典的な小さなケース、エルデシュ-セケレスの上限とエルデシュの確率的下限、および多色およびハイパーグラフのラムゼー数への拡張について扱います。これはラムゼー理論の定量的な核心です。

Core questions

• 与えられたサイズの単色クリークを強制するために、完全グラフはどのくらい大きくなくてはならないか？
• ラムゼー数の既知の厳密な値と範囲は何か？
• 確率的議論はラムゼー数の下限をどのように与えるのか？
• この定理は、複数の色やハイパーグラフにどのように一般化されるのか？

Key concepts

• グラフのラムゼーの定理
• ラムゼー数 R(s,t)
• 単色クリーク
• エルデシュ-セケレスの限界
• 確率的下限
• 多色およびハイパーグラフのラムゼー数

Key theories

エルデシュ-セケレスの上限

ラムゼー数は有限であり、R(s,t) は s+t-2 から s-1 を選ぶ二項係数以下であるという上限によって制限されます。これは、明示的な推定値でラムゼーの定理を証明する漸化式に基づいた上限です。

エルデシュの確率的下限

ランダムな彩色における期待される単色クリークの数を数えることにより、エルデシュは1947年に、対角ラムゼー数 R(s,s) が少なくとも指数関数的に増加することを示しました。これは確率的手法の創始的な応用です。

Clinical relevance

ラムゼー数の下限を通じて導入された確率的手法は、組み合わせ論および理論計算機科学全体における中心的なツールとなり、ラムゼー型の保証は、通信およびデータ構造における下限の基礎となっています。

History

エルデシュとセケレスは、1935年に凸多角形を研究している際にラムゼーの定理を再発見し、定量化しました。エルデシュの1947年のランダム彩色による下限は、確率的手法を確立しました。

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

なぜ R(3,3) は6に等しいのですか？

6人のうち、3人が互いに知り合いであるか、または3人が互いに見知らぬ人であるかのいずれかですが、5人ではどちらも避けるように配置できるため、6が正確な閾値となります。

厳密なラムゼー数は知られていますか？

厳密に知られているのはごくわずかです。R(5,5)でさえ未解決であり、探索空間が計算で解決するには速すぎるため、現在の知識では範囲を絞り込むことしかできません。