Sum-of-squares method shows Conway 99-graph likely does not exist
Towards a Sum-of-Squares Proof for the Nonexistence of Conway's 99-graph
Discrete Mathematics
Summary
There has been a long-standing puzzle about whether a special kind of graph called Conway's 99-graph exists. This graph would have very specific properties involving connections between points. The authors used a mathematical tool called sum-of-squares programming, combined with known restrictions on the graph’s small structures, to estimate the maximum number of certain triangles such a graph could have. Their calculated limit is smaller than what the theory predicts, suggesting that the Conway 99-graph probably does not exist.
What this means in practice
- •For graph algorithm designers: Exclude the existence of specific graph structures to optimize algorithms that rely on graph classification.
- •For network security engineers: Avoid relying on impossible graph configurations when modeling secure communication networks with strongly regular properties.
A theory result. No direct application yet.
Authors
Joseph Natal, Oleksiy Al-saadi
Abstract
Conway's $99$-graph is a strongly regular graph with parameters $(v,k,λ,μ) = (99,14,1,2)$ and whose existence has long been an open problem. We use both a sum-of-squares program and the fact that a strongly regular graph with $λ= 1, μ= 2$ has no diamond or $K_{2,3}$ subgraph to derive a loose upper bound for the number of triangles that such a graph could contain. This bound is less than the number of triangles that the graph's spectrum asserts, implying that it does not exist.