Featured image of post ラムゼー理論：無秩序の中にも必ず規則が現れる——6人の人間関係を色分けで証明
数学

ラムゼー理論：無秩序の中にも必ず規則が現れる——6人の人間関係を色分けで証明

6人集まると、互いに知り合いの3人か、互いに知り合いではない3人が必ず存在します。ラムゼー数 R(3,3)=6 を色分けした図で証明し、5人の反例、全32768通りの検証、数列やネットワークへの応用まで解説します。

1. 6人集まると、必ず見つかる3人組

パーティーに6人が集まったとします。昔からの知り合いもいれば、初対面の人もいるでしょう。誰と誰が知り合いなのかは、どれほど入り組んでいてもかまいません。それでも、次のどちらかが必ず見つかります。

  • 3人のどの2人を選んでも、互いに知り合いである。
  • 3人のどの2人を選んでも、互いに知り合いではない。

「たいてい見つかる」ではありません。関係をどう組み立てても、例外なく見つかります。さらに、6人という数は最小です。5人なら、どちらの3人組も作らない配置が可能です。

この小さな驚きが、ラムゼー理論への入口です。大きな構造をどれだけ複雑に分けても、十分な大きさがあれば、条件のそろった小さな構造を完全には避けられない。そんな「避けられない規則性」を扱います。

ただし、無秩序の中に何でも好きな規則が現れるという意味ではありません。何を対象とし、何種類に分類し、どんな形を探すのかを決めて初めて、数学的な主張になります。まずは紙に6個の点を描ける、身近な例から始めましょう。

2. 人間関係を、赤と青の線に置き換える

モデルの約束

この記事では「知り合い」を対称な関係とします。AがBを知っているならBもAを知っており、各ペアは「知り合い」か「知り合いではない」のどちらかに必ず分類できるとします。

一方的に名前だけ知っている関係や、知っているかどうか不明な関係は、このモデルには含めません。また「知り合いではない」は「嫌い」「敵対している」と同じ意味ではありません。

人を点にし、2人の関係を線にします。

図の要素意味
点（頂点）1人の参加者
赤い実線2人は互いに知り合い
青い破線2人は互いに知り合いではない
同じ色の3辺でできた三角形探している3人組

全員のすべてのペアを結ぶので、これは完全グラフです。頂点が $n$ 個の完全グラフを $K_n$ と書き、辺の数は次のとおりです。

$$ \binom{n}{2}=\frac{n(n-1)}{2} $$

6人なら15本あります。「AはBとCを知っている」だけでは、3人が互いに知り合いとは限りません。BとCの間も赤である必要があります。三角形の3辺すべてが同じ色という条件を忘れないでください。

以降は、すべて赤か、すべて青の三角形を単色三角形と呼びます。色が区別しにくい場合にも読めるよう、図では赤を実線、青を破線で示します。

3. 6人なら必ず見つかることを証明する

この証明で使う道具は、鳩の巣原理だけです。「5個のものを2種類に分けると、少なくとも一方に3個ある」という、ごく素朴な事実を使います。

手順1：1人だけに注目する

6人のうち、好きな1人をAとします。Aからは、残り5人へ5本の線が出ています。それぞれ赤か青なので、同じ色が少なくとも3本あります。

$$ \left\lceil\frac{5}{2}\right\rceil=3 $$

ここで $\lceil x\rceil$ は、$x$ 以上の最小の整数を表します。赤も青も2本以下なら合計4本以下にしかならず、5本を塗れない、と考えても同じです。

赤が3本以上ある場合を考え、その先の3人をB、C、Dと呼びましょう。A–B、A–C、A–Dはすべて赤です。最初に青が3本以上見つかった場合は、以下の赤と青を入れ替えれば同じ議論ができます。

手順2：B・C・Dの間を見る

B–C、B–D、C–Dの3本について、場合は二つしかありません。

場合①：赤い線が少なくとも1本ある。 たとえばB–Cが赤なら、A–BとA–Cも赤なので、A・B・Cが赤い三角形になります。ほかの2本がどんな色でも関係ありません。

場合②：赤い線が1本もない。 するとB–C、B–D、C–Dはすべて青です。今度はB・C・Dが青い三角形になります。

Aから同じ色の3本を選び、その先の3人の間に赤があれば赤い三角形、なければ青い三角形ができる証明図

図の灰色の辺と省略した辺は、証明で色を決める必要がない部分です。実際の完全グラフでは、それらにも赤か青のどちらかが付いています。

これで、どんな色分けでも単色三角形があるとわかりました。15本全部を調べる必要はありません。1人から出る5本と、その先の3人の関係だけで、すべての可能性を覆ったのです。大学教材の解説

4. なぜ5人では足りないのか？

「6人で十分」と「6人が最小」は、別の主張です。最小だと示すには、5人で条件を満たさない例を一つ作る必要があります。

5人を正五角形の頂点に置きます。隣り合う人どうし、つまり五角形の外周5本を赤にします。残る対角線5本はすべて青にします。

五角形の外周を赤、対角線を青に塗った5人の反例。どちらの色にも三角形がない

赤だけを見ると、五角形を一周する輪です。3人を選んでも、赤い辺だけで三角形を閉じられません。青だけを見ると星形ですが、頂点をたどる順番を変えれば、これも5個の頂点を一周する輪です。青にも三角形はありません。

星形の交差点は新しい頂点ではありません。人に対応するのはAからEの5点だけです。線の交差で小さな三角形が見えても、それはこの問題で数える三角形ではないことに注意しましょう。

赤い3人組も青い3人組も避けられるので、5人では保証できません。「6人なら必ず」と合わせて、最小人数が6だと確定します。

5. この「最小の大きさ」をラムゼー数と呼ぶ

完全グラフの辺を赤と青に塗ったとき、赤い $K_s$ または青い $K_t$ が必ず現れる最小の頂点数を、ラムゼー数 $R(s,t)$ と書きます。

赤い $K_s$ とは、選んだ $s$ 個の頂点の間のすべての辺が赤いことです。単に赤い道でつながっているだけでは足りません。$K_3$ は三角形なので、ここまでの結論は次の1行になります。

$$ R(3,3)=6 $$

ラムゼーの定理は、固定した有限の $s,t$ に対して、このような有限の数が存在すると述べます。しかし「存在する」ことと「最小値を簡単に求められる」ことは違います。三角形の証明は短くても、探す単色の集団を大きくすると計算は急激に難しくなります。

基本的な上界には、次の関係があります。

$$ R(s,t)\leq R(s-1,t)+R(s,t-1) \qquad(s,t\geq3) $$

右辺を $N$ として、$N$ 個の頂点のうち1個を選びます。その頂点から赤でつながる頂点が $R(s-1,t)$ 個以上あれば、その中に赤い $K_{s-1}$ または青い $K_t$ があります。前者なら元の頂点を加えて赤い $K_s$ にできます。後者ならそのまま目的達成です。

赤がそこまで多くなければ、青でつながる頂点が $R(s,t-1)$ 個以上あります。同じ議論を反対の色で行えばよいのです。これも「1点に注目し、同じ色の隣人を集める」という証明の拡張です。

境界の値 $R(2,t)=t$ と $R(s,2)=s$ から出発すれば、この関係で有限な上界を順に作れます。ただし不等号なので、得られた数が最小とは限りません。「保証できる大きさ」と「本当に必要な最小値」を区別することが大切です。

6. 「ほぼ必ず」と「例外なく必ず」は違う

今度は実験として、各辺を互いに独立に、確率 $1/2$ で赤か青に塗るとします。この確率モデルは証明には不要ですが、結果の違いを眺めるのに役立ちます。

頂点にA、B、C……と名前を付けたまま数えると、色分けの総数は次のようになります。回転や名前の付け替えで同じ形になるものも、別の色分けとして数えます。

$$ 2^{\binom{n}{2}} $$

