Ramsey数和无三角的Cayley图

Ramsey Numbers and Triangle Free Cayley Graphs

摘要:

记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.

Abstract:

Let Zn={0,1,…,n} be the additive group of integers modulo n and let Z*n=Zn＼{0}. For an inverse closed subset AZ*n，let Gn(A) be the Cayley graph on vertex set Zn, in which {x,y} is an edge if and only if |x－y|∈A. We compute the independence numbers for triangle free Cayley graphs of orders up to 258, which improves the known lower bounds for Ramsey numbers r(3,q) for 27≤q≤38.