Upper Tails for Edge Eigenvalues of Random Graphs

DOI10.1137/18M1230852zbMath1437.05211arXiv1811.07554OpenAlexW3016503308MaRDI QIDQ5107095

Shirshendu Ganguly, Bhaswar B. Bhattacharya

Publication date: 22 April 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

large deviationrandom graphsedge eigenvalues

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Large deviations (60F10)

Related Items (9)

Large deviations for the largest eigenvalue of matrices with variance profiles ⋮ Upper tail of the spectral radius of sparse Erdös-Rényi graphs ⋮ Upper tail for homomorphism counts in constrained sparse random graphs ⋮ Moderate deviations in cycle count ⋮ Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime ⋮ Large deviations of subgraph counts for sparse Erdős-Rényi graphs ⋮ Spectral edge in sparse random graphs: upper and lower tail large deviations ⋮ Large deviations for the largest eigenvalue of Rademacher matrices ⋮ Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

Cites Work

• Unnamed Item
• Unnamed Item
• Large deviations principle for the largest eigenvalue of Wigner matrices without Gaussian tails
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• A large deviation principle for Wigner matrices without Gaussian tails
• The large deviation principle for the Erdős-Rényi random graph
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Large deviations for the largest eigenvalue of Rademacher matrices
• Limits of dense graph sequences
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Large deviations for Wigner's law and Voiculescu's non-commutative entropy
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• On the concentration of eigenvalues of random symmetric matrices
• Upper tails via high moments and entropic stability
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the missing log in upper tail estimates
• Universality of the mean-field for the Potts model
• Upper tails and independence polynomials in random graphs
• Nonlinear large deviations
• Large Deviations for Random Matrices
• Large Deviations of Extreme Eigenvalues of Random Matrices
• On replica symmetry of large deviations in random graphs
• Large deviations of the maximum eigenvalue in Wishart random matrices
• Upper Tail Large Deviations for Arithmetic Progressions in a Random Set
• On the Lower Tail Variational Problem for Random Graphs
• On the variational problem for upper tails in sparse random graphs
• Aging of spherical spin glasses

This page was built for publication: Upper Tails for Edge Eigenvalues of Random Graphs