2014/11/02 by Cook, Nicholas A.
#15B52 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1411.0243
We prove that the (non-symmetric) adjacency matrix of a uniform random d-regular directed graph on n vertices is asymptotically almost surely invertible, assuming min(d,n-d)≥ Clog2n for a sufficiently large constant C>0. The proof makes use of a coupling of random regular digraphs formed by "shuffling" the neighborhood of a pair of vertices, as well as concentration results for the distribution of edges recently obtained by the author (arXiv:1410.5595). We also apply our general approach to prove a.a.s. invertibility of Hadamard products Σ∘ Ξ, where Ξ is a matrix of iid uniform ±1 signs, and Σ is a 0/1 matrix whose associated digraph satisfies certain "expansion" properties.