Invertibility of adjacency matrices for random d-regular directed graphs

2018/06/04 by Jiaoyang Huang, Huang, Jiaoyang · 1 citation
Mathematics · #05C80 #15B33 #15B52 #Advanced Algebra and Geometry #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1806.01382

openalex publication_date 2018/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let d≥ 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, \mathbb P(\textA is singular in \mathbb F_p)≤ \frac1+o(1)p-1, as n goes to infinity. As a consequence, as a random matrix in \mathbb R, \mathbb P(A is singular in \mathbb R)=o(1) 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.

Cited by

• Spectral gap in random bipartite biregular graphs and applications

Related

• Invertibility of adjacency matrices for random d-regular graphs
• On the singularity of adjacency matrices for random regular digraphs
• A note on the singularity probability of random directed d-regular graphs
• Sharp transition of the invertibility of the adjacency matrices of\n sparse random graphs
• Dense random regular digraphs: singularity of the adjacency matrix