Reinforced Generation of Combinatorial Structures: Ramsey Numbers

This paper introduces AlphaEvolve, an LLM-based code mutation agent that serves as a unified meta-algorithm to improve the lower bounds of five classical Ramsey numbers and successfully recover or match existing bounds across various cases, demonstrating a shift from bespoke search methods to a single, adaptable framework for combinatorial structure generation.

The Gist

Imagine you are a master architect trying to build the largest possible city without ever creating two specific, forbidden patterns:

1. A super-gang of 4 friends who all know each other (a "clique").
2. A silent club of 15 strangers who all don't know each other (an "independent set").

In the world of mathematics, this is the quest for Ramsey Numbers. The question is: "How big can your city get before you are forced to accidentally create one of these forbidden patterns?"

If you can build a city of 159 people without these patterns, you've proven the answer is at least 160. The bigger the city you can build, the better you are at the game.

The Problem: The Search is Hard

For decades, mathematicians have been trying to build these "forbidden-pattern-free" cities. It's like trying to find a needle in a haystack, but the haystack is infinite, and the needle keeps changing shape.

Previously, to find a slightly bigger city, a human expert had to write a custom, one-of-a-kind computer program (a "search algorithm") for each specific problem. It was slow, manual, and required a genius to design the search strategy for every single new number.

The Solution: The "Evolutionary Code Gardener"

This paper introduces a new tool called AlphaEvolve. Think of AlphaEvolve not as a calculator, but as a digital gardener or a code-mutation agent.

Here is how it works, using a simple analogy:

1. The Garden (The Population): AlphaEvolve starts with a small garden of different computer programs. Some are bad at building cities; some are okay.
2. The Mutator (The LLM): A powerful AI (a Large Language Model) acts as the gardener. It looks at the best-performing programs in the garden and says, "Let's tweak this one." It might change a few lines of code, swap a strategy, or try a new way of connecting people. This is like a gardener taking a healthy plant, cutting a branch, and grafting it onto a new stem to see if it grows better.
3. The Test (The Simulation): The new, mutated program tries to build a city.
   • Success: If it builds a city of 159 people without the forbidden patterns, it gets a high score.
   • Failure: If it accidentally creates a super-gang or a silent club, it gets a low score.
4. Survival of the Fittest: The programs that built the biggest cities are kept. The ones that failed are thrown out. The AI then takes the winners, mutates them again, and repeats the process thousands of times.

Over time, the AI doesn't just find a better city; it invents a better way to build cities. It evolves the search algorithm itself.

The Big Wins

Using this "self-evolving" approach, the researchers achieved something remarkable. They didn't just find one new city; they found five new record-breaking cities where no one had ever gone before:

• R(3, 13): They built a city of 61 people (previously the record was 60).
• R(3, 18): They built a city of 100 people (previously 99).
• R(4, 13): They built a city of 139 people (previously 138).
• R(4, 14): They built a city of 148 people (previously 147).
• R(4, 15): They built a city of 159 people (previously 158).

Why This is a Game Changer

In the past, if you wanted to improve the record for R(4, 15), you needed a human to spend months designing a specific search strategy.

With AlphaEvolve, the AI automatically discovered the strategy.

• For some numbers, it realized, "Hey, let's start with a random mess and clean it up."
• For others, it figured out, "No, we need to start with a very specific, math-heavy structure (like a Paley graph) and tweak it."
• For others, it invented a "fractal" approach, copying patterns from smaller parts of the city to build the whole.

The AI didn't just solve the puzzle; it wrote the instruction manual on how to solve the puzzle, and it did it for five different difficult cases at once.

The Takeaway

This paper shows that we are entering an era where AI doesn't just solve math problems by being "smart"; it solves them by learning how to write the code that solves them.

It's like giving a robot a toolbox and a goal. Instead of the robot just picking up a hammer, it realizes, "I need a better hammer," so it builds a new hammer, tests it, and then uses that new hammer to build a bigger house. In this case, the "house" is a mathematical proof, and the "bigger house" is a new record in the history of mathematics.

Technical Summary

Here is a detailed technical summary of the working paper "Reinforced Generation of Combinatorial Structures: Ramsey Numbers" by Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta.

1. Problem Statement

The paper addresses the problem of determining Ramsey numbers, specifically $R(r, s)$, which is defined as the smallest integer $n$ such that every undirected graph with $n$ vertices contains either a clique of size $r$ or an independent set of size $s$.

• The Challenge: While exact values are known for small parameters, there are significant gaps for many pairs $(r, s)$. Establishing a lower bound $R(r, s) \ge n+1$ requires constructing a specific graph with $n$ vertices that contains no cliques of size $r$ and no independent sets of size $s$.
• Current State: Historically, these lower bounds have been derived using bespoke, human-designed search algorithms (e.g., simulated annealing, branch-and-bound) tailored to specific $(r, s)$ pairs. These methods are labor-intensive and often lack generalizability.

2. Methodology: AlphaEvolve

The authors employ AlphaEvolve, a meta-algorithmic framework that uses Large Language Models (LLMs) to iteratively evolve code snippets to discover better search algorithms.

• Core Mechanism: Instead of manually designing heuristics, AlphaEvolve maintains a population of search programs. It uses an LLM to select a parent program and mutate it to create a new candidate program ($p_{new}$).

