组合数学第二节Ramsey问题与Ramsey数.docx

《组合数学第二节Ramsey问题与Ramsey数.docx》由会员分享，可在线阅读，更多相关《组合数学第二节Ramsey问题与Ramsey数.docx（11页珍藏版）》请在三一文库上搜索。

1、第二节： Ramsey 问题与 Ramsey 数1958年67月号美国数学月刊上登载着这样一个有趣的问题： “任何 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 条边着红色

2、或蓝色。由鸽巢5原理知，其中至少有 5 3 条边同色，不妨设 1与21若 2, 3, 4间有一条红边，不妨设为 2 3 ，则 1 22 3 4 是一 蓝色三角形。类似于命题 1.3.1，还有如下的命题 1.3.2命题 1.3.4：2, 3, 4所连的 3 条边均为红色，如图 1.3.1 所示。命题 1.3.2 对 6 个顶点的完全图 K6 任意进行红、蓝两边着色，都至少有两个同色三角形。证明 设 1, 2, 3, 4, 5, 6是K6的 6个顶点，由命题 1.3.1知，对 K6任意进行红、蓝两边着色都有一个 同色三角形，不妨设 1 2 3 是红色三角形，以下分各种情况来讨论：（1）若1,2,3

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为红边，此时若边 24,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 是蓝色三角形。

4、（ii）若 4 5, 4 6均为红边，见图 1.3.5。此时，若 1, 5, 6之间有一条红边， 不妨设 1, 5为红边，则 1 4 5 为红色三角形；否则， 1 5 6 为蓝色三角形。由以上对各种情况的讨率知，对K6 的任意红、蓝两边着色均有两个同色三角形。命题 1.3.3 对 10 个顶点的完全图 K 10任意进行红、蓝两边着色，都或者有一红色K4 ，或者有一蓝色 K3 。证明 设a是 K 10的一个顶点，与 a相关联的 9条边用红、蓝两色着色，由鸽巢原理知，这9条边中要么有 6 条红边，要么有 4 条蓝边。类似于前面两个命题的分析证明过程可以得出结论， 具体分析过程见图 1.3.6 。

5、命题 1.3.4 对 9 个顶点的完全图 K 9任意进行红、 蓝两边着色， 都或者有一个红色 K 4 ，或者有一蓝色 K3 。592证明 在 K9中，如果与每个顶点关联的红边均为5 条，因为一条红边连着两个顶点，所以 K9 中应有5，设此顶点为 a ，则与 a45条边， 它不是整数， 所以不成立。 故必有一个顶点关联的红边数不为2关联的红边数至少为 6 或至多为 4。1.3.2 Ramsey 数从 1.3.1 小节的讨论中可以归纳出如下的一般性定义：对于任意给定的两个正整数a 与 b ，如果存在最小 的正整数 r ( a,b) ，使得当 N r(a,b)时，对 K N中均有红色 Ka或蓝色 K

6、b ，则r (a,b)称为 Ramsey数。由命题 1.3.1知r (3,3) 6；在 K5中按图 1.3.7的方式进行红、蓝两边着色(实线为红边，虚线为蓝边)则既无红色 K 3也无蓝色 K3，所以 r (3,3) 5 。从而得知 r (3,3) 6。由命题 1.3.4 r (4,3) 9；在 K8中按图 1.3.8的方式进行红、蓝两边着色，则既无红色K 4也无蓝色 K3，所以 r (4,3) 8。从而得知 r (4,3) 9Ramsey 于 1930 年证明了对于任给的整数 a 和 b ，Ramsey 数 r(a,b) 的存在性。但是， Ramsey 数的确定却是一个非常难的问题，以至于至今

7、 r (5,5) 尚不为世人所知。表 1.3.1 中列出了目前所知的一些 Ramsey 数。易证（留作习题）（1） r（a,b） r（b,a）;（1.3.1）（2） r（a,2） a（1.3.2）定理 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 ，对K N任意进行红、 蓝两边着色。 设x是K N的一个顶点， 在KN中 与 x 相关联的边共有 r a 1,b r a,b 1 1条，这些边要么为红色， 要么为蓝色。 由鸽巢原理知， 与 x 相关联的这些边中，要么至少有 r a 1,b 条红边，要么至少有 r

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

9、蓝色 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 ，有a b 2 a b 2 !r a,ba 1 a 1! b 1!证明 对 a b 作归纳。当 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

