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

DOI10.1007/S00440-022-01164-7MaRDI QIDQ2099809zbMATH OpenOpenAlexFDO

Authors Shirshendu Ganguly, Kyeongsik Nam

Publication date 18 November 2022

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

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

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)

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.

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

Cites work

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