Sharp transition of the invertibility of the adjacency matrices of sparse random graphs

• 成果类型: Article
• 署名作者: Basak, Anirban; Rudelson, Mark
• 署名单位: Tata Institute of Fundamental Research (TIFR); International Centre for Theoretical Sciences, Bengaluru; Weizmann Institute of Science; University of Michigan System; University of Michigan
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-021-01038-4
• 发表日期: 2021
• 页码: 233-308
• 关键词: smallest singular-value; circular law; condition numbers; UNIVERSALITY; rank; probability; Digraphs; NORM

摘要

We consider three models of sparse random graphs: undirected and directed Erdos-Renyi graphs and random bipartite graph with two equal parts. For such graphs, we show that if the edge connectivity probability p satisfies np >= log n + k(n) with k(n) -> infinity as n -> infinity, then the adjacency matrix is invertible with probability approaching one (n is the number of vertices in the two former cases and the same for each part in the latter case). For np <= log n -k(n) these matrices are invertible with probability approaching zero, as n -> infinity. In the intermediate region, when np = log n + k(n), for a bounded sequence k(n) is an element of R, the event Omega(0) that the adjacency matrix has a zero row or a column and its complement both have a non-vanishing probability. For such choices of p our results show that conditioned on the event Omega(c)(0) the 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 Omega(c)(0), with a large probability, establishing von Neumann's prediction about the condition number up to a factor of n(o(1)).