■いろいろの漸化式と母関数(その32)

 K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.=K6の辺を2色に塗り分ければ必ず単色のK3が含まれる.

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

 色を4色に増やす.K66では同色の三角形K3がどこかにできる.(証明されているわけではない)

 色をC色に増やす.Kmでは同色の三角形K3がどこかにできる.

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

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

[1]拡張

 K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.=K6の辺を2色に塗り分ければ必ず単色のK3が含まれる.

 2色塗りのK6は単色のK3を含む.

 2色塗りのK18は単色のK4を含む.

 2色塗りのKnは単色のKmを含むものとする.

しかし,m=5の場合でもnの値は知られていない.すなわち,

 2色塗りのKnは単色のK5を含む.n=?

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

[2]もうひとつの拡張

 K6の2色着色では単色三角形が少なくとも2個含まれる.

 K7の2色着色では単色三角形が少なくとも4個含まれる.

 Knの2色着色では単色三角形が少なくとも△個含まれる.

頂点iに結合している赤辺の数をriとすると,青辺の数はn−1−ri

単色三角形の数は

△=(n,3)−1/2・Σri(n−1−ri)

△≧(n,3)−[n/2[{(n−1)/2}^2]]

n=6のとき

△≧20−[3[25/4]]=2

n=7のとき

△≧35−[7/2[18]]=4

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