6人なら $2^{15}=32768$ 通りです。3～6人についてすべてを調べると、次の結果になります。

人数色分けの総数単色三角形がない色分け単色三角形がある割合
3人8625.00%
4人641871.88%
5人10241298.83%
6人327680100.00%

3～6人で単色三角形が存在する割合を比較。5人では98.83%だが12通りの反例が残り、6人では100%になる

5人でも無作為に塗ると約98.83%で単色三角形があります。数回試しただけなら、「5人でも必ずある」と思ってしまうかもしれません。しかし、1024通りのうち12通りの反例が残っています。確率が高いことと、反例が一つもないことの間には、明確な違いがあります。

この表は独立・等確率で塗る場合の割合です。現実の知り合い関係が独立に半々で発生すると主張しているわけではありません。一方、6人の定理は確率に依存しないため、どれほど偏った関係でも成り立ちます。

平均では、いくつ見つかる？

固定した3頂点には3本の辺があり、色分けは8通りです。そのうち全部赤と全部青の2通りが単色なので、確率は $1/4$。単色三角形の個数を $T$ とすると、期待値の線形性から、

$$ E[T]=\binom{n}{3}\frac14 $$

となります。6人では平均5個です。三角形どうしは辺を共有するので独立とは限りませんが、期待値を足すことには独立性は必要ありません。

ただし、平均が正だからといって、すべての色分けに存在するとは言えません。5人の平均も2.5個なのに、0個の反例があります。「平均」と「最悪の場合」を混同しないことも、ラムゼー理論が教えてくれる視点です。

7. Pythonで32768通りを確かめる

次のコードは標準ライブラリだけで動きます。赤を0、青を1として、各辺の色を2進数の各桁に対応させます。3頂点を選び、その間の3辺が同色かどうかを調べます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from itertools import combinations

def check_all(n):
    edges = list(combinations(range(n), 2))
    edge_index = {edge: i for i, edge in enumerate(edges)}
    triples = [
        [edge_index[e] for e in combinations(vertices, 2)]
        for vertices in combinations(range(n), 3)
    ]
    total = 1 << len(edges)
    without_triangle = 0
    minimum = len(triples)

    for coloring in range(total):
        count = 0
        for i, j, k in triples:
            if ((coloring >> i) & 1) == ((coloring >> j) & 1) == ((coloring >> k) & 1):
                count += 1
        without_triangle += (count == 0)
        minimum = min(minimum, count)

    return total, without_triangle, minimum

for n in range(3, 7):
    total, missing, minimum = check_all(n)
    print(f"{n}人: 全{total}通り、三角形なし{missing}通り、最小{minimum}個")

1
2
3
4

3人: 全8通り、三角形なし6通り、最小0個
4人: 全64通り、三角形なし18通り、最小0個
5人: 全1024通り、三角形なし12通り、最小0個
6人: 全32768通り、三角形なし0通り、最小2個

6人の「最小2個」は、最初の証明より少し強い発見です。実際、赤い辺の本数を各頂点で $r_v$、青い辺の本数を $b_v$ とすると、$r_v+b_v=5$ で、$r_vb_v\leq6$ です。

単色でない三角形には、赤と青の2本が接する頂点がちょうど二つあります。そこで各頂点の「赤1本・青1本の組」を数えると、非単色三角形を2回ずつ数えます。全三角形は20個なので、

$$ T=\binom63-\frac12\sum_{v=1}^{6}r_vb_v \geq20-\frac12\cdot6\cdot6=2 $$

と証明できます。しかも、6頂点を3個ずつに分け、各組の内部を赤、組をまたぐ辺を青にすれば、赤い三角形が二つ、青い三角形がゼロになります。したがって最小値2も正確です。

この全列挙は小さい人数には有効ですが、色分け総数は $2^{n(n-1)/2}$ で増えます。人数を増やして同じコードを走らせると急に重くなるため、ここでは3～6人に限定しています。図と詳細な分布は再現用スクリプトと計算結果JSONで確認できます。

8. 応用①：ネットワークの「全接続」か「全非接続」

