A generalization of generalized Paley graphs and new lower bounds for R(3, q)

作者：Wu, Kang^*; Su, Wenlong; Luo, Haipeng; Xu, Xiaodong

来源：Electronic Journal of Combinatorics, 2010, 17(1): N25.

Generalized Paley graphs are cyclic graphs constructed from quadratic or higher residues of finite fields. Using this type of cyclic graphs to study the lower bounds for classical Ramsey numbers, has high computing efficiency in both looking for parameter sets and computing clique numbers. We have found a new generalization of generalized Paley graphs, i.e. automorphism cyclic graphs, also having the same advantages. In this paper we study the properties of the parameter sets of automorphism cyclic graphs, and develop an algorithm to compute the order of the maximum independent set, based on which we get new lower bounds for 8 classical Ramsey numbers: R (3,22) >= 131, R (3,23) >= 137, R (3,25) >= 154, R (3,28) >= 173, R (3,29)>= 184, R (3,30) >= 190, R (3,31) >= 199, R (3,32) >= 214. Furthermore, we also get R (5,23) >= 521 based on R (3,22) >= 131. These nine results above improve their corresponding best known lower bounds

• 出版日期2010-5-7
• 单位华南师范大学; 梧州学院; 广西科学院