■グラフ理論(その2)

【2】エルデシュ予想

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

  5>2+2

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

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

  17>5+5+5

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

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

  65>16+16+16+16

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

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

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

  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!

こうして,エルデシュは

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

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

N(q)はラムゼー理論と密接な関係にあるが,高次ラムゼー数の大多数はまだ知られていない.たとえば,49個の頂点がある完全グラフK49のすべての辺や対角線を赤線か青線で結ぶとき,この図形には5点をつなぐ線がすべて赤か,すべて青の五角形が存在することが知られている.49個の頂点がある完全グラフK42のすべての辺や対角線を赤線か青線で結ぶとき,この図形には5点をつなぐ線がすべて赤か,すべて青の五角形が存在しないことが知られている.その間隙は埋まらないのである.

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