On the Rank, Kernel, and Core of Sparse Random Graphs

arXiv2105.11718MaRDI QIDQ6368457

Alexandre Moreira, Patrick DeMichele, Margalit Glasgow

Publication date: 25 May 2021

Abstract: We study the rank of the adjacency matrix $A$ of a random Erdos Renyi graph $GsimmathbbG(n,p)$. It is well known that when $p=(log(n)-omega(1))/n$, with high probability, $A$ is singular. We prove that when $p=omega(1/n)$, with high probability, the corank of $A$ is equal to the number of isolated vertices remaining in $G$ after the Karp-Sipser leaf-removal process, which removes vertices of degree one and their unique neighbor. We prove a similar result for the random matrix $B$, where all entries are independent Bernoulli random variables with parameter $p$. Namely, we show that if $H$ is the bipartite graph with bi-adjacency matrix $B$, then the corank of $B$ is with high probability equal to the max of the number of left isolated vertices and the number of right isolated vertices remaining after the Karp-Sipser leaf-removal process on $H$. Additionally, we show that with high probability, the $k$-core of $mathbbG(n,p)$ is full rank for any $kgeq3$ and $p=omega(1/n)$. This partially resolves a conjecture of Van Vu for $p=omega(1/n)$. Finally, we give an application of the techniques in this paper to gradient coding, a problem in distributed computing.

This page was built for publication: On the Rank, Kernel, and Core of Sparse Random Graphs

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