Outliers in spectrum of sparse Wigner matrices. Issue 3 (27th November 2020)

• Record Type: Journal Article
• Authors: Tikhomirov, Konstantin; Youssef, Pierre
• Is Part Of: Random structures & algorithms. Volume 58:Issue 3(2021)
• Page Start: 517
• Page End: 605
• Publication Date: 2020-11-27
• Subjects: BBP phase transition -- Erdos‐Renyi graph -- moment method -- outliers -- spectral gap; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20982
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In this paper, we study the effect of sparsity on the appearance of outliers in the semi‐circular law. Let ( W n ) n = 1 ∞ be a sequence of random symmetric matrices such that each W n is n × n with i.i.d. entries above and on the main diagonal equidistributed with the product b n ξ, where ξ is a real centered uniformly bounded random variable of unit variance and b n is an independent Bernoulli random variable with a probability of success p n . Assuming that lim n → ∞ n p n = ∞, we show that for the random sequence ( ρ n ) n = 1 ∞ given by ρ n : = θ n + n p n θ n, θ n : = max ( max i ≤ n ‖ row i ( W n ) ‖ 2 2 − n p n, n p n ), the ratio ‖ W n ‖ ρ n converges to one in probability. A noncentered counterpart of the theorem allows to obtain asymptotic expressions for eigenvalues of the Erdős–Renyi graphs, which were unknown in the regime n p n = Θ ( log n ) . In particular, denoting by A n the adjacency matrix of the Erdős–Renyi graph 𝒢 ( n, p n ) and by λ | k | ( A n ) its k th largest (by the absolute value) eigenvalue, under the assumptions lim n → ∞ n p n = ∞ and lim n → ∞ p n = 0 we have (1) (No non‐trivial outliers): if liminf n p n log n ≥ 1 log ( 4 / e ) then for any fixed k ≥ 2, | λ | k | ( A n ) | 2 n p n converges to 1 in probability; and (2) (Outliers): if limsup n p n log n < 1 log ( 4 / e ) then there is ε > 0 such that for any k ∈ ℕ, we have lim n → ∞ ℙ | λ | k | ( A n ) | 2 n p n > 1 + ε = 1 . On a conceptual level, our result reveals similarities in appearance of outliers in spectrum of sparse matrices and the so‐called BBP phase transition phenomenon in deformed Wigner matrices.