How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.

But what is known about the expected number of distinct eigenvalues of a random graph?

-
Have you looked in Bollobas's book on random graphs? I'd expect all the eigenvalues to be distinct (with asymptotic probability 1), but I don't know that for a fact. – Andreas Blass Apr 21 '13 at 20:27
Do you mean the eigenvectors (in $\ell_1$) of the adjacency matrix of the infinite Rado graph? – Goldstern Apr 21 '13 at 22:13
I assumed the question referred to the asymptotic behavior of large finite random graphs. That might make a big difference, since the infinite random graph has lots of automorphisms, while finite random graphs are rigid with asymptotic probability 1. – Andreas Blass Apr 22 '13 at 1:43
Pretty sure it isn't known, though most people would conjecture the even stronger result that the characteristic polynomial is usually irreducible. Chris Godsil will give us an authoritative answer shortly. – Brendan McKay Apr 22 '13 at 4:15

1 Answer

In this recent paper of Erdos, Knowles, Yau, and Yin, it is shown that in the bulk of the spectrum, the spacing between eigenvalues of an Erdos-Renyi graph on $n$ vertices obeys GOE statistics asymptotically. This implies that most of the eigenvalues are simple (i.e. $n-o(n)$ of the $n$ eigenvalues are simple) asymptotically almost surely, so that the number of distinct eigenvalues is $n-o(n)$ a.a.s.. It is very likely that in fact a.a.s. all of the $n$ eigenvalues are simple; Van Vu and I have some preliminary unpublished results in this direction but we are still working on the full problem.

-
Have you published your work on that subject already? – Bach Oct 13 '14 at 13:08
We now have an arXiv preprint: arxiv.org/abs/1412.1438 – Terry Tao Dec 5 '14 at 1:25