Ransey问题与Ransey数.pptVIP

1.3Ramsey问题与Ramsey数,组合数学Chapter1,Contents,一、Ramsey问题完全图的染色问题,二、Ramsey数,一、Ramsey问题完全图的染色问题,著名的Ramsey问题：,问题1:1958年67月号美国数学月刊上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3人互相认识或互相不认识.”,问题2:1959年美国数学月刊第2期又进一步提出：“任何18个人的聚会，其中总会有4人互相认识或互相不认识.”,转化为完全图的染色问题来解决.,定义有n个顶点且每两个顶点都有一条边的简单图称为n阶完全图，记为Kn.,于是,Ramsey问题1为下面的定理1.,定理1对6阶完全图K6的边任意涂红、蓝两色,则必存在一个红色三角形或一个蓝色三角形.,证明设是K6的6个顶点,所连的5条边着红色或蓝色，由鸽巢原理知，其中至少有3条边同色.,不妨设所连的3条边均为红色,如图所示,若间有一条红边,不妨设为，,则是一红色三角形.,否则，,间均为蓝边,即是一蓝色三角形.,显然,当时,把K6换成Kn定理的结论显然仍成立.但当n=5时,定理的结论就不一定成立了.例如对下图所示的实边涂红色,虚边涂蓝色,既无红色的三角形，也无蓝色的三角形,所以,6为结论成立的最小数.,这个最小数称为Ramsey数,记为N(3,3;2)，即N(3,3;2)=6.,定理1我们还可叙述为：,S为n元集合,当n6时,把S的所有2元子集放入两个盒子,则或者有3个元素其所有2元子集全在第一个盒子里，或者有3个元素其所有2元子集全在第二个盒子里,定理2对9阶完全图K9的边任意涂红、蓝两色，则必存在一个红色(蓝色)的K4,或者必存在一个蓝色(红色)的K3.,为了证明定理2先证下面的引理,引理对9阶完全图K9的边任意涂红、蓝两色,则必存在一个顶点,从这点引出的8条线段中,红色（蓝色）线段或多于3条或少于3条,证明用反证法,如果不存在这样的顶点,即从每一顶点发出的线段中,红色（蓝色）线段都是三条.现在对9个顶点逐点统计由它们发出的红色（蓝色）线段的条数,应为27条,另一方面，若设,K9中实有红色（蓝色）线段总数为m条,现对这m条边的端点逐点统计由它们发出的红色线段的条数，,由于每条线段有,两个端点,故应有2m条,由此得出2m=27这是不可能的,故引理得证,证明定理2:,设是构成K9的9个顶点,由引理其中必有一点,或少于3条.对这两种情况分别讨论如下：,(1)从v0引出的8条线段中,蓝色线段多于3条,即至少有4条，,不妨设为蓝色线段,点所构成的完全图K4，,若这个K4中没有一条线段是蓝色的,则,这个K4就是一个红色的完全四边形.若这个K4至少有一条蓝边,则它的两个端点连同v0便构成一个蓝色三角形；,即结论成立,定理2对9阶完全图K9的边任意涂红、蓝两色，则必存在一个红色(蓝色)的K4,或者必存在一个蓝色(红色)的K3.,(2)从v0引出的8条线段中,蓝色线段少于3条，即至多有2条,这时,从v0引出的红色线段就会至少有6条，不妨设为,再看由这6个点构成的K6，,由定理1可知,这个K6必有一个同色三角形.,若是红色的,则这个红色三角形,的顶点连同v0一起便构成一个红色的完全四边形K4.,即结论成立,综合以上两种情况，定理2得证,若是蓝色的,这个三角形即为蓝色的K3.,显然,当时,把K9换成Kn定理的结论显然仍成立.但当n=8时,定理的结论就不一定成立了.例如对下图所示的实边涂红色,虚边涂蓝色,既无红色的完全四边形，也无蓝色的三角形,所以,9为结论成立的最小数.,这个最小数称为Ramsey数,记为N(3,4;2)，即N(3,4;2)=9.,定理2我们还可叙述为：,S为n元集合,当n9时,把S的所有2元子集放入两个盒子,则或者有3个元素其所有2元子集全在第一个盒子里，或者有4个元素其所有2元子集全在第二个盒子里,Ramsey问题2为下面的定理3.,定理3对18阶完全图K18的边任涂红、蓝两色,则必存在一个红色的K4,或者存在一个蓝色的K4.,证明设是K18的18个顶点，现考察K18中,从v0出发的17条线段,它们分成了红、蓝两类,由鸽巢原理知,至少有9条是同色的，,不妨设它们是红色.,考察这9条红色线段,异于v0的9个端点所构成的K9，,由定理2知K9中必存在一个红色,三角形K3,或一个蓝色完全四边形K4.,若是后者，则命题得证；,若是前者,则这个红色三角形的三个顶点和v0便构成一个红色的完全四边形.,所以,定理成立.,显然,当时,把K18换成Kn定理的结论显然仍成立.但当n=17时,定理的结论就不一定成立了.,例如把K17的17个顶点记为,在把数字1,2,16分为A,B两组,按以下规则对K17的边进行涂色：,涂红色；,涂蓝色；,这样涂得的K17即不存在红色K4的也不存在蓝色的K4,所以n=18是定理结论成立的最小数.这个数记为,这个数记为,定理3我们还可叙述为：,S为n元集合,当n18时,把S的所有2元子集放入两个盒子,则或者有4个元素其所有2元子集全在第一个盒子里，或者有4个元素其所有2元子集全在第二个盒子里,当n=?时,对完全图Kn的边任涂红、蓝两色,则必存在一个红色的K5,或者存在一个蓝色的K5.,目前已证得43n49.,当n=?时,对完全图Kn的边任涂红、蓝两色,则必存在一个红色的K6,或者存在一个蓝色的K6.,目前已证得102n165.,二、Ramsey数,关于完全图的两种颜色的染色问题，可归纳出如下的一般情况：,对于任意给定的两个正整数a和b，存在最小的正整数N(a,b;2),使得当,对Km的边任意涂于红、,蓝两色,Km中必存在红色的Ka或蓝色Kb.,我们把N(a,b;2)称为Ramsey数.简记为r(a,b).,由上面的定理可知:,S为n元集合,对于任意给定的两个正整数a和b，存在最小的正整数N(a,b;2),当nN(a,b;2)时,把S的所有2元子集放入两个盒子,则或者有a个元素其所有2元子集全在第一个盒子里，或者有b个元素其所有2元子集全在第二个盒子里,Ramsey于1928年已经证明了对于任给的整数a和b,Ramsey数的存在性.但是Ramsey数的确定却是一个非常难的问题,以致于至今知道的还极少.,(见P17表.),虽然难以确定，但关于它具有以下的一些性质,性质1为Ramsey数，则有,性质2对任意的正整数,有,证明令下面只要证明对KN的边任着红、蓝两色，必存在红色的Ka或蓝色的Kb.设x为KN的一个顶点，与x关联的边有N-1条，对这些边任意着红、蓝两色,由鸽巢原理,性质2对任意的正整数,有,1.若至少有r(a-1,b)条红边.这些红边与x相关联的顶点有r(a-1,b)个,在这些顶点构成的完全图中,必有一个红色,的Ka-1或一个蓝色的Kb.,若为红色的Ka-1,则该红色的Ka-1加上,顶点x及x与Ka-1之间的红边,即构成一个红色的Ka;否则，就有一个蓝色的Kb.,2.若至少有r(a,b-1)条蓝边.这些蓝边与x相关联的顶点有,r(a,b-1)个,在这些顶点构成的完全图中,必有一个红色,的Ka或蓝色的Kb-1.,若为前者结论成立,若为后者,则该蓝色的,的Kb-1加上顶点x及关联的蓝边即构成一个蓝色的Kb.,所以有,性质3对任意的正整数,当都为偶数时,有,证明,考虑由t个点所构成的完全图Kt，将它的边涂以红、蓝两色,我们证明必定存在红色（蓝色）的Ka或存在蓝色（红色）Kb,为此,我们从t个点中选取一个点v0,它与其余t-1个点所连成的t-1条边中，一定出现有多于2m-1条红色边，或少于2m-1条红色边,因为否则从每一顶点引出的红色边都是2m-1条,这时从t个顶点引出的红色边将共(2m-1)(2m+2l-1)有条.由于其中每条边有两个端点都被计算了两次,假设kt中有h条红色边,于是便有,产生矛盾，所以从v0引出的t-1条边中，一定出现有多于2m-1条红色边，或少于2m-1条红色边,对上面的两种情况分别讨论如下：,(1)从v0点引出的t-1条边中红色边多于2m-1条，即至少有2m条,我们考察由2m条红色边所有异于v0的端点构成的完全图K2m.因为,所以K2m中必定存在红色的Ka-1，或存在蓝色的Kb,若为后者结论成立,若为前者,则红色的Ka-1连同v0一起便构成了红色的Ka,结论也成立。,(2)从v0点引出的t-1条边中红色边少于2m-1条，即至多有2m-2条,于是蓝色边至少有2l条，,我们考察由2l条蓝色边所有异于v0的端点构成的完全图K2l因为,所以K2l中必定存在红色的Ka，或存在蓝色的Kb-1,若为前者结论成立,若为后者,则蓝色的Kb-1连同v0一起便构成了蓝色的Kb,结论也成立,所以有,性质4对任意的正整数,有,证明对a+b进行归纳.,当a+b5时，有a=2或b=2,由性质1结论成立.,假设对一切满足5a+bm+n的a,b都成立，下面证明a+b=m+n时结论也成立.,由归纳假设有,由归纳法，结论成立.,世界各国的数学竞赛经常出现与Ramsey问题有关的题目.,例1（波兰）平面上有6个点，任何3点都是一个不等边三角形的顶点，则这些三角形中，有一个三角形的最长边是另一个三角形的最短边.,证明：以平面上这6个点构作完全图K6,并按如下方式用红、蓝二色对K6的边着色：,对K6的每个三角形的最短边都涂上红色，剩余的边再涂上蓝色.,由定理1，此K6中必有同色的三角形.,由于该三角形的最短边,为红色,因此这个同色的三角形是红色的三角形.,而这个三角,形的最长边为红色,按涂色方法知,必是另一个三角形的最短边.,所以,有一个三角形的最长边是另一个三角形的最短边.,1964年第六届国际数学奥林匹克数学竟赛有这样一道试题：,有17名学生互相通信讨论3个问题，但每对学生间仅讨论其中一个问题，证明至少有3名学生间彼此讨论的是同一个问题.,这个问题是前面Ramsey问题1问题2的推广，把它转化为图的染色问题，可得到下面定理：,定理4对17阶完全图K17的边任涂红、蓝、黄三色，则必存在一个同色的三角形.,证明设是K17的17个顶点，现考察K17中,从v0出发的16条线段,当对它们涂于红、蓝、黄三色时,由鸽巢原理知至少有6条边是同色的，,不妨设,是红色边，,再看由这6个点构成的K6，,若这个K6有一条红边，则它的两个端点连同v0便构成一个红色三角形,结论成立；,若这个K6没有一条红边，,则它的边,只能涂于蓝色和黄色，由定理1知它一定会出现一个蓝色的三角形，或一个黄色三角形，结论成立,所以定理得证,而且已经证明