Adjacency matrices of random digraphs: Singularity and anti-concentration

Let D_n,d be the set of all d-regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from D_n,d and M be its adjacency matrix. We show that M is invertible with probability at least 1−Cln³⁡d/d for C≤d≤cn/ln²⁡n, where c,C are positive absolute constants. To this end, we establish a few properties of d-regular directed graphs. One of them, a Littlewood–Offord type anti-concentration property, is of independent interest. Let J be a subset of vertices of G with |J|≈n/d. Let δ_i be the indicator of the event that the vertex i is connected to J and define δ=(δ₁,δ₂,…,δ_n)∈{0,1}ⁿ. Then for every v∈{0,1}ⁿ the probability that δ=v is exponentially small. This property holds even if a part of the graph is “frozen.”