The Spectral Gap of Random Graphs with Given Expected Degrees - Coja-Oghlan, Amin; Lanka, André (The Electronic Journal of Combinatorics, 2009)
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 $≥1-c_0\bar d_{\min}^{-1/2}$ with high probability; here $c_0>0$ is a constant, and $\bar d_{\min}$ signifies the minimum expected degree. The result in particular applies to sparse graphs with $\bar d_{\min}=O(1)$ as $n→∞$. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].