arXiv:2605.01120cs.AImath.CO2026-05被引 8

用大模型进化搜索,首次算出3个图论极值问题的精确解。

New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search

论文配图:New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
图 1 · 摘自论文原文
  • 用基于LLM的进化算法优化图构造,自动生成新解法。
  • 精确求出3个扎兰基维奇数:116、121、132,还给出41个新下界。
  • 成本低于30美元/参数,适合数学研究者快速验证猜想。

扎兰基维奇数 $ extbf{Z}(m, n, s, t)$ 表示在不含完全二分子图 $K_{s, t}$ 的条件下,$m imes n$ 二分图最多能有多少条边。本文首次确定了三个扎兰基维奇数的精确值:$ extbf{Z}(11, 21, 3, 3)=116$,$ extbf{Z}(11, 22, 3, 3)=121$,$ extbf{Z}(12, 22, 3, 3)=132$。同时,我们为41个更多扎兰基维奇数建立了新的下界,其中部分结果仅比已知上界少一条边,并且在四个闭合情形中与已有值一致。所有成果均通过 OpenEvolve——一个基于大语言模型(LLM)的开源进化算法实现,该算法通过定制奖励信号迭代优化图构造生成策略。本文不仅报告了生成的构造,还公开了生成算法、实现细节及计算开销。每组参数的计算成本不足30美元,表明大模型引导的进化搜索是一种低成本、可复现、易获取的组合构造发现工具。

原文摘要 · Abstract (English)

The Zarankiewicz number $\textbf{Z}(m, n, s, t)$ is the maximum number of edges in a bipartite graph $G_{m, n}$ such that there is no complete $K_{s, t}$ bipartite subgraph. We determine for the first time the exact values of three Zarankiewicz numbers: $\textbf{Z}(11, 21, 3, 3)=116$, $\textbf{Z}(11, 22, 3, 3)=121$, and $\textbf{Z}(12, 22, 3, 3)=132$. We further establish lower bounds for 41 more Zarankiewicz numbers, including several that are within one edge of the best known upper bound, and we match the established value in four more closed cases. Our results are obtained using OpenEvolve, an open-source evolutionary algorithm based on Large Language Models (LLMs) that iteratively improves algorithms for generating mathematical constructions by optimizing a reward signal which we tailored for this specific problem. These findings provide new extremal graph constructions and demonstrate the potential of LLM-guided evolutionary search to contribute to mathematical research. In addition to presenting the resulting constructions, we report the generation algorithms produced, describe the relevant implementation details, and provide our computational costs. Our costs are remarkably low, at less than \$30 for each Zarankiewicz parameter combination, showing that LLM-guided evolutionary search can be an inexpensive, reproducible, and accessible tool for discovering new combinatorial constructions.

图论组合优化大模型进化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。