The eigenvalues $\lambda_1 \geq \cdots \geq \lambda_n$ of the adjacency matrix of a graph encode a lot of information. For instance, an elegant bound on the chromatic number is known due to Hoffman. There are so many structural properties which admit good spectral estimates that one may start to wonder whether the spectrum perhaps contains all the structure:
Does the spectrum of the adjacency matrix determine a graph uniquely up to isomorphism?
This question is a graph-theoretic analogue to the question “Can one hear the shape of a drum” which was famously posed by Kac in 1966. Indeed, the fundamental tones that a drum can produce are given by the eigenvalues of a linear operator associated to the drum.
Unfortunately, as with Kac’s question, the answer is “No”.
Theorem. (Collatz and Sinogowitz, 1957) There exist non-isomorphic graphs $G$ and $H$ whose adjacency matrices have the same spectrum. Such graphs are said to be cospectral.
The smallest example of two such graphs is displayed in Figure 1. Note that this example also demonstrates that the spectrum is not sufficient to determine if a graph is connected or not.
In fact, not only do cospectral graphs exists, the following result shows that almost all trees are cospectral!
Theorem. (Schwenk, 1973) Denote $\mathcal{T}_n$ for the set of all trees on $n$ nodes. Then,
$$\lim_{n\to \infty}\frac{1}{\#\mathcal{T}_n}\# \{T \in \mathcal{T}_n: T\text{ is cospectral} \} =1.$$
Proof outline. Given two rooted trees $S,T$, denote $S\cdot T$ for the tree found by identifying the roots. Then, Schwenk provides two rooted trees $R$ and $S$ on 9 vertices such that for any rooted tree $T$ it is easy to show that $T \cdot R$ and $T\cdot S$ are cospectral; see Figure 2. Subsequently, and this takes a bit of work, Schwenk shows that a random tree $\tau$ in $\mathcal{T}_n$ can be expressed as $\tau \cong T\cdot R$ for some $T$ with high probability. Then, $\tau$ is cospectral to $T\cdot S$. $\square$
Schwenk’s result is quite striking because it shows that trees are only rarely determined by their spectrum. Ever since this result, many researchers have wondered what might be true for generic graphs. Note that trees are only a negligible proportion of all graphs so Schwenk’s result can not tell much about this. The general question turns out to be quite difficult. For instance, the following statement may be found in Godsil’s book from 1993:
It is still an open question whether almost all graphs are characterized by their characteristic polynomials. It is not even clear if we should seek to prove this, or to disprove it.
This problem remains open to this day. Still, there is nowadays a suspicion in what direction the answer may lie. It has been conjectured that the situation is the opposite from that in Schwenk’s result:
Conjecture. (van Dam and Haemers, 2003) Denote $\mathcal{G}_n$ for the set of all graphs on $n$ nodes. Then, $$\lim_{n\to \infty}\frac{1}{\#\mathcal{G}_n}\# \{G \in \mathcal{G}_n: G\text{ is determined by spectrum} \} =1.$$
This conjecture arose from the following line of reasoning:
- The standard method for producing cospectral graphs, known as Godsil-McKay switching, only produces an asymptotically negligible number of graphs.
- Based on some numerical evidence arising from an enumeration of all graphs with $n\leq 11$ vertices, it seems possible that a nontrivial proportion of all cospectral graphs arises from Godsil-McKay switching.
Note that $n\leq 11$ is rather small. Accessing significantly larger values is challenging because the number of graphs on $n$ vertices grows incredibly quickly and we have no general-purpose techniques to show that a graph is determined by its spectrum. (That is, apart from exhaustive enumeration.) The conjecture is hence quite bold as the evidence is not conclusive by any means!
To illustrate the state-of-the-art of results and proof techniques in the spirit of this conjecture, consider the following recent result:
Theorem. (Koval and Kwan, 2023) There exists a constant $c>0$ such that for all $n\geq 1$, $$\#\{G \in \mathcal{G}_n: G\text{ is determined by spectrum} \} \geq \exp(cn).$$
This result represents a breakthrough since the best known lower bound had been stuck at $\exp(c\sqrt{n})$ for a long time. However, considering that there are at least $\exp(c n^2)$ non-isomorphic graphs on $n$ vertices, the proportion relative to $\#\mathcal{G}_n$ still vanishes quite quickly.
The employed proof structure is typical for this line of work. One first considers a special family of graphs; see Figure 3. Subsequently, one exploits the special structure of the family to prove that each graph in the family is determined by its spectrum.
Unfortunately, it seems unlikely that such constructive arguments will lead to a resolution of the conjecture. In fact, Koval and Kwan argue that a lower bound of the form $\exp(cn^{1+\varepsilon})$ for any fixed $\varepsilon >0$ may already be beyond constructive techniques. Since constructive techniques are the only known methods to produce graphs which can be proved to be determined by spectrum, it seems that the technology required to address the conjecture is lacking at the moment.
My next post concerns a slight variation of the problem where in addition to the spectrum of the graph, one is also given the spectrum of the complement graph. Intriguingly, this slight variation admits flexible sufficient conditions! This will give more insight and provide additional evidence in favor of the conjecture.