• The Evolution Loop (Algorithm 1):

  1. Initialization: Starts with a baseline (often an empty graph or a simple random graph).
  2. Execution: The mutated program $p_{new}$ runs to generate two graphs:
     • $G_1$: A primary graph intended to be a valid witness (no $r$-cliques, no $s$-independent sets).
     • $G_2$: A "prospect" graph that may violate constraints but is close to valid.
  3. Scoring & Selection:
     • If $G_1$ is valid, it is scored based on its size ($v_1$). Scores are heavily boosted if $v_1$ exceeds the current State-of-the-Art (SoTA) bound ($n_{SoTA}$).
     • $G_2$ contributes an additive bonus based on how few violations it has relative to a random graph baseline ($E_{viol}$). This guides the search toward the "boundary" of validity.
  4. Population Update: High-scoring programs are retained to seed the next generation of mutations.

• Key Innovation: The system does not just search for a graph; it searches for the algorithm that finds the graph. This allows the discovery of novel heuristics, initialization strategies, and optimization loops that humans might not conceive.

3. Key Contributions

1. New Lower Bounds: The paper establishes improved lower bounds for five classical Ramsey numbers:
   • $R(3, 13)$: Increased from 60 to 61.
   • $R(3, 18)$: Increased from 99 to 100.
   • $R(4, 13)$: Increased from 138 to 139.
   • $R(4, 14)$: Increased from **147 to 148.
   • $R(4, 15)$: Increased from 158 to 159.
2. Unified Meta-Algorithm: Unlike prior work that uses distinct, hand-crafted algorithms for each Ramsey number, AlphaEvolve uses a single meta-algorithm to generate the specific search procedures for all 28 bounds reported (including matching existing SoTA for many other cases).
3. Algorithmic Discovery: The system discovered diverse search strategies, categorized into four initialization families:
   • Random & Stochastic: Standard Erdős-Rényi graphs or greedy baselines.
   • Paley & Algebraic: Seeding with algebraic structures (e.g., cubic residues, quadratic residues).
   • Circulant & Cyclic: Bootstrapping from cyclic graphs or sum-free sets.
   • Hybrid & Fractal: Complex mixtures involving spectral properties or self-similar constructions.
4. Recovery of Known Results: The system successfully recovered lower bounds for all Ramsey numbers known to be exact, validating its capability to replicate human-level combinatorial discovery.

4. Technical Details of Discovered Algorithms

The paper details specific algorithms discovered by AlphaEvolve for the new records, highlighting how they differ from prior human-designed approaches:

• R(3, 13) (Algorithm 2): Uses a Cyclic Bootstrap followed by Iterative Expansion. It employs a "Hitting Set" strategy where new vertices are connected to intersect existing independent sets of size $s-1$. It utilizes Adaptive Simulated Annealing where weights dynamically shift to prioritize destroying triangles if they dominate the violation count.
• R(4, 13) (Algorithm 4): Initialized with a highly specific Algebraic Bootstrap (Cayley graph of cubic residues in $\mathbb{F}_{127}$). It features Incremental Violation Tracking, maintaining explicit sets of cliques/anticliques to allow $O(1)$ updates upon edge flips, avoiding full graph rescans. It uses a Two-Stage Move Evaluation (heuristic filter followed by exact check) and a Strategic Kick to escape local minima.
• R(4, 14) (Algorithm 5): Restricts the search to Vertex-Transitive Circulant Graphs. It reduces the global constraint check to a local check around a single vertex (vertex 0), drastically reducing computational complexity. It uses High-Performance Bitset Filtration for rapid subgraph isomorphism checks.
• R(4, 15) (Algorithm 6): Employs a Harmonic Genetic Memory, tracking the frequency of successful edges and cyclic distances ("orbits") across generations. It uses Spectral Initialization and a Look-Ahead scoring mechanism that penalizes moves likely to create large independent sets while rewarding the preservation of historically successful edge patterns.

5. Comparison to Prior Work

• Divergence from Human Heuristics: While some discovered algorithms share initialization families with prior work (e.g., using Paley graphs for $R(4, 13)$), the optimization strategies differ significantly. AlphaEvolve often chains multiple heuristics (e.g., Tabu search + Simulated Annealing + Genetic memory) or uses custom delta-update mechanisms not found in the literature.
• Novelty: For cases like $R(4, 10)$, the discovered algorithm (Algorithm 24) uses a "Near-Miss Repository" and adaptive probability learning for generator selection, a strategy absent in existing literature.
• Efficiency: The system avoids the computational bottleneck of full graph rescanning by implementing incremental update logic (e.g., tracking common neighbors for $\Delta K_r$) automatically discovered during the evolution process.

6. Significance

• Automated Scientific Discovery: This work demonstrates that LLM-based agents can autonomously discover complex mathematical algorithms, not just by prompting for a solution, but by evolving the search procedure itself.
• Scalability: The ability to use a single meta-algorithm to solve a wide range of combinatorial problems suggests a path toward automating the discovery of extremal structures in other domains (e.g., coding theory, design theory).
• Bridging the Gap: By improving lower bounds for long-standing open problems, the paper pushes the boundaries of known combinatorial limits, providing new data points for theoretical conjectures.
• Methodological Shift: It contrasts with recent AI math breakthroughs that rely on direct theorem proving via prompting. Here, the AI acts as a programmer, generating the code that performs the heavy lifting of combinatorial search, which appears more effective for finding extremal objects than direct reasoning.

In conclusion, the paper presents a paradigm shift in extremal combinatorics, moving from human-designed, bespoke search algorithms to an AI-driven, evolutionary framework capable of discovering novel, high-performance search strategies that improve upon decades of human research.