The Exact Rank of Sparse Random Graphs

arXiv2303.05435MaRDI QIDQ6429002FDOQ6429002

Mehtaab Sawhney, Ashwin Sah, Margalit Glasgow, Matthew Kwan

Publication date: 9 March 2023

Abstract: Two landmark results in combinatorial random matrix theory, due to Koml'os and Costello-Tao-Vu, show that discrete random matrices and symmetric discrete random matrices are typically nonsingular. In particular, in the language of graph theory, when $p$ is a fixed constant, the biadjacency matrix of a random ErdH{o}s-R'enyi bipartite graph $mathbbG(n,n,p)$ and the adjacency matrix of an ErdH{o}s-R'enyi random graph $mathbbG(n,p)$ are both nonsingular with high probability. However, very sparse random graphs (i.e., where $p$ is allowed to decay rapidly with $n$) are typically singular, due to the presence of "local" dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper we give a combinatorial description of the rank of a sparse random graph $mathbbG(n,n,c/n)$ or $mathbbG(n,c/n)$ in terms of such local dependencies, for all constants $cee$ (and we present some evidence that the situation is very different for $c=e$). This gives an essentially complete answer to a question raised by Vu at the 2014 International Congress of Mathematicians. As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well-approximated by its matching number, and we deduce a central limit theorem for the rank of $mathbbG(n,c/n)$.

This page was built for publication: The Exact Rank of Sparse Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429002)