THe largest eigenvalue of sparse random graphs

2001/06/10 by Michael Krivelevich, Benny Sudakov, Krivelevich, Michael +1 · 5 citations
Mathematics · #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #math.PR #msc:05C80 #msc:15A52

paper · pdf · doi:10.48550/arxiv.math/0106066

arxiv created 2001/06/10 · arxiv updated 2009/11/30

Abstract

We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n,p) satisfies almost surely: λ₁(G)=(1+o(1))max√Δ,np, where Δis a maximal degree of G, and the o(1) term tends to zero as max√Δ,np tends to infinity.

Cited by

• Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
• Correlation-Weighted Communicability Curvature as a Structural Driver of Dengue Spread: A Bayesian Spatial Analysis of Recife (2015-2024)
• Sparse graphs and their Benjamini-Schramm limits: a spectral tour
• On irreducible central limit theorems
• Eigenvalue spectral tails and localization properties of asymmetric networks

Related

• On the largest eigenvalue of a sparse random subgraph of the hypercube
• Sparse random graphs: Eigenvalues and Eigenvectors
• The largest eigenvalue of a graph: A survey
• Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large\n Deviations
• Eigenvalues and extremal degrees in graphs