Ramsey定理 (3-2)

上述问题可以继续推广至 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 时已证。

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