■漸化式と母関数(その12)

 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)はラムゼー理論と密接な関係にあるが,高次ラムゼー数の大多数はまだ知られていないのである.

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

[おまけ]アダマール予想「n=0(mod4)に対して,n次のアダマール行列が必ず存在する」は完全解決には至っておらず,現在,存在のわかっていない最小のnはn=668である.

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