Ramsey定理 (3-1)

无穷组合中的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) 。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。