《组合数学》 第五章 抽屉原理和Ramsey理论
5.4 Ramsey数
问题：对于给定的正整数p、q≥2，是否存在一个最小的正整数r，具有下述性质：对完全图Kn的每条边涂以颜色C1或C2，当n≥r时，在Kn中必含有一个完全子图Kp，其所有边涂的是颜色C1（即同色Kp），或含有一个完全子图Kq，其所有边涂的是颜色C2（即同色Kq）。
定义5.4.1 满足上述条件的数r称为Ramsey数，记为r(p,q;2)，简记为r(p, q)。
已经知道r(3,3)＝6，r(3,4)＝9。 例5.4.1 证明r(4,4)＝18。
（证）设v0,v1,v2,?,v17是完全图K18的顶点，现考察K18中从v0出发的17条线段，它们分成了红、蓝两类，由抽屉原理可知：至少有9条是同色的，不妨设它们为红色（蓝色）。进一步再来考察这9条红色（蓝色）线段里，异于v0的9个端点所构成的K9，其中一定会出现一个红色（蓝色）K3，或一个蓝色（红色）K4。若是前者，则这个红色（蓝色）K3的三个顶点和v0一起便构成一个红色（蓝色）K4，若是后者，则本身已存在蓝色（红色）K4。 由此可知，r(4,4)≤18，下面证r(4,4)>17，从而有r(4,4)＝18。
在一个圆周上画出共17个等分点，将其依次编号为v0,v1,?,v16，把整数1，2，?，16分成两组
X组：1，2，4，8，9，13，15，16 Y组：3，5，6，7，10，11，12，14
选取正整数a，b?0?a,b?16?，按以下规则进行涂色： 当a?b?X时，边vavb涂红色（或蓝色）； 当a?b?Y时，边vavb涂蓝色（或红色）
21/37
《组合数学》 第五章 抽屉原理和Ramsey理论
这样涂得的K17不会出现同色的K4。
由上述涂色规则可以看出，两点连线为红色的顶点对有：?v0,v1?，?v0,v2?，?v0,v4?，?v0,v16?，?v1,v3?，?v1,v2?，?，
?v1,v5?，?，?v1,v16?，?，?v15,v16?；连线为蓝色的顶点对有：?v0,v3?，?v0,v5?，?v0,v6?，?，?v0,v14?，?v1,v4?，?v1,v6?，?v1,v7?，?，?v1,v15?，?，?v11,v14?。读者可
以按此方法画出具有两种颜色的边的K17，并观察结果。 §5.4.1 Ramsey数的性质
对于任意的正整数p、q，要求出r(p,q)，是相当困难的。这里只给出Ramsey数的有关性质和上、下界的估计。
定理5.4.1 Ramsey数r(1,q;2)具有以下性质
(1) r(p,q)＝ r(q,p); (2) r(1,q)＝ r(p,1)＝1; （3）r(2,q)＝q, r(p,2)＝p;
（4）当p、q≥2时，有r(p,q)≤r(p,q-1)＋ r(p-1,q)，若r(p,q-1)和 r(p-1,q)都为偶数，不等式严格成立。 （证）（1）、（2）显然成立。
对于Kq，当所有边都涂的是同一种颜色时，Kq本身即满足条件。否则，至少有两点的连线涂的是另一色，那么，该两点构成一个同色的K。所以r(2,q)＝q成立，同理可证r(p,2)＝p也成立。即性质（3）成立。
2至于性质（4），令n＝r(p,q-1)＋r(p-1,q)，可以证明，对Kn的边用红、蓝着色后，其中必存在红色的Kp或蓝色的
Kq，从而可知n≥r(p, q)。原因如下：
任取Kn的一个顶点v，由抽屉原理，v与其余n－1个顶点的连线中，要么红边不少于r(p-1, q)，要么蓝边不少于r(p, q-1)。若是前者，即由v出发与之以红边相连的顶点有r?p?1,q?个，按照r?p?1,q?的定义，这r?p?1,q?个顶
22/37
《组合数学》 第五章 抽屉原理和Ramsey理论
点本身所构成的完全图Kr?p?1,q?即可导出蓝色的Kq或红色的Kp?1，而Kp?1再加上顶点v即可构成红色的Kp。若为
后者，同理由与v以蓝边相连的r(p,q－1)个点再加上顶点v所构成的完全图Kr?p,q?1??1中就存在红色Kp或蓝色Kq。 若r(p,q－1)和 r(p－1,q)都为偶数，令m＝r(p,q－1)＋ r(p－1,q)－1（m为奇数），可以证明在涂过色的K上存在红色的Kp或蓝色的Kq，从而可知r(p,q) ≤m m首先证明：在Km上存在一点vk，以它为端点的红边一定是偶数条。若不然，设cj是以顶点vj为端点的全部红边数 m（j＝1,2,?，m），所有cj为奇数，从而知c?c?cj?1j为奇数， 而Km上的全部红边数＝≠整数，矛盾（注意，按顶点统 2计时，将Km的每条红边都计数两次）。 其次，以前述的vk为端点的m－1＝ r(p,q－1)＋ r(p－1,q)－2条边中，或者至少有r(p－1,q)条红边，或者至少有r(p,q－1)条蓝边。再仿照前边的证明，即得结论。 例5.4.2 证明r(3,5)＝14。 （证）由性质（4）知 r?3,5??r?2,5??r?3,4?=5＋9=14 对于K13，可以给出一种边2染色方案，其中既无红色边组成的K3，又无蓝色边组成的K5。方法是将圆周等分为13等份，视各等分点为K3的顶点，从某点开始对各点依此编号为0，1，?，12，当i与k满足 k?i?1,i?5,i?8,i?12,mod13， ?i?0,1,?,12? 时，第i点与第k点之间连红色线，否则连蓝色线。 23/37 《组合数学》 第五章 抽屉原理和Ramsey理论 定理5.4.2 关于Ramsey数的上、下界，有如下结论： ?1（1）r?p,q??Cp； p?q?2p（2）r?p,p??22，p?2； p????2????2??O?1???r?p,q??t?Cp（3）p22??e?????p????ln?lnp?lnp， t为常数。 ?1（4）r?p,q??q?Cp?， s为常数。 p?q?2s22（5） c1q?lnq?2?r?3,q??c2qlnq， c1、c2为常数。 关于Ramsey数的部分结果，可见表5.4.1。 表5.4.1 p、q较小时的r(p,q) q p 3 4 5 6 7 8 9 10 3 6 4 9 18 5 14 25 42/55 6 18 34/36 57/94 102/169 7 23 41/59 126/586 8 28/29 ?/88 282/? 9 36 10 39/44 ?/124 ?/168 374/? 458/? 注：？表示目前还无结果 §5.4.2 Ramsey数的推广 将染色问题可以推广到一般情形： （1） 增加颜色数：设有n个顶点的平面完全图Kn，用 24/37 《组合数学》 第五章 抽屉原理和Ramsey理论 m种颜色c1,c2,?,cm随意给Kn的边着色。那么，对于给定的正整数p1, p2, ?pm,（pi≥2，i＝1,2, ?,m），是否存在最小的正整数r?p1,p2,?,pm;2?，当n≥r?p1,p2,?,pm;2?时，在Kn中一定含有某个Kpi，它的所有边都为颜色ci 。 （2） 扩大空间的维数：设Kn为k维空间上的具有n个顶点的完全图，对同样的问题，是否也存在r?p1,p2,?,pm;2?。 比较：两种情况的不同点是Kn的顶点所在的空间的维数不同，共同点是颜色增多，且最关键之处是被染色的对象都是Kn中任意两点所连接成的边。 用第三种方式描述：设集合A??e1,e2,?,en?，令S??XX?A,X?2?（以A上所有二元子集为元素构成的集合），再用?S1,S2,?,Sm?表示S的一个m分拆，即 S1?S2???Sm?S， SiSj??， Si可空 n≥r?p1,p2,?,pm;2?时，对集合A中的元素，下面结论至少有一个成立：在A中存在pi?1?i,j?m,i?j?。那么，当 个元素，其全部二元子集都属于Si?i?1,2,?,m?。 相应于（1）、（2）的结论称作“两点结合的Ramsey定理”，或称“边的Ramsey定理”。 （3） 增多子集X中元素的个数：“设集合A??e1,e2,?,en?，令S??XX?A,X?t，t?1?（以A上所有t元子集为元素构成的集合），再用?S1,S2,?,Sm?表示S的一个m分拆，即S1?S2???Sm?S，SiSj??，S可空?1?i,j?m,i?j?。那么，总存在一个仅依赖于p1,p2,?,pm和t的正整数N，当n≥N时，对集合A中的元素，下面结论至少有一个成立：在A中存在pi个元素，其全部t元子集都属于Si?i?1,2,?,m?”。称这样的数N为广义Ramsey数，记为r?p1,p2,?,pm;t?。 i几何角度：当k=t=3，m=2时，考虑空间中任何四点都 25/37