组合数学——Ramsay数

Ramsey 理论是另一类组合极值问题。著名组合学家 Rota 说，如果要在组合数学中举出且仅举出一个精美的定理，那么大多数组合学家会提名 Ramsey 定理。 简单的抽屉原理背后是深刻的 Ramsey 定理，而 Ramsey 数的计算是对人类智力的极大挑战。

通过 Ramsey 定理可以体会到：完全的无序是不可能的，任一足够大的结构中必定包含一个给定大小的规则子结构这样一些哲理。

• Wolf 奖得主 Erdős（1983）和 Lovász（1999）
• Fields 奖得主 Gowers（1998）和 Tao（2006）
• Abel 奖得主 Szemerédi（2012） 都对 Ramsey 理论有重大贡献。

抽屉原理

例

• 任取三粒围棋，必有两粒同色。
• 任意 $13$ 人中，必有两个人在同一个月份出生。
• 把 $11$ 只鸽子放进 $10$ 只笼子，必有两只放进同一只笼子。
• 把多于 $n$ 个东西任意放进 $n$ 个抽屉，那么一定有一个抽屉放了不止一个东西。

鸽笼原理 / 抽屉原理 把多于 $k\times n$ 个东西任意放进 $n$ 个抽屉，那么一定有一个抽屉放进了至少 $k+1$ 个东西。 因 Dirichlet 曾明确用过这个原理，故又称为 Dirichlet 原理。

Dirichlet 逼近定理，1842

任给 $x\in \mathbb{R}$ 和 $n\in {\mathbb{Z}}^{+}$，一定有 $p\in {\mathbb{Z}}^{+}$ 和 $q\in \mathbb{Z}$ 使得

$$|px-q|<\frac{1}{n}.$$

• 每个实数都可用有理数逼近（$\frac{q}{p}$ 和 $x$ 足够接近）

例 1. 从 $[200]$ 中任取 $101$ 个数，其中必有一个整除另一个。

证明. $\forall n\in {\mathbb{Z}}^{+}$，有唯一表示

$$n=2^{r}q,$$

其中 $r\in \mathbb{N}$，$q$ 是 $n$ 的奇因数。 由于 $n\le 200$ 的奇因数只能是 $1,3,\dots ,199$ 这 $100$ 个数，故任取 $101$ 个中一定有两个奇因数相同，即

$$a=2^r\cdot q,b=2^s\cdot q.$$

若 $r<s$，则 $a\mid b$。 注. 从 $[2n]$ 中任取 $n+1$ 个数，其中必有一个整除另一个。

例 2.（中国剩余定理） 设 $m,n$ 是互素的正整数。则对任意 $0\le a\le m-1$ 和 $0\le b\le n-1$，存在整数 $x$ 和相应的整数 $p,q$ 使得

$$x=pm+a=qn+b.$$

证明. 只需证明

$$a,m+a,2m+a,\cdots ,(n-1)m+a$$

这 $n$ 个数被 $n$ 除的余数各不相同，即它们构成模 $n$ 的一个完全剩余系，从而其中必有一个是模 $n$ 余 $b$ 的。

若不然，则存在 $i,j(0\le j<i\le n-1)$ 使得

$$n\mid (im+a)-(jm+a)=(i-j)m.$$

由于 $m$ 与 $n$ 互素，故 $n\mid (i-j)$。这与 $0<i-j<n$ 矛盾。 注. 设 $m_1,\cdots ,m_k$ 是两两互素的正整数，则任给 $k$ 个整数 $a_1,\cdots ,a_k$，必存在 $x\in \mathbb{N}$ 使得

$$x\equiv a_i(\mathrm{mod}{m}_i),i=1,\cdots ,k.$$

例 3.（Erdős, Szekeres, 1935） 任意一个 $n^2+1$ 项实数列

$$a_1,a_2,\cdots ,a_{n^2+1}$$

