The spectral gap of random graphs with given expected degrees

MaRDI QIDQ2380304zbMATH OpenFDO

Authors Amin Coja-Oghlan, André Lanka

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222646, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r138.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52)

Review text

Summary: We investigate the Laplacian eigenvalues of a random graph \(G(n,{\mathbf d})\) with a given expected degree distribution \textbf{d}. The main result is that w.h.p. \(G(n,{\mathbf d})\) has a large subgraph \(\operatorname{core} G(n,{\mathbf d})\) such that the spectral gap of the normalized Laplacian of \(\operatorname{core} G(n,{\mathbf d})\) is \(\geq 1-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\to\infty\). The present paper complements the work of \textit{F. Chung, L. Lu} and \textit{V. Vu} [Internet Math. 1, No.~3, 257--275 (2004; Zbl 1080.05021)].

Recommendations

• The Spectral Gap of Random Graphs with Given Expected Degrees
• On the Laplacian Eigenvalues of G_n,p
• A remark on the spectra of random graphs with given expected degrees
• The Spectra of Random Graphs with Given Expected Degrees
• On the spectra of general random graphs

Cited in

(20)

• Spectral gap of random hyperbolic graphs and related parameters
• Size biased couplings and the spectral gap for random regular graphs
• On the spectra of general random mixed graphs
• A note on the warmth of random graphs with given expected degrees
• Universality of the mean-field for the Potts model
• A remark on the spectra of random graphs with given expected degrees
• Loose Laplacian spectra of random hypergraphs
• The Spectral Gap of Random Graphs with Given Expected Degrees
• Spectra of edge-independent random graphs
• The Spectra of Random Graphs with Given Expected Degrees
• Lack of hyperbolicity in asymptotic Erdős-Renyi sparse random graphs
• Spectral techniques applied to sparse random graphs
• On the Laplacian Eigenvalues of G_n,p
• Spectra of random graphs with given expected degrees
• Probability of graphs with large spectral gap by multicanonical Monte Carlo
• The spectral gap of a random subgraph of a graph
• On the second eigenvalue of random bipartite biregular graphs
• Simplex links in determinantal hypertrees
• Beyond the expanders
• Concentration of the adjacency matrix and of the normalized Laplacian matrix in general random signed graphs

This page was built for publication: The spectral gap of random graphs with given expected degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380304)