学位论文 > 优秀研究生学位论文题录展示

关于偶数轮的Ramsey数

作　者: 李婷
导　师: 于洪全
学　校: 大连理工大学
专　业: 基础数学
关键词: Ramsey数星图轮图道路正则图极值图
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 51次
引　用: 0次
阅　读: 论文下载

内容摘要

Ramsey数的定义最早是由英国数学家Ramsey在1928年提出的,它是描述在任何离散结构中,只要”结构”充分大就必然存在某种特殊的子部分,这一定义随后被Gramham,Roth-schild和Spencer发展成为Ramsey理论.图的Ramsey数是Ramsey数理论的推广,它作为图论当中一个著名难题一直备受瞩目,其在图论中的研究已经迅速的发展起来。关于图的Ramsey数R（G₁,G₂）是指对于给定的图G₁,G₂存在一个最小正整数n,使得对任意一个阶为n的图G,要么G包含G₁,要么G的补图包含G₂。 Ramsey数的验证是一个比较艰难的过程,尤其是验证两个阶数都比较大的图形G_n和G_m之间的Ramsey数,但若其中一个图的阶数比较小的话问题就变得容易解决了。在这篇文章里我们将继续讨论阶数比较小的图与图之间的Ramsey数,着重讨论了星图对偶数轮的Ramsey数。星图对轮图的Ramsey数的研究是最近几年图的Ramsey数的主要研究方向,到目前为止只得到了星图对于奇数轮的所有结果,以及星图对W₄和W₆的结果。星图对奇数轮及星图对W₆的Ramsey数结果是由张克民等人在2004年验证的,他们在证明的过程中应用了几个重要的引理,而这几个引理只能对于证明W₆有帮助,无法将其运用到证明其他阶数的偶数轮当中,因此在本文中我们引进了另一种证明方法得出星图对阶为8和10的偶数轮的结果。本文运用的是构造对称极值图的方法,验证了在各种极值图情况下给定的数可以满足Ramsey数的要求,进而验证了在非极值图的情况下给定的数同样也满足Ramsey数的条件。构造对称极值图的最初想法是想将某一个阶数比较小的图形的所有情况列举出来,结果发现利用极值图的情形可以证明。文中的极值图有很多是正则图,而K-正则图构造方法又有很多种,但经验证可以得到无论何种结构下的K-正则图均可以满足Ramsey数的条件,因此我们选择了构造对称极值图的方法。文中是将给定阶数的某一个图按照连通图与非连通图的情形来讨论,而非连通图又分为有无孤立点的情形。讨论非连通图时将图分成几个连通分支来考虑,这其中每个连通分支首先都必须是极值图,其次它们的阶数是依次增大的。由于阶数和极值图的限制,阶数比较小的连通分支构造出的极值图实际上就是完全图。在构造出极值图之后我们要在其中一个或几个连通分支选取满足条件的点构成轮图,需要选取的点越多选取的难度就越大。因此本文只验证了W₈和W₁₀的结果,而对于W_m,m≥12的情形还未得到验证。本文的结构大体如下: 第一章我们首先回顾了Ramsey数的发展历程,理论价值和研究方法。第二章首先介绍了文中所用的各个定义的内容,定义了验证过程中最为重要的极值图的内容,同时对比了Ramsey数的原始定义及在图论中的定义,随后还总结了一些已

关于偶数轮的Ramsey数

内容摘要

全文目录

相似论文