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$. Up to $n=16$ there are at first no zero eigenvalues then there get to be moreAs commented below, maybe half. Sometimes the polynomial doesn't factor beyond that is perhaps not the only choice. Other timesHowever it does. Adding one new vertex does not change things too muchwas an open ended question and I found that choice appealing. It does not lookI had expected that different tothings would be neardifferent right after a new power of $2$ compared to halfwayhalf way between. It would appear based only on those cases that the smallest positive eigenvalue grows two such. I suppose that is obvious given that thereBelow is eigenvalue interlacing. Jump in and explore!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$
