Ramsey极图的性质

本文在引进Ｒａｍｓｅｙ数Ｒ（ｍ，ｎ）的饱和极图Ｇ（ｍ，ｎ）的概念后，证明了Ｇ（３，ｎ）中每个顶点必至少是一个五边形的顶点以及Ｇ（３，ｎ）中至少含有个互不相交的五边形等定理；最后还证明了一个新的下界定理，从而改进了一批Ｒａｍｓｅｙ数的下界，例Ｒ（４，１５）≥１２２，Ｒ（５，９）≥９９等．     

二边色图K35（3,9）的生成

ｎ 个顶点的完全图Ｋｎ ,用红色或蓝色对其边着色,得Ｋｎ 的二边色图．当Ｋｎ 的这种红蓝二边染色既不包含红色团Ｋ３ ,又不包含蓝色团Ｋｐ ,则将由Ｋｎ 经这种染色所得的图记为Ｋｎ （３,ｐ）．如果把Ｋｎ （３,ｐ）成立的最大ｎ 值记为Ｒ（３,ｐ）,那么形如ＫｉＲ（３,ｐ ） （３,ｐ）（ｉ＝ １,２,…,ｍ ,ｍ １）的一系列二边色图称为Ｒａｍ ｓｅｙ 极图,与形如ｒ（３,ｐ）的Ｒａｍ ｓｅｙ 数相关,即Ｒ（３,ｐ）＝ ｒ（３,ｐ）－ １．本文给出了Ｋ３５ （３,９）的一种构造,因而得到ｒ（３,９）３６     

经典Ramsey数R(7,n)的5个下界

通过计算机构造了５个完全图的新的循环图分解,从而获得了Ｒａｍｓｅｙ数Ｒ（７,１８）,Ｒ（７,１９）,Ｒ（７,２０）,Ｒ（７,２１）和Ｒ（７,２２）的下界．这５个结果填补了Ｒａｍｓｅｙ数研究的５个空白．     

经典Ramsey数R(5,18)、R(5,23)和R(5,26)的新下界

构造了３个新的素数阶循环图．从而得到了３个Ｒａｍｓｅｙ数的新下界：Ｒ（５，１８）≥２８２，Ｒ（５，２３）≥４３２，Ｒ（５，２６）≥４６４．     

6个Ramsey数R（3,3,q）的新下界

研究了正则的素数阶循环图，提出了计算多色Ｒａｍｓｅｙ数Ｒ（ｑ１，ｑ２，…，ｑｎ）的下界的一种算法，得到了６个３色Ｒａｍｓｅｙ数的新下界：Ｒ（３，３，１０）≥９８，Ｒ（３，３，１３）≥１７４，Ｒ（３，３，１５）≥１９８，Ｒ（３，３，１６）≥２５２，Ｒ（３，３，２１）≥４１０，Ｒ（３，３，２３）≥４３２。     

5个素数阶完全图的循环图分解

研究了素数阶完全图分解成若干个循环图的方法，给出了这个完全图子图团数的算法获得了２个三色和３个四色Ｒａｍｓｅｙ数的新下界：Ｒ（３，４，８）１３８，Ｒ（３，６，１４）５７０，Ｒ（３，３，５，８）４０２，Ｒ（３，３，６，１３）１０１０，Ｒ（３，４，５，１４）１２１８     

经典Ramsey数R(8,18)、R(8,19)和R(8,20)的下界

通过计算机构造了３个新的循环图,从而获得Ｒａｍｓｅｙ数的３个下界：Ｒ（８,１８）≥６１８,Ｒ（８,１９）≥６６２,Ｒ（８,２０）≥７５２．这些结果填补了Ｒａｍｓｅｙ数研究的３个空白．     

6个多色Ramsey数的下界

研究了素介完全图ＫＰ的边的ｎ－染色,给出了计算它的子图Ｇｐ（Ｓｉ）的团数的一种算法,得到２个三色,４个四色Ｒａｍｓｅｙ数的新的下界。     

一个实用的检验Kn(3,p)的算法

设Ｋｎ是ｎ个顶点的完全图，若对Ｋｎ的每条边着以红色或蓝色，并且图中既不包含红色团Ｋ３也不包含蓝色团Ｋｐ，这样就得到一个二色边图Ｋｎ，同时将这种染色所得的图记为Ｋｎ（３，ｐ），把使Ｋｎ（３，ｐ）成立的最大值记为Ｒ（３，ｐ），Ｒ（３，ｐ）＝ｒ（３，ｐ）－１，ｒ（３，ｐ）是Ｒａｍｓｅｙ数，本给出一个实用的算法，可以对给定连通图检验Ｋｎ（３，ｐ）是否成立 。     

5个新的素数阶循环图

