On the spectrum of random regular graph

Question

For a random $d$-regular graph, where $d$ can be fixed or can grow slowly with the size of the graph $n$, what can we say about its spectrum - Do you believe it has simple spectrum?

Thank you,

Answer 1

Yes, I believe that it will have simple spectrum for d >= 3 and it feels like something that should have been proved, though I can't actually find it.

There is a loose association between automorphisms of a graph and multiple eigenvalues, and as most regular graphs have trivial automorphism group we lose this source of multiple eigenvalues. There are no other (frequently occurring) "reasons" for a graph to have multiple eigenvalues and so in general they won't be there.

ADDED:

Here are some exact numbers for connected (pairwise nonisomorphic) cubic graph: disconnected graphs vanish numerically and so we can ignore them.

10 vertices - 19 graphs - 6 with no repeated eigs = 31% simple

12 vertices - 85 graphs - 18 with no repeated eigs = 21% simple

14 vertices - 509 graphs - 316 with no repeated eigs = 62% simple

16 vertices - 4060 graphs - 2181 with no repeated eigs = 54% simple

18 vertices - 41301 graphs - 26446 with no repeated eigs = 64% simple

(Actually this is growing more slowly than I expected... )

Answer 2

In 1986, Noga Alon conjectured in a Combinatorica article that, for any degree $d \ge 3$ and for any $\epsilon > 0$, most $d$-regular graphs on $n$ vertices have all their eigenvalues except $\lambda_1=d$ bounded above by $2 \sqrt{d−1} + \epsilon$. In 2003, Joel Friedman established this conjecture: "A proof of Alon's second eigenvalue conjecture," 2003. Some further developments on the distribution of the eigenvalues are reported in a paper by Miller, Novikoff, and Anthony Sabelli, "The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs" in Experimental Mathematics, 2008. Perhaps some of these references will help.

Answer 3

I guessed no but Gordon has changed my mind for degree greater than 2.

If it has degree 2 it is a union of cycles. Eigenvalues are $2\cos(\frac{2 \pi j}{k})$ for various $ k$. In particular 2 has multiplicity the number of components.

For random regular graphs of degree more than 2 I'd wildly guess that the eigenvalue behavior is like that of a large random symmetric matrix. This has been well studied, but not by me, all I know is the phrase "Gaussian Orthogonal Ensemble".

Some experiments with degree 3 graphs suggest that with 30 vertices one component is highly likely and there is a repeated eigenvalue ( most often 0) about 2% of the time. At 60 vertices it is more like 0.2%.

Answer 4

I am posting this answer to provide some additional references and information regarding the bulk spectrum of the adjacency matrix. (I believe that with probability $1$ the eigenvalues will be simple)

McKay's Law [1] for random $d$-regular graphs states that the spectrum weakly converges to the spectrum of the universal cover of the graph, which is a $d$-regular tree in this case. The spectral measure is given by $$d\mu_{\text{McKay}}(x)=d\mu(x)=\begin{cases} \frac{d\sqrt{4(d-1)-x^{2}}}{2\pi(d^{2}-x^{2})}dx & |x|\leq2\sqrt{d-1}\\ 0 & |x|>2\sqrt{d-1} \end{cases}. $$

In other words, if we take a random $d$-regular graph $G_n$ with adjacency matrix $A_n$, and eigenvalues $\lambda_n\leq \dots \leq \lambda_1=d$, then for every $-2\sqrt{d-1}\leq a<b\leq 2\sqrt{d-1}$ we have

$$\frac{\#\left\{ \lambda_{i}:\ a\leq\lambda_{i}\leq b\right\} }{n}=\int_{a}^{b}d\mu_{McKay}(x)+o_{n}(1)$$ with probability going to $1$ as $n\rightarrow \infty$.

Tran Vu and Wang [2] showed that if $d\rightarrow\infty$ as the size of the graph goes to infinity then the spectrum converges to Wigner's semicircle law. Note that for low fixed degree we don't get the semi circle - this is because the $2k^{th}$ moments are not simply the $k^{th}$ Catalan number multiplied by the spectral radius to the power of $2k$ - the base point has degree $d$ and this affects the calculation when $\frac{d}{d-1}\neq 1+o(1)$.

For a brief description of these results along with more references, I recommend Yufei Zhao's note Spectral Distributions of Random Graphs

References:

[1] Brendan Mckay, 1981, The expected eigenvalue distribution of a large regular graph.

[2] Linh Tran, Van Vu, Ke Wang, 2010 Sparse random graphs: Eigenvalues and Eigenvectors.

Answer 5

Fwiw, a plot of the spectrum of the sum of 10 random permutation matrices
shows the (semi)circle law: