关于偶数轮的Ramsey数

摘要

Ramsey数的定义最早是由英国数学家Ramsey在1928年提出的，它是描述在任何离散结构中，只要”结构”充分大就必然存在某种特殊的子部分.这一定义随后被Gramham,Roth-schild和Spencer发展成为Ramsey理论.图的Ramsey数是Ramsey数理论的推广，它作为图论当中一个著名难题一直备受瞩目，其在图论中的研究已经迅速的发展起来.关于图的Ramsey数R(G1，G2)是指对于给定的图G1，G2存在一个最小正整数n，使得对任意一个阶为n的图G，要么G包含G1，要么G的补图包含G2.Ramsey数的验证是一个比较艰难的过程，尤其是验证两个阶数都比较大的图形Gn和Gm之间的Ramsey数，但若其中一个图的阶数比较小的话问题就变得容易解决了. 在这篇文章里我们将继续讨论阶数比较小的图与图之间的Ramsey数，着重讨论了星图对偶数轮的Ramsey数. 星图对轮图的Ramsey数的研究是最近几年图的Ramsey数的主要研究方向，到目前为止只得到了星图对于奇数轮的所有结果，以及星图对W4和W6的结果.星图对奇数轮及星图对W6的Ramsey数结果是由张克民等人在2004年验证的，他们在证明的过程中应用了几个重要的引理，而这几个引理只能对于证明W6有帮助，无法将其运用到证明其他阶数的偶数轮当中.因此在本文中我们引进了另一种证明方法得出星图对阶为8和10的偶数轮的结果. 本文运用的是构造对称极值图的方法，验证了在各种极值图情况下给定的数可以满足Ramsey数的要求，进而验证了在非极值图的情况下给定的数同样也满足Ramsey数的条件.构造对称极值图的最初想法是想将某一个阶数比较小的图形的所有情况列举出来，结果发现利用极值图的情形可以证明.文中的极值图有很多是正则图，而K-正则图构造方法又有很多种，但经验证可以得到无论何种结构下的K-正则图均可以满足Ramsey数的条件，因此我们选择了构造对称极值图的方法. 文中是将给定阶数的某一个图按照连通图与非连通图的情形来讨论，而非连通图又分为有无孤立点的情形.讨论非连通图时将图分成几个连通分支来考虑，这其中每个连通分支首先都必须是极值图，其次它们的阶数是依次增大的.由于阶数和极值图的限制，阶数比较小的连通分支构造出的极值图实际上就是完全图.在构造出极值图之后我们要在其中一个或几个连通分支选取满足条件的点构成轮图，需要选取的点越多选取的难度就越大.因此本文只验证了W8和W10的结果，而对于Wm，m≥12的情形还未得到验证.本文的结构大体如下： 第一章我们首先回顾了Ramsey数的发展历程，理论价值和研究方法. 第二章首先介绍了文中所用的各个定义的内容，定义了验证过程中最为重要的极值图的内容，同时对比了Ramsey数的原始定义及在图论中的定义，随后还总结了一些已经得到的有关星图对轮图的Ramsey数，树对轮的Ramsey数及道路对轮图的Ramsey数，如下(其中Sn代表阶为n的星图，Wm代表阶为m+1的轮图)：定理：R(Sn，W6)=2n+1，n≥3和R(Sn，Wm)=3n-2，n≥m-1≥2，m为奇数； 这一定理是由张克民等人在2004年得到的，他们只得出了星图对奇数轮和W6的结果.在第二章中我们将利用本文所运用构造极值图的方法再一次证明R(Sn，W6)=2n+1，n≥3的结论，同时也说明了构造对称极值图这一方法的可行性.第三章是本文的重要章节，在这里我们将星图对阶为偶数的轮的Ramsey数作了进一步的推广，得到了星图对W8和W10Ramsey数的结论，如下：定理1：R(Sn，W8)=2n+1，n≥6定理2：R(Sn，W10)=2n+1，n≥8 这一章中我们将全部运用构造对称极值图方法进行详细地证明. 最后在第四章中还证明了阶数比较小的道路对轮的Ramsey数的几个结论，这一章的证明方法与前文的不同，主要是因为这里面的道路的阶数都比较小，因此只要能找到几个特殊的图形就可以说明Ramsey数是否成立.我们得到的结论如下：定理3：R(P2，Wn)=n+1，n≥6，定理A：R(P3,Wn)={n+1n≥8,n是偶数n+2n≥9,n是奇数，定理5：R(P4,Wn)={n+2n≡0,2(mod3),n≥11n+3n≡1(mod3),≥10.

目录

文摘

英文文摘

独创性说明及大连理工大学学位论文版权使用授权书

1 绪论

2 Ramsey数的预备知识

3 星图对偶数轮的Ramsey数

4 道路对偶数轮的Ramsey数

参考文献

攻读硕士学位期间发表学术论文情况

致谢