Invertibility of adjacency matrices for random d-regular directed graphs-猫眼课题宝

随机 d-正则有向图邻接矩阵的可逆性

DOI：

发表时间：

2018

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

Jiaoyang Huang

设$d\geq3$为一个固定整数，$p$为一个素数且$\gcd(p,d)=1$。设$A$为$n$个顶点上的一个随机$d$-正则有向图的邻接矩阵。我们证明，作为$\mathbb{F}_p$中的一个随机矩阵，当$n$趋于无穷时， \[ \mathbb{P}(A在\mathbb{F}_p中是奇异的)\leq\frac{1 + o(1)}{p - 1} \] 作为一个推论，作为$\mathbb{R}$中的一个随机矩阵，当$n$趋于无穷时， \[ \mathbb{P}(A在\mathbb{R}中是奇异的)=o(1) \] 这回答了弗里兹（Frieze）[12]和武（Vu）[29,30]关于随机$d$-正则二部图的一个公开问题。证明结合了一个局部中心极限定理和一个大偏差估计。

Let $dgeq 3$ be a fixed integer, and a prime number $p$ such that $gcd(p,d)=1$. Let $A$ be the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. We show that as a random matrix in ${mathbb F}_p$, egin{equation} {mathbb P}( ext{$A$ is singular in ${mathbb F}_p$})leq frac{1+{mathrm{o}}(1)}{p-1}, end{equation} as $n$ goes to infinity. As a consequence, as a random matrix in $mathbb R$, egin{equation} {mathbb P}( ext{$A$ is singular in $mathbb R$})={mathrm{o}}(1) end{equation} as $n$ goes to infinity. This answers an open problem by Frieze [12] and Vu [29,30], for random $d$-regular bipartite graphs. The proof combines a local central limit theorem and a large deviation estimate.

Invertibility of adjacency matrices for random d-regular directed graphs

随机 d-正则有向图邻接矩阵的可逆性

文献摘要

被引文献

相似文献