# Outliers in spectrum of sparse Wigner matrices

Research paper by **Konstantin Tikhomirov, Pierre Youssef**

Indexed on: **31 Jul '19**Published on: **16 Apr '19**Published in: **arXiv - Mathematics - Probability**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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 $\lim\limits_{n\to\infty}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},\quad \theta_n:=\sqrt{\max\big(\max\limits_{i\leq n}\|{\rm
Row_i}(W_n)\|_2^2-np_n,n p_n\big)},$$ the ratio $\frac{\|W_n\|}{\rho_n}$
converges to one in probability. A non-centered counterpart of the theorem
allows to obtain the following corollary for the Erd\H{o}s--Renyi graph
$\mathcal{G}(n,p_n)$. 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 $\lim\limits_{n\to\infty }n
p_n=\infty$ and $\lim\limits_{n\to\infty}p_n=0$ we have:
-(No non-trivial outliers) If $\liminf\frac{n p_n}{\log n}\geq\frac{1}{\log
(4/e)}$ then for any fixed $k\geq2$, $\frac{|\lambda_{|k|}(A_n)|}{2\sqrt{n
p_n}}$ converges to $1$ in probability.
-(Outliers) If $\limsup\frac{n p_n}{\log n}<\frac{1}{\log (4/e)}$ then there
is $\varepsilon>0$ such that for any $k\in\mathbb{N}$, we have
$\lim\limits_{n\to\infty}\mathbb{P}\Big\{\frac{|\lambda_{|k|}(A_n)|}{2\sqrt{n
p_n}}>1+\varepsilon\Big\}=1$.
On a conceptual level, our result highlights similarities between spectral
properties of sparse random matrices and the so-called BBP phase transition
phenomenon in deformed Wigner matrices.