## Abstract

In this paper, we study the effect of sparsity on the appearance of outliers in the semi-circular law. Let (Formula presented.) 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 (Formula presented.), where (Formula presented.) 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 (Formula presented.), we show that for the random sequence (Formula presented.) given by (Formula presented.), the ratio (Formula presented.) 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 (Formula presented.). In particular, denoting by A_{n} the adjacency matrix of the Erdős–Renyi graph (Formula presented.) and by (Formula presented.) its kth largest (by the absolute value) eigenvalue, under the assumptions (Formula presented.) and (Formula presented.) we have (1) (No non-trivial outliers): if (Formula presented.) then for any fixed k ≥ 2, (Formula presented.) converges to 1 in probability; and (2) (Outliers): if (Formula presented.) then there is ε > 0 such that for any (Formula presented.), we have (Formula presented.). 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.

Original language | English (US) |
---|---|

Pages (from-to) | 517-605 |

Number of pages | 89 |

Journal | Random Structures and Algorithms |

Volume | 58 |

Issue number | 3 |

DOIs | |

State | Published - 2020 |

## Keywords

- BBP phase transition
- Erdos-Renyi graph
- moment method
- outliers
- spectral gap

## ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics