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

Coja-Oghlan, Amin; Lanka, André

Electron. J. Comb. 16, No. 1, Research Paper R138, 47 p. (2009).

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)

Citations:

Zbl 1080.05021