A Generalization of Generalized Paley Graphs and New Lower Bounds for R(3,q)

Kang Wu, Wenlong Su, Haipeng Luo, Xiaodong XuElectr. J. Comb 2010 · OpenReview

Abstract

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 eight 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 improve their corresponding best-known lower bounds.

Introduction

Ramsey theory centers on the principle that complete disorder is impossible. The classical Ramsey number $R(k, q)$ represents the minimum number of vertices $n$ such that any graph of order $n$ must contain either a clique of size $k$ or an independent set of size $q$. Determining these numbers is a notoriously difficult combinatorial problem. For most values of $k$ and $q$, mathematicians must rely on establishing lower and upper bounds.

Lower bounds are typically established through constructive methods: by exhibiting a specific graph of order $n-1$ that lacks both a $k$-clique and a $q$-independent set, one proves $R(k, q) \geq n$. Historically, Paley graphs—constructed using quadratic residues in finite fields—have been a primary tool for this purpose due to their high degree of symmetry. However, Paley graphs are restricted to orders that are prime powers. This paper introduces "automorphism cyclic graphs," a generalization that extends the efficiency of Paley-like constructions to arbitrary integer orders.

Construction of Automorphism Cyclic Graphs

The core innovation of this work is the definition of automorphism cyclic graphs over the cyclic group $\mathbb{Z}_n$. Unlike standard Paley graphs, which require the algebraic field properties of prime powers, these graphs can be constructed for any integer $n$.

The authors define a set of "special elements" $k \in \mathbb{Z}_n$ that satisfy $(k, n) = 1$. These elements act as automorphisms on the graph's parameter sets. Specifically, if $S_1$ is the set of edges connected to the vertex 0, the graph is constructed such that $S_1$ is invariant under multiplication by these special elements. This group of automorphisms, denoted as $P$, preserves the graph's structure and allows for a more flexible search for graphs with specific clique and independent set properties.

Algorithmic Optimization and Symmetry

Calculating the clique number or the maximum independent set of a graph is an NP-hard problem, making the verification of large Ramsey graphs computationally expensive. The authors overcome this by leveraging the inherent symmetry of automorphism cyclic graphs to prune the search space.

By introducing a total order on the vertices and focusing on representatives of equivalence classes defined by the automorphism group $P$, the authors developed an optimized search algorithm. This approach reduces the computational complexity by a factor of $1/2s$, where $s$ is the order of the special element. This optimization is significant; computations that would typically require years of processing time were completed in approximately six hours on a standard PC (AMD6400+ CPU).

New Lower Bounds for R(3, q)

The primary application of this framework was finding new lower bounds for $R(3, q)$. By searching for cyclic graphs of orders $n=35$ to $n=213$ with a clique number of 2 (meaning the graph contains no triangles), the authors identified several parameter sets that yielded larger independent sets than previously recorded.

The following table summarizes the nine new lower bounds established in this study:

Ramsey Number Previous Best New Lower Bound
$R(3, 22)$ 125 131
$R(3, 23)$ 136 137
$R(3, 25)$ 153 154
$R(3, 28)$ 172 173
$R(3, 29)$ 182 184
$R(3, 30)$ 187 190
$R(3, 31)$ 198 199
$R(3, 32)$ 212 214
$R(5, 23)$ 509 521

The bound for $R(5, 23)$ was derived using the recursive inequality $R(5, t) \geq 4R(3, t-1) - 3$. By improving the bound for $R(3, 22)$ to 131, the authors were able to push the lower bound for $R(5, 23)$ to 521.

Conclusion

This research demonstrates that the structural advantages of Paley graphs—specifically their symmetry and computational tractability—can be successfully generalized to cyclic graphs of arbitrary order. The introduction of automorphism cyclic graphs provides a powerful new tool for Ramsey theory, as evidenced by the nine improved lower bounds. Future work may involve refining the heuristic search for optimal parameter sets $S_1$ and extending these high-efficiency algorithms to higher-order Ramsey numbers like $R(4, q)$ directly.

Summary updated

Abstract

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.
BibTeX
@article{wu2010generalization,
  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 = {Electr. J. Comb.},
  year = {2010},
  url = {https://openreview.net/forum?id=6Ect4mquoLY},
}
Figure