TY - JOUR

T1 - Adjacency matrices of random digraphs

T2 - Singularity and anti-concentration

AU - Litvak, Alexander E.

AU - Lytova, Anna

AU - Tikhomirov, Konstantin

AU - Tomczak-Jaegermann, Nicole

AU - Youssef, Pierre

N1 - Publisher Copyright:
© 2016 Elsevier Inc.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2017/1/15

Y1 - 2017/1/15

N2 - Let Dn,d be the set of all d-regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1−Cln3d/d for C≤d≤cn/ln2n, 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 δ=(δ1,δ2,…,δn)∈{0,1}n. Then for every v∈{0,1}n the probability that δ=v is exponentially small. This property holds even if a part of the graph is “frozen.”

AB - Let Dn,d be the set of all d-regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1−Cln3d/d for C≤d≤cn/ln2n, 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 δ=(δ1,δ2,…,δn)∈{0,1}n. Then for every v∈{0,1}n the probability that δ=v is exponentially small. This property holds even if a part of the graph is “frozen.”

KW - Adjacency matrices

KW - Anti-concentration

KW - Invertibility of random matrices

KW - Littlewood–Offord theory

KW - Random regular graphs

KW - Singular probability

UR - http://www.scopus.com/inward/record.url?scp=84995393659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84995393659&partnerID=8YFLogxK

U2 - 10.1016/j.jmaa.2016.08.020

DO - 10.1016/j.jmaa.2016.08.020

M3 - Article

AN - SCOPUS:84995393659

VL - 445

SP - 1447

EP - 1491

JO - Journal of Mathematical Analysis and Applications

JF - Journal of Mathematical Analysis and Applications

SN - 0022-247X

IS - 2

ER -