The Library
The spectral gap of random graphs with given expected degrees
Tools
Tools
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. ISSN 1077-8926.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 |
