## 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)].

### MSC:

 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: