Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
复制标题
稀疏随机图邻接矩阵可逆性的急剧转变
DOI：
10.1007/s00440-021-01038-4
复制
发表时间：
2021
影响因子：
2
通讯作者：
Rudelson, Mark
中科院分区：
文献类型：
--
作者：
Basak, Anirban;Rudelson, Mark
我们考虑了稀疏随机图的三种模型：无向和有向Erdens-Rényi图以及两个相等部分的随机二部图。对于这类图，我们证明了如果边连通概率p满足，则邻接矩阵可逆，概率接近1（在前两种情况下为顶点数，在后一种情况下为每个部分的顶点数）。对于这些矩阵是可逆的概率接近零，如。对于有界序列，在中间区域，当邻接矩阵有零行或零列的事件及其补阵都有非零概率时。对于这样的选择倒结果表明，条件的事件，矩阵再次可逆的概率趋于一.这表明这种矩阵不可逆的主要原因是存在零行或零列。我们进一步推导出这些矩阵的（修改后的）条件数上的界，以很大的概率，建立冯诺依曼的预测的条件数的一个因素。
We consider three models of sparse random graphs: undirected and directed Erdős–Rényi graphs and random bipartite graph with two equal parts. For such graphs, we show that if the edge connectivity probabilitypsatisfieswithas, then the adjacency matrix is invertible with probability approaching one (nis the number of vertices in the two former cases and the same for each part in the latter case). Forthese matrices are invertible with probability approaching zero, as. In the intermediate region, when, for a bounded sequence, the eventthat the adjacency matrix has a zero row or a column and its complement both have a non-vanishing probability. For such choices ofpour results show that conditioned on the eventthe matrices are again invertible with probability tending to one. This shows that the primary reason for the non-invertibility of such matrices is the existence of a zero row or a column. We further derive a bound on the (modified) condition number of these matrices on, with a large probability, establishing von Neumann’s prediction about the condition number up to a factor of.
登录
查看更多内容
随机正则有向图的循环定律
DOI：
10.1214/18-aihp943
发表时间：
2017
期刊：
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
影响因子：
--
作者：
Nicholas A. Cook
通讯作者：
Nicholas A. Cook
随机 d-正则有向图邻接矩阵的可逆性
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
Jiaoyang Huang
通讯作者：
Jiaoyang Huang
随机矩阵的命中时间定理
DOI：
--
发表时间：
2013
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
L. Addario;Laura Eslava
通讯作者：
Laura Eslava
对称随机矩阵的可逆性
影响因子：
1
作者：
R. Vershynin
通讯作者：
R. Vershynin
随机矩阵的可逆性：酉扰动和正交扰动
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
M. Rudelson;R. Vershynin
通讯作者：
R. Vershynin