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

ラムゼー数

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

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

ですから，

$n$を自然数とし，平面に$m(n)$個の点がある． 各2点を結ぶ線分を$n$色のうちのいずれかの色でぬる． このとき3辺が同じ色の三角形が存在するような$m(n)$の最小値を求めよ．

という問題が生じます．

$$m(n)\le a_n$$

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

南海　 実は

$$m(2)=6,\ m(3)=17$$

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

定義 1 (ラムゼー数)        定理2によって存在する$R$のうちの最小値を

$$R(q_1,\ q_2,\ \cdots,\ q_n\ ;\ r)$$

と表し，ラムゼー数という．

例 0.1        先の命題

色が$n$色ある．各2点を結ぶ線分を$n$色のうちのいずれかの色でぬる． このとき3辺が同じ色の三角形が存在する．

では，$r=2$， $q_1=q_2=\cdots=q_n=3$である． 従ってこのとき，

$$R(3,\ 3,\ \cdots,\ 3\ ;\ 2) \le [en!+1]$$

が成り立つ．

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

ある集合が指定された規則正しい部分構造を含む．

この命題が成立するか否かが問題になる．

第1

集合の位数に関する十分条件が存在する．

第2

その上限を確定する．

第3

その下限を確定する．

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

それでこれを分けた．