Ramsey Numbers and Triangle Free Cayley Graphs

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.

Key words:triangle free Cayley graph; maximal sum free set; Ramsey number