Invertibility of adjacency matrices for random $d$-regular graphs
Preprint
Abstract
Let $d\geq 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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Fixed energy universality of Dyson Brownian motionAdvances in Mathematics, 2019
- The rank of random regular digraphs of constant degreeJournal of Complexity, 2018
- The smallest singular value of a shifted d-regular random square matrixProbability Theory and Related Fields, 2018
- Invertibility of sparse non-Hermitian matricesAdvances in Mathematics, 2017
- On the singularity of adjacency matrices for random regular digraphsProbability Theory and Related Fields, 2015
- Invertibility of symmetric random matricesRandom Structures & Algorithms, 2012
- Smallest singular value of a random rectangular matrixCommunications on Pure and Applied Mathematics, 2009
- The Littlewood–Offord problem and invertibility of random matricesAdvances in Mathematics, 2008
- The rank of random graphsRandom Structures & Algorithms, 2008
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978