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,6;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数的相应结果。