ｎ頂点の完全グラフの各辺を赤か青で着色する。ｋ頂点でこれらを結ぶすべての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)のとき、それは１より小さいことを示すことができる

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