第3节Ransey问题与Ransey数.pptVIP

§1.3 Ramsey问题与Ramsey数;Contents;一、Ramsey问题——完全图的染色问题; 定理1 对6阶完全图K6的边任意涂红、蓝两色, 则必存在一个红色三角形或一个蓝色三角形.; 显然, 当 时,把K6换成 Kn定理的结论显然仍成立. 但当n=5时,定理的结论就不一定成立了.例如对下图所示的 实边涂红色, 虚边涂蓝色, 既无红色的三角形，也无蓝色的三角形． ; 定理2 对9阶完全图K9的边任意涂红、蓝两色，则必存在一个红色(蓝色)的K4 ,或者必存在一个蓝色(红色)的K3.;两个端点, 故应有2m条． ;(2) 从v0引出的8条线段中,蓝色线段少于3条，即至多有2条． ; 显然, 当 时,把K9换成 Kn定理的结论显然仍成立. 但当n=8时,定理的结论就不一定成立了.例如对下图所示的 实边涂红色, 虚边涂蓝色, 既无红色的完全四边形，也无蓝色的三角形． ;Ramsey问题2为下面的定理3.; 显然, 当 时,把K18换成 Kn定理的结论显然仍成立. 但当n=17时,定理的结论就不一定成立了.;定理3 我们还可叙述为：;二、Ramsey数; Ramsey于1928年已经证明了对于任给的整数a和b, Ramsey数 的存在性. 但是Ramsey数的确定却是一个非常难的问题, 以致于至今知道的还极少. ;性质2 对任意的正整数 , 有; 性质3 对任意的正整数 ,当 都为偶数时,有;因为否则从每一顶点引出的红色边都是2m-1条, 这时从t个顶点引出的红色边将共(2m-1) (2m+2l-1)有条. 由于其中每条边有两个端点都被计算了两次, 假设kt中有h条红色边,于是便有; 我们考察由2m条红色边所有异于v0的端点构成的完全图K2m . 因为 , 所以K2m中必定存在红色的Ka-1，或存在蓝色的Kb ,若为后者结论成立,若为前者, 则红色的Ka-1连同v0一起便构成了红色的Ka ,结论也成立。;性质4 对任意的正整数 , 有;世界各国的数学竞赛经常出现与Ramsey问题有关的题目. ;1964年第六届国际数学奥林匹克数学竟赛有这样一道试题：;证明 设 是K17的17个顶点，现考察K17中;定理4 我们还可叙述为：;作业：