■シューアの定理(その3)

【1】パーティー問題

 K5の正五角形を赤線で,星形五角形を青線で結ぶ.この図形には点をつなぐ線がすべて赤かすべて青の三角形は存在しない.

 しかし,K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.

 従って,どのような6人の集団でも,3人の友人関係が存在するか,互いに見知らぬ3人が存在することになる(パーティー問題).つまり,この問題はラムゼー理論と密接な関係にある.

===================================

 色を3色に増やす.K16は同色の三角形が存在しないように配色することができるが,K17では同色の三角形がどこかにできるのである.

  N(1)=2,N(2)=5,N(3)=16

  N(q)≦Σq!1/k!

であるが,エルデシュは

  N(q)=q!Σ1/k!

と予想している.

 これによると,N(4)=65であるが,K65に対する良い4配色は見いだされていない.つまり,N(4)=65であると証明されているわけではないことに注意.

 N(q)はラムゼー理論と密接な関係にあるが,高次ラムゼー数の大多数はまだ知られていないのである.

===================================

【2】ファン・デル・ヴェルデン数

 ファン・デル・ヴェルデン数は前述の問題に似ている.自然数kに対して,

  1,2,3,・・・,n(k)

を2色でどう塗り分けても,長さkの等差数列をなす同色のものができるものと定義される.

 9は等差数列をなす同色の3数ができる最小の整数nである.

 35は等差数列をなす同色の4数ができる最小の整数nである.

 175は等差数列をなす同色の5数ができる最小の整数nである.

 もっと一般に,任意のkに対し,等差数列をなす同色のk数ができる最小の整数n(k)が存在することをファン・デル・ヴェルデンが証明した.

===================================