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

CREATORAida Abiad, Anuj Dawar, Octavio B. Zapata-Fonseca
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32163
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.03601

Browse the full library · About the Tower of Babel