Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
1  
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
2  
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 1

up vote 9 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|improve this answer
    
Have you published your work on that subject already? –  Bach Oct 13 at 13:08
    
We now have an arXiv preprint: arxiv.org/abs/1412.1438 –  Terry Tao Dec 5 at 1:25

Your Answer

 
discard

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.