算法与数据结构 / 图论 · 从基础语言到现代结构理论 / Ramsey 理论：完全的混沌并不存在 待审核 9 / 13
ramsey · R(s,t) · 鸽巢

Ramsey 理论：完全的混沌并不存在

把完全图 K_n 的每条边随意染成红或蓝，试图造出一张「毫无规律」的图——Ramsey 理论断言这种努力注定失败：只要 nn 足够大，任何红蓝染色里都必然浮现出一块整齐的结构（一个同色的完全子图 K_s）。本页把这件事落到最小的非平凡情形 R(3,3)=6 上：K6 的任意红蓝染色必含同色三角形，而 K5 存在一种染色躲开它。先动手染色看规律如何被逼出来，再看上界为何成立，最后看 Ramsey 数增长有多快。

Ramsey 数 R(s,t) 定义为最小的 nn，使得对 K_n 的边做红 / 蓝二染时，总能找到一个红色 K_s 或一个蓝色 K_t。Ramsey 定理保证这个最小 nn 有限——它一定存在。最经典的结论 R(3,3)=6 用「派对」的语言说就是：任意 6 个人里，必有 3 个人两两相识，或者 3 个人两两互不相识。

图 1-1 · 交互式边染色。可在 K5 与 K6 之间切换并任意染色或随机生成，同色三角形一旦出现即被高亮。

K5 躲得开：把 5 个顶点排成圈。外圈 5 条边（相邻顶点之间，构成一个 5-圈 C5）染红，内部五角星的 5 条对角边（相隔一个顶点，又是一个 C5）染蓝。红边自成一个 C5、蓝边也自成一个 C5——而 C5 是奇圈但无三角形，所以红、蓝两边里都找不出同色三角形。这正是 R(3,3)>5 的见证：存在 K5 的染色不含同色 K3。点上方「K5 无同色三角形染色」按钮即可加载并验证它。

K6 躲不开（鸽巢论证）： 任取一个顶点 v，它向其余 5 个顶点各连一条边。这 5 条边染红或蓝两色——由鸽巢原理，必有至少 3 条同色（5 条放进 2 个颜色，某色 ≥ ⌈5/2⌉ = 3）。不妨设 v 到 a、bb、c 这三条边都是红色。再看 a、bb、c 三者之间的三条边：其一，若其中任意一条是红色（比如 ab 红），那么 v、a、bb 就构成一个红色三角形；其二，若这三条边全是蓝色，那么 a、bb、c 自己构成一个蓝色三角形。无论哪种情况，同色三角形都跑不掉——这就证明了 R(3,3)≤6R(3,3)\le 6。在上面的交互区切到 K6，无论怎么染（含随机）都至少有一个同色三角形被高亮。

图 2-1 · 鸽巢论证的图示：从任一顶点引出的五条边里必有三条同色，随后三点之间无论怎么染都会落进两种情形之一。

Ramsey 数增长极快，几乎算不动。 已知的对角值寥寥无几：R(3,3)=6、R(4,4)=18。再往上 R(5,5)R(5,5) 至今未知，目前只知道它落在 43 与 46 之间（下界 43 由 Exoo 于 1989 年给出，上界 46 由 Angeltveit 与 McKay 于 2024 年给出；核对于 2026-08）。困难在于搜索空间爆炸：K_n 有 C(n,2) 条边，二染方案数是 2^{C(n,2)}——以 n=43n = 43 计已是 29032^{903} 这个量级的天文数字，穷举无望。Erdős 有一句广为流传的设想：若有强大外星文明要求人类算出 R(5,5)，人类应集全球之力去算；但若要求算 R(6,6)，则应当设法先消灭这些外星人——以此说明每往上一格，难度都呈指数级跳升。

Ramsey 定理（二色对角形式） 对任意正整数 s, t，存在最小的 R(s,t)，使得 K_n (n≥R(s,t)n \ge R(s,t)) 的任何红蓝边染色都含有红色 K_s 或蓝色 K_t。经典递推上界 R(s,t)≤R(s−1,t)+R(s,t−1)R(s,t) \le R(s-1,t) + R(s,t-1) 给出 R(s,t)≤C(s+t−2,s−1)R(s,t) \le C(s+t-2, s-1)，由此 R(3,3)≤C(4,2)=6R(3,3) \le C(4,2) = 6；配合上面 K5 的染色见证 R(3,3) > 5，两边夹出 R(3,3)=6。

几个已知与未知的 R(s,t)：

图 3-1 · 几个已知与未知的 Ramsey 数一览。

对角线上能精确确定的只到 R(4,4)=18；R(5,5)R(5,5) 仅有区间，更大的 R(6,6)R(6,6) 区间更宽：已知 102≤R(6,6)≤160102 \le R(6,6) \le 160，其中下界自 1965 年起未再改进（核对于 2026-08）。