Exponentially many graphs are determined by their spectrum

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.