通过计算机构造了５个新的素数阶循环图,从而获得了Ｒａｍｓｅｙ数的５个下界：Ｒ（６,１３）≥２４２,Ｒ（８,１７）≥６０２,Ｒ（８,１８）≥６４２,Ｒ（８,１９）≥６８４,Ｒ（８,２０）≥７６２．这些结果填补了Ｒａｍｓｅｙ数研究的５个空白．     

(3,11,45)-Ramsey图的递阶构造

给出了10-正则循环(3,11,45)-Ramsey图的一个递阶生成构造.该正则循环图的弦长序列是:1,3,5,12,19.同时证明了拉姆赛数R(4,5) 46.进一步,我们发现了一个有趣的结果,作为(3,11,45)-Ramsey图的一个子图(3,10,38)-Ramsey图,改变(3,10,38)-Ramsey图的4条Ramsey临界边,该图将变为另一个10正则的循环(3,10,38)-Ramsey图.该正则循环图的弦长序列也是:1,3,5,12,19.     

推广的 Ramsey 数的上界估计

设f1,f2,…,fk是关于图的一些参数.该文运用归纳法给出了一般化的Ramsey数r(f1≥n1,f2≥n2,…,fk≥nk)一个一般的上界估计.同时讨论了混合Ramsey数叭v(f;m;H)在一定条件下的一个上界,并给出了在取特殊参数xF情况下混合Ramsey数的一个准确表达式.     

关于Ramsey数的若干定理及其推广

章主要应用概率中的一些基本知识讨论了几个关于Ramsey数的定理并对它们进行了推广。     

生成二色Ramsey图R（3，p）的基本元方法

构造二色Ramsey极图其复杂度是NP完全难的问题。通过生成Kn(3,p)阶图（见献[1]以期获得阶最大极图R（3,p）（Kn,(3,p)≤R（3,p)=r(3,p)-1。本给出了一种生成Ramsey图R（3,p）的基本生成元方法。     

用图的分割原理计算一些Ramsey数

Ramsey数R(G,H)为最小的正整数N,使得对完全图KN的边集的任意红蓝二着色,都存在红色的子图G或者蓝色的子图H.结合Burr的一个定理和图的分割原理,证明当n≥|G|2+2χ(G)α(G)时,R(Pn,G)=(χ(G)-1)(n-1)+σ(G).     

Ramsey数 r(3,q)中的新下界

我们利用计算机来构造既没有三角形又没有q个顶点的独立集的循环图。当q=14、15、16,17时,由我们构造的循环图得到Ramsey数的四个新下界: r(3,14)≥64; r(3,15)≥73; r(3,16)≥79; r(3,17)≥88。     

拉姆齐图R(4,5)的递阶生成

对于已知经典的拉姆齐数，其对应的拉姆齐图R(3，3)，R(3，4)R(3，5)，R(3，6)，R(3，7)，R(3，8)和R(3，9)均可递阶生成．给出了一个通过R(4，4)图递阶生成的一个R(4，5)拉姆齐图，证明了R(4，5)≥25．同时发现修改所构造的R(4，5)图的10条拉姆齐临界边，该图将变为经典10-正则的R(4，5)图．     

一个查找二色Ramsey图中可能存在的自由边的算法

Kn(s,t)定义为一个正整数n,同时存在一个由二色边构成简单完成图Kn,使得Kn中既不存在单色完全子图Ks和单色子完全子图Kt,在Ramsey图Kn(s,t)中一条自由边定义为,即使单独改变这条边的颜色,所得到的新图仍是一个二色Ramsey图Kn(s,t)。本基于作在献[2]中给出的算法,提出一个新算法,该算法可以找出一个给定Ramsey图Kn(s,t)中的所有可能的自由边,并简要分析了其时间复杂性。对于一个已有的Ramsey图Kn(,s,t),利用该算法可能找出其他Ramsey图Kn(s,t)。     

$P_n$和$C_n^k$的Ramsey数

称Fk为图F的k幂次图,如果V(Fk)=V(F),且Fk中的任意两个顶点相邻当且仅当在F中的距离至多为k.给定图G和H,Ramsey数R(G,H)为最小的正整数N,使得完全图KN的任意红蓝-边着色都会含有一个红色的子图G或者蓝色的子图H.证明了渐近阶R(Pn,Ckn)=(n-1)(χ(Ckn)-1)+σ(Ckn)+o(n),其中k是常数.     

书图和扇形图的Ramsey数

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,或者存在红色子图G,或者存在蓝色子图H.用G+H表示两个不交的图G和H之间完全连边所得到的图.设Bm=K2+mK1,Fn=K1+nK2.证明了当m≥1且n≥max{2,3 m-2},R(Bm,Fn)=4n+1;当n≥38,R(F2,K2,n)=2n+3.