■ラムゼー数(その28)

 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点も赤で結ばれていないとすると別色の三角形を形成するというわけである.

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

 以上を一般式の形で表したものが,

  N(q)≦Σq!/k!

である.

(証)

  N(1)≦1+1

  N(2)≦2N(1)+1

  N(3)≦3N(2)+1

  ・・・・・・・・・・・・ 

  N(q)≦qN(q−1)+1

したがって,

  N(q)≦1+q+q(q−1)+・・・+q!+q!≦Σq!/k!

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