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

DOI10.3150/19-BEJ1192zbMath1439.60010arXiv1801.02157OpenAlexW3018507535MaRDI QIDQ2175000

Gábor Lugosi, Nikita Zhivotovskiy, Shahar Mendelson

Publication date: 27 April 2020

Published in: Bernoulli (Search for Journal in Brave)

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

zbMATH Keywords

empirical processesrandom graphsconcentration

Mathematics Subject Classification ID

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

Related Items

Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Upper Tails for Edge Eigenvalues of Random Graphs, A unified approach to synchronization problems over subgroups of the orthogonal group, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality
• The eigenvalues of random symmetric matrices
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• Moment inequalities for functions of independent random variables
• On the concentration of eigenvalues of random symmetric matrices
• Entrywise bounds for eigenvectors of random graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• The Largest Eigenvalue of Sparse Random Graphs
• Sparse random graphs: Eigenvalues and eigenvectors
• An Introduction to Matrix Concentration Inequalities
• Spectral norm of random matrices