next up previous 次: 存在定理 上: ラムゼー型定理 前: ある問題と一般化

ラムゼー数

南海  しかし,この$R$は存在するための十分条件でしかない.

太郎  私が色の数を$a_n$とおいたあの$a_n$も,点の個数が$a_n$であればつねに同色の三角形が存在する, ということでした.それより小さい数でも,つねに存在することが言えるのか,あるいは言えない反例があるのかは, 何もいっていません.

ですから,

$n$を自然数とし,平面に$m(n)$個の点がある. 各2点を結ぶ線分を$n$色のうちのいずれかの色でぬる. このとき3辺が同じ色の三角形が存在するような$m(n)$の最小値を求めよ.
という問題が生じます.
\begin{displaymath}
m(n)\le a_n
\end{displaymath}

ですが,等号が成立するのか否かはわかりません.

南海  実は

\begin{displaymath}
m(2)=6,\ m(3)=17
\end{displaymath}

であることが知られている. しかし$m(4)$以上についてはわかっていない. $m(2)=6$の方は,5なら3辺が同色でない三角形が存在することはすぐわかるが, $m(3)=17$は難しい.これについては 『めざせ,数学オリンピック』を見てほしい. こうして次の数が定義される.

定義 1 (ラムゼー数)        定理2によって存在する$R$のうちの最小値を
\begin{displaymath}
R(q_1,\ q_2,\ \cdots,\ q_n\ ;\ r)
\end{displaymath}

と表し,ラムゼー数という.

例 0.1
       先の命題
色が$n$色ある.各2点を結ぶ線分を$n$色のうちのいずれかの色でぬる. このとき3辺が同じ色の三角形が存在する.
では,$r=2$ $q_1=q_2=\cdots=q_n=3$である. 従ってこのとき,
\begin{displaymath}
R(3,\ 3,\ \cdots,\ 3\ ;\ 2) \le [en!+1]
\end{displaymath}

が成り立つ.

このようにラムゼー問題といわれる一連の問題群がある. いずれも,

ある集合が指定された規則正しい部分構造を含む.
この命題が成立するか否かが問題になる.
第1
集合の位数に関する十分条件が存在する.
第2
その上限を確定する.
第3
その下限を確定する.

もちろん上限が確定すれば,それは十分条件の存在も示しているのであるが,具体的に上限が表せなくても,十分条件の存在は示されることがある.

それでこれを分けた.


Aozora
2015-03-04