Outliers in spectrum of sparse Wigner matrices

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}^{\infty }$ be a sequence of random symmetric matrices such that each $W_n$ is $n\times n$ with i.i.d entries above and on the main diagonal equidistributed with the product $b_n\xi$, where $\xi$ 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 $\underset{n\to \infty }{\lim }n{p}_n=\infty$, we show that for the random sequence $({\rho }_n{)}_{n=1}^{\infty }$ given by $${\rho }_n:={\theta }_n+\frac{n{p}_n}{{\theta }_n},{\theta }_n:=\sqrt{\max (\underset{i\le n}{\max }\Vert \mathrm{Ro}{\mathrm{w}}_{\mathrm{i}}(W_n){\Vert }_2^2-n{p}_n,n{p}_n)},$$ the ratio $\frac{\Vert W_n\Vert }{{\rho }_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{p}_n=\Theta (\log n)$. In particular, denoting by $A_n$ the adjacency matrix of $\mathcal{G}(n,p_n)$ and by ${\lambda }_{|k|}(A_n)$ its $k$-th largest (by the absolute value) eigenvalue, under the assumptions $\underset{n\to \infty }{\lim }n{p}_n=\infty$ and $\underset{n\to \infty }{\lim }{p}_n=0$ we have: -(No non-trivial outliers) If $\mathrm{liminf}\frac{n{p}_n}{\log n}\ge \frac{1}{\log (4/e)}$ then for any fixed $k\ge 2$, $\frac{|{\lambda }_{|k|}(A_n)|}{2\sqrt{n{p}_n}}$ converges to $1$ in probability. -(Outliers) If $\mathrm{limsup}\frac{n{p}_n}{\log n}<\frac{1}{\log (4/e)}$ then there is $\epsilon >0$ such that for any $k\in \mathbb{N}$, we have $\underset{n\to \infty }{\lim }\mathbb{P}\{\frac{|{\lambda }_{|k|}(A_n)|}{2\sqrt{n{p}_n}}>1+\epsilon \}=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.

Added reference to the related work arXiv:1905.03243