# What is the spectrum of the Rado graph?

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.

-
As David Cohen commented, what notion of spectrum are you intending for a graph in which every vertex has infinite degree? – András Salamon Mar 18 '13 at 16:58

## 1 Answer

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$

-
Why would $0,…,n−1$ using Rado's original numbering be the natural choice of finite restriction—why not the $n$ least-numbered neighbours of some enumeration of the vertices, or the first $n$ vertices in some other numbering of the graph? The spectrum seems to depend on this choice, and it seems possible that the limits obtained for some choices differ from other choices. – András Salamon Mar 18 '13 at 22:05
I only said one could look at it. I'd say it seems a reasonable choice but I agree that it may not be and that others may be better. Perhaps the spectrum is pretty robust. That might be a nice result. – Aaron Meyerowitz Mar 19 '13 at 6:33