Metraipolis › archive › dc_ecda23c117a2

A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph — arXiv:2608.11211

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11211
License (as archived)
CC0-1.0
Archived
2026-10-19T05:15:07.556Z
SHA-256 of the archived text
4f0261de985c8de3ee1f7903011f7cf30dfb11b08b9a047d7fdc00890dae3f53
Stable URL of this page
https://metraipolis.com/documento/dc_ecda23c117a2

How to cite

A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph — arXiv:2608.11211 — arXiv (en), https://arxiv.org/abs/2608.11211 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ecda23c117a2 (Metraipolis archive dc_ecda23c117a2, sha256 4f0261de985c8de3ee1f7903011f7cf30dfb11b08b9a047d7fdc00890dae3f53)
BibTeX
@misc{dcecda23c117a2,
  title = {A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph — arXiv:2608.11211},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11211},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ecda23c117a2; sha256 4f0261de985c8de3ee1f7903011f7cf30dfb11b08b9a047d7fdc00890dae3f53},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11211. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Conway's 99-graph problem asks whether a strongly regular graph with parameters $\mathrm{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 $\mathrm{srg}(9,4,1,2)$. We also prove by exhaustive enumeration that no circulant graph on $\mathbb{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. 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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-13 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Symbolic Computation (cs.SC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.11211 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:08:46.594Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).