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 数的表现。