Exponentially Many Graphs Are Determined By Their Spectrum
The Quarterly Journal of Mathematics · 22.08.2024 · 75 (3) · 869-899
DOI: 10.1093/qmath/haae030 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Quarterly Journal of Mathematics, online erschienen am 19.06.2024. Verfasst von Illya Koval und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
As a discrete analogue of Kac’s celebrated question on ‘hearing the shape of a drum’ and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that ‘almost all graphs are determined by their spectrum’, meaning that the fraction of unlabelled n-vertex graphs which are determined by their spectrum converges to 1 as $n\to\infty$. In this paper, we make a step towards this conjecture, showing that there are exponentially many n-vertex graphs which are determined by their spectrum. This improves on previous bounds (of shape $\it{e}^{c\sqrt{n}}$). We also propose a number of further directions of research.
Zitieren
APA
Koval, I., & Kwan, M. (2024). Exponentially Many Graphs Are Determined By Their Spectrum. The Quarterly Journal of Mathematics, 75(3), 869-899. https://doi.org/10.1093/qmath/haae030
Vancouver
Koval I, Kwan M. Exponentially Many Graphs Are Determined By Their Spectrum. The Quarterly Journal of Mathematics. 2024;75(3):869-899. doi:10.1093/qmath/haae030
BibTeX
@article{Koval2024,
author = {Koval, Illya and Kwan, Matthew},
title = {Exponentially Many Graphs Are Determined By Their Spectrum},
journal = {The Quarterly Journal of Mathematics},
year = {2024},
volume = {75},
number = {3},
pages = {869--899},
doi = {10.1093/qmath/haae030}
}
EUVIMED