Source-linked AI summary
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta
TL;DR
Many Ramsey lower bounds rely on bespoke computational search algorithms, while substantial gaps remain for numerous parameter pairs. This paper uses AlphaEvolve to evolve search procedures and reports nine improved bounds, recovery of all known exact lower bounds, and matches to many other best-known bounds.
Problem
Computational Ramsey lower bounds use varied bespoke search algorithms, while large gaps remain for many parameter pairs.
Method
AlphaEvolve evolves LLM-generated code and search algorithms that construct larger graphs avoiding specified clique and independent-set constraints.
Results
The paper improves nine Ramsey lower bounds, recovers lower bounds for all known exact values, and matches many other best-known bounds.
Takeaways & Limitations
A single AlphaEvolve meta-algorithm yields search algorithms across the reported Ramsey lower-bound results.
Takeaways & Limitations
The work addresses lower bounds; upper-bound improvement requires proving that no larger qualifying graph exists.
Abstract
from arXiv · showhide
We present improved lower bounds for nine classical Ramsey numbers: $\mathbf{R}(3, 13)$ is increased from $60$ to $61$, $\mathbf{R}(3, 18)$ from $99$ to $100$, $\mathbf{R}(4, 13)$ from $138$ to $139$, $\mathbf{R}(4, 14)$ from $147$ to $148$, $\mathbf{R}(4, 15)$ from $158$ to $159$, $\mathbf{R}(4, 16)$ from $170$ to $174$, $\mathbf{R}(4, 18)$ from $205$ to $209$, $\mathbf{R}(4, 19)$ from $213$ to $219$, and $\mathbf{R}(4, 20)$ from $234$ to $237$. These results were achieved using AlphaEvolve, an LLM-based code mutation agent. Beyond these new results, we successfully recovered lower bounds for all Ramsey numbers known to be exact, and matched the best known lower bounds across many other cases. These include bounds for which previous work does not detail the algorithms used. Virtually all known Ramsey lower bounds are derived computationally, with bespoke search algorithms each delivering a handful of results. AlphaEvolve is a single meta-algorithm yielding search algorithms for all of our results.
1 Introduction
The paper targets gaps in computational lower bounds for classical Ramsey numbers and uses AlphaEvolve to discover search algorithms that generate larger valid witness graphs. It reports new bounds, matches many existing best results, and documents performance categories in Table 1.
- Problem: R(r, s) is lower-bounded by n + 1 when a graph on n vertices avoids both r-cliques and s-independent sets.This witness-graph formulation turns lower-bound improvement into a constructive search problem.
- Approach: AlphaEvolve evolves LLM-generated code snippets into search algorithms for graphs that avoid the required clique and independence-set constraints.It serves as a single meta-algorithm rather than a collection of bespoke search procedures.
- Results: Nine Ramsey lower bounds improve over prior values, including R(4, 19) from 213 to 219 and R(4, 16) from 170 to 174.The reported improvements also include R(3, 13), R(3, 18), R(4, 13), R(4, 14), R(4, 15), R(4, 18), and R(4, 20).
- Results: The study matches the state of the art on many other Table 1 cells, including all cells whose exact Ramsey values are known.Table 1 distinguishes optimal, matched-best-known, and newly improved lower bounds by color.
2 AlphaEvolve Meta-search, and Discovered Search Algorithms
AlphaEvolve maintains and mutates a population of Ramsey search programs, scoring valid graphs and low-violation prospects to evolve procedures that improve current lower bounds. The discovered algorithms use different initialization and structural strategies across cells.
- Evolution pipeline: AlphaEvolve evolves a population of search algorithms by selecting parent programs, prompting an LLM mutation, executing the mutation, and scoring its resulting graphs.The process maintains candidate programs rather than directly optimizing a single graph.
- Scoring: A valid primary graph receives a size-based score, while a larger prospect graph earns a bonus when its clique and independent-set violations decrease.The prospect score uses violation counts to guide searches toward feasible boundary cases.
- Algorithm interface: The input includes r, s, and the current best graph size nSoTA, and the output is the program with the best graph found.Here r denotes clique size and s denotes independent-set size.
- Discovered algorithms: AlphaEvolve discovered nine cell-specific search algorithms for the nine newly improved Ramsey bounds, while additional algorithms cover other Table 1 cells.The algorithms’ success generally does not transfer between cells, even after reasonably long runs.
- Initialization strategies: Initialization strategies fall into generic Erdős–Rényi search, algebraic-graph seeding, and searches constrained to structural families such as cyclic graphs.Table 2 summarizes this initialization-based taxonomy.
- Computational setting: Clique counting was not a limiting factor because the Table 1 instances had relatively small graph sizes.The passage identifies clique and independent-set counting as a frequent bottleneck in general Ramsey construction searches.
3 Comparison to Prior Work
The comparison uses public computational precedents and shows that AlphaEvolve both improves selected bounds and matches others while often using different initialization or optimization strategies. Its results also recover cases whose prior algorithmic details were unavailable.
- Comparison scope: The comparison is restricted to lower bounds with public references and computational derivations because many historical results rely on personal communications without algorithmic details.This defines the evidence base used for the state-of-the-art comparison.
- Search strategies: For R(4, 14), AlphaEvolve uses circulant graphs with varying periodicities, whereas Exoo’s prior search starts from a cubic graph.The subsequent optimization strategies also differ: AlphaEvolve uses evolved heuristics instead of simulated annealing.
- Search strategies: For R(4, 18), AlphaEvolve develops a ground-up heuristic instead of relying on the prior bound obtained by differencing other Ramsey cells.For R(4, 15), its Paley-graph initialization also differs from the earlier Cayley-graph approach.
- Related AI work: The work extends a broader line of AI applications in extremal combinatorics, including graph counterexamples, capsets, grid subsets, Ramanujan graphs, and Kakeya bounds.The authors position AlphaEvolve within recent computational mathematics research.
4 Conclusion
The paper frames AlphaEvolve as an automation of heuristic discovery for progress on classical extremal-combinatorics problems. Its results concern Ramsey lower bounds, while upper-bound improvements require proving that larger witness graphs do not exist.
- Positioning: The work applies LLM-based systems to progress on classic, well-studied mathematical and computer-science problems.The authors state that their aim is to derive results that stand the test of time.
- Novelty: AlphaEvolve automates heuristic discovery, replacing the bespoke human-designed heuristics typically executed in prior Ramsey lower-bound searches.The overarching Algorithm 1 remains the main human-designed component described by the authors.
- Scope: The paper addresses Ramsey lower bounds by constructing witness graphs that avoid specified cliques and independent sets.This constructive objective differs fundamentally from proving upper bounds.
- Scope: Improving Ramsey upper bounds requires demonstrating that no larger qualifying graph exists, rather than constructing a single example.The conclusion cites formal methods proving R(4, 5) = 25 as a recent example of that different challenge.