Invertibility of adjacency matrices for random d-regular directed graphs

arXiv1806.01382MaRDI QIDQ6302544FDOQ6302544

Jiaoyang Huang

Publication date: 4 June 2018

Abstract: Let $dgeq3$ 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 ${mathbbF}_p$, �egin{equation} {mathbb P}( ext{$A$ is singular in ${mathbbF}_p$})leq frac{1+{mathrm{o}}(1)}{p-1}, end{equation} as $n$ goes to infinity. As a consequence, as a random matrix in $mathbbR$, �egin{equation} {mathbb P}( ext{$A$ is singular in $mathbbR$})={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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

This page was built for publication: Invertibility of adjacency matrices for random d-regular directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6302544)