Geodesic
A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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) \geq 131$, $R(3,23) \geq 137$, $R(3,25) \geq 154$, $R(3,28) \geq 173$, $R(3,29) \geq 184$, $R(3,30) \geq 190$, $R(3,31) \geq 199$, $R(3,32) \geq 214$. Furthermore, we also get $R(5,23) \geq 521$ based on $R(3,22) \geq 131$. These nine results above improve their corresponding best known lower bounds.
DOI : 10.37236/474
Classification : 05C55
Mots-clés : generalized paley graphs, lower bounds, classical Ramsey numbers, automorphism cyclic graphs, lower bounds 
@article{10_37236_474,
     author = {Kang Wu and Wenlong Su and Haipeng Luo and Xiaodong Xu},
     title = {A generalization of generalized {Paley} graphs and new lower bounds for {\(R(3,q)\)}},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/474},
     zbl = {1188.05089},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/474/}
}
TY  - JOUR
AU  - Kang Wu
AU  - Wenlong Su
AU  - Haipeng Luo
AU  - Xiaodong Xu
TI  - A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/474/
DO  - 10.37236/474
ID  - 10_37236_474
ER  - 
%0 Journal Article
%A Kang Wu
%A Wenlong Su
%A Haipeng Luo
%A Xiaodong Xu
%T A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/474/
%R 10.37236/474
%F 10_37236_474
Kang Wu; Wenlong Su; Haipeng Luo; Xiaodong Xu. A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\). The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/474

Cité par Sources :