第三节Ransey问题与Ransey数

§1.3Ramsey问题与Ramsey数《组合数学》－Chapter1Contents一、Ramsey问题——完全图的染色问题二、Ramsey数一、Ramsey问题——完全图的染色问题著名的Ramsey问题：问题1:

1958年6～7月号美国《数学月刊》上登载着这样一个有趣的问题：“任何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元集合,当n≥6时,把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个顶点,由引理其中必有一点不妨设为，从这一点引出的8条线段中,蓝色线段或多于3条，或少于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元集合,当n≥9时,把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元集合,当n≥18时,把S的所有2元子集放入两个盒子,则或者有4个元素其所有2元子集全在第一个盒子里，或者有4个元素其所有2元子集全在第二个盒子里．当n=?时,对完全图Kn的边任涂红、蓝两色,则必存在一个红色的K5,或者存在一个蓝色的K5

.目前已证得43≤n≤49.当n=?时,对完全图Kn的边任涂红、蓝两色,则必存在一个红色的K6,或者存在一个蓝色的K6

.目前已证得102≤n≤165.二、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),当n≥N(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+垦b≤5时，取有a=2或b=2冠,由性脑质1结论山成立.假设渡对一柱切满舌足5≤a+先b<m+跟n的a,丢b都成宿立，再下面勇证明a+孝b=m+裕n时结并论也挡成立.由归浩纳假主设有由归涂纳法离，结观论成俭立.世界彻各国诸的数非学竞惯赛经银常出摔现与Ra筒ms园ey问题通有关池的题剧目.例1（波交兰）虎平面宅上有6个点甲，任弹何3点都仍是一买个不绣等边源三角忠形的景顶点痒，则叼这些吵三角堂形中贼，有误一个脑三角岸形的少最长稳边是四另一海个三兴角形侦的最夸短边.证明赵：以塑平面狡上这6个点圾构作结完全扬图K6,并按射如下货方式订用红确、蓝睛二色低对K6的边浪着色载：对K6的每歇个三嫌角形缠的最忠短边巴都涂药上红播色，撑剩余虽的边蛋再涂羊上蓝号色.由定经理1，此K6中必旬有同隙色的到三角构形.由于皂该三城角形袖的最私短边为红段色,因此邮这个糊同色策的三死角形求是红桃色的缝三角谊形.而这犁个三吐角形的腿最长码边为拴红色,按涂娇色方拌法知,必是尸另一根个三南角形篇的最败短边.所以,有一版个三涛角形害的最管长边斩是另麻一个串三角林形的蠢最短满边.19贫64年第彻六届郊国际污数学两奥林敌匹克般数学誓竟赛掏有这体样一肆道试蚁题：有17名学杂生互点相通镇信讨讽论3个问灶题，强但每研对学呜生间叨仅讨无论其晚中一剖个问藏题，绵证明洞至少道有3名学镰生间愁彼此呀讨论愿的是受同一熄个问贱题.这个涛问题记是前澡面Ra忧ms除ey问题1问题2的推伸广，劣把它梅转化奇为图婶的染菠色问牧题，屿可得愚到下衔面定模理：定理4对17阶完竭全图K17的边块任涂跟红、甲蓝、藏黄三址色，休则必暴存在弄一个饰同色何的三零角形.证明设是K17的17个顶点，现考察K17中从v0出发虹的16条线述段,当对疏它们截涂于报红、比蓝、府黄三衡色时,由鸽肺巢原庸理知抹至少谱有6条边