Ramsey 定理

一、Ramsey 定理

Ramsey 定理是关于鸽巢原理的重要拓展，甚至可以从另一个维度解释鸽巢原理。

1.1 $\quad$ 基本定义

我们先给出一些定义。

对于由 $n$ 个点构成的图，两两节点直接都有边直接相连，则成这张图是完全图。

我们把 $p$ 个点的完全图，记作 $K_p$。

我们用两种颜色对所有边进行染色，染色成 $a$ 或者 $b$，如果下面两个条件至少满足其一：

存在 $n$ 个点的子集，使其构成的完全图中所有边的颜色为同一种颜色 $a$；
存在 $m$ 个点的子集，使其构成的完全图中所有边的颜色为同一种颜色 $b$。

我们记作

$K_p\rightarrow K_m,K_n$

我们记 Ramsey 数 $r(n,m)$ 是使 $K_p\rightarrow K_n,K_m$ 的最小正整数 $p$。我们不难发现

$r(n,m)=r(m,n)$

例子 $\quad$ 在 $6$ 个人构成的集合中，要么 $3$ 个人互相认识，要么 $3$ 个人互相不认识。

我们给出这个例子的证明。

我们对于 $6$ 个点的完全图，两个人间互相认识则边染红色，否则边染蓝色。考虑图中的任意一个点 $p$，与其相连的 $5$ 条边中，至少有 $3$ 条边颜色相同（根据鸽巢原理可得）。因为情况对称，我们令染红色的边数至少为 $3$，那我们举出这三条边连接的三个点 $a,b,c$，分类考虑以下情况：

如果由 $a,b,c$ 三个点构成的完全图中所有边都是蓝色，那么这三个点构成一个蓝 $K_3$。
如果由 $a,b,c$ 三个点构成的完全图中有一个边是红色，那么这条红边连接的两个点，和点 $p$ 构成一个红 $K_3$。

则红 $K_3$ 和蓝 $K_3$ 两个至少有一个成立。即证明了这个结论。

1.2 $\quad$ 基本的 Ramsey 定理

下面给出更广泛的定理和证明。

定理 $\quad$ $\forall n,m\ge 2,\exists p\in \mathbb{N}_+$，使得

$K_p\rightarrow K_m,K_n$

证明 $\quad$ 我们很容易确定 $r(2,n)$ 和 $r(n,2)$ 的值。下面证明 $r(2,n)=r(n,2)=n$。

确定 $r(2,n)\leq n$：如果所有边都是同一种颜色，则 $K_n$ 成立；否则 $K_2$ 成立。
确定$r(2,n)>n-1$：如果有一个红 $K_{n-1}$，我们并不能得到蓝 $K_2$ 或者红 $K_n$。

下面用归纳法证明广泛结论。

假设 $m,n\ge 3$ ，归纳假设为 $r(m-1,n)$ 和 $r(m,n-1)$ 存在。设 $p=r(m-1,n)+r(m,n-1)$，下面证明 $K_p\rightarrow K_m,K_n$ 存在。

假设 $K_p$ 已经通过某种方式完成红色和蓝色的染色，我们对其中的一个节点 $x$，记 $B_x,R_x$ 分别为通过蓝色边和红色边在图中与 $x$ 相连的点的集合。有

$|R_x|+|B_x|=p-1=r(m-1,n)+r(n,m-1)-1$

也就是说，以下两个条件至少有一个成立：

$|R_x|\ge r(m-1,n)$；
$|B_x|\ge r(m,n-1)$。

可以通过鸽巢原理说明这一点，因为如果两个都不成立，则 $|R_x|+|B_x|\le r(m+1,n)+r(m,n-1)-1=p-2$，矛盾。

我们假设条件1成立，也就是 $|R_x|\ge r(m-1,n)$，说明下面两个条件至少有一个成立：

可能存在一个红 $K_{m-1}$，这个图的节点就是 $R_x$ 中的节点。如果我们将 $x$ 加入这个图，因为与 $x$ 相连的边为红色，就可以得到一个 $K_m$，完成证明；
可能存在一个蓝 $K_n$，这时我们直接完成了证明。

所以此时结论成立。同理，若条件2成立，则结论也一定成立。

证毕。

上面的证明不仅证明了 Ramsey 数的存在，也给出了不等式

$r(m,n)\le r(m-1,n)+r(m,n-1)\quad (m,n\ge 3)$

设函数

$f(m,n)=\dbinom{m+n-2}{m-1}\quad (m,n\ge 2)$

得到

$f(m,n)=\dbinom{m+n-3}{m-1}+\dbinom{m+n-3}{m-2}=f(m-1,n)+f(m,n-1)$

这是一个等式。因为 $r(2,n)=n=f(2,n)\ ,\ r(m,2)=m=f(m,2)$，所得 Ramsey 数满足

$r(m,n)\le \dbinom{m+n-2}{m-1}=\dbinom{m+n-2}{n-1}$

1.3 $\quad$ Ramsey 定理的推广

上面我们将一个完全图每条边染成了 $2$ 种颜色，我们将其扩展，对一个点数为 $n$ 的完全图，用 $k$ 种颜色染色。如果 $n_1,n_2,\cdots,n_k\ge 2$，则存在 $p$ 使得：

$K_p\rightarrow K_{n_1},K_{n_2}\cdots,K_{n_k}$

使得该结论成立的最小整数 $p$ 称为 Ramsey 数 $r(n_1,n_2,\cdots ,n_k)$。

如果我们把点对（两个元素的子集）扩展成 $t$ 个元素的子集，令 $K_n^t$ 表示 $n$ 元素集合种所有 $t$ 个元素的子集的集合，扩展 Ramsey 定理。

给定整数 $t\ge 2$ 和整数 $q_1,q_2,\cdots ,q_k\ge t$，存在整数 $p$，使得

$K_p^t\rightarrow K_{p_1}^t,K_{p_2}^t,\cdots,K_{p_k}^t$

满足结论的最小整数 $p$ 称为 Ramsey 数 $r(q_1,q_2,\cdots,q_k)$。

$q_1,q_2,\cdots,q_k$ 的排列并不影响 Ramsey 数的表现。