Ramsey 数

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

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

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

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

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

而精确值是 $R(3,4)=9$。上界可由奇偶性补全：若九点图既无三角形又无四点独立集，每个邻域独立，故各点度数至多三；每个非邻域既无三角形又无三点独立集，由 $R(3,3)=6$ 知其至多五点，故各点度数至少三。于是九个点全为三度，度数和二十七为奇数，与握手恒等式矛盾。下界取八圈并加上四条连接对顶点的边：它无三角形；八圈的四点独立集只能是两个交替点集，而新增的对顶边恰好破坏它们，所以也无四点独立集。对角数 $R(k,k)$ 的精确值只知道很少几个。对 $k\ge 2$，随机染色却能迅速给出指数下界：若

独立公平地选择每条边的颜色时，左侧就是单色 $K_k$ 的期望个数；由一阶矩方法理路一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。，存在没有单色 $K_k$ 的二染色，因而 $R(k,k)>n$。这里第一因子 $2$ 选择颜色，后项是固定 $k$ 点成单色的概率。

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

Ramsey 数与极值数理路极值数Extremal number · Turán number · ex(n,H)固定顶点数并禁止给定子图时，无向简单图所能拥有的最大边数。都描述不可避免性，但优化轴不同。$\mathrm{ex}(n,H)$ 固定 $n$，最大化在一种图结构中避开 $H$ 的边数；$R(s,t)$ 最小化 $n$，同时要求图与补图分别不能避开 $K_s$ 与 $K_t$。对 $s,t\ge 2$，还可用极值不等式推出 Ramsey 上界：若对某个 $n$ 有

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

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