Anti-concentration property for random digraphs and invertibility of their adjacency matrices

Let D n , d be the set of all directed d -regular 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 − C ln 3 ⁡ d / d for C ≤ d ≤ c n / ln 2 ⁡ n , where c , C are positive absolute constants. To this end, we establish a few properties of directed d -regular 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 | ≤ c n / d . Let δ i be the indicator of the event that the vertex i is connected to J and δ = ( δ 1 , δ 2 , … , δ n ) ∈ { 0 , 1 } n . Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.