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

MaRDI QIDQ976679zbMATH OpenFDO

Authors Kang Wu, Wenlong Su, Haipeng Luo, Xiaodong Xu

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/226188, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1n25.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

automorphism cyclic graphsclassical Ramsey numbersgeneralized paley graphslower bounds

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Review text

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.

Recommendations

• Lower bounds for r₂(K₁ + G) and r₃(K₁ + G) from Paley graph and generalization
• Generalized Paley graphs and their complete subgraphs of orders three and four
• On the adjacency properties of generalized Paley graphs
• The number of edges on generalizations of Paley graphs
• Lower bounds for R(3,q) based on automorphism cyclic graphs
• scientific article; zbMATH DE number 6130240
• On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
• scientific article; zbMATH DE number 832233
• Cubic and quadruple Paley graphs with the n-e.c. property
• scientific article; zbMATH DE number 5584977

Cited in

(8)

• Generalised Paley graphs with a product structure
• Random cyclic triangle-free graphs of prime order
• Ramsey numbers and triangle-free Cayley graphs
• Lower bounds for R(3,q) based on automorphism cyclic graphs
• scientific article; zbMATH DE number 78022 (Why is no real title available?)
• Lower bounds for r₂(K₁ + G) and r₃(K₁ + G) from Paley graph and generalization
• Paley-type graphs of order a product of two distinct primes
• Transitive subtournaments of k-th power Paley digraphs and improved lower bounds for Ramsey numbers

This page was built for publication: A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976679)