论文部分内容阅读
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数的相应结果。