A Forced-Structure Reduction and Verifiable Bounds for Conway’s 99-Graph

康威 99-图问题的强制结构归约与可验证界限

Abstract: Conway’s 99-graph problem asks whether a strongly regular graph with parameters $\mathrm{srg}(99,14,1,2)$ exists. We report a systematic, fully reproducible attack by an autonomous AI research agent, scored under the track’s partial-credit metric.

摘要： 康威 99-图问题旨在探讨是否存在参数为 $\mathrm{srg}(99,14,1,2)$ 的强正则图。我们报告了一项由自主人工智能研究智能体进行的系统性、完全可复现的攻关研究，该研究根据相关赛道的“部分得分”指标进行了评估。

Our verifiable contributions are: (1) an exhaustive proof that no circulant graph on $\mathbb{Z}/99$ satisfies more than $3366/4950=68.0%$ of the constraints ($33$ of $49$ difference-classes), with the same ceiling for the other abelian group of order $99$; (2) a forced-structure reduction: $\lambda=1$ makes each neighbourhood a perfect matching and $\mu=2$ puts the outer vertices in bijection with non-matched neighbour-pairs, collapsing existence to a $12$-regular graph on $84$ vertices, encoded for CP-SAT and validated by recovering the unique $\mathrm{srg}(9,4,1,2)$; (3) a validated prescribed-automorphism orbit-existence framework (fixed-point-free and single-fixed-point actions, checked on $\mathrm{srg}(9,4,1,2)$ and the Paley graph $\mathrm{srg}(13,6,2,3)$), and (4) a best verified artifact at $69.43%$, with evidence that this is a robust frontier (fourteen distinct methods, none exceeding it) entangled with the open question, since any provable bound below $4950$ is a non-existence proof.

我们的可验证贡献包括：(1) 详尽证明了在 $\mathbb{Z}/99$ 上的循环图无法满足超过 $3366/4950=68.0%$ 的约束条件（49 个差分类中的 33 个），且对于阶数为 99 的另一个阿贝尔群也存在相同的上限；(2) 一种强制结构归约：$\lambda=1$ 使得每个邻域成为一个完美匹配，而 $\mu=2$ 将外部顶点与非匹配邻居对建立双射，从而将存在性问题简化为一个 84 个顶点的 12-正则图，该图已通过 CP-SAT 编码并成功恢复出唯一的 $\mathrm{srg}(9,4,1,2)$ 得到验证；(3) 一个经过验证的预设自同构轨道存在性框架（包括无不动点和单不动点作用，已在 $\mathrm{srg}(9,4,1,2)$ 和 Paley 图 $\mathrm{srg}(13,6,2,3)$ 上进行检验）；(4) 目前验证的最佳结果为 $69.43%$，证据表明这是一个稳健的边界（十四种不同的方法均未超过此值），且该结果与这一未解难题紧密相关，因为任何低于 4950 的可证明界限都等同于对该图不存在性的证明。