Tail bounds for gaps between eigenvalues of sparse random matrices (Q2076604)

The authors study the eigenvalue gaps of sparse random matrices. The theory of sparse random matrices is of interest in its own right, but it also has innumerable applications in computer science and statistics. In contexts where sparse random matrices have similar spectral guarantees as their dense counterparts, they offer significant advantages as they require less space to store, allow quicker multiplication, and fewer random bits is necessary to generate them. The main contribution of the paper is to go beyond verifying the fact that such matrices have simple spectrum, and prove a tail bound for the minimal eigenvalue gap of these sparse random matrices. So, the first eigenvalue repulsion bound for sparse random matrices is established. As a consequence, it is proved that these matrices have simple spectrum, improving the range of sparsity and error probability from the previous works. It is also proved that for sparse Erdős-Rényi graphs, weak and strong nodal domains are the same.