ラムゼーの定理

ラムゼーの定理

ラムゼーの定理は、数学の組合せ論における基本的な定理の一つで、フランク・ラムゼイによって1930年に発表されました。この定理は、十分に大きな集合を分割したり彩色したりした場合、その中に必ず特定の性質を持つ一様な部分構造が存在することを保証します。

定理の概要

ラムゼーの定理には、主に「無限ラムゼーの定理」と「有限ラムゼーの定理」の二つの形式があります。

無限ラムゼーの定理

無限集合から特定の個数の要素を選んでできる部分集合を、いくつかのカテゴリにどのように分類しても、元の無限集合の中に無限部分集合が存在し、その部分集合から選ばれる同じ個数の要素からなる全ての部分集合が同一のカテゴリに属するという定理です。簡単に言えば、無限の世界では、どんな分け方をしても必ず無限に続く同じ性質のパターンが見つかるということです。

有限ラムゼーの定理

有限集合に関する定理で、より応用範囲が広いです。ある非負整数 s, r, k₁, k₂, ..., kᵣ (ただし kᵢ ≥ s) が与えられたとき、それを満たす十分大きな整数 R が存在するというものです。具体的には、要素数が R 以上の有限集合から s 個の要素を選んでできる部分集合全体を r 個のカテゴリ C₁, C₂, ..., Cᵣ に分類した場合、必ずいずれかのカテゴリ Cᵢ に属するような、kᵢ 個の要素からなる部分集合が存在します。この条件を満たす最小の整数 R をラムゼー数と呼び、Rr(s; k₁, k₂, ..., kᵣ) と表記します。有限ラムゼーの定理は、無限ラムゼーの定理から導出されます。

ラムゼーの定理は、s=1 の場合に鳩の巣原理として知られる原理を含むため、鳩の巣原理の一般化とみなすことができます。

グラフ理論における表現

特に s=2 の場合、ラムゼーの定理はグラフ理論の言葉で表現されることが多いです。これは、n 個の頂点を持つ完全グラフ（どの2点間も辺で結ばれているグラフ）の辺を r 色に彩色した場合、必ずある色 i で彩色された kᵢ 個の頂点からなる完全部分グラフ（クリック）が存在するという形で述べられます。

有名な例：R₂(3, 3) = 6

ラムゼー数の最も有名で理解しやすい例の一つが R₂(3, 3) = 6 です。これは、「6人集まれば、その中に互いに全員が知り合いである3人組か、あるいは互いに全員が誰とも知り合いでない3人組が必ず存在する」という事実に対応します。

この例をグラフ理論で考えると、6頂点の完全グラフの辺を2色（例えば赤と青）で塗ることに相当します。赤は「知り合い」、青は「知り合いでない」関係を表すとします。R₂(3, 3) = 6 は、この彩色されたグラフには必ず単色（赤だけ、または青だけ）の三角形（3頂点の完全部分グラフ）が存在することを意味します。

証明の概略:
6つの点から任意の1点 A を選びます。点 A から他の5点への辺は、赤か青のいずれかです。鳩の巣原理により、5本の辺のうち少なくとも3本は同じ色であるはずです。例えば、赤色の辺が3本以上あったとします。点 A と赤い辺で結ばれている3つの点 B, C, D を考えます。

もし点 B, C, D のうちいずれか2点（例えば BとC）を結ぶ辺が赤であれば、三角形 ABC は全ての辺が赤になります。これは単色の三角形です。
もし点 B, C, D のどの2点を結ぶ辺も赤でなければ、辺 BC, CD, DB は全て青になります。この場合、三角形 BCD は全ての辺が青になります。これも単色の三角形です。

したがって、点 A から出る赤い辺が3本以上ある場合、必ず単色の三角形が存在します。点 A から出る青い辺が3本以上ある場合も同様の議論で単色の三角形が存在することが示せます。これにより、6点あれば必ず単色の三角形が存在することが証明されます。

なお、5点の場合では単色の三角形が存在しない彩色が可能であることが知られており、このことから R₂(3, 3) は5よりも大きいことがわかります。

ラムゼー数の性質と計算の難しさ

ラムゼー数は多くの性質を持ち、いくつかの重要な不等式が知られています。例えば、r=s=2 の場合のラムゼー数 R(k, l) = R₂(k, l) については、以下の関係などが知られています。

R(k, l) ≤ R(k-1, l) + R(k, l-1)
R(k, k) ≤ 4R(k, k-2) + 2

これらの不等式は、ラムゼー数の存在を示すための帰納的な議論にも用いられます。

ラムゼー数の具体的な値を決定することは非常に困難な問題であり、特定のパラメータに対する値でさえ、確定しているものは非常に少ないです。例えば、r ≥ 3 の場合で値が確定しているのは R₃(3, 3, 3) = 17 のみであることが知られています。R₃(3, 3, 3) = 17 は、1から17までの整数を3つの集合にどのように分割しても、そのうちの一つの集合の中に x + y = z を満たす3数 (x, y, z は同じ集合内) が存在することを示します。

より多くのパラメータに対するラムゼー数は、正確な値ではなく、その取りうる範囲（下界と上界）のみが知られている場合が多いです。例えば、R₄(3, 3, 3, 3) については 51 ≤ R₄(3, 3, 3, 3) ≤ 62 という範囲が知られています。

関連する定理

ラムゼーの定理に類似する定理は数多く存在し、ファン・デル・ヴェルデンの定理などが知られています。これらの定理は、近年発見された Hales-Jewett の定理によって一つの統一的な理論の中に位置づけられるようになりました。

ラムゼーの定理は、一見すると単純な組合せ的な性質を述べているように見えますが、その背後には深い構造が存在し、特にラムゼー数の決定問題は現代数学における大きな未解決問題の一つとなっています。

もう一度検索