Adjacency matrices of random digraphs: Singularity and anti-concentration

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS

卷:445

Article

Litvak, Alexander E.¹  Lytova, Anna¹  Tikhomirov, Konstantin¹  Tomczak-Jaegermann, Nicole¹  Youssef, Pierre² 

[1] Univ Alberta, Dept Math & Stat Sci, Edmonton, AB T6G 2G1, Canada

[2] Univ Paris Diderot, Lab Probabilites & Modeles Aleatoires, F-75013 Paris, France

关键词: Adjacency matrices;    Anti-concentration;    Invertibility of random matrices;    Littlewood-Offord theory;    Random regular graphs;    Singular probability;   

DOI  :  10.1016/j.jmaa.2016.08.020

来源: Elsevier

【 摘 要 】

Let D-n,D- 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-d and M be its adjacency matrix. We show that M is invertible with probability at least 1-Cln(3) d/root d for C <= d <= cn/ln(2)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 vertical bar J vertical bar approximate to n/d. Let delta(i) the indicator of the event that the vertex i is connected to J and define delta = (delta(1), delta(2),..., delta(n)) is an element of {0,1}(n). Then for every v is an element of {0,1}(n) the probability that delta = v is exponentially small. This property holds even if a part of the graph is frozen. (C) 2016 Elsevier Inc. All rights reserved.

【 授权许可】

Free