关于偶数轮的Ramsey数

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:lhchg1982
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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.
其他文献
本文主要研究了一类二阶阻尼非线性微分不等式:x(t)[(a(t)x(t))+q(t)φ(x(t),x(t))+p(t)f(x(t))]≤0(*)解的振动性. 文章总假设下列条件成立:(i)a∈C[[t0,∞),R+],q∈C[[t0,∞),R+
在财产保险中,保费厘定的主要依据之一是经验比率表,而经验比率表又与历史索赔次数息息相关。本文是在频率风险模型中引入随机效应的概念,把混合泊松分布的参数用随机效应和一个
信息技术教育不单是课程目标的变革,更是学习方法的革新。作为目前普遍使用的任务驱动教学法,如何对学生学习进行反馈检测,如何保证学生学习的有效性,如何及时对学生进行评价
偏微分方程来源于各种实际问题,在许多物理、化学、生物乃至经济学等学科中都有实际应用。波动方程和板方程是两类很重要的偏微分方程,它们来源于许多振动现象,对于线性波动方程
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
本刊第一期在“问题讨论”专栏发表了邵道生同志的文章“怎样监督‘第一把手’”,《人民日报》主办的人民网1月12日转载此文后引起众多网民的强烈反响,参与讨论的有350多条意
本文对匹配与覆盖及其应用进行了研究。文章讨论了生产一种锁具,符合一定的条件的锁具分为一批,并且60个分为一箱,顾客购买多少箱不会出现互开现象,然后根据相关知识得以解决.第
班级管理是学校管理工作的基本组成单位,班级管理事关班级工作好坏的重要环节.良好的班级制度管理可以有效地调动学生的学习动力,帮助教师更好的完成教学目标,在班级构建过程
本文对ω-超可微函数空间ε中的卷积运算进行了研究。文章指出,上世纪五十年代以来,由于广义函数的出现,使偏微分方程的理论有了突飞猛进的发展。从六十年代起,出于不同问题的需
本文回顾了线性模型理论的基础知识,并将统计判决理论中的minimax估计问题在带约束条件和不带约束条件下的线性模型中在损失函数为二次损失下的minimax估计和最大风险问题进行