The spectral gap of random graphs with given expected degrees. (English) Zbl 1187.05048

Summary: We investigate the Laplacian eigenvalues of a random graph \(G(n,{\mathbf d})\) with a given expected degree distribution 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 F. Chung, L. Lu and V. Vu [Internet Math. 1, No. 3, 257–275 (2004; Zbl 1080.05021)].


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 Random graphs (graph-theoretic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
15B52 Random matrices (algebraic aspects)


Zbl 1080.05021
Full Text: EuDML EMIS