MathLabs
定理証明済み

ラムゼーの定理

内容

任意の正の整数 r,sr, s に対し、最小の整数 R(r,s)R(r,s) が存在して、n≥R(r,s)n \ge R(r,s) なる完全グラフ KnK_n の辺の任意の2彩色は、第一の色の単色な KrK_r または第二の色の単色な KsK_s のいずれかを含む。

なぜ正しいのか?

完全な無秩序は規模が大きくなると不可能になる。パーティーの人数が十分多ければ、互いに知り合いである rr 人のグループか、互いに見知らぬ同士である ss 人のグループのどちらか一方は必ず存在する。クリークを避けようとして赤と青の辺をどう混ぜ合わせても、グラフが十分大きくなれば一様な塊が必ず現れる。

証明の概略

r+sr+s に関する帰納法で R(r,s)≤R(r−1,s)+R(r,s−1)R(r,s) \le R(r-1,s) + R(r,s-1) を示す。n=R(r−1,s)+R(r,s−1)n = R(r-1,s) + R(r,s-1) なる2彩色された KnK_n の頂点 vv を一つとると、鳩の巣原理により、vv は少なくとも R(r−1,s)R(r-1,s) 個の赤い隣接頂点を持つか、少なくとも R(r,s−1)R(r,s-1) 個の青い隣接頂点を持つ。前者の場合、赤い近傍は赤い Kr−1K_{r-1}（vv と合わせて赤い KrK_r をなす）または青い KsK_s を含む。後者も対称である。

この定理を使うトピック

ラムゼー理論

関連する定理

鳩の巣原理セメレディの定理

ステップごとの証明

この定理のステップごとの証明はまだありません。

参考文献

  1. Frank P. Ramsey (1930). On a Problem of Formal Logic · DOI:10.1112/plms/s2-30.1.264