Van Dam–Haemers Conjecture: are almost all graphs determined by their adjacency spectrum?
Statement
Two graphs are *cospectral* if their adjacency matrices have the same multiset of eigenvalues. A graph is *determined by its spectrum* (DS) if no non-isomorphic graph is cospectral with it. Van Dam & Haemers (2003) conjectured that **almost all graphs are DS**, i.e. the fraction of (unlabeled) $n$-vertex graphs that are DS tends to $1$ as $n \to \infty$. Determine whether this holds. Computational sub-question: compute, for $n$ as large as feasible, the fraction $q_n$ of $n$-vertex graphs that have a cospectral mate (equivalently $1 - q_n$ is the DS fraction), and study its trend.
Acceptance. FULLY RESOLVES: a proof or disproof of the asymptotic statement. PARTIAL PROGRESS (computational, checkable): using $\texttt{nauty}$/$\texttt{geng}$ to enumerate all graphs on $n$ vertices and grouping them by characteristic polynomial, report the exact count of graphs with a cospectral mate for $n \ge 12$ (extending the published tables), with the eigenvalue/char-poly code and the cospectral-pair census. Any such new exact $q_n$ is independently reproducible and advances the empirical picture.
Background
Frontier: exact DS fractions were computed by Haemers & Spence up to $n = 11$; the fraction with a cospectral mate is small and non-monotonic at those sizes. Koval & Kwan (2024) proved that *exponentially many* $n$-vertex graphs are DS (arXiv:2309.09788, Quart. J. Math. 75), a major step, but the 'almost all' conjecture remains open. Source: Open Problem Garden, 'Are almost all graphs determined by their spectrum?' (www.openproblemgarden.org/op/are_almost_all_graphs_determined_by_their_spectrum); E. R. van Dam & W. H. Haemers, 'Which graphs are determined by their spectrum?', Linear Algebra Appl. 373 (2003) 241-272; see also MathWorld, 'Haemers Conjecture'.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Are almost all graphs determined by their spectrum? — Open Problem Garden | link |
| REF-02 | Koval & Kwan, Exponentially many graphs are determined by their spectrum (2024) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.