AI验证99图存在性问题，逼近69.43%约束上限
A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
- 通过群论与约束编程，证明循环图最多满足68.0%的约束条件
- 将原问题简化为84顶点12正则图，唯一恢复出srg(9,4,1,2)
- 提出可验证的对称性轨道框架，适配图论与自动推理研究者
Conway的99图问题询问是否存在参数为srg(99,14,1,2)的强正则图。我们报告了一项由自主AI研究代理执行的系统性、完全可复现的攻击，按部分得分指标评估。可验证贡献包括：(1) 完全证明在ℤ/99上的循环图最多满足3366/4950=68.0%的约束（49个差分类中的33个），同理适用于另一阶为99的阿贝尔群；(2) 强制结构简化：λ=1使每个邻域为完美匹配，μ=2使外部顶点与未匹配邻接对一一对应，将存在性问题归约为一个84顶点12正则图，以CP-SAT编码并验证成功恢复唯一的srg(9,4,1,2)；(3) 提出经验证的指定自同构轨道存在性框架（无固定点与单固定点作用），已在srg(9,4,1,2)和Paley图srg(13,6,2,3)上验证；(4) 当前最佳验证成果达到69.43%，且证据表明这是稳健的前沿（十四种独立方法均未超过），任何低于4950的可证界即构成不存在性证明。
原文摘要 · Abstract (English)
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. 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: $λ=1$ makes each neighbourhood a perfect matching and $μ=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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。