On the rank, Kernel, and core of sparse random graphs.

We study the rank of the adjacency matrix A$$ A $$ of a random Erdős‐Rényi graph G∼픾(n,p). It is well known that when p=(log(n)−ω(1))/n$$ p=\left(\log (n)-\omega (1)\right)/n $$, with high probability, A$$ A $$ is singular. We prove that when p=ω(1/n)$$ p=\omega \left(1/n\right) $$, with high probability, the corank of A$$ A $$ is equal to the number of isolated vertices remaining in G$$ 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$$ B $$, where all entries are independent Bernoulli random variables with parameter p$$ p $$. Namely, we show that if H$$ H $$ is the bipartite graph with bi‐adjacency matrix B$$ B $$, then the corank of B$$ 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$$ H $$. Additionally, we show that with high probability, the k$$ k $$‐core of 픾(n,p) is full rank for any k≥3$$ k\ge 3 $$ and p=ω(1/n)$$ p=\omega \left(1/n\right) $$. This partially resolves a conjecture of Van Vu for p=ω(1/n)$$ p=\omega \left(1/n\right) $$. Finally, we give an application of the techniques in this paper to gradient coding, a problem in distributed computing. [ABSTRACT FROM AUTHOR]