A note on the singularity probability of random directed d-regular graphs

2023/08/12 by Nguyen, Hoi H., Pan, Amanda
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2308.06461

Abstract

In this note we show that the singular probability of the adjacency matrix of a random d-regular graph on n vertices, where d is fixed and n → ∞, is bounded by n^-1/3+o(1). This improves a recent bound by Huang. Our method is based on the study of the singularity problem modulo a prime together with an inverse-type result on the decay of the characteristic function. The latter is related to the inverse Kneser's problem in combinatorics.

Related

• Invertibility of adjacency matrices for random d-regular graphs
• Invertibility of adjacency matrices for random d-regular directed graphs
• On the singularity of adjacency matrices for random regular digraphs
• The smallest singular value of dense random regular digraphs
• Dense random regular digraphs: singularity of the adjacency matrix