Ramsey定理-拓崇最新章节-免费小说-全文免费阅读-拓崇作品-话本小说网

无穷组合中的Ramsey定理起源于图论里的Ramsey问题。首先我们来看一个简单情况。

Ramsey（k＝3，l＝3）：平面上有6个点，两两之间连边，并且每条边染成红色或蓝色，则要么有红边构成的三角形，要么有蓝边构成的三角形。

证明：

记这6个点为 A₁，…，A₆，我们来逐点分析。对于 A₁ 而言，它与剩下5个点之间连的5条边中，红色边与蓝色边之中必有一类不少于3条（抽屉原理）。不妨设 A₁ 与 A₂，A₃，A₄ 连的都是红边，此时分为两种情况：

若 A₂，A₃，A₄ 之间存在红边，不妨设 A₂A₃ 是红边，那么 A₁A₂A₃ 就是红边三角形。

若 A₂，A₃，A₄ 之间全是蓝边，则 A₂A₃A₄ 是蓝边三角形。

综上，总存在红边或蓝边三角形。 ◻

对上述问题简单推广，就得到Ramsey问题的表述。

Ramsey问题：对一个 n 阶无向完全图的边红蓝二染色，要么存在边全为红色的 k 阶完全子图，要么存在边全为蓝色的 l 阶完全子图。给定 k，l ，总存在满足条件的 n 吗？

事实上，这样的 n 总是存在的，并且我们把最小的 n 称为Ramsey数，记为 R(k，l) 。

证明：

对 k＋l 使用数学归纳法。

首先，显然有 R(1，l)＝1 和 R(k，1)＝1 成立。

假设 R(k−1，l) 与 R(k，l−1) 都存在，记 n₁＝R(k−1，l)，n₂＝R(k，l−1) ，希望证明任意 n₁＋n₂ 阶完全图 G 存在红色 k 阶完全子图或蓝色 l 阶完全子图，即 R(k，l) 存在且不超过 n₁＋n₂ 。取 G 中一个点 A ， A 与其他点连了 n₁＋n₂−1 条边，这些边里要么红边至少有 n₁ 条，要么蓝边至少有 n₂ 条。

• A 连出的红边至少有 n₁ 条：由归纳假设，这 n₁ 个点中要么存在红色 k−1 阶完全子图，要么存在蓝色 l 阶完全子图。如果是后者，则命题得证。如果是前者，记这个子图为 G₁ ，由于 A 与 G₁ 中的点连的都是红边，因此 G₁∪{A} 是红色 k 阶完全子图，命题亦得证。

• A 连出的蓝边至少有 n₂ 条：由归纳假设，这 n₂ 个点中要么存在红色 k 阶完全子图，要么存在蓝色 l−1 阶完全子图。如果是前者，则命题得证。如果是后者，记这个子图为 G₂ ，由于 A 与 G₂ 中的点连的都是蓝边，因此 G₂∪{A} 是蓝色 l 阶完全子图，命题亦得证。

由数学归纳法，原命题得证。 ◻

Ramsey数很难计算，至今无人给出确切通项。不过在上述证明中，我们已给出了估计Ramsey数的一个不等式，即 R(k，l)≤R(k−1，l)＋R(k，l−1) 。与组合数递推式 (ⁿ) ⁿ⁻¹

(ᵣ)＝(ᵣ)＋

(ⁿ⁻¹)

(ᵣ) 比较，可以通过归纳给出Ramsey数的上界： R(k，l)≤(ᵏ⁺ˡ⁻²)

(k−1) 。

上述问题可以继续推广至 m 染色的情况。可证明对任意正整数 k ，存在足够大的 n 使得任意 n 阶完全图进行 m 染色都存在 k 阶同色完全子图。有兴趣的同学自己证明。

对以上问题总结，Ramsey研究的就是将某一个结构划分成小部分，为了使其中存在满足给定条件的部分，原结构至少应有多大。下面我们把这一思想推广至不可思议的地步。

[1]划分命题：设 r，s，κ，λ 为基数，表达式 κ→(λ)ʳₛ 表示以下命题：

• 记 [X]ʳ＝{A⊆X||A|＝r} 。

设 X 的基数为 κ ，对于任意函数 f：[X]ʳ → s ，总存在 H⊆X 满足 |H|＝λ ，且 f 限制在 [H]ʳ 上是常值函数。我们称 f 为划分函数， H 是划分函数的齐一集。

