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

DOI10.3150/19-BEJ1192MaRDI QIDQ2175000zbMATH OpenOpenAlexFDO

Authors Gábor Lugosi, Shahar Mendelson, Nikita Zhivotovskiy

Publication date 27 April 2020

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.02157, https://projecteuclid.org/euclid.bj/1587974540

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)

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$.

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

Cites work

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

Cited in

(11)

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