On low-degree dependencies for sparse random graphs

Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies" such as isolated vertices and pairs of degree-1 vertices with the same neighborhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $k\geq 3$ and $\lambda>0$, an Erdős–Rényi random graph of $n$ vertices and edge probability $\lambda/n$ typically has the property that its $k$-core (largest subgraph with min-degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 ICM, and adds to a short list of known nonsingularity theorems for "extremely sparse" random matrices with density $O(1/n)$. In subsequent work, we draw on related techniques to give a precise combinatorial characterization of the co-rank of the Erdős–Rényi random graph with density $\lambda/n$ coming from the Karp-Sipser core. A key aspect of our proof is a technique to extract high-degree vertices and use them to "boost" the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge and Salez.

This talk is based on joint works with Asaf Ferber, Margalit Glasgow, Matthew Kwan, and Ashwin Sah.