拉姆塞问题的证明是什么？
拉姆塞问题是一个在组合数学中非常有名的问题，它被称为“人类追求智慧的最高境界”。该问题的原始形式是：如果在一个有限的 *** 中，任意两个元素都有不同的颜色，那么能否在该 *** 中找到一个大小为r的子集，使得该子集的所有元素都是同一颜色？
换句话说，拉姆塞问题就是在寻找一种颜色分割方式，使得无论如何划分，都能找到一组同色子集。比如，对于一个5个点的完全图，我们想知道是否存在一个大小为3的clique或者一个大小为3的independent set。这个问题的答案是肯定的，具体证明如下。
我们先考虑最简单的情形，即r=2。此时我们要证明的命题是：在任意一个有限的 *** 中，无论如何为其中的元素染色，必定有至少一个大小为2的子集，其元素颜色相同。
用反证法，假设我们在染色的时候没有找到这样的颜色分割方式。因此，对于任意的子集都不成立。那么，我们可以构造两个颜色分别为a和b的点，使得它们组成一个无色边。对于其他任意的点，它们都染有a或b这两种颜色之一。那么我们可以分别考虑包含一个a结点或一个b结点的点集，由于这两个点之间没有边，因此它们必然构成一个无色边。
此时我们可以通过归纳法来证明一般情形的结论。假设在任意一个有限 *** 中，存在一个大小为r-1的子集，使得该子集的元素颜色相同。那么我们来考虑一个大小为r的 *** ，用任意一种颜色分割方式染色。由于每个元素可以染任何一种颜色，我们可以分别考虑包含一个指定元素和不包含它的指定颜色的点集。此时，我们把子集划分成两个大小为r-1的子集，根据归纳假设，这两个子集中必定都有一个元素颜色相同。如果这两个元素颜色相同，那么我们就可以从这两个子集中构造出一个大小为r的同色子集；如果这两个元素颜色不同，那么它们就可以作为一个含有两种颜色的元素，放到划分出的另一个包含它的点集中去，此时我们又构造出了一个大小为r的同色子集。
所以，拉姆塞问题在任意一个有限 *** 中均存在这样的分割方式，使得无论如何划分，都能找到一组同色子集。
Tags：