中必有 $n+1$ 项的单调子数列。 证明. 令以 $a_i$ 为首项的所有递增子数列中项数的最大值为 $p_i$。

1. 若 $\exists p_i\ge n+1$，则有长为 $n+1$ 的递增子数列。
2. 若 $p_i\le n,\forall i$，则由抽屉原理，这 $n^2+1$ 个数必有 $n+1$ 个彼此相等。设

$$p_{i_1}=p_{i_2}=\cdots =p_{i_{n+1}},$$

其中

$$i_1<i_2<\cdots <i_{n+1}.$$

可证：若 $p_j=p_k$ 且 $j<k$，则 $a_j>a_k$。
（否则 $a_j<a_k$，则以 $a_j$ 开头的递增子列一定比以 $a_k$ 开头的递增子数列长，矛盾。）

因此

$$a_{i_1}>a_{i_2}>\cdots >a_{i_{n+1}},$$

这就是一个长为 $n+1$ 的递减子列。 例 4.（Dilworth 引理） 在任一含 $mn+1$ 个元素的偏序集中，或者有一条长度至少为 $m+1$ 的链，或者有一条长度至少为 $n+1$ 的反链。

Ramsay定理（简式）和Ramsay数

《美国数学月刊》于 1958 年刊出问题：

任意 6 人中，或有 3 人互相认识，或有 3 人互不相识。

证明：在完全图 $K_6$ 中，将每条边染成红色或蓝色，则必存在一个同色三角形。 其中 红边表示两人互相认识；蓝边表示两人互不相识。 任取其中一个人，记为 $A$ $A$ 与其余 5 个人之间共有 5 条关系边。 每条边只有两种可能：红边：表示认识； 蓝边：表示不认识。 由抽屉原理，在这 5 条边中，至少有 3 条颜色相同。 不妨设这 3 条同色边为红边。 也就是说，存在三个人 $B,C,D$，使得$AB,AC,AD$都是红边。 现在考虑 $B,C,D$ 三人之间的关系。 共有三条边：$BC,BD,CD$ 分两种情况讨论。 情况一：$BC,BD,CD$ 中至少有一条红边 不妨设 $BC$ 是红边。 由于$AB,AC$也是红边，所以$AB,AC,BC$构成一个红色三角形。这表示 $A,B,C$ 三人两两相识。 情况二：$BC,BD,CD$ 中没有红边 如果 $BC,BD,CD$ 中没有红边，那么它们全都是蓝边。 于是$BC,BD,CD$构成一个蓝色三角形。 这表示 $B,C,D$ 三人两两互不相识。 综上，无论哪种情况，都必然存在：3 人两两相识；或 3 人两两互不相识。 因此，任意 6 人中，必有 3 人互相认识，或有 3 人互不相识。 即$R(3,3)=6$

完全图的边着色 $n$ 阶完全图：有 $n$ 个顶点，且任意两个顶点都连边的图，记为 $K_n$。 例：

• $K_2$
  图示：两个顶点之间连一条边。
• $K_3$
  图示：三个顶点两两相连，构成一个三角形。
• $K_4$
  图示：四个顶点两两相连，可画成一个正方形并加上两条对角线。 相识问题： 将 $K_6$ 每条边任意着红色或蓝色后，在 $K_6$ 中或者含有（各边都是）红色的 $K_3$，或者含有蓝色的 $K_3$。换言之，任意 $6$ 个点的图中，或者有一个 $3$ 阶的团（clique），或者有一个 $3$ 阶的独立集（independent set）。 注. 结论对 $K_n(n>6)$ 仍成立，但对 $K_5$ 不成立。例如，$K_5$ 的如下着色中不存在红 $K_3$ 或蓝 $K_3$。

图示：下方给出一个 $K_5$ 的边着色例子。

