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?

Improve this question
$\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$
    – Andreas Blass
    Commented 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
    Commented 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$
    – Andreas Blass
    Commented 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$
    – Brendan McKay
    Commented Apr 22, 2013 at 4:15

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .