The spectral gap of random graphs with given expected degrees (Q2380304)

Summary: We investigate the Laplacian eigenvalues of a random graph \(G(n,{\mathbf d})\) with a given expected degree distribution \textbf{d}. The main result is that w.h.p. \(G(n,{\mathbf d})\) has a large subgraph \(\operatorname{core} G(n,{\mathbf d})\) such that the spectral gap of the normalized Laplacian of \(\operatorname{core} G(n,{\mathbf d})\) is \(\geq 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\to\infty\). The present paper complements the work of \textit{F. Chung, L. Lu} and \textit{V. Vu} [Internet Math. 1, No.~3, 257--275 (2004; Zbl 1080.05021)].