Ramsey理论中图的构造与计算

论文摘要

Ramsey理论是组合数学中的一个重要分支,在通信、计算机信息检索和决策学等方面有一系列的具体应用,近年来在与其他数学分支的相互渗透中得到了迅猛的发展。Ramsey数,Ramsey重数和Folkman数是Ramsey理论的重要研究对象,目前只有很少的Ramsey数,Ramsey重数和Folkman数的精确值被确定,人们知道的上下界大多相距很远,进一步的工作,即使是给出较好的上下界,面对的都是非常巨大的计算量。本文对Ramsey理论中的若干问题作了相关的研究,讨论了经典Ramsey数、广义2色Ramsey数、路与圈的3色Ramsey数、Ramsey重数和Folkman数等有关问题,主要研究内容如下:（1）研究Ramsey图的性质有助于寻找新的Ramsey图,以改进Ramsey数的下界。本文研究了Ramsey图与准正则图之间的关系,提出了用构造准正则图的方法寻找新的Ramsey图,特别是（5,5）-图;验证了（5,5）Ramsey图中不存在强正则自补图;通过寻找满足一定条件的同构的子图,得到了三个经典Ramsey数R（6,8）,R（7,9）和R（8,17）的新下界129,235和937。（2）确定小的R（Cm,Bn）,R(Km,n,Kp,q)型Ramsey数以及R（Bm,Bn）的精确值是一个非常困难的问题,目前也都只得到了其中很少的精确值。本文通过计算得到了若干R（Cm,Bn）的值,计算得到R（B3,B4）=15,利用正则图得到了R(K2,5,K2,9),R(K2,6,K2,9),R(K2,7,K2,9)的新下界,从而确定了其精确值。（3）对于3色的广义Ramsey数,对3色圈,路以及圈和路混合形式的Ramsey数研究较多,目前只得到了若干小的圈和路混合形式的Ramsey数的精确值,以及R（P3,Ck,Ck）,R（P3,P4,Ck）,R（P3,P5,Ck）和R（P4,P4,Ck）的精确值。本文利用计算机和数学证明相结合,得到了一些新的路,以及圈和路混合形式的Ramsey数,以及若干R（P4,P5,Ck）和R（P4,P6,Ck）的精确值。（4）2002年,S.P.Radziszowski和Kung-Kuen Tse给出R（C4,K9）≤33,R(C4,K10)≤40。本文将R（C4,K9）和R（C4,K9）的上界分别改进为32和39,并得到了若干C4对完全图的多色Ramsey数的上下界。（5）图G的重数M（G）定义为:对KR（G,G）的所有可能的边2-着色中,含有单色子图G的最少的个数。直到2001年,人们才求出了了4阶的Ramsey重数的精确值,其中,M（K4）的精确值直到2001年才被解决。本文通过计算机算法,求得了17个5阶图的Ramsey重数精确值,通过模拟退火算法得到了5个5阶图的Ramsey重数的上界。（6）本文研究了一些Folkman图的性质和算法,通过计算得到了Fv（3,5;6）,Fv（3,6;7）,Fv（3,7;8）和Fv（3,8;9）的新上界,分别为16,18,22和23。并给出了Fv（3,k;k+1）类型的Folkman数的新上界公式;将Fv（4,4;5）新的上界由25改进到23,下界由16改进到17;证明了当k≥4时,Fv（k,k;k+1）≥4k-1;给出了Fe（3,4;5）的下界22。（7）引进了多重图的Ramsey数的概念,并对它进行了系统的研究,推广了许多关于经典Ramsey数的相应结果。

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 研究背景
• 1.2 研究目的
• 1.3 图的Ramsey理论简史与研究现状
• 1.4 研究思路与创新点
• 1.5 图论的基本概念
• 1.6 研究内容与组织结构
• 2 几个经典Ramsey数的下界
• 2.1 强正则自补图与Ramsey数R（5,5）
• 2.2 准正则图与Ramsey数
• 2.3 R（6,8）,R（7,9）和R（8,17）的新下界
• 2.4 本章小结
• 3 广义2色Ramsey数的计算
• m,B_n）的精确值'>3.1 若干Ramsey数R（C_m,B_n）的精确值
• m,n,K_p,q)的精确值'>3.2 若干Ramsey数R(K_m,n,K_p,q)的精确值
• 2,B₃）和R（B₃,B₄）的精确值'>3.3 Ramsey数R（B₂,B₃）和R（B₃,B₄）的精确值
• 3.4 本章小结
• 4 广义多色Ramsey数
• 4.1 若干路与圈的3色Ramsey数的精确值
• 4对K_n的Ramsey数的上下界'>4.2 C₄对K_n的Ramsey数的上下界
• 4.3 本章小结
• 5 Ramsey重数的计算
• 5.1 Ramsey重数精确值的计算
• 5.2 Ramsey重数的上界
• 4;43）的上界'>5.3 M（K₄;43）的上界
• 5.4 本章小结
• 6 若干Folkman数的上下界
• v（4,4;5）的界'>6.1 F_v（4,4;5）的界
• v（3,k;k+1）的上界'>6.2 F_v（3,k;k+1）的上界
• v（k,k;k+1）的下界'>6.3 F_v（k,k;k+1）的下界
• v（2,3,3;4）和F_v（2,2,2,3;4）的界'>6.4 F_v（2,3,3;4）和F_v（2,2,2,3;4）的界
• e（3,4;5）的下界'>6.5 F_e（3,4;5）的下界
• 6.6 本章小结
• 7 经典Ramsey数的多重图推广
• 7.1 简单图的Ramsey数推广到多重图的Ramsey数
• k^k-1（q）的下界和Alon等人的一篇文章'>7.2 f_k^k-1（q）的下界和Alon等人的一篇文章
• 7.3 本章小结
• 8 总结与展望
• 8.1 全文总结
• 8.2 尚待研究的工作
• 致谢
• 参考文献
• 附录1 攻读学位期间发表的学术论文
• 附录2 博士学位论文章节内容与博士期间发表论文的关系