论文标题
密集的随机常规挖掘的最小奇异值
The smallest singular value of dense random regular digraphs
论文作者
论文摘要
令$ a $为$ n $顶点的均匀随机$ d $ regractul digraph的邻接矩阵，并假设$ \ min（d，n-d）\geqλn$。我们表明，对于任何$κ\ geq 0 $，\ [\ mathbb {p} [s_n（a）\leqκ] \ leqc_λκ\ sqrt {n}+2e^{ - c_λn}。条目是i.i.d $ \ text {ber}（d/n）$随机变量。我们结果的特殊情况$κ= 0 $证实了库克关于密集的随机常规挖掘物的奇异性的概率的猜想。
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.
