组合数学-第二节:Ramsey问题与Ramsey数

2023年12月9日发(作者：联考半期考高三数学试卷)

第二节：Ramsey问题与Ramsey数

1958年6~7月号美国《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。”这就是著名的Ramsey问题。

以6个顶点分别代表6个人，如果两人相识，则在相应的两顶间连一红边，否则在相应的两顶点间连一蓝边，则上述的Ramsey问题等价于下面的命题：

命题1.3.1 对6个顶点的完全图K6任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。

证明 设1,2,3,4,5,6是K6的6个顶点，1与2,3,4,5,6所连的5条边着红色或蓝色。由鸽巢原理知，其中至少有3条边同色，不妨设1与2,3,4所连的3条边均为红色，如图1.3.1所示。2若2,3,4间有一条红边，不妨设为23，则123是一红色三角形。否则，2,3,4间均为蓝边，即5234是一蓝色三角形。

类似于命题1.3.1，还有如下的命题1.3.2~命题1.3.4：

命题1.3.2 对6个顶点的完全图K6任意进行红、蓝两边着色，都至少有两个同色三角形。

证明 设1,2,3,4,5,6是K6的6个顶点，由命题1.3.1知，对K6任意进行红、蓝两边着色都有一个同色三角形，不妨设123是红色三角形，以下分各种情况来讨论：

（1）若1,2,3,4,5,6均为蓝边，如图1.3.2所示，则若4,5,6之间有一蓝边，不妨设为4,5，则145为蓝色三角形；否则，456为红色三角形。

（2）若1,2,3,4,5,6中有一红边，不妨设1,4为红边，此时若边24,34中有一条红边，不妨设34是红边，则134是一红色三角形，见图1.3.3。

以下就24,34均为蓝边的情况对与4相关联的边的颜色进行讨论：

（i）若45,46中有一蓝边，不妨设4,5为蓝边，如图1.3.4所示。此时，若25,35均为红边，则235是红色三角形；否则，245或345是蓝色三角形。

,（ii）若4546均为红边，见图1.3.5。此时，若1,5,6之间有一条红边，不妨设1,5为红边，则145为红色三角形；否则，156为蓝色三角形。

由以上对各种情况的讨率知，对K6的任意红、蓝两边着色均有两个同色三角形。

命题1.3.3 对10个顶点的完全图K10任意进行红、蓝两边着色，都或者有一红色K4，或者有一蓝色K3。

证明 设a是K10的一个顶点，与a相关联的9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有6条红边，要么有4条蓝边。类似于前面两个命题的分析证明过程可以得出结论，具体分析过程见图1.3.6。

命题1.3.4 对9个顶点的完全图K9任意进行红、蓝两边着色，都或者有一个红色K4，或者有一蓝色K3。

证明 在K9中，如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以K9中应有5945条边，它不是整数，所以不成立。故必有一个顶点关联的红边数不为5，设此顶点为a，则与a22关联的红边数至少为6或至多为4。

1.3.2 Ramsey数

从1..3.1小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数a与b，如果存在最小的正整数r(a,b)，使得当Nr(a,b)时，对KN中均有红色Ka或蓝色Kb，则r(a,b)称为Ramsey数。

由命题1.3.1知r(3,3)6；在K5中按图1.3.7的方式进行红、蓝两边着色（实线为红边，虚线为蓝边），则既无红色K3也无蓝色K3，所以r(3,3)5。从而得知r(3,3)6。

由命题1.3.4r(4,3)9；在K8中按图1.3.8的方式进行红、蓝两边着色，则既无红色K4也无蓝色K3，所以r(4,3)8。从而得知r(4,3)9

Ramsey于1930年证明了对于任给的整数a和b，Ramsey数r(a,b)的存在性。但是，Ramsey数的确定却是一个非常难的问题，以至于至今r(5,5)尚不为世人所知。表1.3.1中列出了目前所知的一些Ramsey数。

易证（留作习题）

（1）r(a,b)r(b,a);

（2）r(a,2)a

定理1.3.1 对任意的正整数a3,b3，有ra,bra1,bra,b1

证明 令Nra1,bra,b1，对KN任意进行红、蓝两边着色。设x是KN的一个顶点，在KN中与x相关联的边共有ra1,bra,b11条，这些边要么为红色，要么为蓝色。由鸽巢原理知，与x相关联的这些边中，要么至少有ra1,b条红边，要么至少有ra,b1条蓝边。

（1）这些边中有ra1,b条红边。在以这些红边与x相关联的ra1,b个顶点构成的完全图Kra1,b中，必有一个红色Ka1或有一个蓝色Kb，若有红色Ka1，则该红色Ka1加上顶点x以及x与Ka1之间的红边，即构成一个红色Ka；否则，就有一个蓝色Kb。

（2）这些边中有ra1,b条蓝边。在以这些蓝边与x相关联的ra,b1个顶点构成的完全图Kra,b1中，必有一个红色Ka或有一个蓝色Kb1。若有一个蓝色Kb1，则该Kb1加上顶点x以及x与Kb1之间的蓝边，即构成一个蓝色Kb；否则，就有一个红色Ka。

综合（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 对任意的正整数a2,b2，有

（1.3.1）

