例:R2 =6

ウィキペディア小見出し辞書

例:R2 (3, 3)=6

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/08 18:21 UTC 版)

「ラムゼーの定理」の記事における「例:R2 (3, 3)=6」の解説

上にもあるが、R2 (3, 3)=6は「6人いれば、互いに知り合いである3人組か、互いに知り合いでない3人組が存在する」として有名である。これを示す。なお、上の図より、R2 (3, 3)>5であり、5人いても互いに知り合いである3人組も互いに知り合いでない3人組も存在しない場合がある。 6つの点があり、その中のどの2つの点も赤い線か青い線で結ばれているとする。赤一色の三角形か青一色の三角形が存在することを示せばよい。6つの点のうち、どれでも良いので1つの点に着目し、その点をAとする。Aからは5本の線が出ているので、そのうちの3本以上は同じ色の線である筈である。Aから赤い線が3本以上出ている場合を考える。Aと赤い線でつながっている点は3つ以上あるが、そのうちの3点をB,C,Dとする。BとCが赤い線で結ばれている場合、三角形ABCはどの辺も赤い赤一色の三角形である。CとD、DとBが赤い線で結ばれている場合も同様に赤一色の三角形が存在する。よって、B,C,Dの中のいずれか2点が赤い線で結ばれている場合は赤一色の三角形が存在する。そうでない場合、即ち、B,C,Dのうちどの2点も青い線で結ばれている場合、三角形BCDはどの辺も青い青一色の三角形である。よってこの場合も一色の三角形が存在する。Aから青い線が3本以上出ている場合も同様である。 これとは別の方法で、一色の三角形が2個以上存在することを示すこともできる。相異なる3つの点の組(x,y,z)で、辺xyの色と辺yzの色が異なるものの個数をNとする。ただし、(x,y,z)において、xとzの順番は区別しないものとする。y=Aのとき、そのような組(x,y,z)の個数は、0×5=0(yから出ている線が全て同じ色である場合)、1×4=4(yから赤い線が1本だけ、または青い線が1本だけ出ている場合)、2×3=6(yからある色の線が2本出ており、他方の色の線は3本出ている場合)のいずれかである。よって、y=Aのとき、そのような組の個数は最大でも6である。yが他の点である場合も同様なので、Nは6×6=36以下である。一方、一つの一色でない三角形はそのような組(x,y,z)を2つ含む。よって、一色でない三角形の個数は36/2=18以下である。三角形は6C3=20個あるので、一色の三角形は20-18=2個以上ある。