The Spectral Gap of Random Graphs with Given Expected Degrees - Coja-Oghlan, Amin; Lanka, André (The Electronic Journal of Combinatorics, 2009)
We investigate the Laplacian eigenvalues of a random graph G(n,d) with a given expected degree distribution d. The main result is that w.h.p. G(n,d) has a large subgraph core(G(n,d)) such that the spectral gap of the normalized Laplacian of core(G(n,d)) is ≥1-c_0d_^-1/2 with high probability; here c_0>0 is a constant, and d_ signifies the minimum expected degree. The result in particular applies to sparse graphs with d_=O(1) as n→∞. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].