My previous post discussed one of the major open problems in spectral graph theory: the conjecture by van Dam and Haemers which asks to show that almost all graphs are determined by their spectrum. Unfortunately, the proof techniques required to address this conjecture appear to be lacking at the moment. Even numerical investigations are nontrivial.
Here, we’ll take a different perspective which was originally considered by Johnson and Newman in 1980. They proposed that the difficulties surrounding cospectral graphs may be a symptom of some deeper issue:
It is our view, however, that to some extent these examples are algebraic accidents due to the interpretation of the formal symbols $0$ and $1$ as real numbers.
From this viewpoint, the following definitions may be natural:
Definition. (Generalized adjacency matrix) Given a graph $G$ and two real numbers $x,y \in \mathbb{R}$, denote $A^{x,y}$ for the matrix whose coordinates are defined by $$A^{x,y}_{i,j} = \begin{cases}x & \text{ if }i\text{ and }j\text{ are adjacent in }G,\\ y &\text{else.} \end{cases} $$
Definition. (Generalized cospectral) Two non-isomorphic graphs $G$ and $H$ are said to be generalized cospectral if $\operatorname{spec}(A^{x,y}_G) = \operatorname{spec}(A^{x,y}_H)$ for all $x,y \in \mathbb{R}$.
The generalized spectrum provides more information than the classical adjacency spectrum. Hence, there are fewer graphs which are generalized cospectral than are cospectral in the usual sense.
It should be noted that there do exist graphs which are generalized cospectral; see Figure 1 for example. In fact, numerical evidence by Haemers and Spence from 2004 shows that about $20.8\%$ of the graphs on $n = 11$ vertices are generalized cospectral. Considering that that roughly $21.1\%$ are cospectral in the usual sense, it seems possible that generalized cospectrality is not that much more restrictive than the usual sense. If the latter is true, then studying the generalized notion provides a good model for the conjecture by van Dam and Haemers.
Surprisingly, it turns out that the new notion is equivalent to a bunch of other natural criteria:
Theorem 1. Fix two non-isomorphic graphs $G$ and $H$. Then, the following are equivalent:
- The graphs $G$ and $H$ are generalized cospectral.
- The graphs have the same adjacency spectrum and the complement graphs have the same adjacency spectrum.
- The (classical) adjacency matrices are related as $A_G = Q^T A_H Q$ for some orthogonal matrix $Q$ with rational entries whose rows and columns all sum to one.
- It holds that $\operatorname{spec}(A^{x,y}_G) = \operatorname{spec}(A^{x,y}_H)$ when $x = 1 + \varepsilon$ and $y = \varepsilon$ for some irrational $\varepsilon$.
- There are two distinct values of $y\in \mathbb{R}$ such that $\operatorname{spec}(A^{x,y}_G) = \operatorname{spec}(A^{x,y}_H)$ with $x=1$.
The equivalence of 1,2,3 and 5 is due to Johnson and Newman. The equivalence with item 4 was established by van Dam, Haemers, and Koolen in 2007. The equivalence with item 3 has also been established (independently) by Wang and Xu in 2004.
These equivalencies show that generalized cospectrality is a nice notion insofar that interesting things can be said about it, but they do not make the verification much easier. The problem is that the equivalent definitions still make reference to the candidate cospectral graph $H$. Hence, to show that $G$ is determined by its generalized spectrum one still has to enumerate all candidate graphs $H$. Consequently, even numerical investigations remain difficult.
However, and the importance of this result is difficult to overstate, it turns out that there is a tractable sufficient condition!!! The first such criterion was found by Wang and Xu in 2006 and it has been refined in a sequence of subsequent results.
Definition. The walk matrix $W$ of a graph $G$ is the $n\times n$ matrix whose $i,j$-th entry counts the number of walks starting from $i$ which have length $j-1$. Equivalently, if $e = (1,…,1)^T$ is the all-ones vector, then the columns of this matrix may be written as $$W = [e, Ae, A^2e, …, A^{n-1}e].$$
Theorem 2. (Wang, 2017) Assume that $\det(W) = 2^{\lfloor n/2 \rfloor} m$ for some odd square-free integer $m$. Then, $G$ is determined by its generalized spectrum.
Wang conjectured in 2017 that the condition should hold for a non-vanishing fraction of graphs. If true, this would be astounding! Recall that Kwan and Koval’s result from 2023 showing that exponentially many graphs are determined by the usual spectrum may be considered a breakthrough. However, exponentially many is only a quickly vanishing fraction. A constant fraction being determined by generalized spectrum would provide strong evidence for the conjecture by van Dam and Haemers.
Until recently, there was no clear indication in the literature what techniques should be used to study how often the condition is satisfied. This is a problem which I have myself worked on. It turns out that one can use tools from random matrix theory to study the algebraic properties of the walk matrix which occur when $A$ is taken to be a random matrix; see arXiv:2401:12655.
Proof of the sufficient condition
The remainder of this post is devoted to an outline for the proof of Theorem 2. We’ll follow a recent proof by Qui, Wang, Wang, and Zhang from 2023 which yields a stronger result. The reason that to focus on the latter is not necessarily because of the added strength. Rather, the formulation of the new result leads one to new insights. In particular, it suggests that the determinant of $W$ is only a shadow of the data which we should be thinking about.
Note that $W$ is an integer matrix. Consequently, it has a Smith normal form. That is, there exist $U,V\in \mathbb{Z}^{n\times n}$ which are invertible over the integers and a diagonal matrix $D = \operatorname{diag}(d_1,\ldots,d_n)$ with nonnegative diagonal entries satisfying $d_1 \mid d_{2} \mid \ldots \mid d_n$ such that we can factorize $$W = U D V.$$ In concrete terms, invertibility over the integers means that $\det(U), \det(V) \in \{+1,-1 \}$. Consequently, $\det(W) = \pm \prod_{i=1}^n d_i$ which shows that the Smith normal form is more refined data than the determinant.
Now, consider some graph $G$ and suppose that there exists some generalized cospectral mate $H$. Denote $A,B$ for the adjacency matrices of these graphs. Then, by item 3 in Lemma 1, there exists a rational orthogonal matrix $Q$ with $Qe = e$ and $Q^T e=e$ such that $$Q^T A Q = B.$$Being rational, there exists an integer $\ell >0$ such that $\ell Q\in \mathbb{Z}^{n\times n}$ is an integer matrix. Let us call the least such integer $\ell$ the level of $Q$. If we can show that $\ell = 1$, then we are done! Indeed, it then follows that $Q$ is a permutation matrix. Then, $G$ and $H$ are isomorphic, as desired.
The next result shows that the Smith normal form can be used to control the level:
Theorem 3. (Qui, Wang, Wang, and Zhang, 2023) Consider a rational orthogonal matrix $Q$ of level $\ell$ such that $Qe = e$, $Q^Te =e$, and with $Q^TAQ$ is a $\{0,1 \}$-matrix. Additionally, consider a prime $p$ and let $k\geq 0$ be the greatest integer such that $p^k$ divides $d_n$. Then, $$\max\{p, p^{k} \} \not\mid \ell$$ provided that $p$ is odd and $\operatorname{rank}_{\mathbb{F}_p}(W)\geq n-1$, or $p=2$ and $\operatorname{rank}_{\mathbb{F}_p}(W) = \lceil n/2\rceil$.
The reason that $p=2$ has to be a special case is because $W^T W \equiv 0 \bmod 2$ by direct computation. It follows that $\operatorname{rank}_{\mathbb{F}_2}(W) \leq \lceil n/2 \rceil$. Hence, imposing that $\operatorname{rank}_{\mathbb{F}_2}(W) \geq n-1$ as we do for odd primes would give rise to a condition which can not be satisfied.
Theorem 3 implies Theorem 2 as a special case. Indeed, suppose that $\det(W) = 2^{\lfloor n/2 \rfloor}m$ for some square-free odd integer $m$. Then, for odd primes $p$, the relation between the Smith normal form and the determinant implies that $p^2$ does not divide $d_n$. Further, it then follows that $\operatorname{rank}_{\mathbb{F}_p}(W) \geq n-1$ since there may not be more than one $d_i$ which is divisible by $p$. Hence, Theorem 3 implies that $p\not\mid \ell$. For the prime $2$, rank-based considerations similarly imply that exactly $\lceil n/2 \rceil$ of the $d_i$ are divisible by $p$. Further, it then follows that $d_n$ is not divisible by $2^2$. Hence, $2 \not\mid \ell$ and we may conclude that $\ell = 1$ as desired.
It remains to understand why Theorem 3 holds. The key technical ingredient for the argument, which we will assume here without proof, is that the conditions of the theorem imply that there exists a polynomial $M(x):= x^r + \sum_{i=0}^{r-1}a_i x^i$ which satisfies the following equations simultaneously$$
\begin{cases}M(A)e = a_0 e + a_1 Ae + \cdots + a_{r-1}A^{r-1}e + A^r \equiv 0 \bmod p\\
M(B)e = a_0 e + a_1 Be + \cdots + a_{r-1}B^{r-1}e + B^r \equiv 0 \bmod p
\end{cases}
$$with $r= \operatorname{rank}_{\mathbb{F}_p}(W(G))$. (Here, as before, $B$ is the adjacency matrix associated with the generalized cospectral mate $H$.)
To see how this helps us, define an integral matrix $\hat{W}(G)$ by $$\hat{W}(A) = \Bigl[e,Ae, \ldots, A^{r-1}e, \frac{M(A)e}{p},\ldots,\frac{A^{n-r-1}M(A)e}{p}\Bigr]$$and similarly define $\hat{W}(H)$ in terms of $B$. Then, using that $Q^T A Q = B$ implies that $Q^T A^k e= B^k e$ for all $k\geq 0$, $$Q^T\hat{W}(G) =\hat{W}(B).$$ This may be combined with the following two lemmas to conclude the proof.
Lemma 4. Consider two non-singular integer matrices $X,Y$ and a rational orthogonal matrix $Q$ such that $QX = Y$. Then, the level of $Q$ satisfies $\ell \mid \operatorname{gcd}(d_n(X), d_n(Y))$.
Proof. Let $X = USV$ be the Smith normal factorization. Then, we have that $$Q = YV^{-1}S^{-1}U^{-1}.$$In particular, $d_n(X)Q$ is an integer matrix which implies that $\ell \mid d_n(X)$. By symmetry, one can similarly argue that $\ell \mid d_n(Y)$. $\square$.
Lemma 5. Suppose that the Smith normal form of $W$ is $\operatorname{diag}(d_1,\ldots,d_n)$ where $p\not\mid d_r$ and $p\mid d_{r+1}$. Then, the Smith normal form of $\hat{W}$ is $$\operatorname{diag}\Bigl(d_1,\ldots, d_r, \frac{d_{r+1}}{p},\ldots,\frac{d_n}{p}\Bigr).$$
Proof sketch. First, one can show that the matrix $\tilde{W} = [e,Ae, …, A^{r-1}e, M(A)e, AM(A)e,…, A^{n-r-1}M(A)e]$ has the same Smith normal form as $W$. Second, one can study the relation between the Smith normal form of $\tilde{W}$ and $\hat{W}$. $\square$
This concludes the proof outline. More details can be found in the paper by Qui, Wang, Wang, and Zhang. Alternatively, see my preprint arXiv:2401:12655 for some techniques which have been developed to study how often the conditions are satisfied.