The Largest Eigenvalue of Sparse Random Graphs

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: lambda_1(G)=(1+o(1))max{sqrt{Delta},np}, where Delta is a maximal degree of G, and the o(1) term tends to zero as max{sqrt{Delta},np} tends to infinity.

Recommendations

Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
Sparse random graphs: eigenvalues and eigenvectors
The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
Many large eigenvalues in sparse graphs
Sparse regular random graphs: spectral density and eigenvectors
On the distribution of the maximum eigenvalues of graphs
Low eigenvalues of Laplacian matrices of large random graphs
Largest sparse subgraphs of random graphs
Largest sparse subgraphs of random graphs
The First Eigenvalue of Random Graphs

Cited in

(60)

Covariance Matrix Estimation via Network Structure
The skew spectral radius and skew Randić spectral radius of general random oriented graphs
Spectral large deviations of sparse random matrices
Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs
Extreme singular values of inhomogeneous sparse random rectangular matrices
Spectral upper bounds for the Grundy number of a graph
Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
Fluctuations of quadratic chaos
The spectra of random mixed graphs
Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
Top eigenpair statistics for weighted sparse graphs
On connected diagrams and cumulants of Erdős-Rényi matrix models
A limit theorem for scaled eigenvectors of random dot product graphs
Extremal eigenvalues of critical Erdős-Rényi graphs
Lifshitz tails for spectra of Erdős-Rényi random graphs
Concentration of the spectral norm of Erdős-Rényi random graphs
Sparse random tensors: concentration, regularization and applications
Graph partitioning via adaptive spectral techniques
Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
On asymptotic properties of Bell polynomials and concentration of vertex degree of large random graphs
Outliers in spectrum of sparse Wigner matrices
Spectral norm bounds for block Markov chain random matrices
Universality of the mean-field for the Potts model
Spectral edge in sparse random graphs: upper and lower tail large deviations
Gaussianization of the spectra of graphs and networks. Theory and applications
A remark on the spectra of random graphs with given expected degrees
Constructive regularization of the random matrix norm
Localized phase for the Erdős-Rényi graph
Sparse regular random graphs: spectral density and eigenvectors
A spectral signature of breaking of ensemble equivalence for constrained random graphs
Spectral techniques applied to sparse random graphs
Robustness of random graphs based on graph spectra
Capacity of an associative memory model on random graph architectures
An approximation algorithm for the maximum spectral subgraph problem
Many large eigenvalues in sparse graphs
Noise sensitivity for the top eigenvector of a sparse random matrix
The First Eigenvalue of Random Graphs
Detection thresholds in very sparse matrix completion
Learning sparse graphons and the generalized Kesten-Stigum threshold
Patterned sparse random matrices: A moment approach
On high moments of strongly diluted large Wigner random matrices
Loose Laplacian spectra of random hypergraphs
Spectra of edge-independent random graphs
Centrality metrics and localization in core-periphery networks
Sparse random graphs: eigenvalues and eigenvectors
The Hopfield model on a sparse Erdös-Renyi graph
Asymptotic distribution of Bernoulli quadratic forms
On the Laplacian Eigenvalues of G_n,p
On the distribution of the maximum eigenvalues of graphs
Global and individualized community detection in inhomogeneous multilayer networks
Locating the eigenvalues of trees
On the spectra of general random mixed graphs
Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
Upper tails for edge eigenvalues of random graphs
Exploring the “Middle Earth” of network spectra via a Gaussian matrix function
Largest eigenvalues and eigenvectors of band or sparse random matrices
Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
On the largest eigenvalue of a random subgraph of the hypercube
Spectral distributions of adjacency and Laplacian matrices of random graphs
Upper tail of the spectral radius of sparse Erdös-Rényi graphs

This page was built for publication: The Largest Eigenvalue of Sparse Random Graphs

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