実は、この問題はさらに一般化されて、「ラムゼーの定理」と呼ばれるものが存在する。
「完全グラフ」というのは、上記の図のように全ての頂点間が線で結ばれたグラフのことを言うが、頂点数がnの完全グラフを K
nと表すことにする。この時、先のラムゼー問題の結論は、以下のように言い換えることができる。
「K
6の各辺を青と赤の2色でどのように着色しても、赤い辺からなるK
3か、青い辺からなるK
3が部分グラフとして必ず含まれる。」
これを一般化することで、以下の「ラムゼーの定理」が得られる
1。
「cとmを任意の自然数とするとき、次を満たす自然数nが存在する。
K
nの各辺をc色でどのように着色しても、同じ色の辺からなるK
mが部分グラフとして必ず含まれる。」
ラムゼーの定理をさらに一般化して応用する理論は「ラムゼー理論」と言われ、離散型数学のグラフ理論として、現在も数多くの数学者を魅了し、幅広い研究が行われている。
寺垣内政一広島大学大学院教授のペーパー「ラムゼー理論の話題から」によれば、「そのテーマは、粗っぽくいえば、混沌の規模がある程度大きくなると、その内部にある種の秩序が必然的に現われることを意味する。」とのことである。さらに、「いわゆるラムゼー数とよばれる値の決定は、グラフ理論における最難関の課題の1つ」であり、「もっとも単純な問題設定を描写すれば、どんな自然数Nに対しても、ある自然数R(N)が存在し、n≧R(N)ならば、n頂点完全グラフK
nのすべての辺を赤か青でどのように色付けしても、赤辺だけでできたN頂点完全グラフK
Nか、青辺だけでできたK
Nが見つかる。」とされている。
再び、このことをパーティの問題に翻訳し直すと、知り合いを赤、知り合いでなければ青とすれば、
「パーティを開催する際に、少なくともN人がお互いに全員知り合いか、N人のお互いが全く知り合いでないグループを含むようにするには、最低R(N)人を招待すればよい。」ということになる。
さて、先の寺垣内氏のペーパーによれば、「このR(N)がラムゼー数とよばれており、ラムゼーの定理によってその値の存在は保証されている。しかし、R(3)=6、R(4)=18であることを確認するのは困難ではないが、R(5)の値はいまだ決定されていない。」ということである。
R(3)=6であることは、「ラムゼー問題の証明」の箇所で示した通りである。
なお、ラムゼー(Frank Ramsey)(1903~1930)は、英国の数学者、哲学者であるが、わずか26歳でこの世を去っている。
1 ここで述べている「ラムゼーの定理」も、単純化されたものであり、分かりやすい形で表現しているが、通常の「ラムゼーの定理」はさらに一般化されている。