Concentration of the spectral norm of Erdős-Rényi random graphs

DOI10.3150/19-BEJ1192zbMATH Open1439.60010arXiv1801.02157OpenAlexW3018507535MaRDI QIDQ2175000FDOQ2175000

Authors: Gábor Lugosi, Shahar Mendelson, Nikita Zhivotovskiy 

Publication date: 27 April 2020

Published in: Bernoulli (Search for Journal in Brave)

Abstract: We present results on the concentration properties of the spectral norm $|A_p|$ of the adjacency matrix $A_p$ of an ErdH{o}s-R'enyi random graph $G(n,p)$. First we consider the ErdH{o}s-R'enyi random graph process and prove that $|A_p|$ is uniformly concentrated over the range $pin[Clogn/n,1]$. The analysis is based on delocalization arguments, uniform laws of large numbers, together with the entropy method to prove concentration inequalities. As an application of our techniques we prove sharp sub-Gaussian moment inequalities for $|A_p|$ for all $pin[clo{g}^{3}n/n,1]$ that improve the general bounds of Alon, Krivelevich, and Vu (2001) and some of the more recent results of ErdH{o}s et al. (2013). Both results are consistent with the asymptotic result of F"uredi and Koml'os (1981) that holds for fixed $p$ as $noinfty$.

Full work available at URL: https://arxiv.org/abs/1801.02157

Recommendations

• Concentration and regularization of random graphs
• On the spectra of general random graphs
• Spectral radii of sparse random matrices
• Sparse random graphs: eigenvalues and eigenvectors
• Spectra of edge-independent random graphs

zbMATH Keywords

empirical processesconcentrationrandom graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Stochastic matrices (15B51)

Cites Work

• Concentration inequalities. A nonasymptotic theory of independence
• The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality
• The eigenvalues of random symmetric matrices
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Title not available (Why is that?)
• An introduction to matrix concentration inequalities
• Title not available (Why is that?)
• Moment inequalities for functions of independent random variables
• The Largest Eigenvalue of Sparse Random Graphs
• Sparse random graphs: eigenvalues and eigenvectors
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• On the concentration of eigenvalues of random symmetric matrices
• Spectral norm of random matrices
• Entrywise bounds for eigenvectors of random graphs
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs

Cited In (11)

• Joint community detection and rotational synchronization via semidefinite programming
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Concentration and regularization of random graphs
• KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDŐS–RÉNYI RANDOM GRAPH
• A unified approach to synchronization problems over subgroups of the orthogonal group
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• A Berry-Esseen bound with applications to vertex degree counts in the Erdős-Rényi random graph
• Upper tails for edge eigenvalues of random graphs

This page was built for publication: Concentration of the spectral norm of Erdős-Rényi random graphs

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