组合数学-第二节：Ramsey问题与Ramsey数

组合数学-第二节：Ramsey问题与Ramsey数组合数学-第二节：Ramsey问题与Ramsey数组合数学-第二节：Ramsey问题与Ramsey数组合数学-第二节：Ramsey问题与Ramsey数编制仅供参考审核批准生效日期地址：电话：传真:邮编:第二节：Ramsey问题与Ramsey数1958年6~7月号美国《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。”这就是著名的Ramsey问题。以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红边，否则在相应的两顶点间连一蓝边，则上述的Ramsey问题等价于下面的命题：命题对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。证明设是的6个顶点，与所连的5条边着红色或蓝色。由鸽巢原理知，其中至少有条边同色，不妨设与所连的3条边均为红色，如图所示。若间有一条红边，不妨设为，则是一红色三角形。否则，间均为蓝边，即是一蓝色三角形。类似于命题，还有如下的命题命题：命题对6个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形。证明设是的6个顶点，由命题知，对任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角形，以下分各种情况来讨论：（1）若均为蓝边，如图所示，则若之间有一蓝边，不妨设为，则为蓝色三角形；否则，为红色三角形。（2）若中有一红边，不妨设为红边，此时若边中有一条红边，不妨设是红边，则是一红色三角形，见图。以下就均为蓝边的情况对与相关联的边的颜色进行讨论：（i）若中有一蓝边，不妨设为蓝边，如图所示。此时，若均为红边，则是红色三角形；否则，或是蓝色三角形。（ii）若均为红边，见图。此时，若之间有一条红边，不妨设为红边，则为红色三角形；否则，为蓝色三角形。由以上对各种情况的讨率知，对的任意红、蓝两边着色均有两个同色三角形。命题对10个顶点的完全图任意进行红、蓝两边着色，都或者有一红色，或者有一蓝色。证明设是的一个顶点，与相关联的9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有6条红边，要么有4条蓝边。类似于前面两个命题的分析证明过程可以得出结论，具体分析过程见图。命题对9个顶点的完全图任意进行红、蓝两边着色，都或者有一个红色，或者有一蓝色。证明在中，如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以中应有条边，它不是整数，所以不成立。故必有一个顶点关联的红边数不为5，设此顶点为，则与关联的红边数至少为6或至多为4。Ramsey数从1..小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数与，如果存在最小的正整数，使得当时，对中均有红色或蓝色，则称为Ramsey数。由命题知；在中按图的方式进行红、蓝两边着色（实线为红边，虚线为蓝边），则既无红色也无蓝色，所以。从而得知。由命题；在中按图的方式进行红、蓝两边着色，则既无红色也无蓝色，所以。从而得知Ramsey于1930年证明了对于任给的整数和，Ramsey数的存在性。但是，Ramsey数的确定却是一个非常难的问题，以至于至今尚不为世人所知。表中列出了目前所知的一些Ramsey数。易证（留作习题）（1） （）（2） （）定理对任意的正整数，有证明令，对任意进行红、蓝两边着色。设是的一个顶点，在中与相关联的边共有条，这些边要么为红色，要么为蓝色。由鸽巢原理知，与相关联的这些边中，要么至少有条红边，要么至少有条蓝边。（1）这些边中有条红边。在以这些红边与相关联的个顶点构成的完全图中，必有一个红色或有一个蓝色，若有红色，则该红色加上顶点以及与之间的红边，即构成一个红色；否则，就有一个蓝色。（2）这些边中有条蓝边。在以这些蓝边与相关联的个顶点构成的完全图中，必有一个红色或有一个蓝色。若有一个蓝色，则该加上顶点以及与之间的蓝边，即构成一个蓝色；否则，就有一个红色。综合（1）和（2），知。由定理及等式（）容易归纳出对于任意的正整数和的存在性。关于还有定理所述的不等式成立。定理对任意的正整数，有 证明对作归纳。当时，或，由等式（）知定理成立。假设对一切满足的定理成立，由定理及归纳假设，有 所以，对于任意的正事业，定理的结论成立。Ramsey数的推广将节中的红、蓝两色推广到任意k种颜色，对N个顶点的完全图用共k种颜色任意进行k边着色，它或者出现颜色的，或者出现颜色的，……，或者出现颜色的。满足上述性质的N的最小值记为。定理对任意的正整数，有 证明留作习题类似于定理和定理，有如下的结论：定理对任意的正整数，有证明类似于定理的证明。定理对任意的正整数，有证明类似于定理的证明。利用广义Ramsey数，我们来讨论一类集合划分问题。考试集合的一个划分可以看出，在上面的划分的每一块中，都不存在三个数（不一定不同）满足方程 （然而，无论如何将集合划分成三个子集合，总有一个子集合中有三个数满足方程（）。Schur于1916年证明了对任意的正整数n，都存在一个整数，使得无论如何将集合划分成n个子集合，总有一个子集合中有三个数满足方程（）。下面，我们用Ramsey数来证明这个结论。定理设是集合的任一划分，即，且，则对某一个中有三个数（不一定不同），满足方程。其中证明将完全图中的个顶点分别用来标记，对的边进行n着色如下：设是的任意两个项点，若，则将边染成第种颜色。由广义Ramsey数的定义知一定存在同色三角形，即有三个项，使得边有相同的颜色，设为第种颜色。另不妨设，则有，令，则有，且。设是满足下述性质的最小整数：将任意划分成n个子集合，总有一个子集合中含有三个数，满足方程（）。容易证明（见本章习题24）。在本章的习题中，还列有一些关于和的上、下界的结论。将前面的鸽巢原理和Ramsey数进一步推广，可以得到下面更一般的Ramsey定理：定理（Ramsey定理）设，是正整数，且，则必存在最小的正整数，使得当时，设S是一集合且，将S的所有元子集任意分放到n个盒子里，那么要么有S中的个元素，它的所有元子集全在第二个盒子里；……；要么有S中的个元素，它的所有元子集全在第n个盒子里。证明略。当时，Ramsey定理说明存在，使得对任何，把m个物体放入n个盒子里，或者有个物体都在第一个盒子里，或者有个物体都在第二个盒子里，……，或者有个物体都在第n个盒子里。从节中鸽巢原理的加强形式知 当时，可以设想S是一完全图的顶点集合，n个盒子可以设想成n种颜色，S的2元子集就是图中连接两个顶点的边。此时，Ramsey定理中的 特别地，当时，由节中的结论知 定理证明若S中元素少于或等于个，则将S的所有元子集全部放入第一个盒子里。这里，没有S的元子集，它的所有元子集全在