Question

non bipartite random regular graph, degree can be fix, or grow slowly with n, do you believe it has simple spectrum? thanks

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

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 3

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.