10、m n 3 m n 3m 1 m 2mn2m1所以，对于任意的正事业 a 2,b 2 ，定理的结论成立。1.4 Ramsey 数的推广将 1.3 节中的红、蓝两色推广到任意k 种颜色，对N个顶点的完全图 KN用c1,c2,L ,ck共 k种颜色任意进行 k 边着色，它或者出现 c1 颜色的Ka1 ，或者出现c2 颜色的 K a2 ，或者出现 ck颜色的 Kak 。满足上述性质的 N 的最小值记为 r a1, a2 ,Lak 。定理 1.4.1 对任意的正整数 a1,a2 ,Lak ，有证明 留作习题a1,a2,L akr a1,r a2,L ak类似于定理 1.3.1 和定理 1.3.2，有如

11、下的结论：定理1.4.2 对任意的正整数 a1 2,a22,Lak2 ，有证明定理证明r a1, a2,L akr a1 1,a2L akr a1,a2 1,Lakr a1, a2 ,L ak类似于定理 1.3.1 的证明。1.4.3 对任意的正整数 a1,a2 ,L类似于定理 1.3.2 的证明。利用广义考试集合可以看出，ak ，有r a11,a2 1,L ak 1a1 a2 L ak !a1!a2!L ak !Ramsey 数，我们来讨论一类集合划分问题。1,2,L ,13 的一个划分在上面的划分的每一块中，然而，无论如何将集合 1,2,L ,14于 1916 年证明了对任意的正整数1,4

12、,10,13 , 2,3,11,12 , 5,6,7,8,9都不存在三个数xy划分成三个子集合，n，都存在一个整数集合，总有一个子集合中有三个数满足方程（1.4.1）。定理1.4.4 设 S1 ,S2,L Sn 是 集 合 1,2,LSi I Sj其中 rnx, y,z （不一定不同）满足方程总有一个子集合中有三个数满足方程fn ，使得无论如何将集合 1,2,L f面，,rn（i j,1 i, j n） ，则对某一个 i,Si 中有三个数r1 34,32,L4,331.4.11.4.1）。Schur划分成 n 个子我们用 Ramsey 数来证明这个结论。n的 任 一 划 分 ， 即 U 1,2

13、,L ,rn ， 且i1x, y,z （不一定不同） ，满足方程 x yz。证明 将完全图 Krn中的rn个顶点分别用 1,2,L , rn来标记，对 K rn的边进行 n 着色如下：设 u, 是Krn的任意两个项点， 若 uSj ，则将边 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 是满足下述性质的最小整数：

14、将1,2,L Sn 任意划分成 n 个子集合，总有一个子集合中含有三个数x, y, z，满足方程（ 1.4.1）。容易证明 s1 2,s2 5,s3 14 （见本章习题 24）。在本章的习题中，还列有 一些关于 rn和 sn的上、下界的结论。将前面的鸽巢原理和 Ramsey 数进一步推广，可以得到下面更一般的 Ramsey 定理：定理 1.4.5（Ramsey 定理） 设 q1,q2,L qn， t是正整数，且 qi t（1 i n） ，则必存在最小的正整数 N q1,q2,L qn;t ，使得当 m N q1,q2,L qn;t 时，设 S是一集合且 S m，将S的所有 t元子集任意 分放到

15、 n 个盒子里，那么要么有 S 中的 q1个元素，它的所有 t 元子集全在第二个盒子里；要么有 S 中的 qn个元素，它的所有 t元子集全在第 n 个盒子里。证明 略。当 t 1时， Ramsey 定理说明 N（q1,q2,L qn;1） 存在，使得对任何 m N q1,q2,L qn;1 ，把 m 个物体放 入 n 个盒子里， 或者有 q1个物体都在第一个盒子里， 或者有 q2 个物体都在第二个盒子里， ，或者有 qn 个物体都在第 n 个盒子里。从 1.2 节中鸽巢原理的加强形式知N q1,q2,L qn;1 q2 q2 L qn n 1当 t 2时，可以设想 S是一完全图的顶点集合， n

16、 个盒子可以设想成 n 种颜色 c1,c2,cn，S的 2 元子集就是图中连接两个顶点的边。此时， Ramsey 定理中的r q1,q2,L qN q1 , q2 ,L qn;2特别地，当 n 2时，由1.3 节中的结论知N(3,3;2)r (3,3) 6N (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