What is the spectrum of the Rado graph?

Question

Isn't this question self-explanatory? There is a lot of literature about the Rado graph $R$ in various places. This graph is also known as the "Random Graph" because a countable random graph is isomorphic to $R$ with probability 1. There is also a lot of literature about spectra of graphs, finite and infinite. The Rado graph is an exceptional object, and I would expect its spectrum to be interesting as well. For that matter, its characteristic function should be interesting too.

Answer 1

The infinite Rado graph could be specified as having vertices numbered $0,1,2,\cdots$ where there is an edge $(m,i)$ when the $i$th bit of the binary expansion of $m$ is a $1$. One could look at the induced graph on the vertices $0,\cdots,n-1$ either for all $n$ or when $n$ is a power of $2$. As commented below, that is perhaps not the only choice. However it was an open ended question and I found that choice appealing. I had expected that things would be different right after a new power of $2$ compared to half way between two such. Below is a plot of the eigenvalues up to $n=129.$

Some random observations about these $130$ cases:

• The number of distinct eigenvalues for n from $0$ to $12$ are $1,2,3,4,5,6,7,7,9,9,9,8,9$

• Starting with $n=6$ There are $2k+3$ non-zero eigenvalues for $2^k \le n \lt 2^{k+1}.$ These are distinct with the exception of a double eigenvalue of$-2$ at $n=11.$

• There is an eigenvalue of $0$ except for $n=1,3,4,5$. Hence, starting at $n=8$ it has multiplicity $n-2k-1$ for $k$ as above. That is; the multiplicity is $1$ at $n=8$ and then increases by $1$ when $n$ does, except that it drops by $2$ when $n$ is a power of $2.$

• The only non-zero values which occur for more than one $n$ (up to $n=127$) are

  • $-2$ for $n=9,10,11,12,13$,
  • $+1$ for $n=1,4,10,11$ and
  • $-1$ for $n=3,4$

• The only integer eigenvalues not already mentioned are $+2$ for $n=35$ and$-4$ for $n=57$