Invertibility of adjacency matrices for random $d$-regular graphs

Abstract

Let $d\ge 3$ be a fixed integer and $A$ be the adjacency matrix of a random $d$-regular directed or undirected graph on $n$ vertices. We show there exist constants $\mathfrak{d}>0$, \begin{align*} {\mathbb P}(\text{$A$ is singular in $\mathbb{R}$})\leq n^{-\mathfrak{d}}, \end{align*} for $n$ sufficiently large. This answers an open problem by Frieze [12] and Vu [28,19]. The key idea is to study the singularity probability of adjacency matrices over a finite field ${\mathbb{F}}_p$. The proof combines a local central limit theorem and a large deviation estimate.

This new article combined arXiv:1806.01382 with arXiv:1807.06465, and a quantitative estimate of the singularity probability was added

References in corpus (1)

• Cokernels of adjacency matrices of random $r$-regular graphs

Cited by in corpus (4)

• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Spectrum of Random $d$-regular Graphs Up to the Edge
• Invertibility of adjacency matrices for random d-regular directed graphs
• The smallest singular value of random combinatorial matrices