Adjacency matrices of random digraphs: Singularity and anti-concentration

详细信息    查看全文

• 作者：Alexander E. Litvak^a ; ^{aelitvak@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Anna Lytova^a ; ^{lytova@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Konstantin Tikhomirov^a ; ^{ktikhomi@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Nicole Tomczak-Jaegermann^a ; ^{nicole.tomczak@ualberta.ca" class="auth_mail" title="E-mail the corresponding author} ; Pierre Youssef^b ; ^{youssef@math.univ-paris-diderot.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Adjacency matrices ; Anti-concentration ; Invertibility of random matrices ; Littlewood&ndash ; Offord theory ; Random regular graphs ; Singular probability
• 刊名：Journal of Mathematical Analysis and Applications
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：445
• 期：2
• 页码：1447-1491
• 全文大小：760 K

文摘

Let D_n,d${\mathcal{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${\mathcal{D}}_{n,d}$ and M be its adjacency matrix. We show that M   is invertible with probability at least $1-C{\ln }^{3}d/\sqrt{d}$ for C≤d≤cn/ln²⁡n$C\le d\le cn/{\ln }^{2}n$, where c,C$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$|J|\approx n/d$. Let δ_i${\delta }_i$ be the indicator of the event that the vertex i is connected to J   and define δ=(δ₁,δ₂,...,δ_n)∈{0,1}ⁿ$\delta =({\delta }_1,{\delta }_2,...,{\delta }_n)\in {\{0,1\}}^n$. Then for every v∈{0,1}ⁿ$v\in {\{0,1\}}^n$ the probability that δ=v$\delta =v$ is exponentially small. This property holds even if a part of the graph is “frozen.”