扇形图与匹配图的临界星图Ramsey数

对于完全图Kn和一个额外的顶点v,通过在v与Kn之间添加k条边所得出的图,记为KnK1,k.设G和H是任意的图,临界星图Ramsey数r*(G,H)定义为最小的正整数k,使得图KN-1K1,k的任意红蓝2-边着色,或者存在单色的红色子图G,或者存在单色的蓝色子图H,这里N指的是Ramsey数r(G,H).文中找到了r(Fn,mK2)的所有临界图,利用这些临界图得到了临界星图Ramsey数r*(Fn,mK2)=m+1,nm≥1,以及r*(Fn,mK2)=2 m,n≤m,这里Fn=K1+nK2是扇形图.     

圈与K4的临界完全图Ramsey数

对给定的2个图G和H,Ramsey数r(G,H)是最小的正整数r,使得对完全图Kr的边任意红蓝着色或存在红色子图G、或存在蓝色子图H.临界完全图Ramsey数r_K(G,H)是最大的正整数n,使得图K_r-K_n的边任意红蓝着色或存在红色子图G或存在蓝色子图H.当正整数n≥5时,r_K(C_n,K_4)=n/2,C_n为n个点的圈.     

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

关于图的Ramsey数的几个下界

推广了3个C4对完全图的R am sey数下界以及一个经典R am sey数下界问题,得到了3个C4对完全图的R am sey数的线性下界,以及一个关于多项式的经典R am sey数下界.     

一些扫帚图的Ramsey数

给定图G,Ramsey数R(G)是最小的正整数N,满足对完全图K_N的边任意红蓝着色,则或者存在红色子图G或者存在蓝色子图G.扫帚图B_(k,m)是将星图K_(1,k)的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时,R(B_(k,2k-1))=4k-2且R(B_(k,4))=2k+3.     

用循环图计算的Ramsey下界数

利用计算机,构造了既不含５－点团也不含１３－独立点集的１３９项点循环图,从而求得了二色Ｒａｍｓｅｙ数Ｒ（５,１３）的新下界：Ｒ（５,１３）≥１４０。     

完全图的循环图分解和5个Ramsey数的下界

研究了素数阶完全图分解为循环图的方法 ,给出了计算它的子图的团数的一种算法 ,得到2个三色 ,3个四色Ramsey 数的新的下界 :R(3,4,18)≥458,R(3,6,19)≥882,R(3,3,4,15)≥770,R(3,3,4,16)≥812,R(3,3,5,16)≥1124。     

Petersen图的反Ramsey数

给出Petersen图的反Ramsey数AR（n,P）的上下界.若n≤9,则AR（n,P）=n（n-1）/2.若n≥10,则当n为奇数时,t（n,2）＋2≤AR（n,P）≤t（n,8）＋1;当n为偶数时,t（n,2）＋3≤AR（n,P）≤t（n,8）＋1.     

K2,t+1和K1,n的Ramsey数

本文得到了一个较T.D.Parsons[3]的R(C4,K1,n)更为一般的R(K,t+1,K1,n)的结果.     

关于Ramsey数下界的一个注记

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

关于圈对完全图的多色Ramsey数

证明了关于k个偶圈对完全图的多色Ramsey数的上界.     

关于完全三部图的Ramsey数

该文对完全三部图的Ramsey数r(kt,m,n,kn)的上界进行了研究。将自然数集划分为2类集合{n′}和{n″},用高斯超几何函数表示独立数的下界。证明了r(Kt,m,n,Kn)=O[nm+t+1/(logn)m+t]。     

一些Ramsey数的下界

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

关于全着色Ramsey数

以χ２（Ｇ）记一图Ｇ之全色数,全着色Ｒａｍｓｅｙ数χ２（ｍ,ｎ）为最小正整数ｐ,使得每一ｐ阶图Ｇ或有χ２（Ｇ）≥ｍ,或其补图Ｇ满足χ２（Ｇ）≥ｎ。本文给出χ２（ｍ,ｎ）的上、下界     

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

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

Ramsey数和无三角的Cayley图

记Zn={0,1,…,n}为模n的整数加群,Z*n=Zn\{0}.对一个Z*n逆元封闭的子集A,定义Cayley图Gn(A)为:其点集为Zn,而{x,y}是一条边当且仅当|x-y|∈A.计算了这些Cayley图的独立数至n≤258,改进了Ramsey数r(3,q)的的下界,27≤q≤38.     

对角Ramsey数R(k,k)的新下界

研究了自补图Ｇｐ的一些性质，提出新的算法，得到３个对角Ｒａｍｓｅｙ数的新下界：Ｒ（１７，１７）≥８９１７，Ｒ（１８，１８）≥１１００５，Ｒ（１９，１９）≥１７８８５。