Ramsey 数 | Codeboy's Blog

形式陈述

对正整数 $s,t$ ，Ramsey 数 $R(s,t)$ 是满足下述性质的最小整数 $N$ ：任意把完全图 $K_N$ 的边作红蓝染色（这里采用边染色，而非通常的顶点染色），都含红色 $K_s$ 或蓝色 $K_t$ 。等价地，对任意 $N$ 点简单图 $G$ ，必有

\omega(G)\ge s \quad\text{或}\quad \alpha(G)\ge t.

把红边视为 $G$ 的边、蓝边视为补图的边，就得到这两个表述的对应。有限Ramsey 定理保证具有该性质的 $N$ 非空，因此最小值确实是有限整数。颜色互换给出

R(s,t)=R(t,s).

边界值为 $R(1,t)=1$ 与 $R(2,t)=t$ 。常用递推式

R(s,t)\le R(s-1,t)+R(s,t-1), \qquad s,t\ge2,

来自考察一个顶点的红邻域与蓝邻域；若两者分别小于相应阈值，其大小之和就容不下其余全部顶点。

直觉

Ramsey 数衡量最坏染色能把规则结构推迟多久。上界证明要说明每种染色都逃不掉，通常递归地把一个顶点的邻边按颜色分组；下界则必须展示或证明存在一幅仍能逃脱的染色。两边的论证方向相反，算出一个上界并不等于知道 Ramsey 数。

图与补图的表述揭示了“红团或蓝团”其实是同一图中的“大团或大独立集”。宿主之所以取完全图，是因为每一对顶点必须有一种关系；若原问题存在“未知”或“无边且不算另一色”的第三种状态，就不再是这个二色 Ramsey 数。

例子与边界

经典计算是 $R(3,3)=6$ 。对任意六点红蓝染色，固定顶点 $v$ ；它发出的五条边至少三条同色。设 $va,vb,vc$ 都红。若 $ab,bc,ca$ 中有红边，就与 $v$ 组成红三角形；若一条红边也没有，则 $a,b,c$ 组成蓝三角形。因此 $R(3,3)\le6$ 。

为证五点不够，把五圈的边染红、五条对角线染蓝。红图是 $C_5$ ，蓝图也是一个五圈，二者都没有三角形，故 $R(3,3)>5$ 。上、下界在 $6$ 会合才完成精确计算。这个例子也可直接翻译为五点图满足 $\omega(G)=\alpha(G)=2$ 。

递推能给出有限但常常很松的数。例如

R(3,4)\le R(2,4)+R(3,3)=4+6=10,

而精确值是 $R(3,4)=9$ ；要把 $10$ 排除，需要利用比单点鸽巢更细的结构。对角数 $R(k,k)$ 的精确值只知道很少几个，随机染色却能迅速给出指数下界：若

2\binom nk2^{-\binom k2}<1,

则存在没有单色 $K_k$ 的二染色，因而 $R(k,k)>n$ 。这里第一因子 $2$ 选择颜色，后项是固定 $k$ 点成单色的概率。

有限 Ramsey 数不能与无限 Ramsey 定理混同；后者保证无限集合中存在无限同质子集，不提供上述最小有限阈值。多色数 $R(s_1,\ldots,s_q)$ 、超图 Ramsey 数和有序 Ramsey 数也改变了染色对象与目标结构，不能省略下标约定。

推论与应用

Ramsey 数与极值数都描述不可避免性，但优化轴不同。 $\operatorname{ex}(n,H)$ 固定 $n$ ，最大化在一种图结构中避开 $H$ 的边数； $R(s,t)$ 最小化 $n$ ，同时要求图与补图分别不能避开 $K_s$ 与 $K_t$ 。由此可用极值不等式推出 Ramsey 上界：若对某个 $n$ 有

\operatorname{ex}(n,K_s)+\operatorname{ex}(n,K_t)<\binom n2,

则任意图 $G$ 不可能同时满足 $e(G)\le\operatorname{ex}(n,K_s)$ 与 $e(\overline G)\le\operatorname{ex}(n,K_t)$ ，所以 $R(s,t)\le n$ 。

Ramsey 数还为算法最坏情形、通信关系与离散几何提供“规模足够大必见同质块”的定量门槛。概率方法给下界，容器、熵和半随机过程可进一步压缩候选染色；然而任何渐近界都要区分底数、指数与低阶因子，不能把“指数级”当作精确数量级的替代。

参考资料

Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey Theory, 2nd ed., Wiley, 1990, Chapters 1–2.
Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016, Chapter 1.
Stanisław P. Radziszowski, “Small Ramsey numbers,” Electronic Journal of Combinatorics, Dynamic Survey DS1, continuously updated, originally 1994.

形式陈述 ​

反向链接

形式陈述