Dawar, A;
Severini, S;
Zapata, O;
(2016)
Descriptive Complexity of Graph Spectra.
In: Vaananen, J and Hirvonen, A and DeQueiroz, R, (eds.)
Logic, Language, Information, and Computation.
(pp. pp. 183-199).
Springer
Preview |
Text
1603.07030v5.pdf - Accepted Version Download (221kB) | Preview |
Abstract
Two graphs are co-spectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are co-spectral with it are isomorphic to it. We consider these properties in relation to logical definability. We show that any pair of graphs that are elementarily equivalent with respect to the three-variable counting first-order logic C3C3 are co-spectral, and this is not the case with C2C2 , nor with any number of variables if we exclude counting quantifiers. We also show that the class of graphs that are determined by their spectra is definable in partial fixed-point logic with counting. We relate these properties to other algebraic and combinatorial problems.
Type: | Proceedings paper |
---|---|
Title: | Descriptive Complexity of Graph Spectra |
Event: | 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16–19th, 2016 |
Location: | Benemerita Univ Autonoma Puebla, Dept Comp Sci, Puebla, MEXICO |
ISBN-13: | 978-3-662-52920-1 |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1007/978-3-662-52921-8_12 |
Publisher version: | http://dx.doi.org/10.1007/978-3-662-52921-8_12 |
Language: | English |
Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
Keywords: | Science & Technology, Technology, Physical Sciences, Computer Science, Theory & Methods, Mathematics, Applied, Computer Science, Mathematics, Descriptive complexity, Algebraic graph theory, Isomorphism approximations, FINITE-MODELS, PALEY GRAPHS, ISOMORPHISM |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/1526418 |
Archive Staff Only
View Item |