On the Laplacian Eigenvalues of Gn,p

We investigate the Laplacian eigenvalues of sparse random graphs G np . We show that in the case that the expected degree d = ( n -1) p is bounded, the spectral gap of the normalized Laplacian () is o (1). Nonetheless, w.h.p. G = G np has a large subgraph core(G) such that the spectral gap of ((G)) is as large as 1- O ( d −1/2 ). We derive similar results regarding the spectrum of the combinatorial Laplacian L (G np ). The present paper complements the work of Chung, Lu and Vu [8] on the Laplacian spectra of random graphs with given expected degree sequences. Applied to G np , their results imply that in the ‘dense’ case d ≥ ln 2 n the spectral gap of () is 1- O ( d −1/2 ) w.h.p.