Invertibility of adjacency matrices for random d-regular graphs

DOI10.1215/00127094-2021-0006MaRDI QIDQ6304318arXivFDO

Authors Jiaoyang Huang

Publication date 15 July 2018

Published in arXiv

Full work available at URL https://doi.org/10.1215/00127094-2021-0006

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Theory of matrix inversion and generalized inverses (15A09) Random matrices (algebraic aspects) (15B52)

arXiv classification

math.COmath.PR

Abstract: Let $dgeq3$ 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 $mathfrakd>0$, �egin{align*} {mathbb P}( ext{$A$ is singular in $mathbbR$})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 ${mathbbF}_p$. The proof combines a local central limit theorem and a large deviation estimate.

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

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