A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\) (Q976679): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 02:48, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\) |
scientific article |
Statements
A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\) (English)
0 references
16 June 2010
0 references
Summary: 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) \geqslant 131\), \(R(3, 23) \geqslant 137\), \(R(3, 25) \geqslant 154\), \(R(3, 28) \geqslant 173\), \((3, 29) \geqslant 184\), \(R(3, 30) \geqslant 190\), \(R(3, 31) \geqslant 199\), \(R(3, 32) \geqslant 214\). Furthermore, we also get \(R(5, 23) \geqslant 521\) based on \(R(3, 22) \geqslant 131\). These nine results above improve their corresponding best known lower bounds.
0 references
generalized paley graphs
0 references
lower bounds
0 references
classical Ramsey numbers
0 references
automorphism cyclic graphs
0 references