Beyond Classical Ramsey: Solving Ordered and Cyclic Ramsey Numbers via SAT and RL

Executive Summary

TL;DR: This paper tackles the "small-scale" frontier of Ramsey Theory. By combining advanced SAT solvers (Kissat) with Reinforcement Learning (RLGT), the authors calculate new exact values and bounds for Ordered Ramsey Numbers and introduce a fresh concept: Cyclic Ramsey Numbers. They show that while classical Ramsey theory is hard, adding "order" to the vertices creates a rich structural playground where SAT solvers currently reign supreme.

Positioning: This work is both a computational contribution (filling in the blanks of small Ramsey tables) and a theoretical framework-building paper (unifying Ramsey variants under a group-theoretic lens).

The Problem: When Order Matters

Classical Ramsey theory asks for the minimum group size $n$ such that any 2-coloring of the edges of $K_n$ contains a monochromatic subgraph $H$. Ordered Ramsey Theory adds a constraint: the vertices of $H$ must appear in a specific total order. This simple restriction changes everything—path Ramsey numbers, which grow linearly in the classical case, can grow exponentially in the ordered case.

Existing research has struggled with:

1. Search Space: Even for small $n$, the number of possible colorings ($2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$) is astronomical.
2. Lack of Exacts: Most work is asymptotic, leaving "small" values (important for identifying patterns) largely unknown.

Methodology: Logic Meets Learning

1. Reduction to SAT (The Heavy Lifter)

The core insight is that Ramsey problems are essentially constraint satisfaction problems. For a graph of order $n$, the authors define a Boolean variable $x_{u,v}$ for each edge.

• Monochromatic H1 (Color 1) avoidance: ${\bigwedge }_{tuples\in {\mathcal{O}}_1}{\bigvee }_{uv\in E(H_1)}{x}_{w_u,w_v}$
• Monochromatic H2 (Color 2) avoidance: ${\bigwedge }_{tuples\in {\mathcal{O}}_2}{\bigvee }_{uv\in E(H_2)}eg{x}_{w_u,w_v}$

By feeding these into Kissat, the solver either finds a coloring (proving a lower bound) or proves no such coloring exists (establishing an upper bound).

2. Reinforcement Learning (The Heuristic Searcher)

The authors use the RLGT (Reinforcement Learning for Graph Theory) framework. A deep cross-entropy agent acts as a "builder," placing one edge color at a time. The reward function is the negative count of forbidden monochromatic subgraphs.

Table 1: Ordered Ramsey numbers for alternating paths, showcasing the precision achieved.

New Frontiers: Cyclic and Permutational Ramsey Numbers

The paper introduces Cyclic Ramsey Numbers $R_{cyc}(H)$, where the vertex order is preserved only up to a cyclic shift. This serves as a natural middle ground between the "rigid" ordered case and the "loose" classical case.

Mathematically, they show: $R(H)\le R_{cyc}(H)\le R_{ord}(H)$

To unify these, they propose Permutational Ramsey Numbers $R(H^{\Gamma })$, where $\Gamma$ is a subgroup of the symmetric group.

• Ordered: $\Gamma$ is trivial (identity only).
• Cyclic: $\Gamma$ is the cyclic group generated by a single shift.
• Classical: $\Gamma$ is the full symmetric group $S_n$.

Key Experimental Results

Path and Cycle Patterns

The authors identified a striking structure in Nested Matchings ($M_{nest}$), proving that for even $a,b$: $R_{ord}(M_a^{nest},M_b^{nest})=a+b-2$

SAT vs. RL

One of the most interesting meta-results is the performance comparison. While RL (Deep Cross-Entropy) is exciting and finds valid lower bounds (e.g., for $R_{ord}(P_6^{alt},P_6^{alt})$), the SAT solver is more robust. SAT solvers can provide proof of non-existence (upper bounds), whereas RL can only provide "best effort" lower bounds.

Visualizing specific ordered paths like the reverse alternating path $P_6^{ralt}$.

Conclusion and Future Outlook

Takeaways:

• Cyclic Ramsey Numbers provide a new spectrum of problems for combinatorialists.
• SAT Solvers remain the "gold standard" for small-scale extremal graph theory, though RL shows promise for larger, less constrained searches.
• A plethora of Conjectures (4.7 through 4.36) are provided, offering a roadmap for future researchers to prove general formulas for these newly calculated values.

Limitations: The cyclic SAT instances are significantly more complex (more clauses) than ordered ones, making upper bounds for $R_{cyc}$ harder to verify as $n$ grows.

Future Work: Investigating the asymptotic behavior of Cyclic Ramsey numbers—do they scale like Ordered or Classical Ramsey numbers?