A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
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 λ=1 and μ=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 ℤ/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. 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.
Related
- A Local Geometric Analysis of Maximal Coding Rate Reduction via Error Bounds
- Fixed Convex-Lens Spectral Constants: Möbius Reduction, Sharp Model Theorems, and Angle-Dependent Bounds
- Equidistant Affine Subspaces: Explicit Bounds, Codimension-Two Reduction, and Transverse Products
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Weil positivity in compact windows: a finite reduction, certified two-sided bounds, and a Landau-Widom decay law
BibTeX
@misc{thakkar2026forcedstructure,
title = {{A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph}},
author = {Aalok Thakkar and Simone Severini},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.11211},
eprint = {2608.11211},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.11211},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
AU - Aalok Thakkar
AU - Simone Severini
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2608.11211
UR - https://arxiv.org/abs/2608.11211
AB - 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 λ=1 and μ=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 ℤ/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. 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.
ER -