知り合いという言葉を、機器間の直接接続に置き換えてみましょう。6台の機器があり、各ペアは「直接接続あり」か「直接接続なし」のどちらかだとします。向きのない接続であれば、同じ定理をそのまま使えます。

すると、3台すべてのペアに接続がある集団か、3台のどのペアにも直接接続がない集団が必ず存在します。前者は3頂点のクリーク、後者は3頂点の独立集合です。ここで「直接接続なし」は、別の機器を経由しても通信できないという意味ではありません。

この見方は、ペアごとに両立・非両立を決めた作業や、相互関係を調べる小さなネットワークの設計チェックにも使えます。「全組が両立する3件も、全組が非両立な3件も避けたい」と要求しても、対象が6件あれば不可能だと、探索前にわかります。

ただし、定理はどちらが現れるかを選んでくれません。両立する3件が欲しいのに、非両立な3件だけが見つかる場合もあります。また、ペア単位で両立しても3件同時には資源が足りない、という条件は別に確認が必要です。保証の対象は、あくまで与えた二者関係です。

9. 応用②：ばらばらの数列から増加・減少の並びを取り出す

互いに異なる6個の数を、順番に並べます。位置 $i$ が $j$ より前にあるとき、$a_i\lt a_j$ なら赤、$a_i\gt a_j$ なら青で、その2位置を結びます。

これも6頂点の完全グラフの2色分けです。したがって単色三角形が存在します。その3位置を小さい順に $i\lt j\lt k$ とすると、赤い三角形なら、

$$ a_i\lt a_j\lt a_k $$

青い三角形なら、

$$ a_i\gt a_j\gt a_k $$

です。つまり、元の順序を保ったまま、増加する3項か減少する3項を必ず取り出せるとわかります。連続している必要はありません。このように、順番を変えずに一部を抜き出したものを部分列と呼びます。

数列4、1、5、2、6、3から、元の位置2、4、6を選んで増加部分列1、2、3を取り出す図

図の数列 $4,1,5,2,6,3$ では、2・4・6番目を選ぶと $1,2,3$ が得られます。数値を小さい順に並べ替えたのではなく、元の出現順序を保って選んでいます。

これはデータ列の中から規則的な部分構造を見つける考え方につながります。ただし、選び出した3点が増加していても、系列全体が上昇傾向にある証拠にはなりません。どんな並びにも必ず見つかる形なら、その存在だけでは特別な現象といえないからです。

なお、この数列の問題では6項が最小とは限らず、実際には異なる5項でも長さ3の増加または減少部分列が保証されます。これはエルデシュ–セケレシュの単調部分列定理の特別な場合です。数列から作る色分けには大小関係の制約があるため、任意の2色分けより強い結果が得られます。単調部分列に関する講義資料

10. まとめ：乱雑さにも、避けられない形がある

6人の関係を赤と青に置き換え、1人から出る5本に注目するだけで、単色三角形が必ず見つかると証明できました。5人の五角形は反例を与えるので、ラムゼー数は $R(3,3)=6$ です。

覚えておきたいのは、次の三つです。

  • 「必ず」は、無作為な実験で高確率という意味ではない。 5人では約98.83%でも反例が残り、6人では一つも残らない。
  • 規則の存在と、その規則の意味は別である。 単色三角形や増加部分列があるだけで、集団全体の性質や因果関係は決まらない。
  • 保証には対象と条件がある。 関係が対称か、すべてのペアを2種類に分類できるか、どんな部分構造を探すかを明確にする。

ラムゼー理論の面白さは、複雑な全体が単純になることではありません。全体は複雑なままでも、その中の小さな規則を完全に消すことはできない。紙に描いた数本の線から、その考え方を確かめられるのです。

参考資料

本記事の図、全列挙の表、確率と個数の分布は、付属のPythonスクリプトで生成しています。

comments powered by Disqus
© 2020 - 2026 kenjinote
Hugo で構築されています。
テーマ Stack は Jimmy によって設計されています。