Logical aspects of isomorphism of controllable graphs and cospectrality of distance-regularized graphs
Aida Abiad, Anuj Dawar, Octavio B. Zapata-Fonseca · 2026
Read Logical aspects of isomorphism of controllable graphs and cospectrality of distance-regularized graphs by Aida Abiad, Anuj Dawar, Octavio B. Zapata-Fonseca (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03601.txt.
Description
Aida Abiad, Anuj Dawar, and Octavio B Zapata-Fonseca bring logic to two questions about when graphs count as the same. Controllable graphs and distance-regularized graphs are usually characterized algebraically, through spectra and eigenvalues. Whether two such graphs are isomorphic, or merely share a spectrum, had never been studied through definability in first-order logic. Their 2026 paper is the first to do so, extending and unifying earlier results.
The headline result: cospectral distance-regularized graphs cannot be told apart by counting first-order logic with three variables. The same holds for the broader pseudo-distance-regularized family. Earlier theorems of this kind covered only strongly regular graphs and distance-regular graphs separately. The new work subsumes both, giving logicians and graph theorists one common frame for these equivalence questions.
Catalog record
| CREATOR | Aida Abiad, Anuj Dawar, Octavio B. Zapata-Fonseca |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32163 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03601