• 五个顶点排成五边形；
• 蓝边构成外侧的一个 $5$-环；
• 红边构成内部的五角星；
• 因而不存在红色的 $K_3$，也不存在蓝色的 $K_3$。 Ramsey 数 相识问题—一般情形 给定整数 $p,q\ge 2$，是否存在 $n\in {\mathbb{Z}}^{+}$，使得将 $K_n$ 的每条边任意着红色或蓝色后，在 $K_n$ 中或者含有红色的 $K_p$，或者含有蓝色的 $K_q$？换言之，任意 $R(p,q)$ 个点的图中，或者有一个 $p$ 阶的团，或者有一个 $q$ 阶的独立集。

Ramsey (1928) 证明了 $n$ 的存在性。
将最小的 $n$ 记为 $R(p,q)$，称为 Ramsey 数。

• $R(3,3)=6$。
• $R(p,q)=R(q,p)$。
• $R(2,q)=q$。 （$K_q$ 中或者有一条红边，或都是蓝边）

Ramsey 定理

Ramsey 定理（简式）

任给整数 $p,q\ge 2$，数 $R(p,q)$ 存在；并且当 $p,q\ge 3$ 时，

$$R(p,q)\le R(p-1,q)+R(p,q-1).$$

证明：先证明递推不等式。 设

$$n=R(p-1,q)+R(p,q-1).$$

任取完全图 $K_n$ 的一次红蓝染边。取任意顶点 $v$，记

• $A$ 为与 $v$ 由红边相连的顶点集合；
• $B$ 为与 $v$ 由蓝边相连的顶点集合。 则

$$|A|+|B|=n-1=R(p-1,q)+R(p,q-1)-1.$$

因而不可能同时有

$$|A|<R(p-1,q),|B|<R(p,q-1),$$

否则

$$|A|+|B|\le (R(p-1,q)-1)+(R(p,q-1)-1)=R(p-1,q)+R(p,q-1)-2,$$

与

$$|A|+|B|=R(p-1,q)+R(p,q-1)-1$$

矛盾。 所以至少有一个成立：

$$|A|\ge R(p-1,q)\text{或}|B|\ge R(p,q-1).$$

若 $|A|\ge R(p-1,q)$，则由 $R(p-1,q)$ 的定义，$A$ 所诱导的子图中必含

• 一个红色 $K_{p-1}$，或
• 一个蓝色 $K_q$。 若出现蓝色 $K_q$，则结论已成立。
  若出现红色 $K_{p-1}$，由于 $v$ 与 $A$ 中每个顶点都以红边相连，于是这个红色 $K_{p-1}$ 与 $v$ 一起构成一个红色 $K_p$。 同理，若 $|B|\ge R(p,q-1)$，则由 $R(p,q-1)$ 的定义，$B$ 所诱导的子图中必含
• 一个红色 $K_p$，或
• 一个蓝色 $K_{q-1}$。 若出现红色 $K_p$，则结论已成立。
  若出现蓝色 $K_{q-1}$，由于 $v$ 与 $B$ 中每个顶点都以蓝边相连，于是这个蓝色 $K_{q-1}$ 与 $v$ 一起构成一个蓝色 $K_q$。

因此，任意 $K_n$ 的红蓝染边中都必存在红色 $K_p$ 或蓝色 $K_q$，从而

$$R(p,q)\le n=R(p-1,q)+R(p,q-1).$$

下面证明 $R(p,q)$ 的存在性。对 $p+q$ 作归纳。

当 $p=2$ 时，

$$R(2,q)=q,$$

同理

$$R(p,2)=p.$$

这给出归纳基础。

设对于所有满足

$$p^{\prime }+q^{\prime }<p+q$$

的整数对 $(p^{\prime },q^{\prime })$，$R(p^{\prime },q^{\prime })$ 都已存在。若 $p,q\ge 3$，则

$$(p-1)+q<p+q,p+(q-1)<p+q,$$

所以 $R(p-1,q)$ 和 $R(p,q-1)$ 都存在。由上面已经证明的递推不等式，

$$R(p,q)\le R(p-1,q)+R(p,q-1),$$

