下载文档原格式
第二节：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）若123456,,,,,υυυυυυ中有一红边，不妨设14,υυ为红边，此时若边2434,υυυυ中有一条红边，不妨设34υυ是红边，则134υυυ∆是一红色三角形，见图1.3.3。
以下就2434,υυυυ均为蓝边的情况对与4υ相关联的边的颜色进行讨论：（i ）若4546,υυυυ中有一蓝边，不妨设45,υυ为蓝边，如图1.3.4所示。
Ramsey型问题及其应用【关键词】ramsey型问题；ramsey数；竞赛数学；通信1 ramsey型问题及相关背景ramsey理论起始于20世纪20年代末，30年代初，最初由英国数学家f.p.ramsey提出，其思想已日益被人们理解、接受并得到了一定的发展。
对于ramsey数的研究，以取得初步成果。
下面就介绍一下关于ramsey的理论知识及其性质定理以及ramsey型问题在数学竟赛和通信方面中的应用。
2 ramsey型问题的基本定理与性质2.1 ramsey定理对任意给定的自然数及都存在时，对的所有元集的任一种染色（每一个元集染上种颜色中的一种），必有一个有一个元子集，它的所有元集是同一种颜色的。
2.2 若干推论对ramsey型问题有以下结论：2.2.1 对6个顶点的完全图的边用红蓝二色任意着色，结果至少有两个同色的三角形。
2.2.2 10个人中若不是3个人互不相识，则必有4个人互相认识。
同样10个人中若不是3个人互相认识，则必有4个人互不相识。
其实此结论只要有9个人就够了。
问题相当于9个顶点的完全图用红，蓝二色任意着色，必然是红色三角形和蓝色的完全四边形两者必有其一。
类似地有红色完全四边形和蓝色边的三角形两者必有其一[2].2.2.3 18个人至少有4个人或互相认识或互相不认识。
这个问题相当于对18个顶点的完全图的边用红，蓝二色任意着色，则至少存在一个同色完全四边形[2].以上推论可写成2.3 ramsey数的一些简单性质ramsey数具有一些特殊性质，如下所示：2.3.1 . （对称性）2.3.2 .（个顶点的完全图的边用红蓝两色染色或存在一个个顶点着红（蓝）色的完全图，或至少存在一条着蓝（红）色的边）。
2.3.3 对任意正整数存在2.3.4 对任意正整数，有.推论：对所有整数和，若和是偶数，则. （详见参考文献[1]）。
2.3.5 对于有.3 ramsey数的推广定理3.1 对任意的正整数有定理3.2 对任意的正整数有。
组合数学讲义(内部资料，严禁商用) 第二章 鸽巢原理和Ramsey 定理 2008-2009学年第二学期第二章 鸽巢原理和Ramsey 定理一、鸽巢原理鸽巢原理是组合数学中的一个重要而又基本的原理，它可以用来解决很多日常生活和科学技术上的趣题，并且常能得到一些令人惊异的结果。
这个原理有各种称呼，最常用的名称是鸽巢原理、Dirichlet 抽屉原理和鞋盒原理。
1、问题的引入1) 366个人中必然有至少两个人生日相同。
2) 抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只是成双的。
3) 某次会议有n 位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的人数是一样的。
4) 任给5个不同的整数，其中至少有3个数的和被3除尽。
这些例子的道理都很简单，以第一个例子为例，一年365天，366个人至少有一天是某两个人的生日。
最后一例子也有类似的道理，5个数中至少有3个同为奇数或同为偶数，无论哪种情况，它们的和都能被3除尽。
2、鸽巢原理的简单形式定理1、如果把1+n 只鸽子放入n 个鸽巢，则至少有一个鸽巢里含有两只或两只以上鸽子。
证明：反证法。
假设每个鸽巢里至多包含一只鸽子，则n 个鸽巢里鸽子的总数小于等于n ，这与已知矛盾。
注：此原理不能用来寻找究竟是那个鸽巢里含有两只或两只以上鸽子。
即此原理只能用来断定这种鸽巢的存在，并未指出怎样构造这种安排或怎样寻找出现这种现象的场合，除非检查所有的可能情况。
此原理的应用：例1、 已知每个人的头发根数都小于20万，对20万人以上的城市就可以断定，至少有两个人头发根数相等。
例2、在边长为1的正三角形中任意放5个点，证明至少有两个点之间的距离不大于21。
证明：构造鸽巢原理如图1,将5个点放在4个边长为21的小正三角形内，根据鸽巢原理，组合数学讲义(涉外学院数学本科用) 2008-2009学年第二学期 制作人 陈勇 必有一个小三角形内至少有两个点，这两个点的距离就小于或等于21。
摘 要Ramsey 理论在组合数学中有着重要的地位，1930年以来其研究对象Ramsey 数更是被大量学者广泛研究。
但是，目前已知的经典Ramsey 数精确值任然很少，由于其计算量巨大，任何进一步的计算都是很困难的。
因此，目前对于广义Ramsey 数及其它相关理论的研究更为广泛。
本文借助计算机针对目前一些未知的广义Ramsey 数精确值进行了计算，同时还研究了平面Ramsey 数的计算问题以及极值图论2,3(,)ex n K 的计算问题。
以下是本文的主要研究工作：第二章中对Gluing 算法进行了改进和实现，提高了计算速度。
借助实现的Gluing 算法我们计算得到了11),(6,24,1=K K R ，13),(7,24,1=K K R ，13),(5,34,1=K K R ，15),(5,35,1=K K R ，17),(4,34,2=K K R 。
另外，在提高了圈图判断速度的基础上计算出了6(,)n R C B 当610n ≤≤的精确值及17),(49=B C R ，5(,)21m R C B m =−其中811m ≤≤。
最后，还计算得到44(,)18R K W =，45(,)17R K W =。
第三章中对平面判定算法进行了研究，并结合第二章中的Ramsey 数计算算法，计算得到了一些平面Ramsey 数4(,)n PR K B 其中(35)n ≤≤，44(,)PR K W ，45(,)PR K W 以及6(,)n PR C B 当(610)n ≤≤的精确值。
第四章中对极值图论2,3(,)ex n K 的上下界及准确值的计算问题进行了研究，并将第二章中的图构造算法进行改进应用到2,3(,)ex n K 的计算及图构造中，借助计算机辅助计算得到了2,3(,)ex n K 当(012)n ≤≤的准确值，以及2,3(,)ex n K 当(1232)n ≤≤的上下界。
关键词：图，Ramsey 数，Gluing 算法，平面图，极值图论，2,3(,)ex n KAbstractRamsey theory has an important role in combinatorics mathematics,and its main research subject Ramsey number has been widely studied by researchers since 1930. Until now,the known exact values of classical Ramsey numbers are very few. Because of its huge computation, any further calculations are very difficult. Therefore,the generalized Ramsey numbers and some other related theory are more widely studied.With the help of the computers some unknown exact values of generalized Ramsey numbers,planar Ramsey numbers and Turán number 2,3(,)ex n K are calculated.The main work of this thesis are follows.In chapter 2, Gluing algorithm are modified and implemented, time-consuming arereduced.1,42,6(,)11R K K =,1,42,7(,)13R K K =,13),(5,34,1=K K R , 15),(5,35,1=K K R , 17),(4,34,2=K K R are obtained with the help of the Gluing algorithm. In addition, the determination speed of cycle graph are reduced, and the exact values of 6(,)n R C B (610)n ≤≤, 17),(49=B C R , 5(,)m R C B =2m 1−(811)m ≤≤, 44(,)18R K W =, 45(,)17R K W = are obtained.In chapter 3,the Planar Graph Testing algorithms are studied.With the help of the algorithm implemented in chapter2, the exact values of planar Ramsey numbers 4(,)(35)n PR K B n ≤≤,44(,)PR K W ,45(,)PR K W ,6(,)(610)n PR C B n ≤≤ are obtained.In chapter 4,some exact values and upper bounds,lower bounds of Turán number 2,3(,)ex n K are studied. With the help of the “geng” program and some programs in chapter 2, exact values of 2,3(,)(012)ex n K n ≤≤ and upper and lower bounds of 2,3(,)(1232)ex n K n ≤≤ are obtained.Key words: Graph, Ramsey number, Gluing algorithm, Planar Graph, Extremal GraphTheory, 2,3(,)ex n K独创性声明本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。
边ramsey数概念全文共四篇示例，供读者参考第一篇示例：兰姆齐数（Ramsey Numbers），是图论中的一个概念，用于描述在一定条件下，图中能够出现的特定结构的最小规模。
这个概念的提出者是英国数学家Frank Plumpton Ramsey，因此得名为Ramsey。
Ramsey数理论在1930年代发展起来，被用于描述图中特定结构的存在性问题。
简单来说，Ramsey数描述了在一个完全图中，当节点数量充足时，一定存在一种特定的结构出现。
这个特定的结构可以是一个完全互连的子图，也可以是一个分割成两部分的特定类型的图。
Ramsey数的定义相对简单，但是要确定具体的数值却是一个非常困难的问题。
因为Ramsey数是一个极限值，其数值通常很大，而且随着图的规模增大，计算其确切数值的复杂度也会快速增加。
在图论中，Ramsey数是一个非常重要的概念，许多图的问题都可以通过Ramsey数来描述和解决。
在计算机网络中，Ramsey数可以描述网络中互相关联的节点之间的通信规律；在社会科学中，Ramsey数可以描述人际关系网中的某种特定模式的存在性；在金融学中，Ramsey数可以描述市场中某种特定的价格波动规律等等。
Ramsey数的研究不仅仅局限于数学领域，它的应用范围非常广泛，涉及到科学、工程、经济等多个领域。
许多著名的数学家都曾经对Ramsey数进行过深入的探讨和研究，提出了各种各样的定理和推论。
Ramsey数的计算方法有很多种，其中比较著名的有暴力搜索法、回溯法、分支界限法等。
虽然计算Ramsey数的方法很多，但是要得到准确的结果并不容易，需要耗费大量的时间和精力。
Ramsey数是图论中一个非常重要的概念，它的研究对于理解和解决图中的结构性问题非常有帮助。
随着科学技术的不断发展，Ramsey 数的研究也在不断深入和拓展，将会有更多新的发现和应用出现。
第二篇示例：拉姆齐数概念源于英国数学家拉姆齐（Frank Plumpton Ramsey）的研究，他是20世纪最杰出的逻辑学家和数学家之一。
第二节：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）若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。
命题1.3.4 对9个顶点的完全图9K 任意进行红、蓝两边着色，都或者有一个红色4K ，或者有一蓝色3K 。
证明 在9K 中，如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以9K 中应有594522⨯=条边，它不是整数，所以不成立。
故必有一个顶点关联的红边数不为5，设此顶点为a ，则与a 关联的红边数至少为6或至多为4。
1.3.2 Ramsey 数从1..3.1小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数a 与b ，如果存在最小的正整数(,)r a b ，使得当(,)N r a b ≥时，对N K 中均有红色a K 或蓝色b K ，则(,)r a b 称为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 数(,)r a b 的存在性。
但是，Ramsey 数的确定却是一个非常难的问题，以至于至今(5,5)r 尚不为世人所知。
表1.3.1中列出了目前所知的一些Ramsey 数。
易证（留作习题） （1）(,)(,);r a b r b a = （1.3.1） （2）(,2)r a a =（1.3.2）定理1.3.1 对任意的正整数3,3a b ≥≥，有()()(),1,,1r a b r a b r a b ≤-+-证明 令()()1,,1N r a b r a b =-+-，对N K 任意进行红、蓝两边着色。
设x 是N K 的一个顶点，在N K 中与x 相关联的边共有()()1,,11r a b r a b -+--条，这些边要么为红色，要么为蓝色。
由鸽巢原理知，与x 相关联的这些边中，要么至少有()1,r a b -条红边，要么至少有(),1r a b -条蓝边。
（1）这些边中有()1,r a b -条红边。
在以这些红边与x 相关联的()1,r a b -个顶点构成的完全图()1,r a b K -中，必有一个红色1a K -或有一个蓝色b K ，若有红色1a K -，则该红色1a K -加上顶点x 以及x 与1a K -之间的红边，即构成一个红色a K ；否则，就有一个蓝色b K 。
（2）这些边中有()1,r a b -条蓝边。
在以这些蓝边与x 相关联的(),1r a b -个顶点构成的完全图(),1r a b K -中，必有一个红色a K 或有一个蓝色1b K -。
若有一个蓝色1b K -，则该1b K -加上顶点x 以及x 与1b K -之间的蓝边，即构成一个蓝色b K ；否则，就有一个红色a K 。
综合（1）和（2），知(),r a b N ≤。
由定理1.3.1及等式（1.3.2）容易归纳出对于任意的正整数a 和,(,)b r a b 的存在性。
关于(,)r a b 还有定理1.3.2所述的不等式成立。
定理1.3.2 对任意的正整数2,2a b ≥≥，有()()()()22!,11!1!a b a b r a b a a b +-+-⎛⎫≤=⎪---⎝⎭证明 对a b +作归纳。
当5a b +≤时，2a =或2b =，由等式（1.3.2）知定理成立。
假设对一切满足5a b m n ≤+<+的,a b 定理成立，由定理1.3.1及归纳假设，有()()(),,11,331221r m n r m n r m n m n m n m m m n m ≤-+-+-+-⎛⎫⎛⎫≤+ ⎪ ⎪--⎝⎭⎝⎭+-⎛⎫= ⎪-⎝⎭所以，对于任意的正事业2,2a b ≥≥，定理的结论成立。
1.4 Ramsey 数的推广将1.3节中的红、蓝两色推广到任意k 种颜色，对N 个顶点的完全图N K 用12,,,k c c c L 共k 种颜色任意进行k 边着色，它或者出现1c 颜色的1a K ，或者出现2c 颜色的2a K ，……，或者出现k c 颜色的k a K 。
满足上述性质的N 的最小值记为()12,,k r a a a L 。
定理1.4.1 对任意的正整数12,,k a a a L ，有()()()1212,,,,k k r a a a r a r a a ≤L L证明 留作习题类似于定理1.3.1和定理1.3.2，有如下的结论： 定理1.4.2 对任意的正整数122,2,2k a a a ≥≥≥L ，有()()()()12121212,,1,,1,,,12k k k k r a a a r a a a r a a a r a a a n ≤-+-++--+L L L L L证明 类似于定理1.3.1的证明。
定理1.4.3 对任意的正整数12,,k a a a L ，有()()121212!1,1,1!!!k k k a a a r a a a a a a ++++++≤LL L证明 类似于定理1.3.2的证明。
利用广义Ramsey 数，我们来讨论一类集合划分问题。
考试集合{}1,2,,13L 的一个划分{}{}{}{}1,4,10,13,2,3,11,12,5,6,7,8,9可以看出，在上面的划分的每一块中，都不存在三个数,,x y z （不一定不同）满足方程x y z +=（1.4.1然而，无论如何将集合{}1,2,,14L 划分成三个子集合，总有一个子集合中有三个数满足方程（1.4.1）。
Schur于1916年证明了对任意的正整数n ，都存在一个整数n f ，使得无论如何将集合{}1,2,n f L 划分成n 个子集合，总有一个子集合中有三个数满足方程（1.4.1）。
下面，我们用Ramsey 数来证明这个结论。
定理 1.4.4 设{}12,,n S S S L 是集合{}1,2,,n r L 的任一划分，即{}11,2,,nni r =L U ，且(,1,)i j S S i j i j n φ=≠≤≤I ，则对某一个,i i S 中有三个数,,x y z （不一定不同），满足方程x y z +=。
其中()3,3,,3n nr r =L 14243证明 将完全图n r K 中的n r 个顶点分别用1,2,,n r L 来标记，对n r K 的边进行n 着色如下：设,u υ是n r K 的任意两个项点，若j u S υ-∈，则将边u υ染成第j 种颜色。
由广义Ramsey 数n r 的定义知一定存在同色三角形，即有三个项,,a b c ，使得边,,ab bc ca 有相同的颜色，设为第i 种颜色。
另不妨设a b c >>，则有,,i a b b c a c S ---∈，令,,x a b y b c z a c =-=-=-，则有,,i x y z S ∈，且x y z +=。
设n S 是满足下述性质的最小整数：将{}1,2,n S L 任意划分成n 个子集合，总有一个子集合中含有三个数,,x y z ，满足方程（1.4.1）。
容易证明1232,5,14s s s ===（见本章习题24）。
在本章的习题中，还列有一些关于n r 和n s 的上、下界的结论。
将前面的鸽巢原理和Ramsey 数进一步推广，可以得到下面更一般的Ramsey 定理：定理 1.4.5（Ramsey 定理） 设12,,n q q q L ，t 是正整数，且(1)i q t i n ≥≤≤，则必存在最小的正整数()12,,;n N q q q t L ，使得当()12,,;n m N q q q t ≥L 时，设S 是一集合且S m =，将S 的所有t 元子集任意分放到n 个盒子里，那么要么有S 中的1q 个元素，它的所有t 元子集全在第二个盒子里；……；要么有S 中的n q 个元素，它的所有t 元子集全在第n 个盒子里。
