6533b857fe1ef96bd12b3aad

RESEARCH PRODUCT

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

subject

description

Let Dn,dDn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,dDn,d and M be its adjacency matrix. We show that M is invertible with probability at least View the MathML source1−Cln3⁡d/d for C≤d≤cn/ln2⁡nC≤d≤cn/ln2⁡n, where c,Cc,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|≤cn/d|J|≤cn/d. Let δiδi be the indicator of the event that the vertex i is connected to J and δ=(δ1,δ2,…,δn)∈{0,1}nδ=(δ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.