The spectral gap of random graphs with given expected degrees
The electronic journal of combinatorics, Tome 16 (2009) no. 1
We investigate the Laplacian eigenvalues of a random graph $G(n,\vec d)$ with a given expected degree distribution $\vec d$. The main result is that w.h.p. $G(n,\vec d)$ has a large subgraph core$(G(n,\vec d))$ such that the spectral gap of the normalized Laplacian of core$(G(n,\vec d))$ is $\geq1-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\rightarrow\infty$. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].
@article{10_37236_227,
author = {Amin Coja-Oghlan and Andr\'e Lanka},
title = {The spectral gap of random graphs with given expected degrees},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/227},
zbl = {1187.05048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/227/}
}
Amin Coja-Oghlan; André Lanka. The spectral gap of random graphs with given expected degrees. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/227
Cité par Sources :