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

원문 초록

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.