Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

DOI10.1007/S00440-022-01164-7zbMATH Open1501.60024arXiv2102.08364OpenAlexW4307716622MaRDI QIDQ2099809FDOQ2099809

Authors: Shirshendu Ganguly, Kyeongsik Nam 

Publication date: 18 November 2022

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Large deviation behavior of the largest eigenvalue $lambd{a}_1$ of Gaussian networks (ErdH{o}s-R'enyi random graphs $mathcal{G}_{n,p}$ with i.i.d. Gaussian weights on the edges) has been the topic of considerable interest. Recently in [6,30], a powerful approach was introduced based on tilting measures by suitable spherical integrals, particularly establishing a non-universal large deviation behavior for fixed $p<1$ compared to the standard Gaussian ($p=1$) case. The case when $po0$ was however completely left open with one expecting the dense behavior to hold only until the average degree is logarithmic in $n$. In this article we focus on the case of constant average degree i.e., $p=fracdn$. We prove the following results towards a precise understanding of the large deviation behavior in this setting. 1. (Upper tail probabilities): For $delta>0,$ we pin down the exact exponent $psi(delta)$ such that ${\displaystyle }$mathbb{P}(lambda_1ge sqrt{2(1+delta)log n})=n^{-psi(delta)+o(1)}.${\displaystyle }$ Further, we show that conditioned on the upper tail event, with high probability, a unique maximal clique emerges with a very precise $delta$ dependent size (takes either one or two possible values) and the Gaussian weights are uniformly high in absolute value on the edges in the clique. Finally, we also prove an optimal localization result for the leading eigenvector, showing that it allocates most of its mass on the aforementioned clique which is spread uniformly across its vertices. 2. (Lower tail probabilities): The exact stretched exponential behavior of $mathbbP(lambd{a}_{1}lesqrt2(1-delta)logn)$ is also established. As an immediate corollary, we get $lambd{a}_{1}approxsqrt2logn$ typically, a result that surprisingly appears to be new. A key ingredient is an extremal spectral theory for weighted graphs obtained via the classical Motzkin-Straus theorem.

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

Recommendations

• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Upper tails for edge eigenvalues of random graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Low eigenvalues of Laplacian matrices of large random graphs

zbMATH Keywords

large deviationlower tail probabilitiesupper tail probabilities

Mathematics Subject Classification ID

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

Cites Work

• Spectral radii of sparse random matrices
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Some estimates of norms of random matrices
• Title not available (Why is that?)
• Aging of spherical spin glasses
• Random graphs.
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Large deviations principle for the largest eigenvalue of Wigner matrices without Gaussian tails
• The Largest Eigenvalue of Sparse Random Graphs
• Large deviations for Wigner's law and Voiculescu's non-commutative entropy
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Proof of the Van den Berg–Kesten Conjecture
• Nonlinear large deviations
• On replica symmetry of large deviations in random graphs
• The Expected Norm of Random Matrices
• On the variational problem for upper tails in sparse random graphs
• The large deviation principle for the Erdős-Rényi random graph
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Introduction to Random Graphs
• On the spectral norm of Gaussian random matrices
• A large deviation principle for Wigner matrices without Gaussian tails
• Superconcentration and related topics
• Mean quantum percolation
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Large deviations for random matrices
• Large deviations for the largest eigenvalue of Rademacher matrices
• Upper tails for edge eigenvalues of random graphs
• Extremal eigenvalues of critical Erdős-Rényi graphs
• The dimension-free structure of nonhomogeneous random matrices
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Universality of the mean-field for the Potts model
• Upper tails and independence polynomials in random graphs
• Large deviations for the largest eigenvalue of sub-Gaussian matrices
• The structure of low-complexity Gibbs measures on product spaces
• Nonlinear large deviations: beyond the hypercube
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Upper tails via high moments and entropic stability

Cited In (4)

• Spectral large deviations of sparse random matrices
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• Upper tails for edge eigenvalues of random graphs

This page was built for publication: Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

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