组合数学幻灯片2.3

在这一节中我们将给出由英国逻F.P.Ramsey给出的一个重要定理。它是鸽笼原理的一个重要推广，这就是Ramsey定理。它的一般形式是很复杂的，由于这个原因，我们从简单的例子入手对它进行探讨。§2.3Ramsey定理证明：先考虑这6个人中的任意一个人，不妨把这个人称作p。则其他的5个人可分为下面的两个集合F和S。其中[定理2.3]在人数为6的一群人中，一定有三个人彼些相识，或者彼些不相识。•F=与p相识的人的集合•S=与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个集合包含有3个人。若F包含有3个人，则这三个人或者彼些不相识，或者有两个人彼些相识。注意：3个人的情况应该分为如下几种：3个人彼此都认识3个人彼此都不认识3个人有2个人彼此认识3个人有2个彼此都不认识如果F中有三个人彼此不相识，则定理结论成立。如果F中有两人相识，则由于这两个人都与p相识，因此有三人彼此相识，故定理结论也成立。类似的，如果S包含有3个人，则这三个人或者彼此相识，或者有两个人彼此不相识。如果这三个人彼此相识，则结论成立。如果有两个人彼此不相识，则由于这两人都与p也不相识，因此有三人彼此不相识，故定理结论也成立。•下面，我们用图形来表示这个定理。这里用平面上的点表示人，用实线或虚线把这些点连结起来，其中实线表示这一对人互相认识，虚线表示这对人彼此不相识。图2.1是这6个人可能情况之一。图2.1于是，定理2.3表明，对平面上的六个点，任意用实线或虚线将这些点连结起来所成的完全图中，或者存在一个实线三角形，或者存在一个虚线三角形。我们称这两种三角形为纯三角形。(类似地，如果由n个点构成的完全图中，所有的边都是实线(或虚线)构成的，则称这样的完全图为纯n角形)。下面，我们希望将定理2.3加以推广。2.3和图2.4分别表示四个人彼此相识和彼此不相识。但是，究竟要多少人组成一群人才能保证一定有4个人彼些相识或彼些不相识?这似乎是一个困难的问题。但我们可以从研究简单的情况入手，最后可以证明：在人数为20的一群人中，一定有4个人彼此相识或不相识。在6个人的情况下，定理2.3是最好的可能结果。因为只有5个人时，我们有图2.2。在这个图中没有一个纯三角形。首先，我们证明下面的定理。定理2.4在人数为10的一群人中，一定有3个人彼此不相识或者有4个人彼此相识。即至少有图2.5所示两图形之一。在这10个人中任意挑选一个人，不妨称这个人为p，则剩下的9个人可以分成两个集合F和S，其中F=与pS=与p不相识的人的集合考虑把某个集合中分6个人，就可以利用定理2.3证明结论了。所以，可以考虑某集合至少6人，因为由鸽笼原理，只能保证有一个集合至少5人。那么还要考虑集合为5人或者4人的情况。所以，考虑：•某集合有4个以上的人•某集合有3个以下的人，则另一个集合则会有6个及以上的人。这样，就考虑全面了。如果S中有4个(或4个以上)人，则或者这四个人(或四个人以上)彼此相识或者有两个人彼此不相识。如果有四个人彼此相识，则定理结论成立。如果在S中有两人彼此不相识，则这两个人也与p不相识，于是有三个人彼此不相识。这意味着，如果S包含3个以上的人，则我们就可以在S中发现我们正好期待的图2.5。如果在S中最多有3个人，则由鸽笼原理知，F中至少有6个人。于是，由定理2.3知，F包含一个纯三角形。如这个三角形是由三条虚线组成的(即三个人彼此不相识)，则定理成立，如果这个三角形是由三条实线所组成(即三个人彼此相识)，则把p加入，就有4个彼此相识的人。故本定理得证。定理2.5在人数为10的人群中，一定有三个人彼此相识或者四个人彼此不相识。现在，我们可以证明下面的定理。定理2.6在人数为20的一群人中，一定有四个人彼此相识或者有四个人彼此不相识。在定理2.4中，如果把“不相识”换成“相识”，“相识”换成“不相识”，则有下面的定理，它的证明类似于定理2.4的证明。证明：在这20人中任意挑选一人，不妨把这个人称作p，则其余19个人可以分为两个集合F(与p相识的人)和S(与p不相识的人)。由鸽笼原理知，这两个集合中至少有一个集合包含有10个人。若F包含有10个人，则由定理2.5知F中有三个人彼此相识或四个人彼此不相识。如果F中有四个人彼此不相识，则定理成立。如果F中有三个人彼此相识，则加入p，就有四个人彼此相识。[定理2.6]另一方面，如果S中包含有10个人(或10个人以上)，则由定理2.4知，在S中一定有三个人彼此不相识或者四个人彼此相识。如果有四个人彼此相识，则定理结论成立。如果有三个人彼此不相识，则加入p就有四个人彼此不相识，因而定理结论也成立。综上所述，定理得证。于是，定理2.3意味着N(3，3)≤6定理2.4意味着N(4，3)≤10定理2.5意味着N(3，4)≤10定理2.6意味着N(4，4)≤20定义2.1设a,b为正整数，令N(a,b)是保证有a个人彼此相识或者有b个人彼此不相识所需要的最少人数，则称N(a,b)为Ramsey数。这些结果仅仅给出了N(a,b)的一个上界，但它们不一定是最好的可能的结果。例如，可以证明N(4，4)≤19。下面我们证明Ramsey数所具有的一些性质的定理。定理2.7N(a,b)=N(b,a)(2.1)N(a,2)=a(2.2)证明：由对称性即得式(2.1)。对式(2.2)，如果在a个人中都彼此相识，则式(2.2)显然成立，否则至少有两个人彼此不相识。故式(2.2)也是成立的。定理2.8当a,b≥2时，N(a,b)是一个有限数，N(a,b)≤N(a-1,b)+N(a,b-1)(2.3)证明：首先证明式(2.3)，当式(2.3)已经证明成立时，即可知N(a,b)是有限的。这是由于若式(2.3)成立，则对式(2.3)不等号的右边反复使用式(2.3)，且因a,b是有限数，故总可以在使用式(2.3)一定次数之后，不等式右边都出现N(a′,2)或N(2,b′)的形式。再由定理2.7中的式(2.2)即可得N(a,b)≤有限数。在N(a-1,b)+N(a,b-1)个人中任意挑选一个人，把这个人称作p，则剩下的N(a-1,b)+N(a,b-1)-1个人可分成两个集合F(与p相识的人)和S(与p不相识的人)。由鸽笼原理(定理2.2)知，或者在F中至少有N(a-1,b)个人，或者在S中至少有N(a,b-1)个人。•下面我们证明式(2.3)。如果在F中有N(a-1,b)个人，这表明有a-1个人彼此相识，或者有b个人彼此不相识。若有a-1个人彼此相识，则加上p就有a个人彼此相识，因而式(2.3)成立。如果在S中有N(a，b-1)个人，这表明有a个人彼此相识，或者b-1个人彼此不相识。若有b-1个人彼此不相识，则加上p就有b个人彼此不相识，因而式(2.3)也成立。定理2.10N(3,3)=6(2.5)N(3,4)=N(4,3)=9(2.6)N(3,5)=N(5,3)=14(2.7)证明：由定理2.3的证明及说明可得式(2.5)。定理2.9当N(a-1,b)和N(a,b-1)都是偶数时，则有N(a,b)≤N(a-1,b)+N(a,b-1)-1(2.4)•证明：留作练习。下面证明式(2.6)。由式(2.2)知N(4，2)=4。又由式(2.5)知N(3，3)=6。4，6都是偶数，故由式(2.4)知N(3，4)=N(4，3)≤N(3,3)+N(4,2)-1=6+4-1=9但当人数只有8时，有图2.6。这个图表明既不存在纯实线三角形，又不存在纯虚线四角形，因此有N(3，4)=N(4，3)8。N(3，4)=N(4，3)=9故式(2.6)成立。式(2.7)的证明如下：(2.1)，(2.3)和(2.6)有N(3，5)=N(5，3)≤N(4，3)+N(5，2)=9+5=14但当人数只有13时，有图2.7。这个图表明既没有纯实线三角形，也没有纯虚线五角形，故有N(3，5)=N(5，3)13。因此有N(3，5)=N(5，3)=14故式(2.7)成立。注意，由于图2-7的线条很多，为清楚起见，把图2-7分解为仅有实线边的图2-8和仅有虚线边的图2-9。，求N(a,b)是一个很困难的问题，到目前为止，我们已知的Ramsey数如表2.1所示(表中，x-y表示对应的Ramsey数N(a,b)具有下界x,上界y)。在前面的讨论a中，如果我们用红色代替实线，蓝色代替虚线，则前面的定理可以改叙如下。例如定理2.3可以叙述成：对6个点构成的完全六角形的边用红、蓝二色任意着色，则在这个完全六角形中一定存在一个红色的三角形或者一个蓝色的三角形。定理2.4可以改叙为：对10个点构成的完全十角形中的边用红、蓝二色任意着色，则在这个完全十角形中一定存在一个蓝色的三角形或者一个红色的完全四角形。其他的定理可以类似地改叙等等。n角形不是用两种颜色对其边着色，而是用r种颜色对其边任意着色。设是保证出现下列情形之一的最小正整数：用颜色着色的一个完全角形或用颜色着色的一个完全角形或用颜色着色的一个完全则有称数为Ramsey数。定理2.11对所有大于1的整数和，数是存在的。着色的所有边用蓝色表示，而用颜色着色的所有边用红色表示。，则在完全p角形中或者有一个纯角形或者有一个纯角形。设，只需证明即可。这是因为是有限数(存在)，于是也是有限数(存在)。在完全Q角形中或者有一个蓝色的纯角形，或者有一个红色的纯p角形。如果后者出现，则在这个完全的p角形中必然有一个纯角形，或者有一个纯角形。QpaN),(1QpaNaaaN),(),,(1321QpaN),(1),,(321aaaN2c1a2a3c3a•即是说在个顶点的完全Q角形中，或者有一个纯角形，或者有一个纯角形，或者有一个纯角形，而是具有以上性质的最小整数，故有•本定理证毕。用类似的方法，我们可以从用三种颜色到四种颜色，从四种颜色到五种颜色，……，归纳得出下面的结果。定理2.12对任意的正整数m和Ramsey是存在的。12,,,2maaa12(,,,)mNaaa下面，将定理再加以推广。我们从n个人的一个集合入手，并考虑关系“相识”和“不相识”，“相识”或“不相识”是两个人之间的关系。这种关系同时定义在两个人之间的。在实际中，还有同时要求3个物体之间的关系的。例如，在平面上的三个点，我们可以说这三个点所构成的三角形或者是锐角三角形，或者是钝角三角形，或者是直角三角形，或者是平角三角形(三点共线)。在通常情况下，我们可以从n个元素的集合着手，并且把具有r个元素的所有子集分成m个类，即类，于是我们问，是否可以将n选择得足够大，使得我们一定能够找到：存在个元素，它的所有r元子集属于类或者存在个元素，它的所有r元子集属于类或者………………或者存在个元素，它的所有r元子集属于类我们把保证上述情形之一成立的最小正整数称作Ramsey数，记作注意，在这之前，我们曾假设r=2，并且没有使用符号“；r”作为Ramsey数符号的一部分。正如所希望的一样，所有这些推广的Ramsey数都是存在的。即有定理2.13对于任何正整数r,Ramsey数存在。实际上，上述定理是鸽笼原理的进一步推广。因为，如果设r=1，这就意味着，把足够多的物体放入m个盒子，我们可以保证得到或者a1个在第一个盒子内，或者a2个在第二个盒子内，……，或者am个在第m个盒子内。显然，只要有个物体就足够了。习题P341011