2019/04/16 by Tikhomirov, Konstantin, Youssef, Pierre · 2 citations
#05C80 #15B52 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1904.07985
In this paper, we study the effect of sparsity on the appearance of outliers in the semi-circular law. Let (Wn)n=1^∞ be a sequence of random symmetric matrices such that each Wn is n× n with i.i.d entries above and on the main diagonal equidistributed with the product bnξ, where ξ is a real centered uniformly bounded random variable of unit variance and bn is an independent Bernoulli random variable with a probability of success pn. Assuming that limn→∞n pn=∞, we show that for the random sequence (ρn)n=1^∞ given by ρn:=θn+(n pn)/(θn), θn:=√max(maxi≤ n‖\rm Rowi(Wn)‖22-npn,n pn), the ratio (‖Wn‖)/(ρn) converges to one in probability. A non-centered counterpart of the theorem allows to obtain asymptotic expressions for eigenvalues of the Erdős--Renyi graphs, which were unknown in the regime n pn=Θ(log n). In particular, denoting by An the adjacency matrix of G(n,pn) and by λ|k|(An) its k-th largest (by the absolute value) eigenvalue, under the assumptions limn→∞ n pn=∞ and limn→∞pn=0 we have: -(No non-trivial outliers) If \liminf(n pn)/(log n)≥(1)/(log (4/e)) then for any fixed k≥2, \frac|λ|k|(An)|2√(n pn) converges to 1 in probability. -(Outliers) If \limsup(n pn)/(log n)0 such that for any k∈ℕ, we have limn→∞ℙ\\frac|λ|k|(An)|2√(n pn)>1+ε\=1. On a conceptual level, our result highlights similarities in appearance of outliers in spectrum of sparse matrices and the so-called BBP phase transition phenomenon in deformed Wigner matrices.