コラム
2017年09月04日

パーティ問題又はラムゼー問題－混沌の中にも、一定のスケールがあれば、特定の秩序が現われるってこと知っていましたか－

このレポートの関連カテゴリ

Xでシェアする Facebookでシェアする

文字サイズ

  • 小
  • 中
  • 大
全文ダウンロード（PDF）

はじめに

皆さん、「パーティ問題」というのをご存知だろうか。政治家の行う政治資金調達のためのパーティー券の購入代金を巡る問題ではない。まさに、我々一般が日常生活において開催・参加する「パーティ」に絡む問題である。

今回の研究員の眼では、こうした「パーティ問題」と呼ばれるもののうち、「ラムゼー問題」と呼ばれるものを紹介する。

ラムゼー問題

一般的に「ラムゼー問題」と呼ばれているものは、パーティを題材にして、

「パーティで6人が集まれば、お互いが知り合いである3人組か、お互いに知らない3人組、のいずれかが必ず存在することを証明せよ。」

という問題である。

これは、グラフ理論や組み合わせ理論において、非常に有名な問題である。一見すると必ずしも自明ではないと思われるが、結論はとても興味深いと感じられるのではないか。こうした考え方は、図表の彩色やデザイン等を考える上で応用されている。

ラムゼー問題の証明

ラムゼー問題の証明はグラフを用いることで容易に理解されうる形で行える。

6人をそれぞれ点（A、B、C、D、E、F）で表すこととし、2人が知り合いであれば赤い線で、知り合いでなければ青い線で結ぶことにする。こうして作成されるグラフにおいて、赤い三角形または青い三角形が存在することを示せばよいことになる。

Aという点(人)に注目すると、この点からは5本の線が出ている。従って、赤い線か青い線のいずれかが少なくとも3本出ていることになる。ここでは、赤い線が3本でているとして、その相手をB、C、Dとする。すると、

BとCを結ぶ線が赤い線であれば、ABCが赤い三角形となる。
CとDを結ぶ線が赤い線であれば、ACDが赤い三角形となる。
BとDを結ぶ線が赤い線であれば、ABDが赤い三角形となる。

上記のいずれでもなければ、BCDが青い三角形となる。

となり、いずれのケースでも、赤い三角形または青い三角形が存在することになる。

何とも簡潔でわかりやすい証明ではないだろうか。
 
これを原始的に証明しようとすれば、6点を結ぶ線は全部で２15（＝32,768）通りあるので、これをチェックすればよいことになるが、これはかなりハードな仕事だろう。
グラフ
因みに、5人の場合には、上記の右図のように、赤い三角形も青い三角形も作らずにグラフを描くことができる。すなわち、どの3人の組み合わせをみても、知り合いや知り合いでない人だけの組み合わせは存在しないことになる。

ラムゼー問題の一般化、ラムゼーの定理、ラムゼー理論

実は、この問題はさらに一般化されて、「ラムゼーの定理」と呼ばれるものが存在する。

「完全グラフ」というのは、上記の図のように全ての頂点間が線で結ばれたグラフのことを言うが、頂点数がnの完全グラフを　Kｎと表すことにする。この時、先のラムゼー問題の結論は、以下のように言い換えることができる。

「K6の各辺を青と赤の2色でどのように着色しても、赤い辺からなるK３か、青い辺からなるK３が部分グラフとして必ず含まれる。」

これを一般化することで、以下の「ラムゼーの定理」が得られる1。

「ｃとｍを任意の自然数とするとき、次を満たす自然数ｎが存在する。
Kｎの各辺をｃ色でどのように着色しても、同じ色の辺からなるKｍが部分グラフとして必ず含まれる。」

ラムゼーの定理をさらに一般化して応用する理論は「ラムゼー理論」と言われ、離散型数学のグラフ理論として、現在も数多くの数学者を魅了し、幅広い研究が行われている。

寺垣内政一広島大学大学院教授のペーパー「ラムゼー理論の話題から」によれば、「そのテーマは、粗っぽくいえば、混沌の規模がある程度大きくなると、その内部にある種の秩序が必然的に現われることを意味する。」とのことである。さらに、「いわゆるラムゼー数とよばれる値の決定は、グラフ理論における最難関の課題の１つ」であり、「もっとも単純な問題設定を描写すれば、どんな自然数Nに対しても、ある自然数R(N)が存在し、n≧R(N)ならば、ｎ頂点完全グラフKｎのすべての辺を赤か青でどのように色付けしても、赤辺だけでできたN頂点完全グラフKNか、青辺だけでできたKNが見つかる。」とされている。

再び、このことをパーティの問題に翻訳し直すと、知り合いを赤、知り合いでなければ青とすれば、

「パーティを開催する際に、少なくともN人がお互いに全員知り合いか、N人のお互いが全く知り合いでないグループを含むようにするには、最低R(N)人を招待すればよい。」ということになる。

さて、先の寺垣内氏のペーパーによれば、「このR(N)がラムゼー数とよばれており、ラムゼーの定理によってその値の存在は保証されている。しかし、R(3)=6、R(4)＝18であることを確認するのは困難ではないが、R(5)の値はいまだ決定されていない。」ということである。

R(3)=6であることは、「ラムゼー問題の証明」の箇所で示した通りである。

なお、ラムゼー（Frank Ramsey）（1903～1930）は、英国の数学者、哲学者であるが、わずか26歳でこの世を去っている。
 
1 ここで述べている「ラムゼーの定理」も、単純化されたものであり、分かりやすい形で表現しているが、通常の「ラムゼーの定理」はさらに一般化されている。

まとめ－ラムゼー理論等のグラフ理論の応用等－

以上、身近なパーティを題材にしたラムゼー問題から、より一般的なラムゼー理論について、簡単に紹介してきたが、結局ラムゼー理論とは、「完全な無秩序というものは存在せず、混沌としたものの中にも、一定のスケールがあれば、特定の秩序が現われる。」と解釈されることになるものと思われる。

こうしたラムゼー理論や様々なグラフ理論の考え方は、ネットワーク・電気回路等の数学的モデルとして利用されている他、ネットワークデザイン、ビジュアルインタフェースなど幅広い分野で応用されている。

この研究員の眼を１つの契機に、ラムゼー理論さらにはグラフ理論に少しは興味を抱いていただければと感じた次第である。

(2017年09月04日「研究員の眼」)

このレポートの関連カテゴリ

Xでシェアする Facebookでシェアする
全文ダウンロード（PDF）

中村 亮一

レポートについてお問い合わせ
(取材・講演依頼)

週間アクセスランキング

保険 総合 領域別

    更新もっと見る

    更新もっと見る

    ピックアップ

    レポート紹介

    【パーティ問題又はラムゼー問題－混沌の中にも、一定のスケールがあれば、特定の秩序が現われるってこと知っていましたか－】【シンクタンク】ニッセイ基礎研究所は、保険・年金・社会保障、経済・金融・不動産、暮らし・高齢社会、経営・ビジネスなどの各専門領域の研究員を抱え、様々な情報提供を行っています。

    パーティ問題又はラムゼー問題－混沌の中にも、一定のスケールがあれば、特定の秩序が現われるってこと知っていましたか－のレポート　Topへ