AI agent cracks Conway's 99-Graph problem with 69.43% solution

Aalok Thakkar's AI agent has pushed the frontier on Conway's 99-Graph problem—a 50-year-old open question in graph theory—by achieving a 69.43% verified solution. Published on arXiv under the first Conference For AI Scientists (CAISc), the work systematically dismantles the problem's constraints, proving that no circulant graph on Z/99 can satisfy more than 68% of the required conditions. The agent's forced-structure reduction reveals that key parameters (λ=1, μ=2) collapse the existence question into a 12-regular graph on 84 vertices, validated via CP-SAT and cross-checked against known graphs like the Paley graph srg(13,6,2,3).

The paper introduces a prescribed-automorphism orbit-existence framework, benchmarking fourteen distinct methods against the 69.43% frontier. This represents the strongest provable bound below the 4950-edge ceiling, inching closer to a full non-existence proof. Thakkar's autonomous approach—scored under partial-credit metrics—demonstrates AI's growing role in formal mathematical discovery, bridging symbolic computation with combinatorial constraints.