Reinforced Generation of Combinatorial Structures: Ramsey Numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914496019169280 |
|---|---|
| author | Nagda, Ansh Raghavan, Prabhakar Thakurta, Abhradeep |
| author_facet | Nagda, Ansh Raghavan, Prabhakar Thakurta, Abhradeep |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09172 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reinforced Generation of Combinatorial Structures: Ramsey Numbers Nagda, Ansh Raghavan, Prabhakar Thakurta, Abhradeep Combinatorics Artificial Intelligence Computational Complexity 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. |
| title | Reinforced Generation of Combinatorial Structures: Ramsey Numbers |
| topic | Combinatorics Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2603.09172 |