Descriptive complexity of graph spectra
DOI10.1016/j.apal.2019.04.005zbMath1430.68119arXiv1603.07030OpenAlexW2939442208WikidataQ128060275 ScholiaQ128060275MaRDI QIDQ2273011
Anuj Dawar, Octavio Zapata, Simone Severini
Publication date: 18 September 2019
Published in: Annals of Pure and Applied Logic, Logic, Language, Information, and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.07030
strongly regular graphsalgebraic graph theoryspectral graph theoryfinite model theorydescriptive complexityisomorphism problemsisomorphism approximationscounting logics
Association schemes, strongly regular graphs (05E30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cospectral graphs and regular orthogonal matrices of level 2
- A note on non-\(\mathbb{R}\)-cospectral graphs
- Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
- Elements of finite model theory.
- Cubic and quadruple Paley graphs with the \(n\)-e.c. property
- Coherent algebras and the graph isomorphism problem
- Developments on spectral characterizations of graphs
- Infinitary logics and 0-1 laws
- An optimal lower bound on the number of variables for graph identification
- Coherent configurations. I: Ordinary representation theory
- How to define a linear order on finite models
- Which graphs are determined by their spectrum?
- Non-isomorphic graphs with cospectral symmetric powers
- Random Graph Isomorphism
- Paley graphs satisfy all first-order adjacency axioms
- Probabilities on finite models
This page was built for publication: Descriptive complexity of graph spectra
