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?



How many distinct eigenvalues does a random graph have?
In [this recent paper](http://arxiv.org/abs/1103.3869) 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.


