用AI生成新算法，大幅提升9个经典图论难题的下界值。
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
- 用大模型自动生成搜索算法，替代传统手工设计。
- 9个拉姆齐数下界显著提高，最高提升至237。
- 首次统一方法解决多个难题，适合算法与组合数学研究者。
我们通过AlphaEvolve——一种基于大语言模型的代码变异代理——获得了九个经典拉姆齐数的新下界：R(3,13)从60提升至61，R(3,18)从99提升至100，R(4,13)从138提升至139，R(4,14)从147提升至148，R(4,15)从158提升至159，R(4,16)从170提升至174，R(4,18)从205提升至209，R(4,19)从213提升至219，R(4,20)从234提升至237。除这些新结果外，我们还成功复现了所有已知精确的拉姆齐数下界，并在众多其他情形中达到最优或接近最优下界，包括此前未公开算法细节的案例。几乎所有已知拉姆齐数下界均依赖于专用计算搜索算法，每个算法仅产生少量结果；而AlphaEvolve作为单一元算法，可自动生成适用于全部结果的搜索策略。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。