右端是一个有限整数，因此 $R(p,q)$ 也存在。 由数学归纳法，任意整数 $p,q\ge 2$，$R(p,q)$ 都存在。定理得证。

Note

若 $R(p-1,q)$ 和 $R(p,q-1)$ 均为偶数，则有

$$R(p,q)\le R(p-1,q)+R(p,q-1)-1.$$

推论

$$R(p,q)\le \left(\genfrac{}{}{0ex}{}{p+q-2}{p-1}\right).$$

对于任意整数 $p,q\ge 2$，有

$$R(p,q)\le \left(\genfrac{}{}{0ex}{}{p+q-2}{p-1}\right).$$

证明： 对 $p+q$ 作归纳。 当 $p=2$ 时，

$$R(2,q)=q=\left(\genfrac{}{}{0ex}{}{q}{1}\right)=\left(\genfrac{}{}{0ex}{}{2+q-2}{2-1}\right).$$

当 $q=2$ 时，

$$R(p,2)=p=\left(\genfrac{}{}{0ex}{}{p}{p-1}\right)=\left(\genfrac{}{}{0ex}{}{p+2-2}{p-1}\right).$$

因此结论对边界情形成立。 现在设 $p,q\ge 3$，并假设对于所有满足

$$p^{\prime }+q^{\prime }<p+q$$

的整数对 $(p^{\prime },q^{\prime })$，结论都成立。由 Ramsey 数的递推不等式，

$$R(p,q)\le R(p-1,q)+R(p,q-1).$$

又因为

$$(p-1)+q=p+q-1<p+q,p+(q-1)=p+q-1<p+q,$$

可对 $R(p-1,q)$ 和 $R(p,q-1)$ 使用归纳假设，得到

$$R(p-1,q)\le \left(\genfrac{}{}{0ex}{}{p+q-3}{p-2}\right),$$

以及

$$R(p,q-1)\le \left(\genfrac{}{}{0ex}{}{p+q-3}{p-1}\right).$$

于是

$$R(p,q)\le \left(\genfrac{}{}{0ex}{}{p+q-3}{p-2}\right)+\left(\genfrac{}{}{0ex}{}{p+q-3}{p-1}\right).$$

由 Pascal 恒等式

$$\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k}\right),$$

可得

$$\left(\genfrac{}{}{0ex}{}{p+q-3}{p-2}\right)+\left(\genfrac{}{}{0ex}{}{p+q-3}{p-1}\right)=\left(\genfrac{}{}{0ex}{}{p+q-2}{p-1}\right).$$

因此

$$R(p,q)\le \left(\genfrac{}{}{0ex}{}{p+q-2}{p-1}\right).$$

推论得证。

人们普遍认为，若没有新的理论方法，仅仅依赖计算能力极强的计算机，也很难进一步确定更多 Ramsey 数的精确值；因此，Ramsey 数问题被视为对人类智慧的一项重大挑战。 Erdős 曾多次用一个著名的比喻来说明这一问题的困难程度：如果外星人入侵地球，并威胁说：“告诉我 $R(5,5)$ 的值，否则就毁灭人类。”那么我们也许应当集中全部计算资源和科学家来求解这个问题；但如果它们要求的是 $R(6,6)$，那么我们最好的选择恐怕就是奋起反抗。 目前已知：

$$43\le R(5,5)\le 49,102\le R(6,6)\le 165.$$

Ramsey 数的下界

定理（Erdős, 1947)：

$$R(p,p)\ge 2^{p/2}.$$

2026 年5月最新研究进展： 研究对象：

$$R(\ell ,C\ell )$$

新的下界。 相关论文： An exponential improvement for Ramsey lower bounds 作者：

• Jie Ma
• Wujie Shen
• Shengjie Xie 期刊：Inventiones mathematicae 论文摘要中的主要结论： 对于任意常数 $C>1$ 和充分大的 $\ell$，证明了 Ramsey 数

$$r(\ell ,C\ell )$$

