ｎ頂点の完全グラフの各辺を赤か青で着色する。ｋ頂点でこれらを結ぶすべてのk(k-1)/2辺が同色で結ばれるようなものが必ず存在する最小のｎ=R(k)は？

すべての辺とは k(k-1)/2なのであるが、 k=3のときが同色の三角形である。

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

R(k)≦2^2kであるが、上界評価は(2k,k)に改良することができる

下界評価はエルデシュによるもので、R(k)≧2^(k/2)がある.

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

各辺を確率1/2で赤に、確率1/2で青に着色する。

頂点集合{x1,x2,・・・xk}のすべてのxiがすべてのxjに赤い辺で結ばれている確率は(1/2)^(k,2)であり、青い辺で結ばれている確率も(1/2)^(k,2)である。すべての辺が同色であるようなｋ点集合が生じる確率は、高々2(1/2)^(k,2)・(n,k)である。

もしこれが１より小さければそのようなｋ頂点が存在しない着色があることになる。ｎ=2^(k/2)のとき、それは１より小さいことを示すことができる

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

Ｋ5の正五角形を赤線で，星形五角形を青線で結ぶ．この図形には点をつなぐ線がすべて赤かすべて青の三角形は存在しない．

しかし，Ｋ6のすべての２頂点間を２色の線で結ぶと，点をつなぐ線がすべて赤かすべて青の三角形ができる．

2^(k/2)≦R(k)≦(2k,k)

ｋ＝3のとき、2√2≦6≦20

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