《组合数学》 第五章 抽屉原理和Ramsey理论
不共面的n个点组成的集合A，将每三个点构成的三角形涂以红色或蓝色，当任意给定了正整数p,q?p,q?3?后，只要点数n超过某一个有限数时，则下列两种情况必有一种成立：或者存在p个点，其中每三个点构成的三角形均为红色（蓝色）；或者存在q个点，其中每三个点构成的三角形均为蓝色（红色）。 这就是“三点结合的Ramsey定理”，或者称作“三角形Ramsey定理”。相应的染色问题叫做面2-染色问题。 一般情形，首先将完全图的概念加以推广，设k维空间有n个点，从中任取t个点及其相邻的边结合在一起，称作t级边（当t=2时就是普通的边， t=3时是三角形， t=4是四面体）。把这n个点与其所有的t级边组成的图叫做t
t级完全图，记做Kn，又称作超图。假如用m种颜色c1,c2,?,cm去涂染这n个点中全部的t级边，每个t级边任意涂染一色，从而将这些t级边划分成了m类，当任意给定一组正整数
tp1,p2,?,pm后，则在n充分大时，t级完全图Kn中一定含有一个t级完全子图Kqt，其所有t级边的颜色都是同一色
ici?1?i?m?。满足上述条件的最小的整整数
n，就是广义
Ramsey数r?p1,p2,?,pm;t?。
特例，当t=1时，就是§6.1所述的抽屉原理，其中 （1） r?p,q;1??p?q?1——两个抽屉时的抽屉原理；（2） r?p1,p2,?,pm;1??p1?p2???pm?n?1——推广形式的抽屉原理；
??r?2,2,?,2;1??n?1——抽屉原理的基本形式。 （3） ???????n个??其次还有，r?p,t;t??p?p?t?，r?t,q;t??q?q?t?。 定理5.4.3 广义Ramsey数r?p1,p2,?,pm;k?是存在的。
26/37
《组合数学》 第五章 抽屉原理和Ramsey理论
例5.4.3 有17位学者，每人给其它人各写一封信，讨论三个问题中的某一个问题，且两人之间互相通信讨论的是同一个问题。证明至少有三位学者，他们之间通信讨论的是同一问题（1964年第六届国际奥林匹克数学比赛题目）。 此问题等价于对K的每条边涂以红、蓝、黄三色之一（即边3－着色），其中必存在同色K 。由此可知，r?3,3,3;2??17。
173（证）设v0,v1,?,v16为给定的17个点，任取一点，不妨设为v0，将v0与其余16点连接成16条边，当用三色涂
?16?染时，由抽屉原理知至少有???6条边被涂上同一颜色，
?3?不妨设为v0vi ?i?1,2,?,6?且这六条边同为红色。考虑由v1,v2,?,v6组成的完全图K6，分两种情况讨论： 如果在这个K6中有一条边，比如v1v2也是红色，则?v0v1v2就是一个同色三角形。否则在这个K6中没有红色的边，于是只能涂上蓝色或黄色，则归结为K6的边2－染色问题，已知其必存在同色的三角形。
例5.4.4 证明r?3,3,3;2??16，即对于K6，存在一种边3－着色方案，使得其中不存在同色K。
3（证）考虑由二进制码组成的集合G＝{0000，0001，0010，?，1111}，定义各元素的加法为二进制的逐位异或运算，即0+0＝0，1+0＝0+1＝1，1+1＝0。则集合G对于加法构成一个16阶交换群（参见§6.1），其中0000为单位元。把G中除去单位元的15个元素分成三个不封闭的子集G1,G2,G3，即使得每个子集里的任意两个元素相加所得的元素不在同一子集里：
G1??1100,0011,1001,1110,1000?， G2??1010,0101,0110,1101,0100?， G3??0001,0010,0111,1011,1111?
然后，建立G与K16的一个映射，使K16的顶点和群G的元
27/37
《组合数学》 第五章 抽屉原理和Ramsey理论
素一一对应起来，并按下面方法用三种颜色对边染色： 取x,y?G，且x?y。那么，当x?y?Gi时，则用颜色i染顶点x与y的连线；当x?Gi时亦用颜色i把0000与x用一线段连接（请读者自己完成）。 按照上述方法构造的经过边3-染色的K16中不存在同色的K。由此可知r?3,3,3;2??16，从而最后可确定r?3,3,3;2??17。
3
???若令R?m?=r3,3,?,3;2m?，即R?m?表示用????????m个3?m种颜色涂染
完全图的边存在同色三角形的最少点数，目前已知R?1??3，
R?2??6，R?3??17。那么，一般的R?m?应该为何？准确地求
出R?m?是困难的，目前只知道关于它的上界的递归不等式。
定理5.4.4 R?m?≤m?R?m?1??1??2
令n=m?R?m?1??1??2，对完全图Kn的边用m种颜色染色后，从其顶点v1引出m?R?m?1??1??1条边，由抽屉原理知，至少有R?m?1?条边为同一种颜色，不妨设边
v1v3v1v2，
，??，v1vR?m?1??1均为红色，v2,v3,?,vR?m?1??1,构成一个
完全图KR?m?1?，则有
（1） KR?m?1?中有一条红色边，比如v2v3，则?v1v2v3就
是一个同色三角形；
（2） KR?m?1?中没有红色的边，则它的边只有m?1种不
同的颜色，根据R?m?1?的定义，这个KR?m?1?中有一个同色三角形。
28/37
《组合数学》 第五章 抽屉原理和Ramsey理论
推论1 R?m?≤m!??1??11!?12!???1???1 m!?（证）用数学归纳法： 当m设m?1时，R?1??3??1?1??1，不等式成立； ?k?1时命题成立，即
??111?1?????R?k?1?≤?k?1?!????1 ??1!2!k?1!??当m?k时，由定理5.4.4知
R?k??k?R?k?1??1??2
由归纳假设得
??111?1?????R?k?≤k??k?1?!????2?k?1?!?1!2!?
即
?11111??R?k??k!?1??????????2?k?1?!k!k!?1!2!?
=k!??1??11!?12!???1???1 k!?由归纳法原理，命题成立。 推论2 R?m?≤?m!e??1。 （证）因为
m!e=m!?k?0?1k!=m!?k?0m+m!?k!1?1k?m?1k!=am?bm
而当m≥1时
29/37
《组合数学》 第五章 抽屉原理和Ramsey理论
?bm=m!?k?m?1?1k!=
1m?11???m?1??m?2???m?i?
i?2?1＜==
1m?11???m?i?1??m?i?
i?2?m?12m?1??i?211?????
?m?i?1m?i?≤1
由此可见：
bm只是m!e的小数部分，所以
?m!e?=m!?1???11!?12!???1?? m!?再由推论1便可得到推论2。 推论3 R?m?≤3m!。
（证）用归纳法：当m=1时，R?1??3?3?1!，结论成立； 设m?k?1时命题成立，即
R?k?1?≤3?k?1?!
当m?k≥2时，由定理5.4.4知
R?k??k?R?k?1??1??2
由归纳假设得
R?k?≤k?3?k?1?!?1??2=3k!??k?2?≤3k!
由归纳法原理，命题成立。
30/37