5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Apr 21, 2013 at 20:27
  • $\begingroup$ Do you mean the eigenvectors (in $\ell_1$) of the adjacency matrix of the infinite Rado graph? $\endgroup$
    – Goldstern
    Apr 21, 2013 at 22:13
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22, 2013 at 1:43
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 22, 2013 at 4:15

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Have you published your work on that subject already? $\endgroup$
    – Bach
    Oct 13, 2014 at 13:08
  • 1
    $\begingroup$ We now have an arXiv preprint: arxiv.org/abs/1412.1438 $\endgroup$
    – Terry Tao
    Dec 5, 2014 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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