Exponentially many graphs are determined by their spectrum
Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899.
Download
Journal Article
| Published
| English
Scopus indexed
Department
Abstract
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 → ∞.
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
√
n
). We also
propose a number of further directions of research.
Publishing Year
Date Published
2024-06-19
Journal Title
Quarterly Journal of Mathematics
Acknowledgement
Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777.
Volume
75
Issue
3
Page
869-899
ISSN
eISSN
IST-REx-ID
Cite this
Koval I, Kwan MA. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 2024;75(3):869-899. doi:10.1093/qmath/haae030
Koval, I., & Kwan, M. A. (2024). Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. Oxford University Press. https://doi.org/10.1093/qmath/haae030
Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” Quarterly Journal of Mathematics. Oxford University Press, 2024. https://doi.org/10.1093/qmath/haae030.
I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their spectrum,” Quarterly Journal of Mathematics, vol. 75, no. 3. Oxford University Press, pp. 869–899, 2024.
Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899.
Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” Quarterly Journal of Mathematics, vol. 75, no. 3, Oxford University Press, 2024, pp. 869–99, doi:10.1093/qmath/haae030.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2024_QuJofMath_Koval.pdf
946.41 KB
Access Level
![Open access file OA](https://research-explorer.ista.ac.at/images/access_open.png)
Date Uploaded
2024-09-06
MD5 Checksum
abf200d37ad69e6f2c0750a30296ad97
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2309.09788