MathLabs
定理已证明

拉姆齐定理

命题陈述

对任意正整数 r,sr, s，存在最小整数 R(r,s)R(r,s)，使得当 n≥R(r,s)n \ge R(r,s) 时，完全图 KnK_n 的边的任意二染色都必然包含第一颜色的同色 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) 的二染色 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