×

Descriptive complexity of graph spectra. (English) Zbl 1430.68118

Väänänen, Jouko (ed.) et al., Logic, language, information, and computation. 23rd international workshop, WoLLIC 2016, Puebla, Mexico, August 16–19th, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9803, 183-199 (2016).
Summary: 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 \(C^3\) are co-spectral, and this is not the case with \(C^2\), 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.
For the entire collection see [Zbl 1343.03002].

MSC:

68Q19 Descriptive complexity and finite models
03C13 Model theory of finite structures
03C80 Logic with extra quantifiers and operators
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05E30 Association schemes, strongly regular graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alzaga, A., Iglesias, R., Pignol, R.: Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements. J. Comb. Theory Ser. B 100(6), 671–682 (2010) · Zbl 1208.05086 · doi:10.1016/j.jctb.2010.07.001
[2] Ananchuen, W., Caccetta, L.: Cubic and quadruple paley graphs with the \[ n \] -e. c. property. Discrete Math. 306(22), 2954–2961 (2006) · Zbl 1107.05078 · doi:10.1016/j.disc.2006.03.073
[3] Babai, L., Erdos, P., Selkow, S.M.: Random graph isomorphism. SIAM J. Comput. 9(3), 628–635 (1980) · Zbl 0454.05038 · doi:10.1137/0209047
[4] Babai, L., Kučera, L.: Canonical labelling of graphs in linear average time. In: 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 39–46. IEEE (1979) · doi:10.1109/SFCS.1979.8
[5] Barghi, A.R., Ponomarenko, I.: Non-isomorphic graphs with cospectral symmetric powers. Electron. J. Comb. 16(1), R120 (2009) · Zbl 1188.05084
[6] Blass, A., Exoo, G., Harary, F.: Paley graphs satisfy all first-order adjacency axioms. J. Graph Theory 5(4), 435–439 (1981) · Zbl 0472.05058 · doi:10.1002/jgt.3190050414
[7] Brouwer, A.E., Van Lint, J.H.: Strongly regular graphs and partial geometries. In: Enumeration and Design (Waterloo, Ont., 1982), pp. 85–122 (1984)
[8] Cai, J., Fürer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389–410 (1992) · Zbl 0785.68043 · doi:10.1007/BF01305232
[9] Ebbinghaus, H.B., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999) · Zbl 0932.03032
[10] Elsawy, A.N.: Paley graphs and their generalizations (2012). arXiv preprint. arXiv:1203.1818
[11] Fagin, R.: Probabilities on finite models. J. Symbolic Logic 41(01), 50–58 (1976) · Zbl 0341.02044 · doi:10.2307/2272945
[12] Friedland, S.: Coherent algebras and the graph isomorphism problem. Discrete Appl. Math. 25(1), 73–98 (1989) · Zbl 0704.05023 · doi:10.1016/0166-218X(89)90047-4
[13] Godsil, C., Royle, G.F.: Algebraic Graph Theory, vol. 207. Springer, New York (2013) · Zbl 0968.05002
[14] Hella, L., Kolaitis, P.G., Luosto, K.: How to define a linear order on finite models. Ann. Pure Appl. Logic 87(3), 241–267 (1997) · Zbl 0884.03034 · doi:10.1016/S0168-0072(97)00008-0
[15] Higman, D.G.: Coherent configurations. Geom. Dedicata 4(1), 1–32 (1975) · Zbl 0333.05010 · doi:10.1007/BF00147398
[16] Immerman, N., Lander, E.: Describing graphs: a first-order approach to graph canonization. In: Selman, A.L. (ed.) Complexity Theory Retrospective, pp. 59–81. Springer, New York (1990) · doi:10.1007/978-1-4612-4478-3_5
[17] Kolaitis, P.G., Vardi, M.Y.: Infinitary logics and 0–1 laws. Inf. Comput. 98(2), 258–294 (1992) · Zbl 0762.03016 · doi:10.1016/0890-5401(92)90021-7
[18] Kučera, L.: Canonical labeling of regular graphs in linear average time. In: 28th Annual Symposium on Foundations of Computer Science, pp. 271–279. IEEE (1987)
[19] Leman, A.A., Weisfeiler, B.: A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya 2(9), 12–16 (1968)
[20] Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004) · Zbl 1060.03002 · doi:10.1007/978-3-662-07003-1
[21] Schwenk, A.J.: Almost all trees are cospectral. In: New Directions in the Theory of Graphs, pp. 275–307 (1973)
[22] Van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241–272 (2003) · Zbl 1026.05079 · doi:10.1016/S0024-3795(03)00483-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.