鳩の巣原理とラムゼー理論 ― 存在定理の組合せ論

一般化鳩の巣原理，Erdős–Szekeresの定理，ラムゼー数$R(s,t)$の存在，$R(3,3)=6$の証明，確率的方法による下界を扱う．

2026年2月27日

1 鳩の巣原理

定理 1 (鳩の巣原理).

n + 1

個の物を

n

個の箱に入れるとき，少なくとも1つの箱には2個以上の物が入る．

証明.

対偶を示す．すべての箱に高々1個の物が入るならば，物の総数は高々

n

個であり，

n + 1

個であることに矛盾する． □

定理 2 (一般化鳩の巣原理).

kn + 1

個の物を

n

個の箱に入れるとき，少なくとも1つの箱には

k + 1

個以上の物が入る．

証明.

すべての箱に高々

k

個ならば物の総数は高々

kn

個であり矛盾． □

2 Erdős–Szekeres の定理

定理 3 (Erd\H{o}s–Szekeres の定理).

長さ

rs + 1

以上の数列は，長さ

r + 1

以上の単調増加部分列または長さ

s + 1

以上の単調減少部分列を含む．

証明.

数列を

a_{1}, a_{2}, \dots, a_{rs + 1}

とする．各

a_{i}

に対して，

a_{i}

から始まる最長単調増加部分列の長さを

ℓ_{i}

とする．ある

i

で

ℓ_{i} \geq r + 1

ならば結論が成り立つ．

すべての

i

で

ℓ_{i} \leq r

と仮定する．

ℓ_{i}

は

{1, 2, \dots, r}

の値をとり，

rs + 1

個ある．鳩の巣原理より，同じ

ℓ_{i} = ℓ

を持つ添字が

s + 1

個以上存在する．これらの添字

i_{1} < i_{2} < \dots < i_{s + 1}

に対して，

a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{s + 1}}

は単調減少でなければならない．実際

a_{i_{j}} \leq a_{i_{k}}

（

j < k

）であれば

a_{i_{j}}

から始まる最長増加列の長さは

ℓ_{i_{k}} + 1 > ℓ_{i_{j}}

となり

ℓ_{i_{j}} = ℓ_{i_{k}}

に矛盾する． □

3 ラムゼー数

定義 4 (ラムゼー数).

K_{N}

の辺を赤と青に2色彩色するとき，赤の

K_{s}

か青の

K_{t}

が必ず見つかるような最小の

N

をラムゼー数

R (s, t)

という．

定理 5 (ラムゼー数の存在).

任意の正整数

s, t \geq 2

に対して

R (s, t) \leq (s - 1 s + t - 2)

が成り立つ．特に

R (s, t)

は有限である．

証明.

s + t

に関する帰納法で示す．

基底：

R (s, 2) = s

および

R (2, t) = t

である．実際，

K_{s}

の辺を2色彩色すれば，赤の辺が1本でもあれば赤の

K_{2}

が存在し，なければすべて青で青の

K_{s}

が存在する．

R (2, t) = t

も同様．

帰納段階：

s, t \geq 3

とし，

R (s - 1, t)

および

R (s, t - 1)

が有限であると仮定する．

N = R (s - 1, t) + R (s, t - 1)

とおき，

K_{N}

の辺を赤と青に2色彩色する．任意の頂点

v

を固定し，

v

に隣接する赤い辺の端点の集合を

A

，青い辺の端点の集合を

B

とする．

∣ A ∣ + ∣ B ∣ = N - 1 = R (s - 1, t) + R (s, t - 1) - 1

であるから，鳩の巣原理より

∣ A ∣ \geq R (s - 1, t)

または

∣ B ∣ \geq R (s, t - 1)

が成り立つ．

∣ A ∣ \geq R (s - 1, t)

の場合：

R (s - 1, t)

の定義より，

A

の誘導部分グラフには赤の

K_{s - 1}

か青の

K_{t}

が含まれる．青の

K_{t}

があれば結論が成り立つ．赤の

K_{s - 1}

があれば，その

s - 1

頂点はすべて

v

と赤い辺で結ばれているので，

v

を加えて赤の

K_{s}

が得られる．

∣ B ∣ \geq R (s, t - 1)

の場合も同様に，

B

内に赤の

K_{s}

か青の

K_{t - 1}

が含まれ，青の

K_{t - 1}

の場合は

v

を加えて青の

K_{t}

が得られる．

以上より

R (s, t) \leq R (s - 1, t) + R (s, t - 1)

が示された．

上界：

R (s, t) \leq (s - 1 s + t - 2)

を

s + t

に関する帰納法で示す．基底は

R (s, 2) = s = (s - 1 s)

，

R (2, t) = t = (1 t)

で成立する．帰納段階では

R (s, t) \leq R (s - 1, t) + R (s, t - 1) \leq (s - 2 s + t - 3) + (s - 1 s + t - 3) = (s - 1 s + t - 2)

が成り立つ（最後の等号はパスカルの恒等式による）． □

4 $R (3, 3) = 6$ の証明

定理 6.

R (3, 3) = 6

．

証明.

上界：

R (3, 3) \leq R (2, 3) + R (3, 2) = 3 + 3 = 6

．

下界：

K_{5}

の辺を2色彩色して単色

K_{3}

を避ける例を構成する．

C_{5}

（5閉路）の辺を赤，補グラフ

\overline{C_{5}}

（ペテルセングラフの内側星型に相当する

C_{5}

）の辺を青とする．赤の辺は

C_{5}

をなし，赤の三角形は含まれない（

C_{5}

に三角形がないため）．青の辺は

\overline{C_{5}} ≅ C_{5}

をなすので青の三角形も含まれない．よって

R (3, 3) > 5

． □

5 確率的方法による下界

定理 7 (Erd\H{o}s, 1947).

(k N) 2^{1 - (2 k)} < 1

ならば

R (k, k) > N

．特に

R (k, k) > 2^{k /2}

．

証明.

K_{N}

の各辺を独立に確率

1/2

で赤または青に彩色する．

k

頂点の部分集合

S

について，

S

が赤の完全グラフである確率は

2^{- (2 k)}

．青の完全グラフである確率も同様で，和集合の上界（union bound）より

Pr [単色 K_{k} が存在] \leq (k N) \cdot 2 \cdot 2^{- (2 k)} = (k N) 2^{1 - (2 k)}

これが

< 1

ならば単色

K_{k}

を含まない彩色が存在し，

R (k, k) > N

．

N = ⌊ 2^{k /2} ⌋

とすれば条件が満たされることが確認でき，

R (k, k) > 2^{k /2}

が得られる． □

確率的方法（probabilistic method）は Erdős が創始した組合せ論の強力な手法であり，構成的でない存在証明を与える．ランダムな対象が高い確率で望む性質を持つことを示すのが典型的な戦略である．

鳩の巣原理とラムゼー理論 ― 存在定理の組合せ論

1 鳩の巣原理

2 Erdős–Szekeres の定理

3 ラムゼー数

4 $R (3, 3) = 6$ の証明

5 確率的方法による下界

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

1 鳩の巣原理

2 Erdős–Szekeres の定理

3 ラムゼー数

4 R(3,3)=6の証明

5 確率的方法による下界

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

4 $R (3, 3) = 6$ の証明