【２】エルデシュ予想

Ｋ6の頂点からは５本の線が発せられている．Ｎ（１）＝２であり，

　　５＞２＋２

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

　Ｋ17の頂点からは１６本の線が発せられている．Ｎ（２）＝５であり，

　　１７＞５＋５＋５

であるから最低でも３色のうちどれかひとつの色は７回出現している．それが赤だと仮定する．この線分の先端にある７点のうち２点が赤で結ばれていたとすれば赤い三角形を形成する．どの２点も赤で結ばれていないとすると別色の三角形を形成する．Ｎ（３）＝１６

　Ｋ66の頂点からは６５本の線が発せられている．Ｎ（３）＝１６であり，

　　６５＞１６＋１６＋１６＋１６

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

Ｎ（１）＝２，Ｎ（２）＝５，Ｎ（３）＝１６，・・・

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

　　Ｎ（ｑ）≦Σｑ！／ｋ！

である．

　　Ｎ（１）≦１＋１

　　Ｎ（２）≦２Ｎ（１）＋１

　　Ｎ（３）≦３Ｎ（２）＋１

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

　　Ｎ（ｑ）≦ｑＮ（ｑ−１）＋１

したがって，

　　Ｎ（ｑ）≦１＋ｑ＋ｑ（ｑ−１）＋・・・＋ｑ！＋ｑ！≦Σｑ！／ｋ！

こうして，エルデシュは

　　Ｎ（ｑ）＝ｑ！Σ１／ｋ！

と予想している．これによると，Ｎ（４）＝６５であるが，Ｋ65に対する良い４配色は見いだされていない．つまり，Ｎ（４）＝６５であると証明されているわけではないことに注意．

Ｎ（ｑ）はラムゼー理論と密接な関係にあるが，高次ラムゼー数の大多数はまだ知られていない．たとえば，４９個の頂点がある完全グラフＫ49のすべての辺や対角線を赤線か青線で結ぶとき，この図形には５点をつなぐ線がすべて赤か，すべて青の五角形が存在することが知られている．４２個の頂点がある完全グラフＫ42のすべての辺や対角線を赤線か青線で結ぶとき，この図形には５点をつなぐ線がすべて赤か，すべて青の五角形が存在しないことが知られている．その間隙は埋まらないのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［補］

　Ｋ6の２色着色では単色三角形が少なくとも２個含まれる．

　Ｋ7の２色着色では単色三角形が少なくとも４個含まれる．

　Ｋnの２色着色では単色三角形が少なくとも△個含まれる．

頂点ｉに結合している赤辺の数をｒiとすると，青辺の数はｎ−１−ｒi

単色三角形の数は

△＝ｎC３−１／２・Σｒi（ｎ−１−ｒi）

△≧ｎC３−［ｎ／２［｛（ｎ−１）／２｝^2］］

ｎ＝６のとき

△≧２０−［３［２５／４］］＝２

ｎ＝７のとき

△≧３５−［７／２［１８］］＝４

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