Metraipolis › archive › dc_417d6fd23831
Neurosymbolic Discovery of Algebraic Graph Constructions — arXiv:2608.08118
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08118
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:09:11.369Z
- SHA-256 of the archived text
e98139f3ea0b2f0328246ee282bfa377511e14532429b8d59153f5a73a3f186d- Stable URL of this page
https://metraipolis.com/documento/dc_417d6fd23831
How to cite
Neurosymbolic Discovery of Algebraic Graph Constructions — arXiv:2608.08118 — arXiv (en), https://arxiv.org/abs/2608.08118 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_417d6fd23831 (Metraipolis archive dc_417d6fd23831, sha256 e98139f3ea0b2f0328246ee282bfa377511e14532429b8d59153f5a73a3f186d)
BibTeX
@misc{dc417d6fd23831,
title = {Neurosymbolic Discovery of Algebraic Graph Constructions — arXiv:2608.08118},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08118},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_417d6fd23831; sha256 e98139f3ea0b2f0328246ee282bfa377511e14532429b8d59153f5a73a3f186d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08118. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
There are several methods for searching for graphs with prescribed properties, such as SAT solvers and specialized generators. These methods return the result as raw data: an adjacency matrix or a string encoding. The raw data certifies that the graph exists, but it does not reveal any structural properties of the graph. We ask whether one can automatically discover a short algebraic description if only this raw data is provided. We look for a description such as a Cayley graph $\mathrm{Cay}(\Gamma, S)$ or a lexicographic product $C_5[K_3]$. We address this question with a neurosymbolic approach. We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training. The model interleaves reasoning with calls to the computer algebra system SageMath: it analyzes the target graph, proposes and tests candidate constructions, and revises them until the output matches the target. The agent communicates with SageMath through a Model Context Protocol (MCP) server, which we release as a general-purpose bridge. Whether a construction matches the target is checked by a single exact isomorphism test, and therefore rests on the symbolic side and not on the model. We test the approach on a benchmark of 100 highly symmetric graphs, namely two-orbit graphs on up to 25 vertices; the benchmark was fixed in advance. Our agent could find verified algebraic constructions for all of them, without falling back to raw encodings. A strong template-enumeration baseline reaches only about $20\%$, and a catalog lookup could not identify any of these graphs. However, construction quality declines when symmetry is removed. As a concrete application, we identify the smallest known counterexample to the Bernhart-Kainen dispersability conjecture, a $16$-vertex graph that enumeration found as raw data. For this graph, our agent found an explicit algebraic construction.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Machine Learning (cs.LG); Symbolic Computation (cs.SC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.08118 — 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-19T09:05:33.604Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).