组合学/拉姆齐定理

拉姆齐定理是组合学中的一个基础结果。该结果的第一个版本由 F. P. 拉姆齐 证明。这开创了被称为拉姆齐理论的组合理论，该理论试图在混乱中寻找规律：寻找具有规律性质的子结构存在的普遍条件。该定理指出

在对足够大的完全图（即每个顶点对之间都有一条边连接的简单图）的边进行任何着色时，都会找到单色完全子图。对于 2 种颜色，拉姆齐定理指出，对于任何一对正整数 (r,s)，存在一个最小的正整数 R(r,s)，使得对于任何具有 R(r,s) 个顶点的完全图，其边被涂成 红色或 蓝色，要么存在一个具有 r 个顶点的完全子图，其完全为红色，要么存在一个具有 s 个顶点的完全子图，其完全为蓝色。这里 R(r,s) 表示一个取决于 r 和 s 的整数。它被理解为代表该定理成立的最小整数。

该定理的扩展适用于任何有限的颜色数量，而不仅仅是两种颜色。更准确地说，该定理指出，对于任何给定的颜色数量 c，以及任何给定的整数 n₁,...,n_c，存在一个数字 R(n₁,...,n_c)，使得如果阶为 R(n₁,...,n_c) 的完全图的边用 c 种不同的颜色着色，则在 1 到 c 之间的某个 i 处，它必须包含一个阶为 n_i 的完全子图，其边都是颜色 i。上面的特例有 c = 2（以及 n₁ = r 和 n₂ = s）。

示例：R(3,3)=6

没有单色 K₃ 的 K₅ 的 2 色着色

假设一个具有 6 个顶点的完全图的边被涂成红色和蓝色。选择一个顶点 v。有 5 条边与 v 相连，因此（根据抽屉原理）至少 3 条边必须是相同的颜色。不失一般性，我们可以假设至少 3 条这些边连接到顶点 r、s 和 t，是蓝色的。（如果不是，在下面交换红色和蓝色。）如果边 (r, s)、(r, t)、(s, t) 中的任何一个也是蓝色的，那么我们就得到了一个完全是蓝色的三角形。如果不是，那么这三条边都是红色的，我们就得到了一个完全是红色的三角形。由于这个论证适用于任何着色，因此任何 K₆ 都包含一个单色 K₃，因此 R(3,3) ≤ 6。这个定理的流行版本被称为朋友和陌生人定理。

一个交替证明方法是通过双重计数。它如下所示：计算顶点 x、y、z 的有序三元组的数量，使得边 (xy) 为红色，边 (yz) 为蓝色。首先，任何给定的顶点将是 0×5=0、1×4=4 或 2×3 = 6 个此类三元组的中间顶点。因此最多有 6×6=36 个此类三元组。其次，对于任何非单色三角形 (xyz)，恰好存在两个此类三元组。因此最多有 18 个非单色三角形。因此，在 K₆ 中的 20 个三角形中，至少有 2 个是单色的。

相反，可以对 K₅ 进行 2 色着色，而不会创建任何单色 K₃，这表明 R(3,3) > 5。右侧显示了唯一的着色。因此 R(3,3) = 6。

定理证明

首先，我们通过对 r + s 进行归纳来证明 2 色情况下的定理。从定义中可以明显看出，对于所有 n，R(n, 1) = R(1, n) = 1。这开始了归纳。我们通过找到它的显式界限来证明 R(r, s) 存在。根据归纳假设，R(r − 1, s) 和 R(r, s − 1) 存在。

断言：R(r, s) ≤ R(r − 1, s) + R(r, s − 1): 考虑一个具有 R(r − 1, s) + R(r, s − 1) 个顶点的完全图。从图中选择一个顶点 v，并将剩余的顶点划分为两个集合 M 和 N，使得对于每个顶点 w，如果 (v, w) 为蓝色，则 w 在 M 中，如果 (v, w) 为红色，则 w 在 N 中。

因为该图具有 R(r - 1, s) + R(r, s - 1) = |M| + |N| + 1 个顶点，所以 |M| ≥ R(r − 1, s) 或 |N| ≥ R(r, s − 1)。在前一种情况下，如果 M 具有一个红色 K_s，那么原始图也具有一个红色 K_s，我们就完成了。否则 M 具有一个蓝色 K_r−1，因此 $M\cup \{v\}$ 根据 M 的定义具有蓝色 K_r。后一种情况类似。

因此断言是正确的，我们完成了对 2 种颜色的证明。我们现在证明了 c 种颜色的一般情况下的结果。证明仍然是归纳法，这次是对颜色数量 c 进行归纳。我们对 c = 1（平凡的）和 c = 2（上面）得到了结果。现在让 c > 2。

断言：R(n₁, ..., n_c) ≤ R(n₁, ..., n_c−2, R(n_c−1, n_c))

注意，右手边只包含 c − 1 种颜色和 2 种颜色的拉姆齐数，因此根据归纳假设，它存在并且是有限数 t。因此，证明断言将证明定理。

断言证明：考虑一个具有 t 个顶点的图，并用 c 种颜色对它的边进行着色。现在“色盲”，假装 c − 1 和 c 是同一种颜色。因此该图现在是 (c − 1) 色的。根据归纳假设，它包含一个 K_ni，用颜色 i 单色着色，对于某个 1 ≤ i ≤ (c − 2)，或者一个 K_R(nc−1,nc)，用“模糊色”着色。在前一种情况下，我们完成了。在后一种情况下，我们恢复了视力，并从 R(n_c−1, n_c) 的定义中可以看到，我们必须要么有一个 (c − 1) 单色 K_nc−1，要么有一个 c 单色 K_nc。在任何一种情况下，证明都完成了。

定理的扩展

该定理也可以扩展到超图。一个 m 超图是一个图，其“边”是 m 个顶点的集合——在一个普通图中，边是 2 个顶点的集合。拉姆齐定理关于超图的完整陈述是，对于任何整数 m 和 c，以及任何整数 n₁,...,n_c，存在一个整数 R(n₁,...,n_c;c,m)，使得如果阶为 R(n₁,...,n_c;c,m) 的完整 m 超图的超边用 c 种不同的颜色着色，则对于某个 1 到 c 之间的 i，超图必须包含一个阶为 n_i 的完整子 m 超图，其超边都是颜色 i。这个定理通常通过对 m（图的“超”程度）进行归纳来证明。证明的基本情况是 m=2，这正是上面的定理。