Ramsey数R(3,3,…,3)的一个上界.pdf

《Ramsey数R(3,3,…,3)的一个上界.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、教学研究Ｒamsey数Ｒ(3，3，…，3)的一个上界孟恋忱(首都师范大学，北京100048)【摘要】本文主要探究了一个图的染色问题:对于一个正整数n，找在三条边颜色相同的三角形”，也即Ｒ(3，3，3)≤17。到一个尽可能小的m:如果把m阶完全图的每条边染成n种不同颜色从简单情形入手，回到Ｒamsey定理:世界上任何六个人中，一之一，无论怎样进行染色，都必然有三条边同色的三角形。定有3个人或者互相认识或者互相都不认识。【关键词】图论Ｒamsey数染色抽屉原理将定理抽象成数学问题:将K6染上2种颜色(

2、不妨记为红、蓝)，一定存在三边颜色相同的三角形。下面用反证法证明这个定理。1Ｒamsey数的概念求证Ｒ(3，3)≤6。即证:K6两染色，必有同色三角形。下面简单介绍图论中的基本对象。(Ｒamsey定理)(1)定义一个图G是指一个有序对(V，E)，其中V是一个证明设A、B、C、D、E、F是K6的六个顶点。假设不存在同色非空集合，称为顶点集或点集，其元素称为顶点或点，元素个数称三角形，考虑以A为端点的边AB、AC、AD、AE、AF，由抽屉原理(又为阶数。E是由V中的点组成的无序点对构成的集合，称为边集

3、，称鸽巢原理，把多于n个物品放到n个抽屉里，至少有一个抽屉里其元素称为边。同一点对在E中可出现多次，其出现的次数称为的物品不少于两件)知这五条边至少有三条颜色相同，不妨就设为这条边的重数，重数大于1的边称为重边。AB、AC、AD，且它们都染成红色。由于不存在同色三角形，故BC、图G的顶点集记为V(G)，边集记为E(G)。图G的阶数和边BD、CD都不是红色。也就是说△BCD三边都不是红色，那么它就数可分别用符号n(G)和m(G)表示。对于u，v∈V，如果(u，v)∈E，是蓝色的三角形，矛盾。故结论成

4、立。则称u和v相邻，记e=uv=(u，v)，称u和v是e的端点，u、v与e相3一些Ｒamsey数的范围关联。若两条边有一个共同的端点，则称这两条边相邻。不与任何虽然Ｒ(3，3)的证明十分巧妙，但是实际上已知的Ｒamsey数边相关联的点称为孤立点。两端点重合的边称为环(也称自环)。非常少，比如Ｒ(3，3)=6，Ｒ(3，4)=9，Ｒ(4，4)=18。已知染色种点集与边集均为有限集合的图称为有限图。只有一个顶点而数超过两种的仅有的非平凡Ｒamsey数为Ｒ(3，3，3)=17。著名数学家保罗·艾狄胥曾以一

5、个故事来描述寻找Ｒamsey数的难度:无边的图称为平凡图。边集为空的图称为空图。既没有环也没有“想像有队外星人军队在地球降落，要求取得Ｒ(5，5)的值，否重边的图称为简单图。其他所有的图都称为复合图。则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家(2)定义设有两个图G=(V，E)和G=(V，E)，若在其111222尝试去找这个数值。若它们要求的是Ｒ(6，6)的值，我们就要尝试顶点集合V1和V2之间存在双射f，使得对于任意的u1v1∈V1有:毁灭这班外星人了。”u1v1是G1的k重边当且仅

6、当f(u1)f(v1)是G2的k重边(k≥0)，则有了Ｒamsey定理，便可以证明之前的题目。仍然用反证法。称两图同构，记为G1G2。求证Ｒ(3，3，3)≤17。即证:K17三染色，必有同色三角形。图的同构是一个等价关系，两个同构的图有相同的结构，差异证明不妨设三种颜色为红、黄、蓝。将17个顶点记为A1，只是顶点和边的名称不同。因此，一般情况下可以将同构的图看A2，…，A17。假设不存在同色三角形，考虑A1以为端点的边A1A2，作相同的图。AA，…，AA，由抽屉原理可知这16条边至少有6条同色，

7、不妨13117(3)定义任意两点均相邻的简单图称为完全图，在同构意设A1A2，A1A3，…，A1A7同为红色。由于不存在同色三角形，故以义下n阶完全图只有一个，记为Kn。A，A，…，A237为顶点的k6中不可能有任何一条边染成红色，也即接下来介绍Ｒamsey数。只有蓝色和黄色，由Ｒamsey定理知，该k6中一定存在同色三角(4)定义Ｒamsey数Ｒ(a，b)是指满足如下性质的最小正整形，矛盾。故结论成立。数r:将r阶的完全图Kr的所有边用红、蓝两种颜色进行着色，无4Ｒ(3，3，…，3)的一个上界论

8、如何进行着色，图中都必定存在红色Ka或蓝色Kb。我们刚刚讨论的题目显然是Ｒamsey定理更进一步的结论。由定义很容易看出，a，b的位置可以互换，即Ｒ(a，b)=Ｒ(b，本文的目的是推广Ｒamsey。a)。下面来计算Ｒ(2，n)的值。如果将n阶的完全图Kn的所有边定理，找到Ｒ(3，3，…，3)(n个3)的一个上界f(n)。也就是用红、蓝两种颜色进行着色，并且不能出现红色K2(这里注意K2说，将Kf(n)染上n种颜色，一定存在同色三角形。通过观察和计算，就是一条边，也就是说不出现任何红