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

《组合数学-第二节：Ramsey问题与Ramsey数.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二节：Ramsey问题与Ramsey数1958年6~7月号美国《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。”这就是著名的Ramsey问题。以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红边，否则在相应的两顶点间连一蓝边，则上述的Ramsey问题等价于下面的命题：命题1.3.1对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。证明设是的6个顶点，与所连的5条边着红色或蓝色。由鸽巢原理知，其中至少有条边同色，不妨设

2、与所连的3条边均为红色，如图1.3.1所示。若间有一条红边，不妨设为，则是一红色三角形。否则，间均为蓝边，即是一蓝色三角形。类似于命题1.3.1，还有如下的命题1.3.2~命题1.3.4：命题1.3.2对6个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形。证明设是的6个顶点，由命题1.3.1知，对任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角形，以下分各种情况来讨论：（1）若均为蓝边，如图1.3.2所示，则若之间有一蓝边，不妨设为，则为蓝色三角形；否则，为红色三角形。（2）若中有一红边，

3、不妨设为红边，此时若边中有一条红边，不妨设是红边，则是一红色三角形，见图1.3.3。以下就均为蓝边的情况对与相关联的边的颜色进行讨论：（i）若中有一蓝边，不妨设为蓝边，如图1.3.4所示。此时，若均为红边，则是红色三角形；否则，或是蓝色三角形。（ii）若均为红边，见图1.3.5。此时，若之间有一条红边，不妨设为红边，则为红色三角形；否则，为蓝色三角形。由以上对各种情况的讨率知，对的任意红、蓝两边着色均有两个同色三角形。命题1.3.3对10个顶点的完全图任意进行红、蓝两边着色，都或者有一红色，或者有一蓝色。证明设

4、是的一个顶点，与相关联的9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有6条红边，要么有4条蓝边。类似于前面两个命题的分析证明过程可以得出结论，具体分析过程见图1.3.6。命题1.3.4对9个顶点的完全图任意进行红、蓝两边着色，都或者有一个红色，或者有一蓝色。证明在中，如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以中应有条边，它不是整数，所以不成立。故必有一个顶点关联的红边数不为5，设此顶点为，则与关联的红边数至少为6或至多为4。1.3.2Ramsey数从1..3.1小节的讨论中可以归纳

5、出如下的一般性定义：对于任意给定的两个正整数与，如果存在最小的正整数，使得当时，对中均有红色或蓝色，则称为Ramsey数。由命题1.3.1知；在中按图1.3.7的方式进行红、蓝两边着色（实线为红边，虚线为蓝边），则既无红色也无蓝色，所以。从而得知。由命题1.3.4；在中按图1.3.8的方式进行红、蓝两边着色，则既无红色也无蓝色，所以。从而得知Ramsey于1930年证明了对于任给的整数和，Ramsey数的存在性。但是，Ramsey数的确定却是一个非常难的问题，以至于至今尚不为世人所知。表1.3.1中列出了目前所

6、知的一些Ramsey数。易证（留作习题）（1）（1.3.1）（2）（1.3.2）定理1.3.1对任意的正整数，有证明令，对任意进行红、蓝两边着色。设是的一个顶点，在中与相关联的边共有条，这些边要么为红色，要么为蓝色。由鸽巢原理知，与相关联的这些边中，要么至少有条红边，要么至少有条蓝边。（1）这些边中有条红边。在以这些红边与相关联的个顶点构成的完全图中，必有一个红色或有一个蓝色，若有红色，则该红色加上顶点以及与之间的红边，即构成一个红色；否则，就有一个蓝色。（2）这些边中有条蓝边。在以这些蓝边与相关联的个顶点构成

7、的完全图中，必有一个红色或有一个蓝色。若有一个蓝色，则该加上顶点以及与之间的蓝边，即构成一个蓝色；否则，就有一个红色。综合（1）和（2），知。由定理1.3.1及等式（1.3.2）容易归纳出对于任意的正整数和的存在性。关于还有定理1.3.2所述的不等式成立。定理1.3.2对任意的正整数，有证明对作归纳。当时，或，由等式（1.3.2）知定理成立。假设对一切满足的定理成立，由定理1.3.1及归纳假设，有所以，对于任意的正事业，定理的结论成立。1.4Ramsey数的推广将1.3节中的红、蓝两色推广到任意k种颜色，对N个

8、顶点的完全图用共k种颜色任意进行k边着色，它或者出现颜色的，或者出现颜色的，……，或者出现颜色的。满足上述性质的N的最小值记为。定理1.4.1对任意的正整数，有证明留作习题类似于定理1.3.1和定理1.3.2，有如下的结论：定理1.4.2对任意的正整数，有证明类似于定理1.3.1的证明。定理1.4.3对任意的正整数，有证明类似于定理1.3.2的证明。利用广义Ramsey数，我们来讨论一