EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Exponentially Many Graphs Are Determined By Their Spectrum

Illya Koval, Matthew Kwan

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →