The Spectral Gap of Random Graphs with Given Expected Degrees
The Spectral Gap of Random Graphs with Given Expected Degrees
We investigate the Laplacian eigenvalues of a random graph $G(n,\vec d)$ with a given expected degree distribution $\vec d$. The main result is that w.h.p. $G(n,\vec d)$ has a large subgraph core$(G(n,\vec d))$ such that the spectral gap of the normalized Laplacian of core$(G(n,\vec d))$ is $\geq1-c_0\bar d_{\min}^{-1/2}$ with high …