跳转至

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

文章背景与核心概要

Conway 99-图问题是图论领域中一个著名的未解难题，旨在探究是否存在参数为 \(\mathrm{srg}(99,14,1,2)\) 的强正则图。该问题因其巨大的搜索空间和复杂的结构约束，长期以来一直是组合数学研究的挑战。

本文提出了一种由自主AI研究智能体执行的系统化且完全可复现的攻击方案。研究通过对循环图约束的穷举证明、利用 \(\lambda=1\) 和 \(\mu=2\) 参数进行的强制结构归约，以及轨道存在性框架，成功将问题简化并转化为可由 CP-SAT 求解器处理的约束满足问题。研究最终给出了 69.43% 的约束满足率上限，并提供了强有力的证据表明该界限可能与问题本身的不可解性深度相关。

摘要总结

Conway 99-图问题旨在探究是否存在参数为 \(\mathrm{srg}(99,14,1,2)\) 的强正则图。本文提出了一种由自主 AI 研究智能体执行的系统化且完全可复现的问题攻击方案。

Conway's 99-graph problem investigates the existence of a strongly regular graph with the parameters \(\mathrm{srg}(99,14,1,2)\). This paper presents a systematic and fully reproducible attack on the problem executed by an autonomous AI research agent.

本工作的主要可验证贡献包括：

The primary verifiable contributions of this work include:

  1. 循环图约束： 一项穷举证明，确立了 \(\mathbb{Z}/99\) 上的任何循环图都无法满足超过 \(3366/4950 = 68.0\%\) 的约束（49 个差分类中的 33 个），并为 99 阶的其他阿贝尔群确立了相同的上限。
  1. Circulant Graph Constraints: An exhaustive proof establishing that no circulant graph on \(\mathbb{Z}/99\) can satisfy more than \(3366/4950 = 68.0\%\) of the constraints (\(33\) of \(49\) difference-classes), establishing the exact same ceiling for the other abelian group of order \(99\).
  1. 强制结构归约： 利用结构参数 \(\lambda=1\)（强制每个邻域为完美匹配）和 \(\mu=2\)（将外部顶点与非匹配邻居对建立双射）。这使得存在性问题归约为 84 个顶点上的 12-正则图，该图被编码为 CP-SAT 格式，并通过恢复唯一的 \(\mathrm{srg}(9,4,1,2)\) 成功验证。
  1. Forced-Structure Reduction: Exploiting the structural parameters \(\lambda=1\) (forcing each neighborhood to be a perfect matching) and \(\mu=2\) (putting outer vertices in bijection with non-matched neighbor-pairs). This collapses the existence problem to a \(12\)-regular graph on \(84\) vertices, which was encoded for CP-SAT and successfully validated by recovering the unique \(\mathrm{srg}(9,4,1,2)\).
  1. 轨道存在性框架： 一个经过验证的预设自同构轨道存在性框架（处理无不动点和单不动点作用），并成功针对 \(\mathrm{srg}(9,4,1,2)\) 和 Paley 图 \(\mathrm{srg}(13,6,2,3)\) 进行了检验。
  1. Orbit-Existence Framework: A validated prescribed-automorphism orbit-existence framework (handling fixed-point-free and single-fixed-point actions), successfully checked against \(\mathrm{srg}(9,4,1,2)\) and the Paley graph \(\mathrm{srg}(13,6,2,3)\).
  1. 已验证界限与产物： 最佳验证产物达到了 69.43% 的约束满足率。论文提供的证据表明，这代表了一个稳健的前沿——在十四种不同的方法中，没有一种超过该阈值——这表明它与该未解问题本身深度纠缠，因为任何低于 4950 的可证明界限最终都充当了非存在性证明。
  1. Verified Bounds and Artifacts: A best verified artifact achieving a \(69.43\%\) constraint satisfaction rate. The paper provides evidence that this represents a robust frontier—across fourteen distinct methods, none exceeded this threshold—suggesting it is deeply entangled with the open question itself, as any provable bound below \(4950\) ultimately acts as a non-existence proof.

文章元数据与参考资料

license icon