■完全グラフと同色の三角形(その23)

 エルデシュは

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

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

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

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

 K6の頂点からは5本の線が発せられている.N(1)=2であり,

  5>2+2

であるから最低でも2色のうちどれかひとつの色は3回出現している.それが赤だと仮定する.この線分の先端にある3点のうち2点が赤で結ばれていたとすれば赤い三角形を形成する.どの2点も赤で結ばれていないとすると青い三角形を形成する.

 K17の頂点からは16本の線が発せられている.N(2)=6であり,

  17>6+6+6

であるから最低でも3色のうちどれかひとつの色は7回出現している.それが赤だと仮定する.この線分の先端にある7点のうち2点が赤で結ばれていたとすれば赤い三角形を形成する.どの2点も赤で結ばれていないとすると別色の三角形を形成する.

 K66の頂点からは65本の線が発せられている.N(3)=16であり,

  65>16+16+16+16

であるから最低でも4色のうちどれかひとつの色は17回出現している.それが赤だと仮定する.この線分の先端にある17点のうち2点が赤で結ばれていたとすれば赤い三角形を形成する.どの2点も赤で結ばれていないとすると別色の三角形を形成するというわけである.

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