解释：在 r＝2 时， X 可视为一个 κ 阶完全图的顶点集，集合 [X]² 就是 κ 阶完全图的边集（任意两个顶点的无序对的集合）。划分函数 f 将每条边对应到了 s 的元素，因此可视为这个 κ 阶完全图的一个 s 染色。而 f 限制在 [H]r 上是常值函数则说明这个 λ 阶完全子图是同色子图。因此，前面Ramsey问题的推广可以表示为：对于正整数 k，m ，存在足够大的正整数 n 保证 n →(k)²ₘ 成立。将其继续推广（至 r＞2 的情形），就得到

Ramsey有限划分定理：对于任意正整数 k，m，l ，存在足够大的 n 保证 n→(k)ˡₘ 成立。

下面将进入这篇文章的核心部分，即无限情形。

[2]命题： ∀1＜m∈ℕ，ω→(ω)²ₘ

证明：

考虑划分函数 f：[ω]² → m ，往证齐一集 |H|＝ω 的存在性。根据上面的解释，该命题等价于：对 ω 阶完全图的边 m 染色，存在 ω 阶同色完全子图。

证明的思路是找到一个顶点序列 Aₙ(n∈ω) 和一个颜色序列 iₙ∈m(n∈ω) ，满足对于任意 k＜n∈ω ，边 AₖAₙ 的颜色总是 f({Aₖ，Aₙ})＝iₖ。由于颜色只有 m 种，必存在一种颜色 t 在序列 iₙ 中出现了无限次。不妨设 iₙₛ＝t(s∈ω) ，记 H＝{Aₙₛ|s∈ω} ，则 |H|＝ω 且其中任意两点连边的颜色都为 t ，因此即为一个 ω 阶同色完全子图。

现在我们来构造。第0个点可以随便选，就取 A₀＝0 。由于颜色有限，顶点无限，必存在某种颜色使其在 A₀ 与其他点连的边中出现了无限次，记为 i₀ ，并记这些点的集合为 H0，₀＝{A∈ω|f({A，A₀})＝i₀}⊆ω ，有 |H₀|＝ω 。因此我们只需把后面的点选在 H₀ 中，即可使 A₀ 与后面的点连边的颜色总是 i₀ 。

接下来归纳定义。设 Aₙ，Hₙ，iₙ 已定义，令 Aₙ₊₁＝min Hₙ ，存在某种颜色在 Aₙ₊₁ 与 Hₙ 其他点连的边中出现了无限次，记为 iₙ₊₁ ，记 Hₙ₊₁＝{A∈ω|f({A，Aₙ₊₁})＝i₁}⊆Hₙ ， |Hₙ₊₁|＝ω 。

显然如此构造的 Aₙ，iₙ 满足条件，命题得证。 ◻

继续推广该命题，最后我们来到Ramsey定理。

Ramsey定理： ∀1＜m，r∈ℕ，ω → (ω)ʳₘ

证明：

下面对 r 归纳， r＝2 时已证。

假设命题对 r 成立，对于划分函数 f：[ω]r，ʳ⁺¹ → m ，往证齐一集 |H|＝ω 的存在性。思路依然是找到序列 Aₙ(n∈ω) 和 iₙ∈m(n∈ω) ，满足对于任意 k＜l₁＜⋯＜lᵣ ∈ ω ， f({Aₖ，Aₗ₁，…，Aₗᵣ})＝iₖ 。必存在 t 在序列 iₙ 中出现了无限次，可不妨设 iₙₛ＝t(s∈ω) ，记 H＝{Aₙₛ|s∈ω} ，则 H 是齐一集。

取 A₀＝0 ，记划分函数 f₀：[ω−{A0}]ʳ → m 满足 f₀(x)＝f(x∪{A₀}) 。运用归纳假设，存在 f₀ 的齐一集 H₀ ， f₀ 在 [H₀]ʳ 上值为 i₀ 。

归纳定义。设 Aₙ，Hₙ，iₙ 已定义，令 Aₙ₊₁＝min Hₙ ，记划分函数 fₙ₊₁：[Hₙ−{Aₙ₊₁}]ʳ → m 满足 fₙ₊₁(x)＝f(x∪{Aₙ₊₁}) 。运用归纳假设，存在 fₙ₊₁ 的齐一集 Hₙ₊₁ ， fₙ₊₁ 在 [Hₙ₊₁]ʳ 上值为 iₙ₊₁。

如此构造的 Aₙ，iₙ 满足条件，定理得证。 ◻

参考

^以下内容参考冯琦《集合论导引》第一卷2.6节

^如果你不知道这个omega是什么意思，可以把它视为自然数集