Invertibility of adjacency matrices for random d-regular directed graphs

Abstract

Let $d\ge 3$ be a fixed integer, and a prime number $p$ such that $\gcd (p,d)=1$. Let $A$ be the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. We show that as a random matrix in ${\mathbb{F}}_p$, \begin{equation} {\mathbb P}(\text{$A$ is singular in ${\mathbb{F}}_p$})\leq \frac{1+{\mathrm{o}}(1)}{p-1}, \end{equation} as $n$ goes to infinity. As a consequence, as a random matrix in $\mathbb{R}$, \begin{equation} {\mathbb P}(\text{$A$ is singular in $\mathbb{R}$})={\mathrm{o}}(1) \end{equation} as $n$ goes to infinity. This answers an open problem by Frieze [12] and Vu [29,30], for random $d$-regular bipartite graphs. The proof combines a local central limit theorem and a large deviation estimate.

1 figure, permanent preprint

References in corpus (2)

• Invertibility of adjacency matrices for random $d$-regular graphs
• Cokernels of adjacency matrices of random $r$-regular graphs

Cited by in corpus (2)

• Spectral gap in random bipartite biregular graphs and applications
• Cokernels of adjacency matrices of random $r$-regular graphs