9个经典Ramsey数R(3,t)的新下界

本文研究了经典Ramsey数R(3,t)的下界问题.利用素数阶循环图的性质改进一般阶循环图团数的计算方法,获得了9个经典Ramsey数R(3,t)的新下界:R(3,29)≥183,R(3,30)≥189,R(3,32)≥213,R(3,33)≥218,R(3,34)≥226,R(3,35)≥231,R(3,36)≥239,R(3,37)≥244,R(3,38)≥256,其中前三个结果分别改进了迄今已知的最好的下界,后6个结果是本文首次报道的.     

关于Ramsey数下界的部分结果

本文得到 Ramsey数下界的一个计算公式 :R( l,s+ t-2 )≥ R( l,s) + R( l,t) -1 ,(式中 l、s、t≥ 3) .用此公式算得的 Ramsey数的下界比用其它公式算得的下界好 .     

7个经典Ramsey数R(k,l)的新下界

利用构造性的方法,得到7个经典Ramsey数的新下界R(3,29)≥174,R(4,23)≥272,R(5,24)≥488,R(7,12)≥312,R(8,18)≥728,R(8,20)≥860,R(9,21)≥1278.     

多色经典Ramsey数(Rn{q,q,…,q)的下界

提出了探求n色经典Ramsey数(Rn{q,q,…,q)的下界的一种方法,并用这种方法借助计算机求得6个新的下界:R4(4)≥458,R3(5)≥242,R3(6)≥1 070,R3(7)≥1 214,R3(8)≥2 834以及R3(9)≥5 282.     

Ramsey数R(K_3,K_(16)-e)的一个下界

图论方法是研究Ramsey理论中最常用的方法,80多年的研究产生了大量的成果.Ramsey数R(G,H)是这样的最小正整数n,使得完全图K_n的边的任何一种红、蓝染色都会有一个红色边子图G,或者有一个蓝色边子图H.本文找到Ramsey数R(K_3,K_(16-e))的一个下界.     

树图对完全图的多色Ramsey数

首先证明了关于一般图的多色Ramsey数的一个下界,该下界是一类星图对完全图的多色Ramsey数的精确下界;其次证明了关于星图对完全图的多色Ramsey数的上界,该上界是一类星图对完全图的多色RamSey数的精确上界;最后证明关于树图对完全图的多色Ramsey数的上界.     

正则图的团横贯数的界

设D是图G的一个顶点子集, 若D含有G的每个团中至少一个顶点, 则D称为G的团横贯集. 图G的团横贯数是指它的最小团横贯集中顶点的数目, 记作τ_c(G). 本文研究正则图的团横贯数. 首先建立了正则图的团横贯数的上、下界, 且刻画了达到下界的极值图. 其次, 对无爪三次图, 得到了改进的可达上、下界并刻画了达到下界的极值图.     

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

研究素数阶完全图分解为循环图的方法 ,给出计算它的子图的团数的一种算法 ,得到 3个三色 ,3个四色 Ramsey数的新的下界 :R(3,3,13) 194 ,R(3,4 ,11) 2 12 ,R(3,6 ,13) 52 2 ,R(3,3,4 ,10 ) 380 ,R(3,3,6 ,14) 1154,R(3,4 ,5,13) 10 94     

对于K2+Tm和完全图的Ramsey函数的渐近上界

本文研究了当n趋于无穷大时,关于K2+Tm和完全图Kn的Ramsey数的渐近上界,以及r(K2+Tm,Kn)和r(K1+Tm,Kn)的渐近关系.利用李雨生等人所给出的一个独立数的下界公式,给出了r(K4,Kn)和r(Kk-c,Kn)的渐近上下界,推广了李雨生等人所给出的r(K1+Tm,Kn)的下界.     

一类仿射型本原非同步置换群的构造

同步置换群的研究是置换群理论中的一个前沿课题.通过在有限域上定义广义Paley图,来讨论这类图的团数(clique number)和色数(chromatic number)相等的条件.然后证明构造的广义Paley图和一类仿射群的轨道图同构,进而讨论这类仿射群的同步性.在此基础上给出一类本原非同步群的构造.     

Size Ramsey numbers for some regular graphs

P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of K_n,n,n. The result is a generalization of a theorem for K_n,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed.     

代数构造及在Ramsey理论中的应用

本文在Galois域上的代数构造和关于一些特定类型图的Ramseyr数之间建立了一个关系．关键问题是研究了关于Galois域上的代数构造的方程及方程组的解．我们得到了一些关于二部图的新的下界和上界．     

代数构造及在Ramsey理论中的应用

这篇文章在伽罗瓦域上的代数构造和关于一些特定类型图的Ramsey数之间建立了一个关系. 研究了关于伽罗瓦域上的代数构造的方程及方程组的解. 我们得到了一些关于二部图的Ramsey数的新的下界和上界.     

求Ramsey数下界的循环巧妙图搜索算法研究

本文研究通过构造循环巧妙图而搜寻Ｒａｍｓｅｙ数下界的算法，给出了一个效率较高的算法，该算法已经编程实现，并由此得出了一个具有４６点（４，７）循环巧妙图，从而证明了ｒ（４，７）≥４７。     

Lower bounds of Ramsey numbers based on cubic residues

A method to improve the lower bounds for Ramsey numbers R(k,l) is provided: one may construct cyclic graphs by using cubic residues modulo the primes in the form p=6m+1 to produce desired examples. In particular, we obtain 16 new lower bounds, which are

R(6,12)230, R(5,15)242, R(6,14)284, R(6,15)374,R(6,16)434, R(6,17)548, R(6,18)614, R(6,19)710,R(6,20)878, R(6,21)884, R(7,19)908, R(6,22)1070,R(8,20)1094, R(7,21)1214, R(9,20)1304, R(8,21)1328.

     

Proof of a conjecture on fractional Ramsey numbers

Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function r_f (a₁, a₂, …, a_k) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010     

Some geometric structures and bounds for Ramsey numbers

We investigate several bounds for both K_2,m−K_1,n Ramsey numbers and K_2,m−K_1,n bipartite Ramsey numbers, extending some previous results. Constructions based on certain geometric structures (designs, projective planes, unitals) yield classes of near-optimal bounds or even exact values. Moreover, relationships between these numbers are also discussed.     

Triple intersection numbers for the Paley graphs

We give a tight bound for the triple intersection numbers of Paley graphs. In particular, we show that any three vertices have a common neighbor in Paley graphs of order larger than 25.