关于临界Ramsey分解

本文在给出分解,Ramsey分解和临界Ramsey分解定义后,导出有关上述分解的某些性质和Ramsey数的下界公式．     

一些Ramsey数的下界

确定Ramsey数一直是图论中的一个难题。讫今为止,已被确定的Ramsey数亦为数不多。有关Ramsey数的一些著名结果是关于它的界限的。本文通过群论的方法,得到了一些Ramsey数的下界,在一定条件下,它们比已知的著名结果要好。     

推广的 Ramsey 数的上界估计

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

Ramsey数的下界

本文由构造循环图得到 Ramsey 数 r(3,q)的下界渐近公式,并且在 Ramsey 循环图的基础上构图,改进了 Ramsey 数 r(3,10)和 r(3,12)的下界。     

12个经典二色Ramsey数R(k,l)的新下界

二色经典Ramsey数R(k,l)是指具有下述性质的最小正整数r:用两种颜色把r 阶完全图Kr的边任意染色后, Kr中一定存在单色的Kk或Kl, 其存在性的证明并不困难,但具体的Ramsey数的计算却是组合数学中非常困难的问题[1]. 当今学术界关于Ramsey数研究的最新进展详见文献[2]动态综述论文.本文沿用文献[3～7]的方法,构造12个素数阶循环图,得到12个二色经典Ramsey数的新下界.研究简报如下.     

用构造性方法计算多重图Ramsey数的界

在图的边染色问题中,通常考虑的是每条边染且只染一种颜色.边的集染色是这种边染色的一种推广,使每条边对应的不一定是一种颜色,而是给定的颜色集的一个子集.多重图的边染色与边的集染色是等价的.多重图Ramsey数是经典Ramsey数的一种自然的推广,它是通过把完全图的边染色推广到完全多重图的边染色实现的.计算Ramsey数的准确值是NP难题,求多重图Ramsey数的准确值往往更加困难.用一些研究经典Ramsey数的方法来研究2-多重图Ramsey数的界,利用构造性方法证明了一些关于不同参数的2-多重图Ramsey数的不等式,并在此基础上得出了一些小参数多重图Ramsey数的准确值或上下界.     

关于Ramsey数下界的一个注记

Ramsey理论是组合论中的一个重要内容，但确定Ramsey数R(k，f)是非常困难的．给出了Ramsey数R(k1，k2，…，km)的一个下界公式；同时也指出了2002年《数学的实践与认识》上某论文中的一些错误。     

生成二色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上界研究

对于无向有限简单图G和H,边Ramsey数R(C,H)是指最小的整数e,使得对一个有e条边的图的边用红蓝两色进行2-染色后要么得到一个红色的G,要么得到一个蓝色的H.通过分支定界法,得到一些边Ramsey数的上界.     

临界完全图Ramsey数

设G和H是任意的图,Ramsey数r(G,H)定义为最小的正整数r,使得图Kr的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.临界星图Ramsey数r_*(G,H)为最小的正整数n,使得图Kr-K_(1,)r_(-1-)n的任意红蓝二边着色或存在单色的红色子图G,或存在单色的蓝色子图H.在临界星图启发下,临界完全图Ramsey数rK(G,H)定义为最大的正整数n,使得图Kr-Kn的任意红蓝二边着色或存在单色的红色子图G或存在单色的蓝色子图H.这里r为Ramsey数r(G,H).确定了rK(W_(1,)n,K_3)和rK(Cn,K_3),其中W_(1,)n=K_1+Cn为轮.     

(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数的若干定理及其推广

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

用图的分割原理计算一些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)图．     

$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图中可能存在的自由边的算法

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)。     

书图和扇形图的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.