cs.AIJul 13, 2026

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

Authors: Aalok Thakkar, Simone Severini

Organizations: Vachani School of Advanced Computing, Ashoka University, India · UCL

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.

Figures & tables

Explore similar work

CardsList
  1. Neurosymbolic Discovery of Algebraic Graph Constructions

    Aug 8, 2026David Seka, Stefan SzeiderGraph ConstructionNeuro-Symbolic Reasoning

  2. AutoGraphForge: Towards Automated Graph Theory Discovery

    Sep 3, 2026Ján PastorekAutomated Theorem ProvingAutomated Algorithm Discovery

  3. RadonBench: A Benchmark of Classical and Learning-Guided Search Techniques for Problems in Combinatorial Geometry

    Oct 23, 2026Xiaoan Xu, Jesus A. De Loera, Ethan X. Fang +2Combinatorial OptimizationBenchmark Design