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

1/7第二节：Ramsey问题与Ramsey数1958年6~7月号美国《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。”这就是著名的Ramsey问题。以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红边，否则在相应的两顶点间连一蓝边，则上述的Ramsey问题等价于下面的命题：命题1.3.1对6个顶点的完全图6K任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。证明设123456,,,,,是6K的6个顶点，1与23456,,,,所连的5条边着红色或蓝色。由鸽巢原理知，其中至少有532条边同色，不妨设1与234,,所连的3条边均为红色，如图1.3.1所示。若234,,间有一条红边，不妨设为23，则123是一红色三角形。否则，234,,间均为蓝边，即234是一蓝色三角形。类似于命题1.3.1，还有如下的命题1.3.2~命题1.3.4：命题1.3.2对6个顶点的完全图6K任意进行红、蓝两边着色，都至少有两个同色三角形。证明设123456,,,,,是6K的6个顶点，由命题1.3.1知，对6K任意进行红、蓝两边着色都有一个同色三角形，不妨设123是红色三角形，以下分各种情况来讨论：（1）若123456,,,,,均为蓝边，如图1.3.2所示，则若456,,之间有一蓝边，不妨设为45,，则145为蓝色三角形；否则，456为红色三角形。2/7（2）若123456,,,,,中有一红边，不妨设14,为红边，此时若边2434,中有一条红边，不妨设34是红边，则134是一红色三角形，见图1.3.3。以下就2434,均为蓝边的情况对与4相关联的边的颜色进行讨论：（i）若4546,中有一蓝边，不妨设45,为蓝边，如图1.3.4所示。此时，若2535,均为红边，则235是红色三角形；否则，245或345是蓝色三角形。（ii）若4546,均为红边，见图1.3.5。此时，若156,,之间有一条红边，不妨设15,为红边，则145为红色三角形；否则，156为蓝色三角形。由以上对各种情况的讨率知，对6K的任意红、蓝两边着色均有两个同色三角形。命题1.3.3对10个顶点的完全图10K任意进行红、蓝两边着色，都或者有一红色4K，或者有一蓝色3K。证明设a是10K的一个顶点，与a相关联的9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有6条红边，要么有4条蓝边。类似于前面两个命题的分析证明过程可以得出结论，具体分析过程见图1.3.6。3/7命题1.3.4对9个顶点的完全图9K任意进行红、蓝两边着色，都或者有一个红色4K，或者有一蓝色3K。证明在9K中，如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以9K中应有594522条边，它不是整数，所以不成立。故必有一个顶点关联的红边数不为5，设此顶点为a，则与a关联的红边数至少为6或至多为4。1.3.2Ramsey数从1..3.1小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数a与b，如果存在最小的正整数(,)rab，使得当(,)Nrab时，对NK中均有红色aK或蓝色bK，则(,)rab称为Ramsey数。由命题1.3.1知(3,3)6r；在5K中按图1.3.7的方式进行红、蓝两边着色（实线为红边，虚线为蓝边），则既无红色3K也无蓝色3K，所以(3,3)5r。从而得知(3,3)6r。由命题1.3.4(4,3)9r；在8K中按图1.3.8的方式进行红、蓝两边着色，则既无红色4K也无蓝色3K，所以(4,3)8r。从而得知(4,3)9rRamsey于1930年证明了对于任给的整数a和b，Ramsey数(,)rab的存在性。但是，Ramsey数的确定却是一个非常难的问题，以至于至今(5,5)r尚不为世人所知。表1.3.1中列出了目前所知的一些Ramsey数。4/7易证（留作习题）（1）(,)(,);rabrba（1.3.1）（2）(,2)raa（1.3.2）定理1.3.1对任意的正整数3,3ab，有,1,,1rabrabrab证明令1,,1Nrabrab，对NK任意进行红、蓝两边着色。设x是NK的一个顶点，在NK中与x相关联的边共有1,,11rabrab条，这些边要么为红色，要么为蓝色。由鸽巢原理知，与x相关联的这些边中，要么至少有1,rab条红边，要么至少有,1rab条蓝边。（1）这些边中有1,rab条红边。在以这些红边与x相关联的1,rab个顶点构成的完全图1,rabK中，必有一个红色1aK或有一个蓝色bK，若有红色1aK，则该红色1aK加上顶点x以及x与1aK之间的红边，即构成一个红色aK；否则，就有一个蓝色bK。（2）这些边中有1,rab条蓝边。在以这些蓝边与x相关联的,1rab个顶点构成的完全图,1rabK中，必有一个红色aK或有一个蓝色1bK。若有一个蓝色1bK，则该1bK加上顶点x以及x与1bK之间的蓝边，即构成一个蓝色bK；否则，就有一个红色aK。综合（1）和（2），知,rabN。由定理1.3.1及等式（1.3.2）容易归纳出对于任意的正整数a和,(,)brab的存在性。关于(,)rab还有定理1.3.2所述的不等式成立。定理1.3.2对任意的正整数2,2ab，有22!,11!1!ababrabaab证明对ab作归纳。5/7当5ab时，2a或2b，由等式（1.3.2）知定理成立。假设对一切满足5abmn的,ab定理成立，由定理1.3.1及归纳假设，有,,11,331221rmnrmnrmnmnmnmmmnm所以，对于任意的正事业2,2ab，定理的结论成立。1.4Ramsey数的推广将1.3节中的红、蓝两色推广到任意k种颜色，对N个顶点的完全图NK用12,,,kccc共k种颜色任意进行k边着色，它或者出现1c颜色的1aK，或者出现2c颜色的2aK，……，或者出现kc颜色的kaK。满足上述性质的N的最小值记为12,,kraaa。定理1.4.1对任意的正整数12,,kaaa，有1212,,,,kkraaararaa证明留作习题类似于定理1.3.1和定理1.3.2，有如下的结论：定理1.4.2对任意的正整数122,2,2kaaa，有12121212,,1,,1,,,12kkkkraaaraaaraaaraaan证明类似于定理1.3.1的证明。定理1.4.3对任意的正整数12,,kaaa，有121212!1,1,1!!!kkkaaaraaaaaa证明类似于定理1.3.2的证明。利用广义Ramsey数，我们来讨论一类集合划分问题。考试集合1,2,,13的一个划分1,4,10,13,2,3,11,12,5,6,7,8,9可以看出，在上面的划分的每一块中，都不存在三个数,,xyz（不一定不同）满足方程xyz（1.4.1然而，无论如何将集合1,2,,14划分成三个子集合，总有一个子集合中有三个数满足方程（1.4.1）。6/7Schur于1916年证明了对任意的正整数n，都存在一个整数nf，使得无论如何将集合1,2,nf划分成n个子集合，总有一个子集合中有三个数满足方程（1.4.1）。下面，我们用Ramsey数来证明这个结论。定理1.4.4设12,,nSSS是集合1,2,,nr的任一划分，即11,2,,nnir，且(,1,)ijSSijijn，则对某一个,iiS中有三个数,,xyz（不一定不同），满足方程xyz。其中3,3,,3nnrr证明将完全图nrK中的nr个顶点分别用1,2,,nr来标记，对nrK的边进行n着色如下：设,u是nrK的任意两个项点，若juS，则将边u染成第j种颜色。由广义Ramsey数nr的定义知一定存在同色三角形，即有三个项,,abc，使得边,,abbcca有相同的颜色，设为第i种颜色。另不妨设abc，则有,,iabbcacS，令,,xabybczac，则有,,ixyzS，且xyz。设nS是满足下述性质的最小整数：将1,2,nS任意划分成n个子集合，总有一个子集合中含有三个数,,xyz，满足方程（1.4.1）。容易证明1232,5,14sss（见本章习题24）。在本章的习题中，还列有一些关于nr和ns的上、下界的结论。将前面的鸽巢原理和Ramsey数进一步推广，可以得到下面更一般的Ramsey定理：定理1.4.5（Ramsey定理）设12,,nqqq，t是正整数，且(1)iqtin，则必存在最小的正整数12,,;nNqqqt，使得当12,,;nmNqqqt时，设S是一集合且Sm，将S的所有t元子集任意分放到n个盒子里，那么要么有S中的1q个元素，它的所有t元子集全在第二个盒子里；……；要么有S中的nq个元素，它的所有t元子集全在第n个盒子里。证明略。当1t时，Ramsey定理说明12(,,;1)nNqqq存在，使得对任何12,,;1nmNqqq，把m个物体放入n个盒子里，或者有1q个物体都在第一个盒子里，或者有2q个物体都在第二个盒子里，……，或者有nq个物体都在第n个盒子里。从1.2节中鸽巢原理的加强形式知1222,,;11nnNqqqqqqn当2t时，可以设想S是一完全图的顶点集合，n个盒子可以设想成n种颜色12,,nccc，S的2元子集就7/7是图中连接两个顶点的边。此时，Ramsey定理中的1212,,;2,,nnNqqqrqqq特别地，当2n时，由1.3节中的结论知(3,3;2)(3,3)6(3,4;2)(3,4)9NrNr定理1.4.61122(,;),(,;)NqttqNtqtq证明若S中元素少于或等于11q个，则将S的所有t元子集全部放入第一个盒子里。这里，没有S的1q元子集，它的所有t元子集全在第一个盒子里；第二个盒子为空，也没有t元子集在第二个盒子里。故11(,;)Nqttq若S中恰有1q个元素，把S的t元子集分放到两个盒子中。若第二个盒子非空，即盒中至少存在一个t元子集，该t元子集的t元子集在第二个盒子中；若第二个盒子为空，则S的所有t元子集全在第一个盒子里，且1Sq，无论哪种情况，均满足要求，故11(,;)Nqttq。综合以上分析，知11(,;)Nqttq同理可证22(,;)Ntqtq