研究论文
AI 研究代理在 Conway 99-图问题上取得可验证上限
arXiv 新论文报告自主 AI 研究代理对 Conway 99-图存在性问题进行系统化求解，最佳可验证结果触及 69.…
2026.08.13 · 周四约 2 分钟阅读
近期发表于 arXiv 的论文《A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph》报告了一次由自主 AI 研究代理完成的系统化、可复现的数学研究，目标直指组合数学中长期悬而未决的 Conway 99-图问题：参数为 srg(99,14,1,2) 的强正则图是否存在。论文以部分给分指标进行评分，给出一系列可机器验证的中间结果。
循环图层面的穷尽证明
研究首先在循环图（circulant graph）框架下进行穷尽搜索。论文证明：在 $\mathbb{Z}/99$ 上的任意循环图至多满足 68.0% 的约束条件（精确为 3366/4950，对应 49 个差分类中的 33 个），并表明对另一个 99 阶阿贝尔群也存在相同的上限。这一结论完全排除了一大类对称结构中存在 srg(99,14,1,2) 的可能性。
强制结构约化
- 由 $\lambda=1$ 推出每个邻域构成一个完美匹配。
- 由 $\mu=2$ 进一步将外部顶点与「未匹配邻居对」建立双射。
- 上述两条性质将原问题折叠为 84 个顶点上的 12-正则图存在性问题。
- 该编码被转化为 CP-SAT 约束满足问题，并通过对 srg(9,4,1,2) 的成功复现完成自洽性验证。
自同群轨道存在框架
论文还给出一种「预设自同群-轨道存在性」验证流程，分别检验无不动点与单不动点两类作用，验证样本包括 srg(9,4,1,2) 与 Paley 图 srg(13,6,2,3)。框架用于在限定自同群的前提下枚举候选轨道，是后续搜索的辅助工具。
当前最佳可验证结果
- 最优可验证工件（artifact）达到 69.43% 的约束满足度。
- 论文同时报告：在十四种不同方法下，无一能够突破该值，提示该数值已接近「可被穷尽验证」意义上的稳健前沿。
- 论文指出，任何可证明低于 4950 的约束满足度上限，都将构成完整的不存在性证明。
整体而言，这项工作展示了自主 AI 研究代理在长期开放数学问题中能够产出可复现、可验证的中间成果，并借助 CP-SAT 等约束求解工具将结构化推理与穷尽搜索相结合。即便仍未解决 99-图存在性本身，其约化路径与公开工件为后续人机协作研究提供了清晰的接口。