The Smallest Singular Value of Dense Random Regular Digraphs

被引：1

作者：

Jain, Vishesh ^{[1
]}

Sah, Ashwin ^{[2
]}

Sawhney, Mehtaab ^{[2
]}

机构：

[1] Stanford Univ, Dept Stat, Stanford, CA 94305 USA

[2] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

INTERNATIONAL MATHEMATICS RESEARCH NOTICES | 2022年 / 2022卷 / 24期

关键词：

ASYMPTOTIC ENUMERATION; RANDOM MATRICES; INVERTIBILITY; NUMBER; GRAPHS;

D O I：

10.1093/imrn/rnab247

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let A be the adjacency matrix of a uniformly random d-regular digraph on n vertices, and suppose that min(d, n - d) >= lambda n. We show that for any kappa >= 0, P[s(n) (A) <= kappa] <= C-lambda kappa root n + 2e(-c lambda n). Up to the constants C-lambda,c(lambda) > 0, our bound matches optimal bounds for n x n random matrices, each of whose entries is an i.i.d Ber(d/n) random variable. The special case k = 0 of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.

引用

页码：19300 / 19334

页数：35