Return to Revisions

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 more, maybe half. Sometimes the polynomial doesn't factor beyond that. Other times it does. Adding one new vertex does not change things too much. It does not look that different to be near a power of $2$ compared to halfway between. It would appear based only on those cases that the smallest positive eigenvalue grows. I suppose that is obvious given that there is eigenvalue interlacing. Jump in and explore!