存在新的下界。 具体地，存在 $\epsilon =\epsilon (C)>0$，使得

$$r(\ell ,C\ell )\ge {\left(p_C^{-1/2}+\epsilon \right)}^{\ell },$$

其中

$$p_C\in (0,1/2)$$

是满足

$$C=\frac{\log p_C}{\log (1-p_C)}$$

的唯一数。这给出了对 Erdős 1947 年经典下界的首次指数级改进。

Ramsay定理（通式）和幸福结局问题

Ramsey 定理（通式）

任给正整数 $r,k$ 以及 $q_1,\dots ,q_k\ge r$，存在 $n\in {\mathbb{Z}}^{+}$，使得对 $[n]$ 的所有 $r$-子集的任一个 $k$-着色，一定存在 $1\le i\le k$ 和相应的 $S_i\subseteq [n]$，使得 $|S_i|=q_i$，并且 $S_i$ 的所有 $r$-子集都着第 $i$ 个颜色。记具有上述性质的 $n$ 的最小值为

$$R^{(r)}(q_1,\dots ,q_k).$$

• 当 $r=1$ 时，即一般形式的抽屉原理。此时

$$R^{(1)}(q_1+1,\dots ,q_k+1)=\sum _{i=1}^k{q}_i+1.$$

• 当 $r=k=2$ 时，通式即简式。（$2$-子集 $\leftrightarrow$ 边）

• 其它已知的精确值：

$$R^{(3)}(4,4)=13,R^{(2)}(3,3,3)=17.$$

Ramsey 定理在几何问题上的应用

Erdős-Szekeres 定理（1935）

设 $m\ge 3$，则存在正整数 $N$，使得平面上任意 $N$ 点（无三点共线）中，必有 $m$ 个点构成凸 $m$ 边形。

引理 1. $(N=5,m=4)$

平面上无三点共线的任意五点中，必有四点构成凸四边形。

证明．两两连接五个点，一定形成凸边形。

• 若形成凸五边形或凸四边形，则已得结论。
• 若只形成三角形，则必有两点在三角形内部。用直线连接这两个内点，则三角形必有两个顶点位于此直线的同侧，从而这两个顶点和两个内点构成一个凸四边形。

引理 2.

设平面上 $m\ge 4$ 个点中无三点共线，且其中任意四点都形成凸四边形，则这 $m$ 个点必形成凸 $m$ 边形。

证明．对 $m$ 作归纳法。$m=4$ 时显然成立。 设 $m>4$，则其中必有三点 $A,B,C$ 使其余 $m-3$ 个点都位于 $\angle BAC$ 内部，且在 $△ABC$ 中没有点。（因任意四点都形成凸四边形） 考虑除 $A$ 外的 $m-1$ 个点，由归纳假设，它们形成凸 $m-1$ 边形，并且 $BC$ 是其中的一条边。将 $BC$ 换成 $AB$ 和 $AC$ 后即得凸 $m$ 边形。

幸福结局问题

引理 1. $(N=5,m=4)$

平面上无三点共线的任意五点中，必有四点构成凸四边形。

引理 1 是 1933 年在布达佩斯的一次学术聚会中，由数学系女生 Klein 发现的问题．此后化学系男生 Szekeres 与 Erdős 合作，重新发现了 Ramsey 定理，并由此一般化了 Klein 的问题，得到如下定理。

Erdős-Szekeres 定理（1935）

设 $m\ge 3$，则存在正整数 $N$，使得平面上任意 $N$ 点（无三点共线）中，必有 $m$ 个点构成凸 $m$ 边形。

这个问题成就了 Klein 和 Szekeres 的婚姻，因而 Erdős 称之为“幸福结局问题”（Happy Ending Problem）．Klein 和 Szekeres 于 1936 年结婚，二战期间因犹太人身份离开匈牙利到上海，最后定居在澳洲，历经 70 年从未分离．2005 年 8 月 28 日在不到一小时内相继去世。