
The Library
The spectral gap of random graphs with given expected degrees
Tools
Coja-Oghlan, Amin and Lanka, André (2009) The spectral gap of random graphs with given expected degrees. Electronic Journal of Combinatorics, Vol.16 (No.1). R138.
Research output not available from this repository, contact author.Abstract
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−c0dˉ−1/2min with high probability; here c0>0 is a constant, and dˉmin signifies the minimum expected degree. The result in particular applies to sparse graphs with dˉmin=O(1) as n→∞. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science > Mathematics | ||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||
Publisher: | Electronic Journal of Combinatorics | ||||
ISSN: | 1077-8926 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Volume: | Vol.16 | ||||
Number: | No.1 | ||||
Page Range: | R138 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |