MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 11 down vote accepted

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.

share|cite|improve this answer
Have you published your work on that subject already? – Bach Oct 13 '14 at 13:08
We now have an arXiv preprint: – Terry Tao Dec 5 '14 at 1:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.