Das and Fox prove Murty-Simon conjecture with AI-found proof, Lean-verified
kevrussell · x · 2026-11-01
Sanjana Das and Jacob Fox posted an arXiv proof of the Murty-Simon conjecture (Erdős #742): diameter-2-critical graphs have at most ⌊n²/4⌋ edges, with equality only for the balanced complete bipartite graph. The ⌊n²/4⌋ bound was originally found by AI; they simplified it and extended the ideas to cover all n, where Füredi's regularity approach only handled astronomically large n. Not yet refereed, but checked by an AI-written Lean proof from J.P. Traverso Gianini.
More from Research
- DIY UBI math with real data: about $2,000 per person after 30 years, not a living wage — edmrunmachine · 2026-11-01
- GRASP authors compare with SuperMimic: extracting more optimization signal from sim experience — hankyang94 · 2026-11-01
- Harvard's GRASP refines human demos in physics sim for dexterous hands and Unitree G1 — hankyang94 · 2026-11-01
- DeepMind researchers publish book offering Bayesian framework for assessing AI consciousness — mhutter42 · 2026-11-01
- Graphical Algebraic Geometry Paper Links Polynomial Reasoning to Quantum ZH Calculus, Accepted at LICS 2026 — ctjlewis · 2026-11-01
- Is There a Modality-Agnostic Taxonomy of ML Techniques? Reddit Asks Which Patterns Repeat Across Text, Image and Audio — OkCampaign8400 · 2026-11-01