Paperlane

no. 12 · Tuesday 10 November 2026

A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph

Aalok Thakkar and Simone Severini

math.CO · v3

Abstract

Conway's 99-graph problem asks whether a strongly regular graph with parameters srg(99,14,1,2) exists. We develop two complementary lines of attack. Fixing one vertex, the conditions lambda=1 and mu=2 force its neighbourhood to be a perfect matching and determine every edge between that neighbourhood and the remaining vertices. For (99,14,1,2), the unresolved part is therefore a constrained 12-regular graph on 84 vertices. We encode this reduction in CP-SAT and validate it by recovering the unique srg(9,4,1,2). We also prove by exhaustive enumeration that no circulant graph on Z/99 satisfies more than 68.0% of the CAISc constraints, and we give a validated orbit formulation for prescribed automorphisms. We then study the partial-score search problem. Fourteen human-designed search configurations reached at most 69.43%. Separately, we supplied the scoring function to an evolutionary program-search system. It produced a degree-preserving 4-vertex-switch tabu search whose best verified artifact scores 70.73%. The generated move differs from those used in our own searches and crosses a plateau that was stable under them. A tabu search restricted to graphs with a prescribed symmetry group, first Z/33 and then its subgroup of order 11, reaches a 14-regular graph scoring 76.67%. These results do not resolve the existence problem, but they reduce the exact search space and improve the best verified partial construction found in our experiments.

comments
An earlier version of this paper was accepted to the first Conference For AI Scientists (CAISc)
fields
Combinatorics
pdf ↗ page arXiv:2608.11211 ↗