Das 与 Fox 借 AI 找到的思路证明 Murty-Simon 猜想

kevrussell · x · 2026-11-01

斯坦福组合数学家 Jacob Fox 与 Sanjana Das 提交 arXiv 论文，证明直径-2 临界图边数至多 ⌊n²/4⌋ 的 Murty-Simon 猜想(Erdős 问题 #742),等号仅在完全平衡二部图取得。关键点：⌊n²/4⌋ 这一上界的原始证明主要由 AI 找到，两人随后简化该证明并把其思想扩展到全部 n,补全完整猜想；此前 Füredi 用正则性方法只对超大 n(超过高度约 10^14 的 2 的幂塔)成立。证明尚未经同行评审，但 J.P. Traverso Gianini 已用 AI 生成的 Lean 形式化证明进行了核对。