Invertibility of the 3-core of Erdos Renyi Graphs with Growing Degree

Abstract

Let $A\in {\mathbb{R}}^{n\times n}$ be the adjacency matrix of an Erdős Rényi graph $G(n,d/n)$ for $d=\omega (1)$ and $d\le 3\log (n)$. We show that as $n$ goes to infinity, with probability that goes to $1$, the adjacency matrix of the $3$-core of $G(n,d/n)$ is invertible.

arXiv commentThis article has been combined with other work, and replaced by the article at arXiv:2105.11718