（1.3.2）

证明 对ab作归纳。

ab2!ab2

ra,ba1a1!b1!当ab5时，a2或b2，由等式（1.3.2）知定理成立。

假设对一切满足5abmn的a,b定理成立，由定理1.3.1及归纳假设，有

rm,nrm,n1rm1,n

mn3mn3

m1m2mn2m1所以，对于任意的正事业a2,b2，定理的结论成立。

1.4 Ramsey数的推广

将1.3节中的红、蓝两色推广到任意k种颜色，对N个顶点的完全图KN用c1,c2,,ck共k种颜色任意进行k边着色，它或者出现c1颜色的Ka1，或者出现c2颜色的Ka2，……，或者出现ck颜色的Kak。满足上述性质的N的最小值记为ra1,a2,定理1.4.1 对任意的正整数a1,a2,

证明 留作习题

类似于定理1.3.1和定理1.3.2，有如下的结论：

定理1.4.2 对任意的正整数a12,a22,ak。

ak，有

ra1,a2,akra1,ra2,ak

ak2，有

ra1,a2,akra11,a2ra1,a21,ra1,a2,akak

ak1n2证明 类似于定理1.3.1的证明。

定理1.4.3 对任意的正整数a1,a2,证明 类似于定理1.3.2的证明。

利用广义Ramsey数，我们来讨论一类集合划分问题。

考试集合1,2,ak，有ra11,a21,ak1a1a2ak!

a1!a2!ak!,13的一个划分1,4,10,13,2,3,11,12,5,6,7,8,9

xyz

可以看出，在上面的划分的每一块中，都不存在三个数x,y,z（不一定不同）满足方程

然而，无论如何将集合1,2,（1.4.1

总有一个子集合中有三个数满足方程（1.4.1）。Schur,14划分成三个子集合，于1916年证明了对任意的正整数n，都存在一个整数fn，使得无论如何将集合1,2,fn划分成n个子集合，总有一个子集合中有三个数满足方程（1.4.1）。下面，我们用Ramsey数来证明这个结论。

定理1.4.4 设S1,S2,Sn是集合1,2,,rn的任一划分，即ni11,2,,rn，且SiSj(ij,1ij,n，则对某一个i,Si中有三个数x,y,z（不一定不同），满足方程xyz。其中rnr3,3,n,3 证明 将完全图Krn中的rn个顶点分别用1,2,,rn来标记，对Krn的边进行n着色如下：设u,是Krn的任意两个项点，若uSj，则将边u染成第j种颜色。由广义Ramsey数rn的定义知一定存在同色三角形，即有三个项a,b,c，使得边ab,bc,ca有相同的颜色，设为第i种颜色。另不妨设abc，则有ab,bc,acSi，令xab,ybc,zac，则有x,y,zSi，且xyz。

设Sn是满足下述性质的最小整数：将1,2,Sn任意划分成n个子集合，总有一个子集合中含有三个数。容易证明s12,s25,s314（见本章习题24）。在本章的习题中，还列有x,y,z，满足方程（1.4.1）一些关于rn和sn的上、下界的结论。

将前面的鸽巢原理和Ramsey数进一步推广，可以得到下面更一般的Ramsey定理：

定理1.4.5（Ramsey定理） 设q1,q2,qn，t是正整数，且qit(1in)，则必存在最小的正整数Nq1,q2,qn;t，使得当mNq1,q2,qn;t时，设S是一集合且Sm，将S的所有t元子集任意分放到n个盒子里，那么要么有S中的q1个元素，它的所有t元子集全在第二个盒子里；……；要么有S中的qn个元素，它的所有t元子集全在第n个盒子里。

证明 略。

当t1时，Ramsey定理说明N(q1,q2,qn;1)存在，使得对任何mNq1,q2,qn;1，把m个物体放入n个盒子里，或者有q1个物体都在第一个盒子里，或者有q2个物体都在第二个盒子里，……，或者有qn个物体都在第n个盒子里。从1.2节中鸽巢原理的加强形式知

Nq1,q2,qn;1q2q2qnn1

当t2时，可以设想S是一完全图的顶点集合，n个盒子可以设想成n种颜色c1,c2,cn，S的2元子集就是图中连接两个顶点的边。此时，Ramsey定理中的

Nq1,q2,qn;2rq1,q2,qn

特别地，当n2时，由1.3节中的结论知

N(3,3;2)r(3,3)6

N(3,4;2)r(3,4)9定理1.4.6

N(q1,t;t)q1,N(t,q2;t)q2

证明 若S中元素少于或等于q11个，则将S的所有t元子集全部放入第一个盒子里。这里，没有S的q1元子集，它的所有t元子集全在第一个盒子里；第二个盒子为空，也没有t元子集在第二个盒子里。故N(q1,t;t)q1

若S中恰有q1个元素，把S的t元子集分放到两个盒子中。若第二个盒子非空，即盒中至少存在一个t元子集，该t元子集的t元子集在第二个盒子中；若第二个盒子为空，则S的所有t元子集全在第一个盒子里，且Sq1，无论哪种情况，均满足要求，故N(q1,t;t)q1。

综合以上分析，知N(q1,t;t)q1

同理可证N(t,q2;t)q2