The smallest singular value of dense random regular digraphs

Let $A$ be the adjacency matrix of a uniformly random $d$-regular digraph on $n$ vertices, and suppose that $\min(d,n-d)\geqλn$. We show that for any $κ\geq 0$, $\mathbb{P}[s_n(A)\leqκ]\leq C_λκ\sqrt{n}+2e^{-c_λn}.$ Up to the constants $C_λ, c_λ> 0$, our bound matches optimal bounds for $n\times n$ random matrices, each of whose entries is an i.i.d $\text{Ber}(d/n)$ random variable. The special case $κ= 0$ of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.

No reviews yet.

No comments yet.