Almost all graphs have no cospectral mate with fixed level

Abstract

Haemers conjectures that almost all graphs are determined by their spectra. Suppose $G\sim \mathcal{G}(n,p)$ is a random graph with each edge chosen independently with probability $p$ with $0<p<1$. Then $$\mathrm{Pr}(G\text{ is not controllable})+\sum _{\ell =2}^{n^{n^2}}\mathrm{Pr}(G\text{ has a generalized copsectral mate with level }\ell )\to 0$$ as $n\to \infty$ implies that almost all graphs are determined by their generalized spectra. It is known that almost all graphs are controllable. We show that almost all graphs have no cospectral mate with fixed level $\ell$, namely $$\mathrm{Pr}(G\text{ has a copsectral mate with level }\ell )\to 0$$ as $n\to \infty$ for every $\ell \ge 2$. Consequently, $$\mathrm{Pr}(G\text{ has a generalized copsectral mate with level }\ell )\to 0$$ as $n\to \infty$ for every $\ell \ge 2$. The result can also be interpreted in the framework of random integral matrices.

8 page