Exponentially many graphs are determined by their spectrum
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916483931570176 |
|---|---|
| author | Koval, Illya Kwan, Matthew |
| author_facet | Koval, Illya Kwan, Matthew |
| contents | 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 $e^{c\sqrt{n}}$). We also propose a number of further directions of research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_09788 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exponentially many graphs are determined by their spectrum Koval, Illya Kwan, Matthew Combinatorics Spectral Theory 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 $e^{c\sqrt{n}}$). We also propose a number of further directions of research. |
| title | Exponentially many graphs are determined by their spectrum |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2309.09788 |