We study the rank of the adjacency matrix $A$ of a random graph $G\sim \mathbb{G}(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 $\mathbb{G}(n, p)$ is full rank for any $k \geq 3$ and $p = \omega(1/n)$. This partially resolves a conjecture of Van Vu [30] for $p = \omega(1/n)$. Finally, we give an application of the techniques in this paper to gradient coding, a problem in distributed computing.

§ INTRODUCTION

Let $A \sim \mathbb{A}(n, p)$ be a random symmetric matrix in $\{0, 1\}^{n \times n}$ where each entry above the diagonal is an i.i.d. Bernoulli random variable that equals $1$ with probability $p$ and $0$ otherwise, and where the diagonal entries are $0$. Equivalently, $A$ is the adjacency matrix of an graph $G \sim \mathbb{G}(n, p)$ on $n$ nodes where an edge appears between each pair of nodes with probability $p$.

Determining the rank of $A$ has been a question of considerable interest. Initial results by Tao, Costello, and Vu [12] proved that $A$ is non-singular with high probability if $p$ is a fixed constant. This result was later improved by Costello and Vu in [14] to show that $A$ is non-singular with high probability if $p > (1+\varepsilon)\log(n)/n$. This work also showed that $p = \log(n)/n$ is a threshold for singularity as $A$ is singular with high probability if $p < (1-\varepsilon)\log(n)/n$.  Recent work by Basak and Rudelson [3] shows this threshold is sharp in the sense that if $p\geq \log(n)/n+\omega(1/n)$, then $A$ is non-singular with high probability, and if $p\leq \log(n)/n-\omega(1/n)$, then $A$ is singular with high probability. Furthermore, they prove the same result holds for the asymmetric matrix $B\sim \mathbb{B}(n,p)$ in $\{0,1\}^{n\times n}$ where each entry is an independent Bernoulli random variable with parameter $p$. More generally, an fundamental question in discrete random matrix theory, dating back to Komlos [23], studies the exact probability that a random matrix is singular. See the survey of Van Vu [30] and the references therein for discussion of the singularity problem.

Following these threshold results, a natural question is determining the rank of $A$ and $B$ when $p$ is small enough that these random matrices are singular with high probability. One approach to understand the rank, previously emphasized by Costello and Vu, is through the following phenomenon:

Linear dependencies among the columns of random matrices arise from small structures.

Costello and Vu [13]  showed that when $p=\Omega(\log(n)/n)$, with high probability, all dependencies in the column space of $A$ result from collections of $k=\Theta(1)$ columns with at most $k-1$ non-zero rows. These so-called non-expanding sets allowed Costello and Vu to prove that when $p=\Omega(\log(n)/n)$, with high probability,

\begin{equation*}
\text{rank($A$)}= \min_{S\subseteq V(G(A))} (n-|S|+|N(S)|)
\end{equation*}

where $N(S)$ denotes the neighborhood of the vertex set $S$, $G(A)$ denotes the graph with adjacency matrix $A$, and $V(G)$ denotes the vertex set of a graph $G$.

Other work has shown additional instances of Phenomenon <ref>. Addario-Berry and Eslava [1] showed that with probability $1- o(1)$, if you expose the non-zero entries of $A$ or $B$ randomly one at time, the matrix becomes singular at the exact moment when any row or column of all zeros disappears. For $B \sim \mathbb{B}(n, p)$, with $\log(n)/n \leq p \leq 1/2$, Tikhomirov [29] and Jain et al. [19] show that the probability of singularity of $B$ is nearly exactly the probability that $B$ has an all-zero row or column (or two equivalent rows and columns when $p = 1/2$). Further work  [20, 18] shows that for various ranges of $p$, the probability that $B$ has corank $k$ is nearly the probability that $k$ rows are all zero.

A second approach towards understanding the rank of $A \sim \mathbb{A}(n,  p)$ or $B \sim \mathbb{B}(n, p)$ is via the Karp-Sipser core of a graph, defined below. Originally introduced in [22] to study maximal matchings, the Karp-Sipser core of graph $G$ is obtained by iteratively performing a leaf-removal process, which at each step removes a vertex of degree one and its unique neighbor. At the end of the process, there remain only isolated vertices and a subgraph of minimum degree at least two, which we denote $G_{\on{KS}}$. Notably, this leaf-removal process, which we also call peeling,  does not change the corank of the graph[We say the corank of a graph to mean the corank of its adjacency matrix.], and so the corank of $G$ equals the corank of the $G_{\on{KS}}$ plus the number of isolated vertices remaining after the leaf-removal process. The following lower bound on the corank of $A$ immediately follows:

\begin{equation}\label{eq:lb_A}
\on{corank}(A) \geq |I_{\on{KS}}|,
\end{equation}

where $I_{\on{KS}}$ is the set of isolated vertices remaining after the Karp-Sipser leaf-removal on $G(A)$. For the asymmetric matrix $B$, a similar lower bound holds. We define $H(B)$ to be the bipartite graph with bi-adjacency matrix $B$ and left and right vertex sets $L$ and $R$ respectively. Then using the invariance of the corank during peeling, we obtain:

\begin{equation}\label{eq:lb_B}
\on{corank}(B) \geq \max\left(|I_{\on{KS}} \cap L|, |I_{\on{KS}} \cap R| \right),
\end{equation}

where $I_{\on{KS}}$ is the set of isolated vertices remaining after the Karp-Sipser leaf-removal on $H(B)$.

A central question asks if these lower bounds on the corank are tight. Two important works yield results on this front for $p = \Theta(1/n)$. Bordenave, Lelarge, and Salez show in [6] that as $n$ grows, the corank of the Karp-Sipser core of $G(A)$ divided by $n$ tends to zero. That is, almost surely,
$$\lim_{n \rightarrow \infty} \frac{\on{corank}(A) - |I_{\on{KS}}|}{n} = 0.$$
A related asymptotic formula was shown by Coja-Oghlan et al. [11] for the asymmetric random matrix $B \sim \mathbb{B}(n, p)$. They showed[This follows from evaluating their rank formula and comparing to the asymptotic size they give for $I_{\on{KS}}$.] that in probability,

$$\lim_{n \rightarrow \infty} \frac{\on{corank}(B) - |I_{\on{KS}} \cap L|)}{n} = 0.$$

Both of these results are proved without explicitly connecting the corank to the size of $I_{\on{KS}}$ (or $I_{\on{KS}} \cap L$), but rather by showing that asymptotically these two values coincide. Due to their connections with the size of maximal matchings, the asymptotic size of $G_{\on{KS}}$ and $I_{\on{KS}}$ are well known, and can be studied via differential equations. Karp and Sipser [22] and the tighter analysis of Aronson, Frieze and Pittel in [2] showed in that for $G \sim \mathbb{G}(n, p)$, in probability,
$$\lim_{n \rightarrow \infty} \frac{|I_{\on{KS}}|}{n} = \frac{\gamma^* + \gamma_* + \gamma^*\gamma_* - 1}{pn},$$

where $\gamma_*$ is the smallest root to the equation $x = pn\exp(-pne^{-x})$, and $\gamma^* = pne^{-\gamma_*}$. Analogously, for the bipartite graph $H(B)$ with $B \sim \mathbb{B}(n, p)$, Coja-Oghlan et al. showed that in probability,
$$\lim_{n \rightarrow \infty} \frac{|I_{\on{KS}} \cap L|}{n} = \frac{\gamma^* + \gamma_* + \gamma^*\gamma_* - 1}{pn}.$$

Our main result is to show that the lower bounds in eqs. <ref> and <ref> are sharp for $p = \omega(1/n)$. In the vein of Phenomenon <ref>, we prove a new structural characterization of linear dependencies in $A$ and $B$, which holds with high probability, and tightens Costello and Vu's notion of non-expanding sets. On the event that this characterization holds, it follows almost directly that the Karp-Sipser leaf-removal and isolated vertex removal process is precisely equivalent to removing all vertices whose respective rows and columns are part of linear dependencies. Equivalently, on this event, the Karp-Sipser core of $A$ is full rank. We state this result in the following theorem.

[Rank of $A$]theoremthmksA
Let $p = \omega(1/n)$ and $p \leq 1/2$ and $A \sim \mathbb{A}(n, p)$. Let $G = G(A)$. With probability $1 - o(1)$,

$$\on{corank}(A\left({G_{\on{KS}}}\right)) = 0.$$

Equivalently, with probability $1 - o(1)$,

$$\on{corank}(A) = |I_{\on{KS}}|,$$

where $I_{\on{KS}}$ is the set of isolated vertices remaining after the Karp-Sipser leaf-removal on $G$.

For the asymmetric matrix $B$, the story is slightly complicated by the fact that typically, there are “complex” linear dependencies that involve large sets of rows or columns of $B$. These linear dependencies can not be characterized using the same simple structural characterization we prove for the symmetric matrix. Fortunately, we are able to a prove a modified characterization result which shows that with high probability, such “complex” linear dependencies only appear in the rows of $B$ or the columns of $B$, but not both. It follows on this event that the bi-adjacency matrix of the Karp-Sipser core of $H(B)$ has full row or column rank. We state this result and the resulting characterization of the rank of $B$ in the following theorem.

[Rank of $B$]theoremthmksB
Let $p = \omega(1/n)$ and $p \leq 1/2$ and $B \sim \mathbb{B}(n, p)$. Let $H = H(B)$ be a bipartite graph with $n$ left vertices $L$ and $n$ right vertices $R$. With probability $1 - o(1)$, either

* $\on{corank}(B({H_{\on{KS}}})) = 0,$ or

* $\on{corank}(B({H_{\on{KS}}})^\top) = 0.$

It follows that with probability $1 - o(1)$,

$$\on{corank}(B) = \max(|I_{\text{KS}} \cap L|, |I_{\text{KS}} \cap R|),$$

where $I_{\on{KS}}$ is the set of isolated vertices remaining after the Karp-Sipser leaf-removal on $H$.

Our main tool in proving these theorems is a new characterization of all minimally linearly dependent sets of columns that occur with constant probability in $A$ and $B$.

A matrix in $M \in \mathbb{R}^{m \times k}$ is a minimal linear dependency if it satisfies the following two properties:

* There exists $x \in \mathbb{R}^k$ such that $Mx = 0$ and $\on{supp}(x) = [k]$.

* $\on{rank}(M) = k-1$.

We sometimes will abbreviate and call such a matrix a minimal dependency.

It is a simple exercise to show that every linearly dependent set of columns has a subset of columns which form a minimal linear dependency. One can additionally show that in any matrix $M$, if the $i$th column $M_i$ is in the span of the remaining columns $\{M_j\}_{j \neq i}$, then there exists some subset of columns of $M$ including $M_i$ which is a minimal dependency (see Lemma <ref>). Let
$$\mathcal{M}_k \subset \bigcup_{m \geq 1} \{0,1\}^{m \times k}$$
denote the set of {0, 1}-matrices of $k$ columns which are minimal linear dependencies. For our main results, we distinguish among $\mathcal{M}_k$ one particular class of minimal linear dependencies, illustrated in Figure <ref>(a).

Instances of the three classes of minimal dependencies of $k = 5$ columns that occur with constant probability in $A$ and $B$ with $p = \Theta(1/n)$. For $p = \omega(1/n)$, with probability $1-o(1)$ only tree dependencies (a) appear. (a) An element of $\mathcal{T}_k$. (b) An element of $\mathcal{T}_k^+$ (see Section <ref>). (c) An element of $\mathcal{T}_k^C$ (see Section <ref>).

Define $\mathcal{T}_k$ as the set of matrices $M\in \bigcup_m \{0,1\}^{m\times k}$ with exactly $2k - 2$ $1$'s such that the non-zero columns of $M$ form the edge-vertex incidence matrix of a tree on $k$ vertices. We call a matrix in $\cup_k \mathcal{T}_k$ a tree dependency.

The following theorem shows that with high probability, all minimal dependencies in $A$ are tree dependencies.

[Characterization of minimal dependencies in $A$]theoremcharsquare
Let $A \sim \mathbb{A}(n, p)$, where $p = \omega(1/n)$ and $p \leq 1/2$. With probability $1 - o(1)$, for all $k$, all minimal dependencies of $k$ columns of $A$ are in $\mathcal{T}_k$.

Similarly, either all subsets of columns of $B$ or of $B^\top$ that are minimal linear dependencies, are tree dependencies.
[Characterization of minimal dependencies in $B$]theoremcharbgc
Let $B \sim \mathbb{B}(n, p)$, where $p = \omega(1/n)$ and $p \leq 1/2$. With probability $1 - o(1)$, one of the following holds:

* For all $k$, all minimal dependencies of $k$ columns of $B$ are in $\mathcal{T}_k$.

* For all $k$, all minimal dependencies of $k$ columns of $B^\top$ are in $\mathcal{T}_k$.

We do not expect the theorem above can be improved, in the sense that often $B$ or $B^\top$ do have minimal linear dependencies with $\Theta(n)$ columns. Intuitively, this is because short and fat rectangular matrices contain minimal dependencies with many columns. When we peel off the rows and columns involved in small minimal linear dependencies, the remaining matrix, $B(H_{\on{KS}})$, may be rectangular if there are more small minimal linear dependencies in the rows than in the columns (or vice versa). This forces a minimal dependency with many columns in $B$ (or $B^\top$).

When $p=\Theta(1/n)$, Theorems <ref> and <ref> fail due to the presence of two other classes of minimal dependencies which appear with constant probability in $A$ and $B$. These two classes are pictured in Figure <ref>(b)(c) and defined formally in Section <ref>.

§.§ Additional Results

A second substructure of random graphs which has received considerable attention is the $k$-core of $G$: the largest induced subgraph of $G$ with minimal degree $k$. The $k$-core, which we denote $\on{core}_k(G)$, can be obtained by iteratively peeling off vertices of degree less than $k$. When the average degree of $G$ is greater than some constant $c = c(k)$, the $k$-core suddenly emerges and has linear size in the number of vertices of $G$ [24]. The exact size of the $k$-core is given by Pittel, Spencer, and Wormald in [25].

Van Vu conjectured in [30] that for $p = \Theta(1/n)$, for a constant $k \geq 3$, almost surely, the adjacency matrix of $\on{core}_k(G)$ is non-singular. We prove the following result, which confirms the conjecture of Vu for $p = \omega(1/n)$. Let $\on{core}_k(A)$ denote the adjacency matrix of the $k$-core of the graph with adjacency matrix $A$.
Let $A \sim \mathbb{A}(n, p)$, where $p = \omega(1/n)$ and $p \leq \frac{3\log(n)}{n}$. For any constant $k \geq 3$, with probability $1 - o(1)$,

$$\on{corank}(\on{core}_k(A)) = 0.$$

We remark that Ferber et al. [15] recently resolved the conjecture of Vu, after a preliminary version of the present paper was made publicly available. This was independent work, and the proof methods are quite different.

We additionally show an application of our techniques to a problem in distributed computing. For this application, we show that our characterization of minimal dependencies also holds for some ensembles of sparse rectangular random matrices. Using this characterization, we can bound the distance from a fixed vector to the span of a random matrix. This is useful for analyzing gradient codes, an object used to provide redundancy in distributed computing. We discuss the particular results in Section <ref>.

§.§ Notation

For a graph $G$, we use $A(G)$ to denote the adjacency matrix of $G$. We use $G(A)$ to denote the graph with adjacency matrix $A$. For a bipartite graph $H = (L \cup R, E)$, we use $B(H)$ to denote the bi-adjacency matrix of $H$, where $L$ indexes rows of $B(H)$, and $R$ indexes columns. We use $H(B)$ to denote the bipartite graph with bi-adjacency matrix $B$. We use $V(G)$ or $V(A)$ to denote the vertex set of a graph $G$ or $G(A)$.

For $n \in \mathbb{N}$, let $[n]$ denote the set $\{1, \ldots , n\}$. For a matrix $M \in \mathbb{R}^{m \times n}$ and $S \subseteq [n]$, we let $M_S$ denote the submatrix of $M$ with columns indexed by $S$. For $S \subseteq [m]$, we let $M^S$ denote the submatrix of $M$ with rows indexed by $S$. Furthermore, for an index $i\in \mathbb{N}$, we let $M_i$ denote the $i$th column of $M$ and we let $M_{\backslash i}$ denote $M$ with the $i$th column removed. We define $M^{\backslash i}$ for rows analogously. We let $M^{(i)}$ denote $M$ with both the $i$th row and $i$th column removed. Finally, we let $M^{\top}$ denote the transpose of $M$. We say the corank of $M$ equals $m - \on{rank}(M)$.

For vectors $x \in \mathbb{R}^n$ and $y \in \mathbb{R}^m$, let  $(x, y) \in \mathbb{R}^{m + n}$ denote the concatenation of $x$ and $y$. We use $e_i$ to denote the $i$th standard basis vector.

§.§ Outline

In Section <ref>, we give a technical overview of the proofs of the main theorems. We break down the proofs of Theorems <ref> and <ref> thematically into Sections <ref> and <ref>, where we prove the main technical lemmas. We conclude the proof in Section <ref>. In Section <ref>, we prove Theorems <ref> and <ref> using Theorems <ref> and <ref>.

§ TECHNICAL OVERVIEW

In this section, we give a high level overview of the proof of the main theorems in this paper.

§.§ Overview of Proposition <ref> and Proposition <ref>
For simplicity, in this overview we primarily focus on the asymmetric matrix $B \sim \mathbb{B}(n, p)$, where $p = d/n$.  We provide comments on when and how the techniques differ for the symmetric matrix $A \sim \mathbb{A}(n, p)$.

Our proof of each characterization result is divided into two domains: a “small” domain and a “large” domain. The small domain considers possible kernel vectors with support at most $\frac{n}{d}$. The large domain considers possible kernel vectors with support at least $\frac{n}{d}$.  Thematically, this is similar to the more-involved casework based on levels of “structuredness” of vectors used classically to show that the kernel of $A$ is empty for $p > \log(n)/n$. (See eg. [27, 29, 19])

§.§.§ Small Domain

The main idea for the small domain comes from the following two simple observations.

Let $M \in \{0, 1\}^{m \times k}$ be a matrix. Then if some row of $M$ contains exactly one $1$, then there is no $x \in \mathbb{R}^k$ such that $Mx = 0$ and $\supp(x) = [k]$.

If there is only one column of $M$ with a $1$ at a certain row-index, that column is linearly independent of all other columns in $M$. Thus, no dependency including all columns of $M$ exists.

Let $M \in \{0, 1\}^{m \times k}$ be a matrix.
If $M$ has support size less than $2k-2$, then $M$ is not a minimal linear dependency.

The requirement that $M$ is rank $k-1$ means that at least $k-1$ rows must have at least one $1$ in them. Hence it follows from Observation <ref> that each of these rows must contain at least two 1s. Thus, if $M$ is a minimal dependency, it contains at least $2k-2$ $1$'s.

Within the small domain, we subdivide into two cases, again depending on the size of the support of the kernel vector. The results for the small domain are proved in Section <ref>.

Small Case 1
The goal of this case is to prove that with high probability, for any $k \leq \Theta(n/d^2)$, and $S \subset [n]$ with $|S| = k$, if $B_S$ is a minimal dependency, then $B_S \in \mathcal{T}_k$. We will take a union bound over all such sets $S$ to prove this. Fix $S$ with $|S| = k$, and define $L$ to be the number of $1$s in $B_S$. Due to Observation <ref>, we only must consider the case when $L \geq 2k - 2$. Further, if $L = 2k - 2$, then if $B_S$ is a minimal dependency, it must also be in $\mathcal{T}_k$ (see Lemma $\ref{lemma:classification}$).

By Observation <ref>, $B_S$ is not a minimal dependency if there exists a row with exactly one $1$ in $B_S$. To lower bound this probability, we condition on $L$, consider the random process which exposes the $L$ positions of $1$s in $B_S$ randomly one at a time. Consider the random walk which increases by $1$ every time we expose a $1$ in an already occupied row, and stays constant otherwise. As long as the value of this random walk is less than $L/2$ at the time all $L$ $1$s are exposed, we know that $B_S$ is not a minimal dependency. When $L \geq 2k - 1$, this occurs with small enough probability that after a union bound on all sets $S$, we succeed with probability $1-o(1)$.

For the case of symmetric matrices, we modify this argument slightly by considering the random walk which also increases every time a $1$ is exposed in the “symmetric” portion of $A_S$, that is, a row of $A_S$ indexed by an element of $S$.

Small Case 2
This case rules out with high probability any minimal dependencies of $k$ columns of $B$ for $\frac{n}{d^2} \lesssim k \lesssim \frac{n}{d}$. Again we use Observation <ref> and take a union bound over all submatrices $B_S$ for sets $S$ of size $k$. We use a Chernoff bound to show that with very high probability, $B_S$ has a row with a single $1$.

§.§.§ Large Domain

As $k$ approaches $n/d$, we can no longer expect $B_S$ to have rows with a single $1$ with high enough probability, so we need to look beyond Observation <ref> to rule out linear dependencies. Our main tool in ruling out larger minimal dependencies are the following Littlewood-Offord anti-concentration results for sparse vectors, from Costello and Vu [14].

[c.f. [14] Lemma 8.2]lemmalosparse
Let $v \in \mathbb{R}^n$ be a deterministic vector with support at least $m$. Let $z \in \mathbb{R}^n$ be a random vector with i.i.d. Bernoulli entries with parameter $p \leq 1/2$. For any $c$,

$$\Pr\left[v^\top z=c\right] \leq \left(\frac{1}{\sqrt{\pi/2}}\right)\frac{1}{\sqrt{mp}}+\left(e^{(\ln(2)-1)mp}\right).$$

In particular, for $mp\geq 9$, we have:

$$\Pr\left[ v^\top z=c\right] \leq \frac{1}{\sqrt{mp}}.$$

In the symmetric matrix case, we will additionally use a quadratic Littlewood-Offord result, originally due to Costello, Tao, and Vu [12], and adapted to sparse random vectors in [14].

Let $M \in \mathbb{R}^{n \times n}$ be a deterministic matrix with a least $m$ non-zero entries in each of $m$ distinct columns of $M$. Let $z \in \mathbb{R}^n$ be the random vector with i.i.d. Bernoulli entries with parameter $p \leq 1/2$. Then for any fixed $c$,

$$\Pr\left(z^\top Mz = c\right) = O\left(\frac{1}{(mp)^{1/4}}\right).$$

Again we subdivide into two cases.

Large Case 1
This case rules out with high probability minimal dependencies of $k$ columns of $B$ for $n/d \lesssim k \leq n/c$, for some constant $c$. In this case, we again perform a union bound over all submatrices $B_S$ for sets $S$ of size $k$. For each $S$, we consider the random process $B^{[1]}_S, B^{[2]}_S, \cdots B^{[n]}_S = B_S$, where we expose rows of $B_S$ one at a time. (Recall that $B^{[i]}_S$ is the submatrix of $B$ given by restricting to the columns in $S$ and the first $i$ rows.) At each step $i$, we keep track of the kernel of $B_S^{[i]}$. Before any rows are exposed, the dimension of the kernel is equal to $k$. Since our goal is to show that the kernel of $B_S$ contains no vectors with support size $k$, we leverage Lemma <ref> as follows: if the kernel of $B^{[i]}_S$ contains a vector $v$ with support $k$, then it is likely that the next row exposed, $B_S^{\{i+1\}}$, will not be orthogonal to $v$. After exposing enough rows, we show that with high probability, we “knock out” all candidate kernel vectors with large support. Notice that we only need to “knock out” such vectors at most $k$ times.

This approach of Large Case 1 breaks down when $k$ approaches $n$. For instance, in the extreme case when $k = n$, we would need to “knock-out” a kernel vector every single time we expose a row of $B$. This certainly won't occur with high probability. Hence we use a different approach when $k \geq n/c$ for some constant $c$.

Large Case 2
Our strategy for ruling out dependencies on the order of $\Theta(n)$ columns is inspired by the approach of Ferber, Kwan, Sauermann [16] to show the almost sure non-singularity of $B$ when $p > \log(n)/n$. For the symmetric matrix $A$, we combine these ideas with some techniques used by Costello, Tau, and Vu in [12] to show almost sure non-singularity of $A$ when $p = 1/2$. The following simple observation is key to our argument for both $A$ and $B$.

Let $M \in \mathbb{R}^{n \times n}$ be a matrix. If $Mv = 0$, and $v$ has support size $k$, then there are at least $k$ columns $M_i$ such that $M_i \in \on{Span}(\{M_j\}_{j \neq i})$.

For the asymmetric case, recall that our goal is to show that either $B$ or $B^\top$ has no kernel vector with support size at least $n/c$. Let $\mathcal{E}_i$ be the event that $B$ has a left kernel vector with support size at least $n/c$, and that column $B_i$ is in the span of the remaining columns $\{B_j\}_{j \neq i}$. Then by Markov's Law and Observation <ref>, the probability that both $B$ and $B^\top$ have kernel vectors with support size at least $n/c$ is at most $c\mathbb{P}[\mathcal{E}_i]$. To bound this probability, consider the matrix $B_{/i}$ formed by removing the $i$th column of $B$. We define $\mathcal{F}_i$ to be the event that $B_{/i}$ has a left kernel vector with support size at least $n/c$, and that column $B_i$ is in the span of the remaining columns $\{B_j\}_{j \neq i}$. Observe that any left kernel vector of $B$ is a left kernel vector of $B_{/i}$, and so $\mathcal{E}_i \subseteq \mathcal{F}_i$. To bound the probability of $\mathcal{F}_i$, we condition on $B_{/i}$ and  leverage the independence of $B_i$ from $B_{/i}$. Assume $B_{/i}$ has some left kernel vector $v$ with $|\on{supp}(v)| \geq n/c$. Lemma <ref> tells us that with probability $1 - O(1/\sqrt{d})$, the column $B_i$ is not orthogonal to $v$, and hence $B_i$ is not in the span of the remaining columns $\{B_j\}_{j \neq i}$. It follows that $\Pr[\mathcal{E}_i] \leq \Pr[\mathcal{F}_i] = O(1/\sqrt{d})$.

In the symmetric case, we let $\mathcal{E}_i$ be the event that the column $A_i$ is in the span of the remaining columns $\{A_j\}_{j \neq i}$. Again we use Markov's Law and Observation <ref> to show that the probability that $A$ has a kernel vector of support size of at least $n/c$ is at most $c\mathbb{P}[\mathcal{E}_n]$. To bound $\mathbb{P}[\mathcal{E}_n]$, we condition on $A^{(n)}$, the matrix formed by removing the $n$th row and column of $A$, and leverage the randomness of $A_n$.

We consider two main cases: one in which $A^{(n)}$ has a kernel vector with large support, and one in which it doesn't. If $A^{(n)}$ has a kernel vector $v$ with large support (on the order of $\Theta(n)$), we use Lemma <ref> to show that with probability $1 - O(1/\sqrt{d})$, $A_n^{/n}$ is orthogonal to $v$, and hence $A_n$ is not in the span of the remaining columns $\{A_j\}_{j \neq n}$ (recall that $A_n^{/n}$ denotes the vector with all but the $n$th entry $A_n$). If $A^{(n)}$ has no kernel vectors with large support, we construct a “pseudoinverse” $P$ for $A^{(n)}$, for which $(A_n^{/n})^\top PA_n^{/n} \neq 0$ implies that $A_n$ is not in the span of $\{A_j\}_{j \neq n}$. We leverage some additional results from the small domain and Large Case 1 to show that $P$ is dense. Lemma <ref> then guarantees that $(A_n^{/n})^\top PA_n^{/n} \neq 0$ with probability $1 - O(1/\sqrt[4]{d})$.

The results for the large domain are proved in Section <ref>.

The roadmap of this proof shows the two places where our techniques break down when $d$ is a constantFirst, in Small Case 1, our union bound only succeeds in ruling out minimal dependencies outside of $\mathcal{T}_k$ with probability $e^{-\Theta(dk)}$. When $k$ and $d$ are constant, this probability no longer goes to $0$. One can check that with constant probability, there are some minimal dependencies outside $\mathcal{T}_k$, but they are contained in two other classes of special structures, which we formally define in Section <ref> as $\mathcal{T}_k^+$ and $\mathcal{T}_k^C$ (pictured in Figure <ref>).

Second, our results for Large Case 2, based on the Littlewood-Offord lemmas, require $d$ to go to infinity to get a result which holds with probability that tends to $1$.

§.§ Overview of Theorem <ref> and Theorem <ref>
Theorems <ref> and <ref> follow directly by combining two linear-algebraic claims about the Karp-Sipser leaf-removal process with the results of Theorems <ref> and <ref>. Specifically, to prove Theorem <ref> on the rank of $A$, we use the following three claims:

* The corank of a matrix is invariant under the Karp-Sipser leaf removal process.

* If the Karp-Sipser core $A_{\on{KS}}$ has a vector in $x$ its kernel, then there must be a kernel vector $y$ of $A$ whose support contains the support of $x$.

* If $Ay = 0$, then by the characterization of minimal dependencies in Theorem <ref>, for all $i \in \on{supp}(y)$, the vertex $i$ will be removed during the Karp-Sipser leaf-removal process or become isolated after this process. Thus, vertex $i$ will not be in the Karp-Sipser core of $A$.

The proof of Theorem <ref> on the rank of $B$ is similar. These claims are proved in Section <ref>.

§.§ Overview of Theorem <ref>

To prove Theorem <ref>, we need to show that the kernel of $\on{core}_k(A)$ is empty. We use the same four cases as in the proof of Theorems <ref> and <ref> above.

The techniques used to rule out minimal dependencies in each of these cases is largely the same as before. In the small domain, we leverage the fact that any subset of $\ell$ columns of $\on{core}_k(A)$ for $k \geq 3$ must have at least $3\ell$ $1$'s.

In Large Case 2, we adapt our argument in a more involved way. We define $\mathcal{E}_i$ to be the event that $\on{core}_k(A)_i$ is in the span of the remaining columns of $\on{core}_k(A)$ and that the $k$-core is “normal” with respect to vertex $i$. Formally, we say the $k$-core is normal with respect to $i$ if vertex $i$ is in the $k$-core, and if we remove vertex $i$ from the $k$-core, the remaining graph still has minimum degree at least $k$. Equivalently and symbolically, this means

$$V(\text{core}_k(A)) = i \cup V(\text{core}_k(A^{(i)})).$$

We proceed to show that the $k$-core is normal with respect to all but $o(n)$ vertices. It follows from Observation <ref> and Markov's Law, that the probability that $\on{core}_k(A)$ has a kernel vector with support size at least $n/c$ is at most $c\Pr[\mathcal{E}_n] + o(1)$.

We can bound $\Pr[\mathcal{E}_n]$ by conditioning on $A^{(n)}$ and leveraging the independent randomness of $A_n$. In a similar vein as before, we consider two main cases: one in which $\text{core}_k(A^{(n)})$ has a kernel vector with large support, and one in which it doesn't. The logic is similar as before.

We prove these results in Section <ref>.

§ THE SMALL DOMAIN

§.§ Definitions and Lemmas for Characterizing Minimal Dependencies

We gather here a few definitions and lemmas that we use in the small domain. We summarize notation in Table <ref>.

While it is sufficient for our main results to consider only tree dependencies (Definition <ref>), we state our results in the small domain to hold for $d \geq d_0$, for $d_0$ a universal constant. For constant values of $d$, with constant probability, $A$ and $B$ include small minimal dependencies that are not tree dependencies, defined below. We believe understanding these dependencies may be of independent interest.

$\mathcal{M}_k$        Set of minimal dependencies with $k$ columns (Definition <ref>)

$\mathcal{T}_k$        Set of tree dependencies of $k$ columns (Definition <ref>, Figure <ref>(a))

$\mathcal{T}_k^+$        Set of two-forest dependencies of $k$ columns (Definition <ref>, Figure <ref>(b))

$\mathcal{T}_k^C$        Set of tree-with-added-edge dependencies of $k$ columns (Definition <ref>, Figure <ref>(c))

$\mathcal{S}_{L, k}$        Subset of matrices  in $\mathcal{M}_k$ with exactly $L$ ones. (Definition <ref>)

$\mathcal{S}_{L, k}'$        Subset of matrices  in $\mathcal{M}_k$ with exactly $L$ ones and exactly $k$ non-zero columns. (Definition <ref>)

Notation in this work

Let $\mathcal{T}_k^+$ be the set of matrices $M\in \bigcup_m \{0,1\}^{m\times k}$ with exactly $2k - 1$ $1$'s satisfying the following:

* $M$ has $k-1$ non-zero rows: $k-2$ rows supported on two entries and one row supported on three entries.

* The submatrix of $M$ restricted to the rows of support $2$ is the edge-vertex incidence matrix of a forest $F$ with two connected components $F_1,F_2$.

* The row of support size three contains $1$'s at column indices $a,b,c$ where $a,b \in F_i$ are connected by an even-length path, and $c \in F_j$ for $\{i, j\} = \{1, 2\}$.

Define $\mathcal{T}_k^C$ as the set of matrices $M\in \bigcup_m \{0,1\}^{m\times k}$ with $2k$ $1$'s such that the non-zero columns of $M$ form the edge-vertex incidence matrix of a tree on $k$ vertices, with an added edge between two vertices in the tree of odd distance from each other. The additional edge may create a multi-edge in the this graph.

The first lemma allows us to show that the minimal dependencies we encounter with constant probability have the graph-structures depicted in Figure <ref>.

Define $\mathcal{S}_{L,k}$ to be the set of matrices $M \in \mathcal{M}_k$ which contain exactly $L$ ones.

Define $\mathcal{S}_{L, k}' \subset \mathcal{S}_{L, k}$ to be the subset of matrices in $\mathcal{S}_{L, k}$ which have exactly $k$ non-zero rows.

The following lemma relates these sets to the sets $\mathcal{T}_k, \mathcal{T}_k^+$ and $\mathcal{T}_k^C$ introduced earlier in Definitions <ref>, <ref>, and <ref>.

[Classification of Dependencies]lemmalemmaclassification
We have the following three equivalences:

* $\mathcal{S}_{2k-2, k} = \mathcal{T}_k$.

* $\mathcal{S}_{2k-1, k} = \mathcal{T}_k^+$.

* $\mathcal{S}_{2k, k}' = \mathcal{T}_k^C$.

Lemma <ref> is proved in Appendix <ref>. The main step in its proof is the following “connectivity” lemma, also proved in Appendix <ref>.

[Connectivity of Minimal Dependencies]lemmalemmaconnect
Let $M \in \mathcal{M}_k$, and let $G$ be the hypergraph on $k$ vertices with hyperedge-vertex incidence matrix $M$, where the rows of $M$ index hyperedges, and the columns index vertices. Then all vertices in $G$ are connected.

§.§ Small Case 1

Our main goal in the Small Case 1 is to prove the following general proposition, which holds for $d$ as small as $1$. The corollary that follows contains the necessary ingredients from Small Case 1 for proving Theorems <ref> and <ref>.

Let $M$ be any of the following random matrices for $d \geq 1$:

* $M = A$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = A^{[n - 1]}$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = B$, where $B \sim \mathbb{B}(n, \frac{d}{n})$

There exists a universal constant $c_{\ref{prop:small}}$ such that for any set $S \subset [n]$ of size $k\in[1,\frac{n}{8e^4d^2}]$, we have

* $\Pr[M_S \in \mathcal{M}_k \setminus \left(\mathcal{T}_k \cup \mathcal{T}_{k}^+ \cup \mathcal{T}_{k}^C \right)] =\left(e^{- d + c_{\ref{prop:small}}\log(d)}\right)^k\left(\frac{k}{n}\right)^{k+1}$.

* $\Pr[M_S \in \mathcal{T}_k^+]\leq \left(\left(e^{- d+c_{\ref{prop:small}}\log( d)}\right)\left(\frac{k}{n}\right)\right)^k$.

* $\Pr[M_S \in \mathcal{T}_k^C]\leq \left(\left(e^{- d+c_{\ref{prop:small}}\log( d)}\right)\left(\frac{k}{n}\right)\right)^k$.

* $\Pr[M_S \in \mathcal{T}_k]\leq  \left(e^{- d+c_{\ref{prop:small}}\log( d)}\right)^k\left(\frac{k}{n}\right)^{k-1}$.

Union bounding over the sets $S$ yields the following corollary when $d = \omega(1)$.

Let $A \sim \mathbb{A}(n, \frac{d}{n})$ and $B \sim \mathbb{B}(n, \frac{d}{n})$ for $d = \omega(1)$. Then each of the following hold with probability $1 - o(1)$:

* $\forall S \in [n]$ with $k = |S| \leq \frac{n}{8e^4d^2}$, $B_S \notin \mathcal{M}_k \setminus \mathcal{T}_k$.

* $\forall S \in [n]$ with $k = |S| \leq \frac{n}{8e^4d^2}$, $A_S \notin \mathcal{M}_k \setminus \mathcal{T}_k$.

* $\forall x$ with $|\supp(x)| \leq \frac{n}{8e^4d^2}$ and $n \in \supp(x)$, $A^{[n - 1]}x \neq 0$.

We introduce some notation, pictured in Figure <ref>. Fix a set $S$ of $k$ columns and consider the submatrix $M_S$ induced by these columns. If $M \in \{A, A^{[n-1]}\}$, we define the following partition of the entries of $M_S$. Let $E_{Sym}$ be the set of entries of $A_S$ whose rows are indexed by values in $S$. Let $E_{SymBD}$ be subset of entries in $E_{Sym}$ that are below the diagonal of $A$, and hence mutually independent. Let $E_{Asym}$ be the set of entries whose rows are not in $S$, and finally, let $E = E_{Asym} \cup E_{SymBD}$ be the full set of mutually independent entries that determine $M_S$. If $M = B$, we define $E_{Asym}$ to be all of the entries in $M_S$. Formally:

\begin{equation*}
\begin{split}
&E_{Sym} := \begin{cases}\{(i, j): i, j \in S \} & M \in \{A, A^{[n-1]}\} \\ \emptyset & M = B\end{cases}\\
&E_{SymBD} := \begin{cases}\{(i, j): i, j \in S, j < i \} & M \in \{A, A^{[n-1]}\} \\ \emptyset & M = B\end{cases}\\
&E_{Asym} := \begin{cases}\{(i, j): j \in S, i \notin S \} & M \in \{A, A^{[n-1]}\} \\ \{(i, j): j \in S\} & M = B\end{cases}\\
&E := E_{SymBD} \cup E_{Asym}
\end{split}
\end{equation*}

a) $A$     b)$A^{[n -1]}$ where $n \in S$     c)$A^{[n -1]}$ where $n \notin S$     d) $B$

Regions of $M$ for $M \in \{A, A^{[n -1]}, B\}$, with matrix rows permuted such that $S$ is at the top.

We will couple the process of randomly exposing the $1$'s in $M_S$ with a random walk that counts the number of times a $1$ is exposed in $E_{Asym}$ in a row that already contains a $1$ or in $E_{SymBD}$. Observe that each consecutive $1$ is exposed in a random entry in $E$, sampled without replacement.

We condition on $L_S$, the number of $1$'s in $E$. Note that $L_S \sim \Bin(|E|, d/n)$. Let $(X_{i})_{i \in L_S}$ be the random walk that increases by one if the $i$th exposed $1$ is in $E_{SymBD}$ or if the $i$th exposed $1$ is in $E_{Asym}$ and is not the first $1$ exposed in its row. Otherwise, let $X_i = X_{i - 1}$.

The following claims say when $X_{L_S}$ is small compared to the number of $1$'s in $M_S$, $M_S$ is not a minimal dependency.

If $X_{L_S} < \max\left(k + 1, \frac{L_S}{2}\right)$ and there are at least $2k + 1$ total $1$'s in $M_S$, then there is a row of $M_S$ (not in $S$) with a single $1$, so $M_S \notin \mathcal{M}_k$.

Let $P$ be the number of $1$'s in $E_{Asym}$, and let $Q$ be the number of $1$'s in $E_{SymBD}$ such that $Q + P = L_S$ and $2Q + P \geq 2k + 1$.
Let $Y:= X_{L_S} - Q$ be the number of $1$'s in $E_{Asym}$ which are not the first in their row.
Now the number of rows not in $S$ which have exactly one $1$ is at least
$$ (P - Y) - Y = P - 2X_{L_S} + 2Q \geq \max(2k + 1, L_S) - 2X_{L_S} \geq \max(2k + 1, L_S) - \max (2k, L_S - 1) \geq  1.$$

If $X_{L_S} < k + 1$, then $M_S \notin \mathcal{S}_{2k, k} \setminus \mathcal{T}_k^C$.

We prove this by contradiction. Assume $M_S \in \mathcal{S}_{2k, k} \setminus \mathcal{T}_k^C$. Let $P$ be the number of $1$'s in $E_{Asym}$, and let $Q$ be the number of $1$'s in $E_{SymBD}$ such that $Q + P = L_S$ and $2Q + P = 2k$. Observe that if $M_S \in \mathcal{S}_{2k, k} \setminus \mathcal{T}_k^C$, then it must have exactly $k - 1$ non-zero rows. Indeed, if it had less than $k - 1$ non-zero rows, then $M_S$ would have rank at most $k - 2$, which contradicts $M_S$ being a minimal dependency. Further, if $M_S$ has more than $k-1$ non-zero rows, then by the fact that $M_S$ is a minimal dependency it must have $k$ non-zero rows (as each non-zero row must have at least two $1$'s and $M_S$ only has $2k$ $1$'s). However, if it has $k$ non-zero rows and is in $\mathcal{S}_{2k,k}$, then it must be in $\mathcal{S}_{2k,k}'$. Hence, by lemma $\ref{lemma:classification}$, $M_S\in \mathcal{T}_k^C$. We proceed in two cases:

Case 1: $Q = 0$. In this case, if each row in $M_S$ has at least two $1$'s, then we must have
$$X_{L_S} = P - \text{number of occupied rows} = 2k - (k - 1) = k + 1 \geq  \max\left(k + 1, \frac{L_S}{2}\right),$$

since $L_S = P = 2k$.

Case 2: $Q > 0$. Note that in this case $M \in \{A, A^{[n - 1]}\}$. Let $Z$ be the number of occupied rows in $E_{Asym}$, such that $k - 1 - Z$ rows are occupied in $E_{SymBD}$. Observe that by the symmetry of $A$, number of occupied columns in $E_{SymBD}$ is at most $k - 1 - Z$.

Since we cannot have all-zero column (this would contradict $M_S$ being a minimal dependency), the number of columns occupied in $E_{Asym}$ that are not occupied in $E_{SymBD}$ must be at least $Z + 1$. However, by the connectivity of minimal dependencies (Lemma <ref>), the number of columns occupied in $E_{Asym}$ that are not occupied in $E_{SymBD}$ is at most $P - Z$. Note that here we also used the fact that $E_{SymBD}$ is non-empty. Thus we have $P - Z \geq Z + 1$.

Summarizing, we have

* $P - Z \geq Z + 1$

* $2k \leq P + 2Q$

* $Q + (P - Z) = X_{L_S} \leq k.$

Combining (2) and (3), we achieve

$$Q + (P - Z) \leq \frac{P + 2Q}{2} \Rightarrow \frac{P - 2Z}{2} \leq 0,$$
which contradicts $(1)$.

The proof of the next two claims are nearly identical to the proof of Claim <ref>, so we omit them.

If $X_{L_S} < \max\left(k, \frac{L_S}{2}\right)$ and there are at least $2k - 1$ $1$'s total in $M_S$, then there is a row of $M_S$ (not in $S$) with a single $1$, so $M_S \notin \mathcal{M}_k$.

If $X_{L_S} < \max\left(k - 1, \frac{L_S}{2}\right)$ and there are at least $2k - 2$ $1$'s total in $M_S$, then there is a row of $M_S$ (not in $S$) with a single $1$, so $M_S \notin \mathcal{M}_k$.

Recall from Observation <ref> that any minimal dependency $M_S$ must have at least $2k - 2$ $1$'s total. By Lemma <ref>, any minimal dependency with $2k - 1$ $1$'s must be in $\mathcal{T}_k^+$. Further, any minimal dependency with $2k$ $1$'s must either be in $\mathcal{T}_k^C$ or in $\mathcal{S}_{2k, k} \setminus \mathcal{T}_k^C$.

Thus, any minimal dependency not in $(\mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C)$ must have at least $2k + 1$ $1$'s or be in $(\mathcal{S}_{2k, k} \setminus \mathcal{T}_k^C)$. As a result, we have by Claim <ref> and Claim <ref>,

\begin{equation*}\Pr[M_S \in  \mathcal{M}_k \setminus (\mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}^C)] \leq \Pr[X_{L_S} \geq \max\left(k + 1, L_S/2\right)]\end{equation*}

Note here the fact that if $M_S \in \mathcal{S}_{2k, k}$, then $\max(k + 1, L_S/2) = k + 1$.

Further, because minimal dependencies in $(\mathcal{T}_k^+ \cup \mathcal{T}_k^C)$ have at least $2k-1$ $1$'s, by Claim <ref>,

\begin{equation*}\Pr[M_S \in  (\mathcal{T}_k^+ \cup \mathcal{T}_k^C)] \leq \Pr[X_{L_S} \geq \max\left(k, L_S/2\right)]\end{equation*}

Finally by Claim <ref>,

\begin{equation*}
\Pr[M_S \in \mathcal{T}_k] \leq \Pr[X_{L_S} \geq \max\left(k - 1, L_S/2\right)].
\end{equation*}

To bound the probability that $X_{L_S}$ is large, we couple $X_i$ with a random walk $(Y_i)_{i \in L_S}$ which increases by one with probability $\frac{k(k + L_S)}{|E|}$ and otherwise stays constant. Observe that $Y_i$ stochastically dominates $X_i$, because there are at most $k + L_S$ rows — and hence $k(k + L_S)$ locations in $E$ — in which exposing a $1$  will increase $X_i$. Then conditioned on $L_S = \ell$, for any $j$, we have

\begin{equation*}
\begin{split}
\Pr\left[X_{\ell} \geq j\right] &\leq \Pr\left[\Bin\left(\ell, \frac{k + \ell}{n - k}\right) \geq j\right].
\end{split}
\end{equation*}

We now use Lemma <ref>, proved in Appendix <ref>, to sum this probability over all values of $L_S$.

[Small Case Binomial Calculation]lemmamastersmall
For constants $\gamma, d > 0$, for $k \leq \frac{n}{8e^4\gamma d^2}$, there exists a constant $c_{\ref{masterlemma:small}}$ such that for any $j \in \{k - 1, k, k + 1\}$ and $\gamma \geq 1/2$, we have

\begin{equation*}
\sum_{\ell \geq 1}^{\infty}\Pr\left[\Bin\left(\ell, \frac{\ell + k}{\gamma n}\right) \geq \max\left(j, \frac{\ell}{2}\right)\right]\Pr[\Bin(\gamma nk, d/n) = \ell] \leq e^{-\gamma dk + c_{\ref{masterlemma:small}}k\log(\gamma d)}\left(\frac{k}{n}\right)^j.
\end{equation*}

We employ this lemma with $\gamma = \frac{|E|}{nk} \geq 1 - k/n$ and $j = \max\left(k+1, L_S/2\right)$, to achieve

\begin{equation*}\Pr[M_S \in \mathcal{M}_k \setminus (\mathcal{T} \cup \mathcal{T}_k^+ \cup \mathcal{T}^C)] \leq e^{-dk + (c_{\ref{masterlemma:small}}+1)k\log(d)}\left(\frac{k}{n}\right)^{k+1}.\end{equation*}

Further, letting $j = \max\left(k, L_S/2\right)$ gives:

\begin{equation}\label{smallcase:both}\Pr[M_S \in (\mathcal{T}_k^+ \cup \mathcal{T}_k^C)] \leq e^{-dk + (c_{\ref{masterlemma:small}}+1)k\log(d)}\left(\frac{k}{n}\right)^k.\end{equation}

Finally, setting $j = \max\left(k - 1, L_S/2\right)$, gives:

\begin{equation*}\Pr[M_S \in \mathcal{T}_k] \leq e^{-dk + (c_{\ref{masterlemma:small}}+1)k\log(d)}\left(\frac{k}{n}\right)^{k - 1}.
\end{equation*}

Putting $c_{\ref{prop:small}} = c_{\ref{masterlemma:small}} + 1$ proves the lemma. Note that eq. <ref> establishes the second and third statements of the lemma simultaneously.

§.§ Small Case 2

Our main goal of this section is to prove the following lemma.

Let $M$ be any of the following random matrices for $d_0 \leq d \leq 3\log(n)$ for some universal constant $d_0$:

* $M = A$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = A^{[n - 1]}$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = B$, where $B \sim \mathbb{B}(n, \frac{d}{n})$

\begin{equation*}
\Pr\left[\exists x: Mx = 0, \frac{n}{8e^4d^2} \leq \supp(x) < \frac{9n}{d}\right] = o(1).
\end{equation*}

We will take a union bound over all possible sets $S \subset [n]$ of size $k \in \left[\frac{n}{8e^4d^2}, \frac{9n}{d}\right]$ of the probability that $M$ has a kernel vector with support $S$. By Observation <ref>, it suffices to show that with probability $1 - o(1)$, for all such sets $S$, there is a row in the submatrix $M_S$ with exactly one $1$.

For each of the three choices of ensemble, the rows $(M_S)^{\{i\}}$ for $i \in [n] \setminus S \setminus \{n\}$ are mutually independent, so we have

\begin{equation*}
\begin{split}
p_k &:= \Pr[\exists x \in \mathbb{R}^{n}, \supp(x) = S, M x = 0] \leq \left(1 - k\frac{d}{n}\left(1 - \frac{d}{n}\right)^{k - 1}\right)^{n - k - 1}\\
&\leq \left(1 - k\frac{d}{n} e^{-2dk/n} \right)^{n - k - 1} \leq e^{- k(n-k-1)\frac{d}{n} e^{-2dk/n}} \leq e^{- \frac{kd}{2} (e^{-2dk/n})}.
\end{split}
\end{equation*}

Note that $p_k$ does not depend on the choice of $S$, just its size $k$. Taking a union bound over all $k$ and all sets $S$ of size $k$, we achieve:

\begin{align*}
\sum_{k = \frac{n}{8e^4d^2}}^{\frac{9n}{d}} \sum_{S \subset [N], |S| = k} p_k &\leq \sum_{k=\frac{n}{8e^4d^2}}^{\frac{9n}{d}} \left(\frac{en}{k}\right)^ke^{- \frac{kd}{2} (e^{-2dk/n})}
\leq \sum_{k=\frac{n}{8e^4d^2}}^{\frac{9n}{d}} e^{-\frac{dk}{2}(e^{-2dk/n}) + k\ln(en/k)} \\
&\leq n \max_{k_1,k_2,k_3 \in [\frac{n}{8e^4d^2}, \frac{9n}{d}]} \left(e^{-\frac{d}{2}(e^{-2dk_1/n}) + \ln(en/k_2)}\right)^{k_3}
= n  \left(e^{-\frac{d}{2}(e^{-18}) + \ln(8e^5 d^2)}\right)^{\frac{n}{8e^4d^2}}\\
&= o(1)
\end{align*}

for sufficiently large $d$.

§ THE LARGE DOMAIN

§.§ Statement of Lemmas

In the large domain, we bound the probability of having minimal dependencies of $k$ columns for $k \geq \frac{9n}{d}$. Large Case 1 (Section <ref>) considers the case when $\frac{9n}{d} \leq k < \frac{n}{C}$ for some constant $C$. Large Case 2 (Section <ref>) considers the case where $\frac{n}{C} \leq k \leq n$. As discussed in the technical overview, our main tool in these two cases are the Littlewood-Offord anti-concentration results.

§.§ Large Case 1

We prove the following lemma.

There exist universal constants $C$ and $d_0$, such that the following holds. Let $M$ be any of the following random matrices for $d_0 \leq d \leq 3\log(n)$:

* $M = A$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = A^{[n-1]}$, where $A \sim \mathbb{A}(n, \frac{d}{n})$

* $M = B$, where $B \sim \mathbb{B}(n, \frac{d}{n})$

\begin{equation*}
\Pr\left[\exists x: Mx = 0, \frac{9n}{d} \leq \supp(x) < \frac{n}{C}\right] = o(1).
\end{equation*}

We union bound over all $k \in [9n/d, n/C]$ and all sets $S$ of size $k$ of the probability that there exists $x \in \mathbb{R}^n$ with $\supp(x) = S$ and $M x = 0$.

Fix a set $S$ of size $k$. We will consider the random process where we expose the $n - k - 1$ rows $M_S^{\{j\}}$ for $j \in [n - 1] \setminus S$ one at a time. Note that these rows are all mutually independent since they do not include rows indexed by $S$. Further, they do not include $n$th row (which does not exist in the case that $M = A^{[n-1]}$). For $i \leq n - k - 1$, let $\mathcal{N}_i \subset \mathbb{R}^k$ be the kernel of the first $i$ rows exposed, and let $\mathcal{D}_i \subseteq \mathcal{N}_i$ be the span of the set of vectors in $\mathcal{N}_i$ which have no zeros. Let $R_i$ be the dimension of $\mathcal{D}_i$.

If $R_i > 0$, then we can choose an arbitrary vector $v$ in $\mathcal{D}_i$ with support $k$, and by Lemma <ref>, with probability at least $1 - \frac{1}{\sqrt{kd/n}}$, the $(i + 1)$th row exposed is not orthogonal to $v$. In this case $R_{i + 1} = R_i - 1$.

If at any point $R_i$ becomes $0$, then this means there can be no dependency involving all the columns of $M_S$. It follows that since $R_0 = k$, we have

\begin{equation}\label{eq:unionboundthis}
\Pr[R_{n - k - 1} \neq 0] \leq \Pr\left[\Bin\left(n - k - 1, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right].
\end{equation}

We employ the following computational lemma, proved in Appendix <ref>:

[Large Case 1 Binomial Calculation]lemmalargegeneral
There exists constants $C$, $d_0$, and $c_{\ref{large_general}}$, such that for all $d \geq d_0$, we have

\begin{equation*}
\sum_{k = \frac{2n}{d}}^{n/C}\binom{n}{k}\Pr\left[\Bin\left(n - k - 1, 1 - \frac{1}{\sqrt{kd/n}}\right) \leq k\right] \leq e^{-c_{\ref{large_general}}n}
\end{equation*}

Consequently, we can union bound eq. <ref> over all $k$ in the desired range and all $\binom{n}{k}$ sets $S$ of size $k$:

\begin{equation*}
\Pr[\exists x: M^\top x = 0, 9n/d \leq \supp(x) \leq n/C] \leq e^{-c_{\ref{large_general}}n}.
\end{equation*}

This concludes the proof of Lemma <ref>.

§.§ Large Case 2

As outlined in the technical overview, the proof strategy for Large Case 2 for the symmetric matrix $A \sim \mathbb{A}(n, p)$ varies significantly from that of the asymmetric matrix $B \sim \mathbb{B}(n, p)$. Since the proof for $B$ is simpler, we begin with that matrix.

§.§.§ Large Case 2 for $B$

For the asymmetric matrix $B$, it is not possible to rule out both left and right kernel vectors of $B$ with large support. Indeed, often such dense kernel vectors do exist. We can, however, rule out having dense right and left kernel vectors simultaneously. We do so in the following lemma.

Let $B \sim \mathbb{B}(n, \frac{d}{n})$. Let $\mathcal{S}_t$ be the set of vectors in $\mathbb{R}^n$ with support size at least $t$. For $t \geq \frac{n}{C}$, where $C$ is the constant from Lemma <ref>, for $d_0 \leq d \leq 3\log(n)$ for some constant $d_0$,

\begin{equation*}
\Pr\left[\exists x, y \in \mathcal{S}_t: Bx = 0 \text{ and } y^\top B = 0 \right] \leq \left(\frac{n}{t}\right)^{3/2}\frac{1}{\sqrt{d}}.
\end{equation*}

For $i \in [n]$, let $H_i$ be the space spanned by the column vectors $B_1, B_2, \cdots B_{i - 1}, B_{i + 1}, \cdots B_n$. Following Observation <ref> from the technical overview, $Bx = 0$ and $y^\top B = 0$ imply that for all $i \in \text{supp}(x)$,

* $B_i \in H_i$;

* $\exists w \in \mathcal{S}_t: w^\top B_j = 0 \:\: \forall j \in [n] \setminus i$.

Let $\mathcal{F}_i$ denote the event that these two events occur for index $i$. Let $X_i$ be the indicator of this event, and let $X = \sum_i X_i$. It follows that

\begin{equation*}
\Pr\left[\exists x, y \in \mathcal{S}_t: Bx = 0 \text{ and } y^\top B = 0 \right] \leq \Pr[X \geq t].
\end{equation*}

By Markov's inequality,

\begin{equation}\label{markov_as}
\Pr\left[X \geq t\right] \leq \frac{\mathbb{E}[X]}{t} = \frac{n\Pr[\mathcal{F}_n]}{t}.
\end{equation}

Now by conditioning on $H_i$ and using the sparse Littlewood-Offord Lemma (Lemma <ref>), we have
\begin{equation*}
\begin{split}
\Pr[\mathcal{F}_n] &= \Pr\left[\exists w \in \mathcal{S}_t: w^\top B_j = 0 \:\: \forall j \in [n - 1] \right]\Pr\left[B_n \in H_n  | \exists w \in \mathcal{S}_t: w^\top B_j = 0 \:\: \forall j \in [n - 1] \right]\\
&\leq \Pr\left[\exists w \in \mathcal{S}_t: w^\top B_j = 0 \:\: \forall j \in [n - 1] \right]\left(\max_{w \in \mathcal{S}_t}\Pr[B_n^\top w = 0]\right)\\
&\leq \max_{x \in \mathcal{S}_t}\Pr[B_n^\top w = 0]
\leq \frac{1}{\sqrt{td/n}}.
\end{split}
\end{equation*}

Here  the first inequality follows from the fact that $B_n \in H_n$ implies that $B_n$ is orthogonal to any normal of $H_n$. We are able to remove the conditioning in this step because $B_n$ is independent from $H_n$ (and hence also the normal $w$). The final inequality follows from Lemma <ref>, where we used the fact that $t \geq \frac{n}{C} \geq \frac{9n}{d}$ for $d$ large enough.

Plugging $\Pr[\mathcal{F}_n]$ in to eq. <ref>, we have $\Pr[X \geq t] \leq \left(\frac{n}{t}\right)^{3/2}\frac{1}{\sqrt{d}},$
which proves the lemma.

§.§.§ Large Case 2 for $A$

For the symmetric matrix $A \sim \mathbb{A}(n, p)$, Large Case 2 reduces the probability of having a kernel vector with large support to the probability of having several smaller structures in $A$. The following is our main technical lemma for $A$:

Let $A \sim \mathbb{A}(n, d/n)$. Let $A^{(i)}$ denote the submatrix of $A$ obtained by removing the $i$th row and column. Let $\textbf{a} \in \mathbb{R}^{n - 1}$ be a random vector with i.i.d. $\Ber(d/n)$ entries. For any $u , r, s, t \in [n]$ with $r < s$,

\begin{equation}\label{eq:lem}
\begin{split}
\Pr\left[\exists x: Ax = 0, \supp(x) > t\right] &\leq
\frac{n}{t}\max_{x \in \mathbb{R}^{n - 1}: \supp(x) \geq s}\Pr\left[x^\top \textbf{a} = 0\right]\\
&\quad +\frac{n}{t}\Pr\left[\exists x: A^{(n)}x = 0, r < |\supp(x)| < s \right]\\
&\quad + \frac{n}{t} \frac{dr}{n}\\
&\quad+ \frac{n}{t}\frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}x = e_1, |\supp(x)| < s\right]\\
&\quad+ \frac{n}{t}\max_{X \in \mathcal{T}^{n - 1}_{n - 1 - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a} = 0\right],
\end{split}
\end{equation}

where $\mathcal{T}^{m}_{\alpha, \beta}$ denotes the set of matrices in $\mathbb{R}^{m \times m}$ with some set of $\alpha$ columns that each have support size at least $\beta$.

Lemma <ref> breaks down the probability that there is a large linear dependency consisting of more than $t$ rows into the sum of the probabilities of several other events. Two of these probabilities (lines 1 and 5 of the right hand side of eq. <ref> in the lemma) we can show to be small via anti-concentration lemmas. Two of the probabilities (lines 2 and 4 of the right hand side of eq. <ref> in the lemma), we will eventually show to be small using the lemmas from Small Case 1, 2, and Large Case 1.

Instantiating Lemma <ref> with $t = \frac{n}{C}$, $s = \frac{n}{C}$, $r = \frac{n}{8e^4d^2}$, $u = \frac{n}{2}$, where $C$ is the constant from Lemma <ref>, we obtain the following lemma.

Let $A \sim \mathbb{A}(n, \frac{d}{n})$ for $ \omega(1) = d \leq 3\log(n)$.
With $C$ equal to the constant from Lemma <ref>,

\begin{equation*}
\begin{split}
\Pr[\exists x: Ax = 0, \supp(x) > n/C] &\leq C\Pr[\exists x: A^{(n)}x = 0, \frac{n}{8e^4d^2} \leq |\supp(x)| \leq n/C] \\
&\qquad + 2C\Pr[\exists x: A^{(n)}x = e_1, |\supp(x)| \leq n/C] + o(1).
\end{split}
\end{equation*}

This follows immediately from plugging in these values of $t, s, r$ and $u$ into Lemma <ref> and applying the anti-concentration results in Lemmas <ref> and <ref> to the first and last terms in eq. <ref>.
Indeed, Lemma <ref> shows that
\begin{equation*}
\frac{n}{t}\max_{x \in \mathbb{R}^{n - 1}: \supp(x) \geq s}\Pr\left[x^\top \textbf{a} = 0\right] \leq \frac{n}{t}\frac{1}{\sqrt{sd/n}} = o(1),
\end{equation*}

where we have used the fact that $sd/n = d/C \geq 9$ since $d = \omega(1)$.
Lemma <ref> shows that

\begin{equation*}
\frac{n}{t}\max_{X \in \mathcal{T}^{n - 1}_{n - 1 - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a}  = 0\right] \leq O\left(\frac{1}{\sqrt[4]{\min(s, n - 1 - r - u)d/n}}\right) = o(1).
\end{equation*}
The third term in eq. <ref> equals $\frac{C}{8e^4d}$ which is also $o(1)$.

To prove Lemma <ref>, we will use the following two linear-algebraic lemmas, proved in Appendix <ref>.
Let $A$ be a matrix with columns $A_i$ for $i \in [n]$. Let $H_i$ be the space spanned by the column vectors $A_1, A_2, \cdots A_{i - 1}, A_{i + 1}, \cdots A_n$. Let $S$ be the set of all $i$ such that $A_i \in H_i$. Then there exists some $y$ with $\text{supp}(y) = S$ such that $Ay = 0$.

With the terminology of the previous lemma, $e_i \in \Span(A^\top )$, if and only if $A_i \notin H_i$.

For each $i \in [n]$, we define $H_i$ to be the space spanned by the column vectors $A_1, A_2, \cdots A_{i - 1}, A_{i + 1}, \cdots A_n$.

Then, as per Observation <ref>, $Ax = 0$ for some $x$ implies that for all $i \in \text{supp}(x)$, $A_i \in H_i$. Let $\mathcal{E}_i$ denote the event that $A_i \in H_i$. Let $X_i$ be the indicator of this event, and let $X = \sum_i X_i$. By Markov's inequality and the exchangeability of the columns,

\begin{equation}\label{markov}
\Pr\left[\exists x : Ax = 0, |\supp(x)| \geq t \right] = \Pr\left[X \geq t\right] \leq \frac{\mathbb{E}[X]}{t} = \frac{n\Pr[\mathcal{E}_n]}{t}.
\end{equation}

We will break down the probability $\Pr[\mathcal{E}_n]$ into several cases, depending on the size of the support of vectors in the kernel of $A^{(n)}$. Let $S \subseteq [n - 1]$ be the set of all $i$ such that $e_i \in \Span(A^{(n)})$, such that by Lemma <ref> and  Lemma <ref>,

\begin{equation*}
k:= \max(\supp(x): A^{(n)}x = 0) = n - 1 - |S|.
\end{equation*}

Case 1: $A^{(n)}$ has a kernel vector $x$ with large support, that is, $k \geq s$.

Case 2: $A^{(n)}$ has a kernel vector $x$ with medium support, that is $r < k < s$.

Case 3: $A^{(n)}$ does not have any kernel vectors with large or medium support vectors in its kernel, that is, $k \leq r$.

We can expand

\begin{equation}\label{cases}
\Pr[\mathcal{E}_n] = \Pr[\mathcal{E}_n| k \geq s]\Pr[k \geq s] + \Pr[\mathcal{E}_n|r < k < s]\Pr[r < k < s] + \Pr[\mathcal{E}_n| k \leq r]\Pr[k \leq r].
\end{equation}

For simplicity, define $\textbf{a} := A_n^{/n}$ to be the first $n - 1$ entries of the column $A_n$.

To evaluate the probability of the first case, we condition on $A^{(n)}$ and let $x$ be any vector of support at least $s$ in the kernel of $A^{(n)}$. Observe that $\mathcal{E}_n$ cannot hold if $x^\top\textbf{a}$ is non-zero. Indeed, if $x^\top \textbf{a} \neq 0$, then let $x' = (x_1, x_2,\ldots,x_{n-1},0)/(x^\top\textbf{a})$ such that $Ax' = e_n$. Then by Lemma <ref>, $A_n \notin H_n$ and hence $\mathcal{E}_n$ does not occur. Since $\textbf{a}$ is independent from $x$, we have

\begin{equation}\label{case_1}
\Pr[\mathcal{E}_n| k \geq s]\Pr[k \geq s] \leq \max_{x: \supp(x) \geq s}\Pr[x^\top\textbf{a} = 0].
\end{equation}

Combined with eq. <ref>, the contribution from this case yields the first term in the right hand side of eq. <ref>.

For the second case, we bound:

\begin{equation}\label{case_2}
\Pr[\mathcal{E}_n|r < k <  s]\Pr[r < k < s] \leq \Pr[r < k < s] \leq \Pr\left[\exists x: A^{(n)}x = 0, r < |\supp(x)| < s \right].
\end{equation}

Combined with eq. <ref>, the contribution from this case yields the second term in the right hand side of eq. <ref>.

The third case will lead to the final three terms in the right hand side of eq. <ref>. In this case, we will show conditions under which we can algebraically construct a vector $v$ such that $Av = e_n$. This will imply by Lemma <ref> that $A_n \notin H_n$.

Recall that $S \subseteq [n - 1]$ is the set of all $i$ such that $e_i \in \Span(A^{(n)})$. For $i \in S$, let $w_i $ be any vector such that $A^{(n)}{w_i } = e_i$. We next construct a sort of “pseudoinverse" matrix $B \in \mathbb{R}^{n - 1 \times n - 1}$ as follows: For $i \in S$, define $B_{ij}$ to be the $i$th entry of $w_i $. That is, for $i \in S$, the $i$th column of $B$ is $w_i $. Define all other entries of $B$ to be zero.

The following claim shows a condition for $\mathcal{E}_n$ not holding.

If $\supp(\textbf{a}) \subseteq S$ and $\textbf{a}^\top B\textbf{a} \neq 0$, then $e_n \in \Span(A)$.

Let ${w'} := B\textbf{a} = \sum_{i \in S}{\textbf{a}_iw_i }$ such that $A^{(n)}{w'} = \sum_{i \in S}{\textbf{a}_ie_i}$. Hence if $\supp(\textbf{a}) \subseteq S$, $A^{(n)}{w'} = \textbf{a}$. Define $w \in \mathbb{R}^n$ to be the vector with $w'$ in the first $n - 1$ entries and $-1$ in the final entry. Then the first $n - 1$ entries of $Aw$ are $0$, and the last entry is ${\bf{a}}^\top  w' = {\bf{a}}^\top  B \bf{a}$. Evidently, if ${\bf{a}}^\top  B {\bf{a}} \neq 0$, then
$$\frac{Aw}{{\bf{a}}^\top  B {\bf{a}}} = e_n,$$
so $e_n \in \Span(A)$.

By definition, in the third case, we have $|S| \geq n - 1 - r$. Hence by Claim <ref>,

\begin{equation}\label{case_3}
\begin{split}
\Pr[\mathcal{E}_n \land k \leq r]
&\leq \Pr\left[\supp(\textbf{a}) \not\subseteq S \land |S| \geq n - 1 - r\right] + \Pr[\textbf{a}^\top B\textbf{a} = 0 \land |S| \geq n - 1 - r].
\end{split}
\end{equation}

Notice that $S$ is a function of $A^{(n)}$ and so $\textbf{a}$ is independent from $S$. It is easy to check that for any set $S$ of size at least $n - 1 - r$,

\begin{equation}\label{case_3_a_S}
\Pr\left[\supp(\textbf{a}) \not\subseteq S\right] \leq 1 - \left(1 - \frac{d}{n}\right)^r \leq \frac{dr}{n}.
\end{equation}

We will break up the second term in eq. <ref> by conditioning on whether the support of $B$ has many entries or not, and using the independence of $\textbf{a}$ from $B$:

\begin{equation}\label{eq:T_term}
\Pr[\textbf{a}^\top B\textbf{a} = 0] \leq \Pr\left[B \notin \mathcal{T}^{n - 1}_{n - 1 - r - u, s}  \wedge |S| \geq n - 1 - r\right] + \max_{X \in \mathcal{T}^{n - 1}_{n - 1 - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a} = 0\right]
\end{equation}

To further bound the first probability on the right hand side, observe that if $|S| \geq n - 1 - r$ and $B \notin \mathcal{T}^{n - 1}_{n - 1 - r - u, s}$, there must exist at least $u$ different values $i \in S$ such that $\supp(w_i ) \leq s$. So

\begin{equation*}
\begin{split}
\Pr\left[B \notin \mathcal{T}^{n - 1}_{n - 1 - r - u, s}  \wedge |S| \geq n - 1 - r\right] &\leq \Pr\left[|\{i: \exists x \neq 0: A^{(n)}x = e_i, |\supp(x)| < s\}| \geq u \right] \\ &\leq \frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}x = e_1, |\supp(x)| < s\right],
\end{split}
\end{equation*}

where the last inequality follows by Markov's inequality. Combining this with eqs. <ref>, <ref>, and <ref> yields

\begin{equation*}
\Pr[\mathcal{E}_n \land k \leq r] \leq \frac{dr}{n} + \max_{X \in \mathcal{T}^{n - 1}_{n - 1 - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a} = 0\right] + \frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}x = e_1, |\supp(x)| < s\right].
\end{equation*}

Plugging this and eqs. <ref> and <ref> into eq. <ref> and finally eq. <ref> yields the lemma.

§ PROOF OF CHARACTERIZATION OF LINEAR DEPENDENCIES: THEOREM <REF> AND THEOREM <REF>

We are now ready to put the results of the small and large domains together to prove Theorem <ref> and Theorem <ref>.

§.§ Proof of Theorem <ref>

For the convenience of the reader, we restate this theorem:

We will need the following two lemmas to show that the first two terms in the right hand size of Lemma <ref> are $o(1)$.

Let $A \sim \mathbb{A}(n, \frac{d}{n})$ with $ \omega(1) = d \leq 3\log(n)$ and let $C$ be as in Lemma <ref>. Then

\begin{equation*}
\Pr\left[\exists x: Ax = 0, \frac{n}{8e^4d^2} < |\supp(x)| < \frac{n}{C} \right] = o(1),
\end{equation*}

\begin{equation*}
\Pr\left[\exists x: A^{[n - 1]}x = 0, \frac{n}{8e^4d^2} < |\supp(x)| < \frac{n}{C} \right] = o(1).
\end{equation*}

This is immediate from lemma from Small Case 2, Lemmas <ref>, and from Large Case 1, Lemma <ref>.

Let $A \sim \mathbb{A}(n, \frac{d}{n})$ with $ \omega(1) = d \leq 3\log(n)$ and let $C$ be as in Lemma <ref>. Then

\begin{equation*}
\Pr\left[\exists x: Ax = e_n, |\supp(x)| < \frac{n}{C} \right] = o(1).
\end{equation*}

We reduce Lemma <ref> to Lemma <ref>, which we are better suited to prove with our lemmas from Small Case 1, 2, and Large Case 1.

Let $A \sim \mathbb{A}(n, \frac{d}{n})$ with $ \omega(1) = d \leq 3\log(n)$ and let $C$ be as in Lemma <ref>. Let $K = \{x: Ax = 0, |\supp(x)| \leq \frac{n}{C}\}$. Then

\begin{equation*}
\Pr\left[\left|\bigcup_{x \in K}{\supp(x)}\right| \geq \frac{n}{8e^4d^2} \right] = o(1).
\end{equation*}

Similarly, suppose $A' = A^{[n-1]}$ is $A$ with the last row removed. Let $K' = \{x: A'x = 0, |\supp(x)| \leq \frac{n}{C}\}$. Then

\begin{equation*}
\Pr\left[n \in \bigcup_{x \in K'}{\supp(x)} \right] = o(1).
\end{equation*}

We first prove Lemma <ref> from Lemma <ref>:

First we consider vectors $x$ with $n \notin \supp(x)$.
Applying the first part of Lemma <ref> to $A^{(n)}$, with probability $1 - o(1)$, there exists some set $T \subseteq [n] \setminus \{n\}$ with $|T| \leq \frac{n}{8e^4d^2}$ such that $\supp(x) \subseteq T$ for all $x$ satisfying that $A^{(n)}x = 0$
and $\supp(x) \leq \frac{n}{C}$. With probability $1 - o(1)$, $\supp(A_n) \cap T = \emptyset$, so for all vectors $x$ with support in $[n - 1]$ and of size less than $\frac{n}{C}$, we do not have $Ax = e_n$.

Next we consider vectors $x$ with $n \in \supp(x)$. If such an $x$ exists, that is, $Ax = e_n$ and $n \in \supp(x)$, then it must be the case that $A'x = 0$. By the second part of Lemma <ref>, the probability that such an $x$ exists is $o(1)$.

Let $\mathcal{L}_2$ be the event that
$$\exists x: Ax = 0, \frac{n}{8e^4d^2} < |\supp(x)| < \frac{n}{C}.$$
Recall that by Lemma <ref>, this event occurs with probability $o(1)$.
To prove the first part, we will show that conditioned on $\mathcal{L}_2$ not occurring, we have $\left|\bigcup_{x \in K}{\supp(x)}\right| < \frac{n}{8e^4d^2}$.

Index the set $K$ as follows: $K = \{x^{(1)}, \cdots, x^{(|K|)}\}$. For $i = 1$ to $|K|$, let $y^{(i)} = \sum_{j = 1}^i{c_i x^{(i)}}$, where $c_i$ is chosen uniformly from the interval $[0, 1]$. It follows that with probability $1$, for all $i \leq |K|$,
$$\supp(y^{(i)}) = \bigcup_{j \leq i}{\supp(x^{(i)})}.$$

If $\mathcal{L}_2$ does not occur, then $|\supp(x^{(i)})| \leq \frac{n}{8e^4d^2}$ for all $i$, so we have that $|\supp(y^{(i + 1)})| \leq |\supp(y^{(i)})| + \frac{n}{8e^4d^2}$. It follows that if $|\supp(y^{(|K|)})| \geq \frac{n}{8e^4d^2}$, then there exists some $i \leq |K|$ such that $|\supp(y^{(i)})| \in [\frac{n}{8e^4d^2}, \frac{2n}{8e^4d^2}]$. However, this would imply that $\mathcal{L}_2$ holds, which is a contradiction.

For the second part, by Lemma <ref>, with probability $1 - o(1)$, $A'$ has no kernel vectors with support size $k \in [\frac{n}{8e^4d^2}, \frac{n}{C}]$. Further, the third implication of Corollary <ref> tells us that with probability $1 - o(1)$, $A'$ has no kernel vector with $n$ in the support and support size at most $\frac{n}{8e^4d^2}$.

We are now ready to prove Theorem <ref>.

First observe that if $\frac{3\log(n)}{n} \leq p \leq 1/2$, then the theorem is trivially true since $A$ is non-singular with probability $1 - o(1)$. Combining Lemma <ref> with the Lemmas <ref> and <ref> presented above, with probability $1 - o(1)$, for any $k \geq \frac{n}{8e^4d^2}$, there are no minimal dependencies of $k$ columns of $A$. Further applying Corollary <ref>, for $k \leq \frac{n}{8e^4d^2}$ we see that with probability $1 - o(1)$, all minimal dependencies of $k$ columns of $A$ must be in $\mathcal{T}_k$.

§.§ Proof of Theorem <ref>

For the convenience of the reader, we restate this theorem:

First observe that if $\frac{3\log(n)}{n} \leq p \leq 1/2$, then the theorem is trivially true since $A$ is non-singular with probability $1 - o(1)$. Assuming $p \leq \frac{3\log(n)}{n}$, this theorem follows directly from combining Corollary <ref>, Lemma <ref>, Lemma <ref>, and Lemma <ref>. We apply Corollary <ref>, Lemma <ref>, and Lemma <ref> to both $B$ and $B^\top $ to show that with probability $1 - o(1)$, neither $B$ nor $B^\top $ has minimal dependencies of $k$ columns outside of $\mathcal{T}_k$  for $k \leq \frac{n}{C}$, where $C$ is the constant from Lemma <ref>. Finally, Lemma <ref> shows that either $B$ or $B^\top $ has no minimal linear dependencies of more than $n/C$ columns.

§ PROOF OF THEOREM <REF> AND THEOREM <REF> ON THE RANK OF A AND B

We will need the following three simple linear algebraic lemmas.

Let $A \in \mathbb{R}^{n \times m}$, and let $A' \in \mathbb{R}^{n - 1 \times m - 1}$ be the matrix obtained be removing from $A$ a column with a single $1$ in it, and the row which indexed the location of the $1$. Then $\on{corank}(A) = \on{corank}(A').$ Furthermore, the union of the supports of vectors in the kernel of $A'$ is a subset of the union of the supports of vectors in the kernel of $A$.

Without loss of generality, assume the last column and first row were removed. Let $K'$ be the kernel of $A'$ and $K$ be the kernel of $A$. Define $\phi: \mathbb{R}^{m - 1} \rightarrow \mathbb{R}^m$, by
$\phi(x') = (x', -y)$, where $y = \sum_{i = 1}^{m - 1}A_{1, i}x'_i$. It suffices to show that $\phi$ is a one-to-one and onto mapping from $K'$ to $K$. The one-to-one is by definition. $\phi$ maps from $K'$ to $K$ since $(A\phi(x'))_j = (A'x')_j$ for $j \neq 1$, and $(A\phi(x'))_1 = \sum_{i = 1}^{m - 1}A_{1, i}x'_i-y = 0$. The mapping is onto since for any $x \in K$, writing $x = (-y, x')$, we must have $A'x' = 0$ and $y = \sum_{i = 1}^{m - 1}A_{1, i}x'_i$, because the first row of $A$ is orthogonal to $x$.

Let $A \in \mathbb{R}^{n \times n}$ be a the adjacency matrix of a graph $G$. Let $A' \in \mathbb{R}^{n - 2 \times n - 2}$ be the adjacency matrix of the graph $G'$ obtained from $G$ by removing any vertex of degree one and its unique neighbor. Then $\on{corank}(A) = \on{corank}(A').$ Furthermore the set of vertices in the support of the kernel of $A'$ is contained in set of vertices in the support of the kernel of $A$.

We apply Lemma <ref> twice. First we remove the column corresponding to the vertex and the row corresponding to its neighbor. This does not change the corank. Then we remove the row corresponding to the vertex and the column corresponding to its neighbor. This does not change the corank, since the matrix is square, so the corank of the row space is the same as the corank of the column space.

To see the last statement, assume without loss of generality the leaf vertex was $n$ and its unique neighbor was $n - 1$. Then if $A'x' = 0$, we have $Ax = 0$, where $x = (x', 0, -y)$, where $y = \langle(A_{n - 1})_{[n-2]}, x'\rangle = \sum_{i = 1}^{n - 2}A_{2, i}x'_i$. Clearly the support of $x'$ is contained in the support of $x$.

For $A \in \mathbb{R}^{m \times n}$, if $Ax = 0$, then for any $i \in \on{supp}(x)$, there exists some set $S$ with $i \in S$ such that $A_S \in \mathcal{M}_{|S|}$.

It suffices to show that if $A_{\supp(x)}$ is not a minimal dependency, then it is possible to find some subset $T \subsetneq \supp(x)$ such that $i \in T$, and there exists some $z$ with $\supp(z) = T$ such that $Az = 0$. By repeating this process, we will eventually find some set $S$ such that $A_S$ is a minimal dependency.

If $A_{\supp(x)}$ is not a minimal dependency, then by definition, there exists some $y$ with $\supp(y) \subseteq \supp(x)$ such that $x^\top y = 0$ and $Ay = 0$. There must exist some index $j \neq i$ such that $\frac{y_j}{x_j} \neq \frac{y_i}{x_i}$, otherwise, we would not have $x^\top y = 0$. Let $z = x - \frac{x_j}{y_j}y$. Notice that $Az = 0$ and $j \notin \supp(z)$, so $\supp(z) \subsetneq \supp(x)$ and $i \in \supp(z)$.

We are now ready to prove Theorem <ref> using Theorem <ref>. We restate Theorem <ref> for the readers convenience. Recall that for a graph $G$, we use $G_{\on{KS}}$ to denote the Karp-Sipser core of $G$.

Let $G$ be the graph with adjacency matrix $A$, and let $A'$ be the adjacency matrix of the graph $G'$ that remains after iteratively peeling off vertices of degree one from $G$ and their unique neighbors. Let $P_{\on{KS}} \subseteq [n]$ be the set of rows peeled during this process. By repeatedly applying Lemma <ref>, we have
$$\on{corank}(A) = \on{corank}(A').$$

Let $I_{\on{KS}} \subseteq [n]$ be the set isolated vertices that remain. Let $G_{\on{KS}}$ be the graph that remains after removing those vertices, and $A_{\on{KS}} := A(G_{\on{KS}})$ be the associated adjacency matrix. Then
$$\on{corank}(A_{\on{KS}}) = \on{corank}(A') - |I_{\on{KS}}|  =  \on{corank}(A) - |I_{\on{KS}}|.$$

It remains to show that on the event that the conclusion of Theorem <ref> holds, which occurs with probability $1 - o(1)$, we have $\on{corank}(A_{\on{KS}}) = 0$. Let $D$ be the set of columns involved in linear dependencies of $A$:

$$D := \bigcup_{x: Ax = 0}{\on{supp}(x)} = \{ i \in [n]: \exists S \ni i: A_S \in \mathcal{M}_{|S|}\}.$$

The equivalence holds because by Lemma <ref>, any column involved in a linear dependency must also be involved in a minimal linear dependency.

Conditional on the event in Theorem <ref> holding,

$$D \subseteq P_{\on{KS}} \cup I_{\on{KS}}.$$

Conditional on the event, we have

$$D = \{ i \in [n]: \exists S \ni i: A_S \in \mathcal{T}_{|S|}\}.$$

Consider any set $S$ for which $A_S \in \mathcal{T}_{|S|}$. By the definition of $\mathcal{T}_{|S|}$, $A_S$ is the edge-vertex incidence matrix of a tree. Hence the leaf-removal process and isolated vertex removal step will necessarily remove all the columns in $S$. This shows that $D \subseteq P_{\on{KS}} \cup I_{\on{KS}}$.

Suppose for the sake of contradiction $A_{\on{KS}}$ was singular, and had some non-zero kernel vector $x$. Then by iteratively applying the second implication of Lemma <ref>, we see that the vertices in the support of the kernel of $A$, namely $D$, must contain the vertices supporting $x$. This implies that $D$ contains a vertex in the Karp-Sipser core of $A$, which contradicts the previous claim. It follows that with probability $1 - o(1)$, $A_{\on{KS}}$ is non-singular.

The proof of Theorem <ref> is nearly identical.

Let $H'$ be the bipartite graph that remains after iteratively peeling off vertices of degree one from $H$ and their unique neighbors, and let $B'$ be the associated bi-adjacency matrix (where we have retained the same left-right partition as $H$). Let $P_{\on{KS}}$ be the set of vertices peeled during this process. By repeatedly applying Lemma <ref>, we have
$$\on{corank}(B) = \on{corank}(B').$$

Let $I_{\on{KS}} \subseteq [n]$ be the set isolated vertices in $H'$. Let $H_{\on{KS}}$ be the graph that remains after removing those vertices, and $B_{\on{KS}} := B(H_{\on{KS}})$ be the associated bi-adjacency matrix. Then

\begin{equation}\label{eq:left_corank}
\on{corank}(B_{\on{KS}}) = \on{corank}(B') - |I_{\on{KS}} \cap L|  =  \on{corank}(B) - |I_{\on{KS}} \cap L|,
\end{equation}

\begin{equation}\label{eq:right_corank}
\on{corank}(B_{\on{KS}}^\top) = \on{corank}(B'^\top) - |I_{\on{KS}} \cap R|  =  \on{corank}(B^\top) - |I_{\on{KS}} \cap R|.
\end{equation}

It remains to show that on the event that the first conclusion of Theorem <ref> holds, we have $\on{corank}(B_{\on{KS}}) = 0$ or $\on{corank}(B_{\on{KS}}^\top) = 0$. We condition on the event that the conclusion of Theorem <ref> holds, which occurs with probability $1 - o(1)$. Without loss of generality, assume the first event holds, which implies that for all $S$ such that $B_S \in \mathcal{M}_{|S|},$ we have $B_S \in \mathcal{T}_{|S|}.$

Let $D$ be the set of columns involved in linear dependencies of $B$:

$$D := \bigcup_{x: Bx = 0}{\on{supp}(x)} = \{ i \in [n]: \exists S \ni i: B_S \in \mathcal{M}_{|S|}\}.$$
The following claim is proved in the same way as Claim <ref>, so we omit its proof.
Conditional on the first event in Theorem <ref> holding,

$$D \subseteq (P_{\on{KS}} \cup I_{\on{KS}}) \cap R.$$

Suppose for the sake of contradiction $B_{\on{KS}}$ did not have full column-rank, and had some non-zero kernel vector $x$ such that $ B_{\on{KS}}x = 0$. Then by iteratively applying the second implication of Lemma <ref>, we see that the right vertices in the support of the kernel of $B$, namely $D$, must contain the vertices supporting $x$. This implies that $D$ contains a vertex in the right side of the Karp-Sipser core of $A$, which contradicts the previous claim. It follows that $\on{corank}(B_{\on{KS}}) = 0$.

To prove the final statement of Theorem <ref>, observe that from eq. <ref> we have

$$\on{corank}(B) = |I_{\on{KS}} \cap L|.$$
Further, since $\on{corank}(B_{\on{KS}}^\top) \geq \on{corank}(B_{\on{KS}}) = 0$ and $\on{corank}(B) = \on{corank}(B^\top)$, it follows from eqs. <ref> and <ref> that $|I_{\on{KS}} \cap L| \geq |I_{\on{KS}} \cap R|$.

§ PROOF OF THEOREM <REF>

In the following section, we prove our result showing that if $p = \omega(1/n)$, then with high probability, the $k$-core of of $G \sim \mathbb{G}(n, p)$ is full rank. Throughout this section, we let $d := pn$.

As outlined in Section <ref>, the proof of the Theorem <ref> is divided in two main domains corresponding to the size the minimal dependencies we consider.

§.§ Small Domain

§.§.§ Small Case 1

We prove the following lemma, which rules out minimal linear dependencies of $k$ columns of $\on{core}_k(A)$ for $k < \frac{n}{d^7}$. Our approach is similar to the prior Small Case 1.

Let  $A \sim \mathbb{A}(n, \frac{d}{n})$, where $d_0 \leq d \leq 3\log(n)$ for some universal constant $d_0$. For a set $S$ of columns and subset $R$ of rows, let $\mathcal{E}_{S, R}$ be the event that:

* $S \subset R$;

* $1 \leq |S| \leq \frac{n}{d^7}$;

* $|\supp(A^R_S)| \geq 3|S|$;

* $A^R_S$ contains no more than one row with a single $1$.

\[\Pr\left[\exists S, R: \mathcal{E}_{S, R} ~\on{occurs}\right] = O\left(\frac{1}{\sqrt[3]{n}}\right).\]

A slightly weaker version of this lemma would require that $A_S^R$ contains no rows with a single $1$. By taking $R$ to be the set of vertices in the $k$-core, this weaker version would suffice to rule out with high probability any minimal dependencies in $\on{core}_k(A)$ with $t$ columns for $t \leq \frac{n}{d^7}$. We state this lemma to be stronger because we will also want to rule out small minimal dependencies in $\on{core}_k(A)^{[n-1]}$, akin to how we studied $A^{[n-1]}$ for the prior results in this paper on the rank of $A$.

We introduce some notation, pictured in Figure <ref>. Fix a set $S$ of $k$ columns and consider the submatrix $A_S$ induced by these columns. Let $E_{Sym}$ be the set of entries of $A_S$ whose rows are indexed by values in $S$. Let $E_{SymBD}$ be subset of entries in $E_{Sym}$ that are below the diagonal of $A$, and hence mutually independent. Let $E_{Asym}$ be the set of entries who rows are not in $S$, and let $E = E_{Asym} \cup E_{SymBD}$ be the full set of mutually independent entries that determine $A_S$. Formally:

\begin{equation*}
\begin{split}
&E_{Sym} := \{(i, j): i, j \in S \}\\
&E_{SymBD} := \{(i, j): i, j \in S, j < i \} \\
&E_{Asym} := \{(i, j): j \in S, i \notin S \}\\
&E := E_{SymBD} \cup E_{Asym}
\end{split}
\end{equation*}

Regions of $A_S$ with $S = [|S|]$.

For $R \subset [n]$, let $E_{Sym}[R], E_{SymBD}[R], E_{Asym}[R]$ and $E[R]$ denote the respective set additionally restricted to entries with $i \in R$. Observe that it suffices to consider $k \geq 2$, because otherwise having at least three $1$s in $A_S^R$ would imply having at least three rows of $A_S^R$ with a single $1$.

We will couple the process of randomly exposing the $1$'s in $A_S$ with a random walk that counts the number of times a $1$ is exposed in $E_{Asym}$ in a row that already contains a $1$ or in $E_{SymBD}$. Observe that each consecutive $1$ is exposed in a random entry in $E$, sampled without replacement. We condition on $L_S$, the number of $1$'s in $E$. Note that $L_S \sim \Bin(|E|, d/n)$. Let $(X_{i})_{i \in L_S}$ be the random walk that increases by one if the $i$th exposed $1$ is in $E_{SymBD}$ or if the $i$th exposed $1$ is in $E_{Asym}$ and is not the first $1$ exposed in its row. Otherwise, let $X_i = X_{i - 1}$.

The following claim says that $X_{L_S}$ must be large for $\mathcal{E}_{S, R}$ to occur for any $R$.

Suppose there exists some $R$ such that event $\mathcal{E}_{S, R}$ occurs. Then $X_{L_S} \geq \lceil{\frac{3k - 1}{2}}\rceil$.

Let $P$ be the number of $1$'s in $E_{Asym}[R]$, and let $Q$ be the number of $1$s in $E_{SymBD}[R]$. Since  $S \subseteq R$, we have $2Q + P = |\supp(A_S^R)|$. It follows by the third condition for the event that $2Q + P \geq 3k$.
Let $Y$ be the number of $1$s in $E_{Asym}[R]$, which are not the first $1$ in their row. Then $Y \leq X_{L_S} - Q$.
Now the number of rows in  $A_S^R$ which have exactly one $1$ is at least $(P - Y) - Y$,
since there are exactly $P - Y$ non-empty rows in $A_S^R$, and at most $Y$ of those rows have more than one $1$.

\[P - 2Y \geq P - 2X_{L_S} + 2Q \geq 3k - 2X_{L_S}.\]

Hence if $X_{L_S} < \lceil{\frac{3k - 1}{2}}\rceil,$ then since $X_{L_S}$ is an integer, we have
\[X_{L_S} \leq \begin{cases}\frac{3k}{2} - 1 & k \:\on{even} \\ \frac{3k - 1}{2} - 1& k \:\on{odd} \end{cases} \leq \frac{3k}{2} - 1,\]
$3k - 2X_{L_S} \geq 3k - (3k - 2) \geq 2,$
meaning that at least two rows in $A_S^R$ have exactly one $1$. It follows that we must have $X_{L_S} \geq \lceil{\frac{3k - 1}{2}}\rceil$ if $A_S^R$ contains at most one row with a single one.

It remains to show that $X_{L_S}$ is small enough with high enough probability to take a union bound over all $\binom{n}{k}$ sets $S$. We will break up this probability as follows.

Let $Q := \ceil*{\frac{3k-1}{2}},$ and define $L_{max} := \max\left(\frac{1}{4}n^{\epsilon}k^{1 - \epsilon}, 3dk\right)$, where $\epsilon = \frac{1}{12}$. Then (for a fixed $S$),

\begin{equation*}
\Pr[\exists R: \mathcal{E}_{S, R} ~\on{occurs}] \leq \Pr\left[L_S > L_{max}\right] + \Pr\left[X_{L_S} \geq Q | L_S < L_{max} \right].
\end{equation*}

We consider first the second term in the equation above. To bound this term, we couple $X_i$ with a random walk that $(Y_i)_{i \in L_S}$ which increases by $1$ with probability $\frac{k + L_S}{n}$ and otherwise stays constant. Observe that $Y_i$ stochastically dominates $X_i$, because there are at most $k + L_S$ rows in $E$ in which placing a $1$ will increase $X_i$.
Then conditioned on $L_S = \ell$,

\begin{equation*}
\begin{split}
\Pr\left[X_{\ell} \geq Q\right] &\leq \Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right].
\end{split}
\end{equation*}

The following lemma, which we prove in Appendix <ref>, bounds this probability.

[Binomial Bound 1 for $k$-core Small Case 1]lemmaclaimxr
For any $d$ larger than some constant, for any $2 \leq k \leq \frac{n}{d^7}$, and for any $\ell \leq \max\left(\frac{1}{4}n^{\epsilon}k^{1 - \epsilon}, 3dk\right)$,

\begin{equation*}
\Pr\left[\Bin\left(\ell, \frac{k + \ell}{n}\right) \geq Q\right] \leq 2\left(\frac{k}{3n}\right)^{k + \frac{1}{3}},
\end{equation*}

where $\epsilon = \frac{1}{12}$ and $Q = \ceil*{\frac{3k-1}{2}}$.

Next we bound the probability that $L_S \geq L_{max}$. Recall that $L_S$ is the number of $1$'s in $E_{Asym}$ and $E_{SymBD}$. Now $|E_{Asym} \cup E_{SymBD}| \leq kn$, and each entry in $E_{Asym} \cup E_{SymBD}$ is $1$ with probability $d/n$. Hence

\begin{equation*}
\begin{split}
\Pr[L_S \geq L_{max}] \leq \Pr\left[\Bin\left(kn, \frac{d}{n}\right) \geq L_{max}\right].
\end{split}
\end{equation*}

The following lemma, which we prove in Appendix <ref>, bounds this binomial tail probability.

[Binomial Bound 2 for $k$-core Small Case 1]lemmarmax
For sufficiently large $n$ and $d$, if $d \leq 3\log(n)$,

\begin{equation*}
\Pr\left[\Bin\left(kn, \frac{d}{n}\right) \geq  L_{max} \right] \leq 2\left(\frac{k}{en}\right)^ke^{-2\log(n)},
\end{equation*}

where $L_{max} = \max(3dk, \frac{1}{4}n^{1/12}k^{11/12})$.

We finish the proof of this lemma by union bounding over all $k$, and all sets $S$ of $k$ rows. Plugging in the result of Lemma <ref>, we have

\begin{equation*}
\sum_{k = 1}^{n/d^7}\binom{n}{k}\Pr[L_S > L_{max}] \leq \sum_{k = 1}^{n/d^7}\binom{n}{k}4\left(\frac{k}{en}\right)^ke^{-2\log(n)} \leq \sum_{k = 1}^{n/d^7} \frac{4}{n^2} \leq \frac{1}{n}.
\end{equation*}

Hence with probability at least $\frac{1}{n}$, for all sets of $k \leq n/d^7$ rows, there are at most $L_{max} = \max(3dk, \frac{1}{4}n^{1/12}k^{11/12})$ $1$'s among the rows. Assuming $L_S \leq L_{max}$, we plug in the result of Lemma <ref> to obtain:

\begin{equation*}
\begin{split}
\sum_{k = 1}^{n/d^7}\binom{n}{k}\Pr[X_{L_S} \geq Q \land L_S \leq L_{max}] &\leq \sum_{k = 1}^{n/d^7}\binom{n}{k}4\left(\frac{k}{3n}\right)^{k + \frac{1}{3}}
\leq  4\sum_{k = 1}^{n/d^7}\left(\frac{ne}{k}\right)^k\left(\frac{k}{3n}\right)^{k + \frac{1}{3}} \\
&\leq 4\sum_{k = 1}^{n/d^7}\left(\frac{e}{3}\right)^k\left(\frac{k}{3n}\right)^{1/3} = O\left(\frac{1}{\sqrt[3]{n}}\right).
\end{split}
\end{equation*}

It follows that

\begin{equation*}
\Pr[\exists S, R: \mathcal{E}_{S, R} ~\on{occurs}] \leq \sum_{S \subset [n]: |S| \leq \frac{n}{d^7}}\Pr\left[L_S > L_{max}\right] + \Pr\left[X_{L_S} \geq Q | L_S < L_{max} \right] \leq \frac{1}{n} + O\left(\frac{1}{\sqrt[3]{n}}\right).
\end{equation*}

§.§.§ Small Case 2

Let $A \sim \mathbb{A}(n, d/n)$. For a set of rows $R$ and a set of columns $S$, let $\mathcal{E}_{S, R}$ be the event that

* $\frac{n}{d^7} \leq |S| \leq \frac{2n}{d}$;

* $|R| \geq \left(1 - \frac{1}{d^7}\right)n$;

* $A_S^R$ contains no more than one row with a single $1$.

There exists a constant $d_0$ such that for all $d_0 < d \leq 3 \log n$,

\[\Pr\left[\exists S, R: \mathcal{E}_{S, R} ~\on{occurs}\right] = e^{-\Theta(n)}.\]

We union bound over all $\frac{n}{d^7} \leq k \leq \frac{2n}{d}$, and all $\binom{n}{k}$ sets $S$ of $k$ columns. We will lower bound the number of length $k$ rows in $A_S$ which have exactly one $1$. We consider only the $n - k$ mutually independent rows. Let $X_i$ be the event that the $i$th row, $A_S^{\{i\}}$, has one $1$ for $i \in [n] \setminus S$. Then

\begin{equation*}
\Pr[X_i] = k\frac{d}{n}\left(1 - \frac{d}{n}\right)^{k - 1}.
\end{equation*}

Let $c := \frac{n}{dk},$ such that $\frac{1}{2} \leq  c < d^6$. Now because $1 - x \geq e^{-\frac{x}{\sqrt{1 - x}}}$ for $0 \leq x \leq 1$, we have
\[\left(1 - \frac{d}{n}\right)^{k - 1} \geq \left(1 - \frac{d}{n}\right)^{k} = \left(1 - \frac{d}{n}\right)^{\frac{n}{cd}} \geq \left(e^{-\frac{\frac{d}{n}}{\sqrt{1 - \frac{d}{n}}}}\right)^{\frac{n}{cd}}= e^{-\frac{1}{c\sqrt{1 - \frac{d}{n}}}} \geq \frac{1}{20},\]

\begin{equation*}
\Pr[X_i] \geq\frac{e^{-\frac{1}{c\sqrt{1 - \frac{d}{n}}}}}{c} \geq \frac{1}{20c},
\end{equation*}

If $A_S^R$ has at most one row with a single one, then necessarily $\sum{X_i} \leq \frac{n}{d^7} + 1 \leq \frac{n}{80d^6}$, assuming sufficiently large $n$. By a Chernoff bound (see Lemma <ref> for reference), for $d$ larger than a large enough constant, for a fixed $S$,

\begin{equation*}
\begin{split}
\Pr[\exists R: \mathcal{E}_{S, R} ~\on{occurs}] &\leq \Pr\left[\sum{X_i} < \frac{n}{80d^6}\right]
\leq \Pr\left[\Bin\left(n - k, \frac{1}{20c}\right) < \frac{n}{80d^6}\right]\\
&\leq \Pr\left[\Bin\left(\frac{n}{2}, \frac{1}{20c}\right) < \frac{n}{80d^6}\right]
\leq e^{-\frac{n}{2}\frac{1}{40c}\left(1 - \frac{c}{2d^6}\right)^2}
\leq e^{-\frac{n}{320c}},
\end{split}
\end{equation*}

where we have used in the final inequality the fact that $c \leq d^6$.

Union bounding over all $\binom{n}{k}$ choices of $S$, and all choices of $k$, we have

\begin{equation*}
\begin{split}
\Pr[\exists S, R: \mathcal{E}_{S, R} ~\on{occurs}] &\leq
\sum_{k = \frac{n}{d^7}}^{\frac{2n}{d}}\binom{n}{k} e^{-\frac{n}{320c}} \leq n\max_{c \in [\frac{1}{2}, d^6]}\left(\frac{ne}{\frac{n}{cd}}\right)^{\frac{n}{cd}} e^{-\frac{n}{320c}}\\
&= n\max_{c \in [\frac{1}{2}, d^6]}\left(ecd\right)^{\frac{n}{cd}} e^{-\frac{n}{320c}}
= \max_{c \in [\frac{1}{2}, d^6]}{e^{n\left(\frac{\log(n)}{n} + \frac{\log(ecd)}{cd} - \frac{1}{320c}\right)}}.
\end{split}
\end{equation*}

Since $c$ grows at most polynomially in $d$, for $d$ a large enough constant, the exponent becomes negative, this probability is $e^{-\Theta(n)}$.

§.§ Large Domain

§.§.§ Large Case 1

Let $A \sim \mathbb{A}(n, d/n)$. For a set of rows $R$ and a set of columns $S$, let $\mathcal{E}_{S, R}$ be the event that

* $\frac{2n}{d} \leq |S| \leq \frac{n}{C}$;

* $|R| \geq \left(1 - \frac{1}{d^7}\right)n$;

* $A^Rx = 0$ for some $x$ with $\supp(x) = S$.

There exists a constant $d_0$ and $C$ such that for all $d_0 \leq d \leq 3\log(n)$,

\[\Pr\left[\exists S, R: \mathcal{E}_{S, R} ~\on{occurs}\right] = e^{-\Theta(n)}.\]

We union bound over all $k$ satisfying $\frac{2n}{d} \leq k \leq \frac{n}{C}$, and all $\binom{n}{k}$ sets $S$ of $k$ columns, and over all sets $R$ of size $\left(1 - \frac{1}{d^7}\right)n$. Fix a set of $k$ columns $S$ and a subset $R$ of rows. We will consider only the at least $n - k - \frac{n}{d}$ mutually independent rows of $A_S^R$, that is, the matrix $A_{S}^{R \setminus S}$.

Consider the following process, where we expose the independent rows of $A_{S}^{R \setminus S}$ one at a time for $i = 1$ to $|R \setminus S|$. Let $\mathcal{A}_i \in \mathbb{R}^k$ be the nullspace of the first $i$ rows vectors exposed, and let $D_i$ be the dimension of the smallest subspace of $\mathcal{A}_i$ which contains all vectors in $\mathcal{A}_i$ which have no zeros.

By Lemma <ref>, if $D_i > 0$, then we can choose an arbitrary vector $v$ in $\mathcal{A}_i$ with support $k$, and with probability at least $1 - \frac{1}{\sqrt{kd/n}}$, the $(i + 1)$th row exposed is not orthogonal to $v$. In this case $D_{i + 1} = D_i - 1$. If $D_i$ ever becomes $0$, then $A_{S}^{R \setminus S}$ has no kernel vectors with no zeros, so there is no kernel vector of $A^R$ with support $S$. Since $D_0 = k$, a Chernoff bound (see Lemma <ref>) yields

\begin{equation*}
\begin{split}
\Pr[D_{|R \setminus S|} \neq 0] &\leq \Pr\left[\Bin\left(n - k - \frac{n}{d}, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right]
\leq \Pr\left[\Bin\left(\frac{n}{2}, 1 - \frac{1}{\sqrt{kd/n}}\right) < k\right]\\
&\leq e^{-\frac{n}{4}\left(1 - \frac{1}{\sqrt{kd/n}}\right)\left(1 - \frac{1}{\sqrt{kd/n}} - \frac{2k}{n}\right)^2}
\leq  e^{-n\epsilon},
\end{split}
\end{equation*}

where $\epsilon > 0.001$. To achieve this value of $\epsilon$, we impose that $C \geq 12$ such we can plug in  $2k/n \leq \frac{1}{6}$ in the last inequality. Finally union bounding over all $R$ and $S$, the probability that $\mathcal{E}_{S, R}$ occurse for some $R$ and $S$ is at most

\begin{equation*}
\sum_{k = \frac{2n}{d}}^{\frac{n}{C}}\binom{n}{k}\binom{n}{\frac{n}{d^7}}e^{-\epsilon n} \leq n\left(eC\right)^{\frac{n}{C}}\left(ed^7\right)^{\frac{n}{d^7}}e^{-\epsilon n} \leq e^{n\left(\frac{\log(n)}{n} + \frac{\log(eC))}{C} + \frac{\log(ed^7))}{d^7} - \epsilon\right)},
\end{equation*}

which for constants $C$ and $d$ large enough, is $e^{-\Theta(n)}$. This concludes the lemma.

§.§.§ Large Case 2

We will use the following lemmas from Section <ref>, which we restate here.

We will use the following notation: For an adjacency matrix $M$, let $C_k(M)$ be the set of vertices in the $k$-core of the graph with adjacency matrix $M$. Further, let $M(k)$ denote adjacency matrix of the $k$-core of $M$. For a matrix $M$ and set $S$, we let $M[S] := M_S^S$ denote the restriction of $M$ to the columns and rows in $S$. Thus $M(k) = M[C_k(M)]$. Recall that we define $M^{(i)}$ to be $M$ with both the $i$th row and $i$th column removed.

The following lemma, which follows from [25],  states that the $k$-core of $A$ is large.

Let $A \sim \mathbb{A}(n, d/n)$. For any constant $k \geq 3$, and for $d \geq d_0(k)$, with probability at least $1 - O(\exp(-n^{0.1}))$,
\begin{equation*}
|C_k(A)| \geq  n\left(1 - d^ke^{-d/2}/(k - 1)! - n^{-1/6}\right).
\end{equation*}

If $d = \omega(1)$ and $d \leq 3\log(n)$, then with probability at least $1 - O(\exp(-n^{0.1}))$,
\[|C_k(A)| \geq  n\left(1 - e^{-d/20}\right).\]

Our main tool to prove Theorem <ref> is the following lemma, which rules out large dependencies in $A(k)$.

Let $A \sim \mathbb{A}(n, d/n)$ for $d \leq 3
\log(n)$ and $d = \omega(1)$. For any $u, r < s, t \in [n]$,

\begin{equation}\label{eq:lem_core}
\begin{split}
\Pr\left[\exists x: A(k)x = 0, \supp(x) > t\right] &\leq
\frac{n}{t - n/d}\max_{x \in \mathbb{R}^{n}: \supp(x) \geq s}\Pr\left[x^\top A_n = 0\right]\\
&\quad +\frac{n}{t - n/d}\Pr\left[\exists x: A^{(n)}(k)x = 0, r < |\supp(x)| < s \right]\\
&\quad + \frac{dr}{t - n/d}\\
&\quad+ \frac{n}{t - n/d}\frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}(k)x = e_1, |\supp(x)| < s\right]\\
&\quad+ \frac{n}{t - n/d}\max_{X \in \mathcal{T}^{n}_{n - n/d^2 - r - u, s}}\Pr\left[A_n^{\top}XA_n = 0\right] \\
&\quad+ o\left(\frac{n}{t - n/d}\right),
\end{split}
\end{equation}

where $\mathcal{T}^{m}_{p, q}$ denotes the set of matrices in $\mathbb{R}^{m \times m}$ with some set of $p$ columns that each have at least $q$ non-zero entries.

For $i \in [n]$, let $S_i := C_k(A^{(i)}) \cup i$, and let $\mathcal{H}_i$ be the space spanned by the column vectors
\[A_1^{S_i}, A_2^{S_i}, \cdots A_{i - 1}^{S_i}, A_{i + 1}^{S_i}, \cdots, A_n^{S_i}.\]

Let $T := \{i: C_k(A) = S_i\}.$ Then $A(k)x = 0$ for some $x$ implies that for all $i \in \supp(x) \cap T,$ we have $A_i^{S_i} = A_i^{C_k(A)} \in \mathcal{H}_i,$ since
\[x_i A_i^{C_k(A)} = -\sum_{j} x_j A_j^{C_k(A)}.\]

We first claim that the set $T$ is large, such that if $\supp(x)$ is large, we must have many $i$ for which $A_i^{S_i} \in H_i$. Let $c_i := |C_k(A^{(i)})|$.

With probability $1 - o(1)$, $|T| \geq n\left(1 - \frac{1}{d}\right)$.

Fix $i$, and consider the probability that $C_k(A) = C_k(A^{(i)}) \cup i$.

Notice that $C_k(A^{(i)})$ is independent of $A_i$, and hence

\begin{equation*}
\begin{split}
\Pr[C_k(A) = C_k(A^{(i)}) \cup i] &\geq \Pr[\supp(A_i) \geq k \land A_{ij} = 0 \: \forall j \notin C_k(A^{(i)})] \\
& = \mathbb{E}_{c_i}\left[\left(1 - \frac{d}{n}\right)^{n - 1 - c_i}\Pr\left[\Bin\left(c_i, \frac{d}{n}\right) \geq k\right]\right]\\
& \geq \Pr\left[c_i \geq n\left(1 - \frac{1}{2d^3}\right)\right]e^{-\frac{1}{d^2}}\Pr\left[\Bin\left(n(1 - 1/2d^3), \frac{d}{n}\right) \geq k\right]\\
& \geq \Pr\left[c_i \geq n\left(1 - \frac{1}{2d^3}\right)\right]e^{-\frac{1}{d^2}}\left(1 - e^{-\frac{n\left(1 - \frac{1}{2d^3}\right)n\left(\frac{d}{n} - \frac{k}{n\left(1 - \frac{1}{2d^3}\right)}\right)^2}{2d}}\right)\\
&\geq \Pr\left[c_i \geq n\left(1 - \frac{1}{2d^3}\right)\right]e^{-\frac{1}{d^2}}(1 - e^{-d/3})\\
&\geq \Pr\left[c_i \geq n\left(1 - \frac{1}{2d^3}\right)\right]\left(1 - \frac{1}{d^{3/2}}\right),
\end{split}
\end{equation*}

where we used a Chernoff bound (see Lemma <ref>) to bound the binomial, and the last two inequalities hold for $d$ large enough relative to $k$.
By Lemma <ref>, with probability $1 - O(\exp(-n^{0.1}))$, we have $c_i \geq n\left(1 - e^{-d/20}\right)$, so we have

\begin{equation*}
\Pr[C_k(A) = C_k(A^{(i)}) \cup i] \geq 1 - \frac{1}{d^{3/2}} - O(\exp(-n^{0.1})).
\end{equation*}

Now by Markov's inequality,

\begin{equation*}
\begin{split}
\Pr\left[|[n] \setminus T| \geq \frac{n}{d}\right] &\leq \frac{d}{n}\sum_i\left(1 - \Pr[C_k(A) = C_k(A^{(i)}) \cup i]\right) \\
&\leq d\left(1 - \left(1 - d^{-3/2} - O(\exp(-n^{0.1})\right)\right) = o(1).
\end{split}
\end{equation*}

Let $\mathcal{E}_i$ denote the event that $A_i^{S_i} \in \mathcal{H}_i$. Let $X_i$ be the indicator of this event, and let $X = \sum_i X_i$. If $|T| \geq n\left(1 - \frac{1}{d}\right)$, at most $n/d$ vertices can be in the $k$-core but not in $T$. Thus by Markov's inequality, we have

\begin{equation}\label{markov_core}
\begin{split}
\Pr\left[\exists x : A(k)x = 0, |\supp(x)| \geq t \right] &\leq \Pr\left[|T| < n\left(1 - \frac{1}{d}\right)\right] + \Pr\left[X \geq t - n/d\right]\\
&\leq o(1) + \frac{\mathbb{E}[X]}{t - n/d}
= o(1) + \frac{\sum_i\Pr[\mathcal{E}_i]}{t - n/d}
= o(1) + \frac{n}{t - n/d}\Pr[\mathcal{E}_n].
\end{split}
\end{equation}

We will break down the probability $\Pr[\mathcal{E}_n]$ into several cases, depending on the size of the support of vectors in the kernel of $A^{(n)}(k)$. Let $S \subset C_k(A^{(n)})$ be the set of all $j$ such that $e_j \in \Span(A^{(n)}(k))$. By Claim <ref> and  Claim <ref>,

\begin{equation*}
\ell:= \max(\supp(x): A^{(n)}(k)v = 0) = c_n - |S|.
\end{equation*}

Case 1: $A^{(n)}(k)$ has a vector $x$ with large support, that is, $\ell \geq s$.

Case 2: $A^{(n)}(k)$ has a vector $x$ with medium support, that is $r < \ell < s$.

Case 3: $A^{(n)}(k)$ does not have any vectors with large or medium support vectors in its kernel, that is, $\ell \leq r$.

We can expand

\begin{equation}\label{cases_core}
\Pr[\mathcal{E}_n] = \Pr[\mathcal{E}_n| \ell \geq s]\Pr[\ell \geq s] + \Pr[\mathcal{E}_n|r < \ell < s]\Pr[r < \ell < s] + \Pr[\mathcal{E}_n| \ell \leq r]\Pr[\ell \leq r].
\end{equation}

Define $\textbf{a} := A_i^{C_k(A^{(n)})}$ to be the restriction of $A_i$ to the indices in the $k$-core of $A^{(n)}$.

To evaluate the probability of the first case, we condition on $A^{(n)}$, and let $x$ be any vector of support at least $s$ in the kernel of $A^{(n)}(k)$. Observe that $\mathcal{E}_n$ cannot hold if $x^\top \textbf{a}$ is non-zero. Since $\textbf{a}$ is independent from $x$, we have

\begin{equation}\label{case_1_core}
\begin{split}
\Pr[\mathcal{E}_n| \ell \geq s]\Pr[\ell \geq s] &\leq \max_{x: \supp(x) \geq s}\Pr[x^\top \textbf{a} = 0] \leq  \max_{x \in \mathbb{R}^{n}: \supp(x) \geq s}\Pr\left[x^\top A_n = 0\right].
\end{split}
\end{equation}

Here the second inequality comes from considering $x$ over a larger domain. Combined with eq. <ref>, the contribution from this case yields the first term in the right hand side of eq. <ref>.

For the second case, we bound

\begin{equation}\label{case_2_core}
\Pr[\mathcal{E}_n|r < \ell <  s]\Pr[r < \ell < s] \leq \Pr[r < \ell < s] \leq \Pr\left[\exists x: A^{(n)}(k)x = 0, r < |\supp(x)| < s \right].
\end{equation}

Combined with eq. <ref>, the contribution from this case yields the second term in the right hand side of eq. <ref>.

In this third case, we will show conditions under which we can algebraically construct a vector $v$ such that $A[C_k(A^{(n)}) \cup n]v = e_n$. This will imply by Claim <ref> that under those conditions, $A_n^{C_k(A^{(n)}) \cup n} \notin \mathcal{H}_n$.

To define these conditions, recall that $S \subset C_k(A^{(n)})$ is the set of all $j$ such that $e_j \in \Span(A[C_k(A^{(n)})])$. For $j \in S$, let $w_j$ be any vector such that $A^{(n)}(k)w_j = e_j$. We next construct a sort of “pseudoinverse" matrix $B \in \mathbb{R}^{C_k(A^{(n)}) \times C_k(A^{(n)})}$ as follows: For $j \in S$, define the column $B_j$ to to be $w_j$. Define all other entries columns of $B$ to be zero. The following claim shows a condition for $\mathcal{E}_n$ not holding.

If $\supp(\textbf{a}) \subset S$ and $\textbf{a}^\top B\textbf{a} \neq 0$, then $e_n \in \Span(A[C_k(A^{(n)}) \cup n])$.

Let $w' := B\textbf{a} = \sum_{j \in S}{\textbf{a}_jw_j}$ such that $A^{(n)}(k)w' = \sum_{j \in S}{\textbf{a}_je_j}$. Hence if $\supp(\textbf{a}) \subset S$, $A^{(n)}(k)w' = \textbf{a}.$ Define $w \in \mathbb{R}^{C_k(A^{(n)}) \cup n}$ to be the vector equal to $w'$ on the coordinates in $C_k(A^{(n)})$ and $-1$ on coordinate $n$. Then

\begin{equation*}
(A[C_k(A^{(n)}) \cup n]w)_j = 0 \qquad  \forall j \in C_k(A^{(n)})
\end{equation*}

\begin{equation*}
(A[C_k(A^{(n)}) \cup n]w)_n = \textbf{a}^\top B\textbf{a}.
\end{equation*}

Evidently, if $\textbf{a}^\top B\textbf{a} \neq 0$, then
\[\frac{A[C_k(A^{(n)}) \cup n]w}{\textbf{a}^\top B\textbf{a}} = e_n,\]
so $e_n \in \Span(A[C_k(A^{(n)}) \cup n])$.

By definition, in the third case, we have $|S| \geq c_n - r$. Hence

\begin{equation}\label{case_3_core}
\begin{split}
\Pr[\mathcal{E}_n \land \ell \leq r]
&\leq \Pr\left[\supp(\textbf{a}) \not\subset S \land |S| \geq c_n - r\right] + \Pr[\textbf{a}^\top B\textbf{a} = 0 \land |S| \geq c_n - r].
\end{split}
\end{equation}

Notice that $S$ is a function of $A^{(n)}$, so $\textbf{a}$ is independent from $S$. Thus for any set $S$,
\[\Pr\left[\supp(\textbf{a}) \not\subset S\right] \leq 1 - \left(1 - \frac{d}{n}\right)^{n - |S|} \leq \frac{d(n - |S|)}{n}.\]

By Lemma <ref>, with probability $1 - o(1)$, we have $c_n \geq n\left(1 - \frac{1}{d^2}\right)$, thus

\begin{equation}\label{case_3_a_S_core}
\Pr\left[\supp(\textbf{a}) \not\subset S \wedge |S| \geq c_n - r\right] \leq o(1) + \frac{d(n - n(1 -\frac{1}{d^2}) + r)}{n} = o(1) + \frac{1}{d} + \frac{dr}{n} = o(1) + \frac{dr}{n}.
\end{equation}

Combined with eq. <ref>, the contribution from this equation yields the third term in the right hand side of eq. <ref>.

We will break up the second term in eq. <ref> by conditioning on whether the support of $B$ has many entries or not, and then by using the independence of $\textbf{a}$ from $B$:

\begin{equation}\label{eq:T_term_core}
\Pr[\textbf{a}^\top B\textbf{a} = 0 \land |S| \geq c_n - r] \leq \Pr\left[B \notin \mathcal{T}^{c_n}_{c_n - r - u, s}  \wedge |S| \geq c_n - r\right] + \max_{X \in \mathcal{T}^{c_n}_{c_n - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a} = 0\right].
\end{equation}

For the second probability on the right hand side, notice that for any positive integers $a \leq b$, if $\textbf{x}$ and $\textbf{y}$ are random vectors from some product distributions $P^{\otimes a}$ and $P^{\otimes b}$ respectively, then

\begin{equation*}
\max_{X \in \mathcal{T}^{a}_{a - r - u, s}}\Pr\left[\textbf{x}^\top X\textbf{x} = 0\right] \leq \max_{X \in \mathcal{T}^{b}_{b - r - u, s}}\Pr\left[\textbf{y}^\top X\textbf{y} = 0\right].
\end{equation*}

Hence since $c_n \geq n\left(1 - \frac{1}{d^2}\right)$ with probability $1 - o(1)$, we have

\begin{equation}\label{c_n_quad}
\max_{X \in \mathcal{T}^{c_n}_{c_n - r - u, s}}\Pr\left[\textbf{a}^\top X\textbf{a} = 0\right] \leq o(1) + \max_{X \in \mathcal{T}^{n}_{n - n/d^2 - r - u, s}}\Pr\left[A_n^\top XA_n = 0\right].
\end{equation}

To bound the first probability on the right hand side of eq. <ref>, observe that if $|S| \geq c_n - r$ and $B \notin \mathcal{T}^{c_n}_{c_n - r - u, s}$, there must exist at least $u$ different $j \in S$ such that $\supp(w_j) \leq s$. So

\begin{equation*}
\begin{split}
\Pr\left[B \notin \mathcal{T}^{c_n}_{c_n - r - u, s}  \wedge |S| \geq c_n - r\right] &\leq \Pr\left[|\{j: \exists x \neq 0: A^{(n)}(k)x = e_j, |\supp(x)| < s\}| \geq u \right] \\ &\leq \frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}(k)x = e_1, |\supp(x)| < s\right],
\end{split}
\end{equation*}

where the last inequality follows by Markov's inequality. Plugging this and eq. <ref> into eq. <ref> yields

\begin{equation*}
\begin{split}
\Pr[\textbf{a}^\top B\textbf{a} = 0 \land |S| \geq c_n - r] &\leq \frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}(k)x = e_1, |\supp(x)| < s\right]\\
& \qquad + \max_{X \in \mathcal{T}^{n}_{n - n/d^2 - r - u, s}}\Pr\left[A_n^\top XA_n = 0\right] + o(1).
\end{split}
\end{equation*}

Combining this with <ref> and <ref> yields

\begin{equation*}
\Pr[\mathcal{E}_n \land k \leq r] \leq o(1) + \frac{dr}{n} + \max_{X \in \mathcal{T}^{n - 1}_{n - n/d^2 - r - u, s}}\Pr\left[A_n^\top XA_n = 0\right] + \frac{n}{u}\Pr\left[\exists x \neq 0: A^{(n)}(k)x = e_1, |\supp(x)| < s\right].
\end{equation*}

Plugging this and eqs. <ref> and <ref> into eq. <ref> and finally eq. <ref> yields the lemma.

§.§ Proof of Theorem <ref>

We are now ready to prove our main theorem, which we restate here.

The proof follows by instantiating Lemma <ref> with the following values:
$t = \frac{n}{C}$, $s = \frac{n}{C}$, $r = \frac{n}{8e^4d^2}$, $u = \frac{n}{2}$. Here $C$ is the constant from Lemma <ref>.

With the following values, it is immediate from the sparse Littlewood-Offord (Lemma <ref>) and quadratic Littlewood-Offord theorems (Lemma <ref>) that the first and last terms in Lemma <ref> respectively are $o(1)$. The third term is $O(1/d) = o(1)$. The two lemmas stated immediately after this proof (Lemmas <ref> and <ref>) will show that the second and fourth terms are $o(1)$.

Assuming these two lemmas, it follows that with probability $1 - o(1)$, there are no kernel vectors with support size at least $n/C$ in $A(k)$. To rule out any minimal dependencies of less than $n/C$ columns of $A(k)$, we use Lemmas <ref>, <ref>, and <ref>: If there were a minimal dependency among $\ell$ columns $S$ of $A(k)$, then it would mean that the matrix $A_S^R$, with $R = C_k(A)$ would:

* Contain $\geq 3\ell$ $1$'s, because $A(k)$ is a $k$-core for $k \geq 3$ and

* Be a minimal dependency.

Thus the event $\mathcal{E}_{S, R}$ of Lemma <ref> occurs for some $S, R$, which occurs with probability $o(1)$.

If $ \frac{n}{d^7}< \ell < n/C$, then applying Lemmas <ref>, and <ref> with $T = C_k(A)$ means that, if $|C_k(A)| \geq n(1 - 1/d^7)$, with probability at least $1 - e^{-\Theta(n)}$, there is no dependency of these sizes in $A(k)$. By Lemma <ref>, $|C_k(A)| \geq n(1 - 1/d^7)$ with probability $1 - o(1)$.

This rules out all dependencies in $A(k)$ with probably $1 - o(1)$, proving the theorem.

It remains to prove lemmas <ref> and <ref>.

Let $A \sim \mathbb{A}(n, d/n)$ for $d = \omega(1)$, and let $C$ be the constant in Lemma <ref>. For any constant $k \geq 3$,

\begin{equation*}
\Pr\left[\exists x: A(k)x = 0, \frac{n}{8e^4d^2} < |\supp(x)| < \frac{n}{C} \right] = o(1).
\end{equation*}

This is immediate from the medium and large case Lemmas <ref> and <ref>, since the $k$-core has size at least $n\left(1 - \frac{1}{d^7}\right)$ with probability $1 - o(1)$. Hence if there was a dependency of $\ell$ columns $S$ in the $k$-core for $\frac{n}{8e^4d^2}< \ell < \frac{n}{C}$, it would mean there would have to be a set $R = C_k(A)$ of size at least $n\left(1 - \frac{1}{d^7}\right)$ with $S \subset R$ such that matrix $A_S^R$ is a minimal dependency. This implied that the even $\mathcal{E}_{S, R}$ of Lemma <ref> or <ref> occurs.

Let $A \sim \mathbb{A}(n, d/n)$ for $d = \omega(1)$, and let $C$ be the constant in Lemma <ref>. Then for any constant $k \geq 3$,

\begin{equation*}
\Pr\left[\exists x: A(k)x = e_1, |\supp(x)| < \frac{n}{C} \right] = o(1)
\end{equation*}

We reduce Lemma <ref> to Lemma <ref>, which will be easier to prove using Lemmas <ref> and <ref>.

Let $A \sim \mathbb{A}(n, d/n)$ for $d = \omega(1)$, and let $C$ be the constant in Lemma <ref>. Let $A'$ be $A(k)$ with the first row removed.
Then for any constant $k \geq 3$,

\begin{equation*}
\Pr\left[\exists x: A'x = 0, |\supp(x)| \leq \frac{n}{C}\right] = o(1).
\end{equation*}

If such a vector $x$ satisfied $A(k)x = e_1$, then necessarily $A'x' = 0$, where $x'$ is $x$ with the first (zero) coordinate removed, and $A'$ is $A(k)$ with the first row removed. This occurs with probability $o(1)$ by Lemma <ref>.

By Lemma <ref>, plugging in $R = C_k(A) \setminus 1$, with probability $1 - o(1)$, there are no vectors $x$ such that $A^Rx = 0$ where $\frac{2n}{d} \leq |\supp(x)| < n/C$. Since $A' = A_R^R$, this implies that there there are no vectors $x$ such that $A'x = 0$ where $\frac{2n}{d} \leq |\supp(x)| < n/C$.

Now suppose there was some set $S$ of size $k \leq \frac{2n}{d}$ such that $A'_S$ is a minimal dependency. Let $R = C_k(A)$, such that $A_S^{R \setminus \{1\}}$ is a minimal dependency. It follows that:

* $S \subset R$;

* $\supp(A_S^R) \geq 3|S|$ by definition of the $k$-core, since $k \geq 3$.

* $A_S^{R \setminus \{1\}}$ contains no rows with a single $1$, and hence  $A_S^{R}$ contains at most one row with a single $1$.

This implies that the event $\mathcal{E}_{S, R}$ of either Lemma <ref> or Lemmas <ref> occurs. Such an event occurs with probability $o(1)$. This concludes the lemma.

§ APPLICATION TO GRADIENT CODES

In the following section, we will shift our focus to the problem of Gradient Coding. The purpose of this section is to present further applications of our structural characterization beyond analyzing the rank of sparse random matrices.

§.§ Introduction to Gradient Coding

Comparison of Related Work. We have normalized the decoding error by $1/n$.

Assignment Matrix Design     Expected Decoding Error     Adversarial Decoding Error
Expander Code (Cor. 23 [26])      -      $< \frac{4p}{d(1 - p)}$
Pairwise Balanced ([4])     $\geq \frac{p}{d(1 - p)}$     -

BIBD ( Const. 1 [21])     -     1in
$ d = \Omega(\sqrt{m})$

BRC ([32])

$d = \Omega\left(-\frac{\log\log(m)}{\log(p)}\right)$

rBGC ([9])      $< \frac{1}{(1 - p)d}$     -

FRC of [28] (and [31])     $p^{d}$     $p$

Graph-based Assignment [17]      $p^{d - o(d)}$     $\frac{(1 + o(1))p}{2(1 - p)}$

This work (Stacked ABC)     $p^{d - o(d)}$     $\Theta(p/d)$

Gradient codes are data replication schemes used in distributed computing to provide robustness against stragglers, machines that are slow or unresponsive [28, 26]. Specifically, such replication schemes can be used to approximately compute the sum $\sum_i f(X_i)$ of the evaluations of a function $f: \mathcal{X} \rightarrow \mathbb{R}$ over a set of data points $X_1, \ldots, X_n \in \mathcal{X}$. Typically in machine learning, the function $f$ represents the gradient of a loss function.

To distribute the computation of $\sum_i f(X_i)$ while maintaining robustness against stragglers, the data points $\{X_i\}$ are distributed redundantly among $m$ machines according to an assignment matrix $A_0 \in \mathbb{R}^{n \times m}$. Each machine $j$ is tasked with computing $g_j := \sum_i (A_0)_{ij}f(X_i)$, a weighted sum of $f$ over the data it stores. A central server then collects these values $g_j$ for all machines $j$ which are not stragglers, and linearly combines the $g_j$ using weights $w_j$ to best approximate $\sum_i f_i(X_i)$.

Formally, we define the decoding error of an assignment $A_0$ along with a set of stragglers $S \subset [m]$ to be
the squared distance between the all-$1$'s vector, $\mathbbm{1}$, and the span of the columns $\{(A_0)_j\}_{j \notin S}$:

\begin{equation*}
\textnormal{err}(A_0, S) := \min_{w: w_j = 0 \: \forall \: j \in S}|A_0w - \mathbbm{1}|_2^2.
\end{equation*}

The decoding error immediately gives us a bound on the approximation error of $\sum_i f(X_i)$. Let $f^*$ be the vector in $\mathbb{R}^n$, where $f^*_i := f(X_i)$. Then for any $w \in \mathbb{R}^m$,

\begin{equation*}
\sum_j w_j g_j - \sum_i f(X_i) = f^{*T}A_0w - f^{*T}\mathbbm{1} = f^{*T}(A_0w - \mathbbm{1}).
\end{equation*}

Hence for any $S$, there exists a vector $w \in \mathbb{R}^{[m] \setminus S}$ such that

\begin{equation*}
\left(\sum_{j \in [m] \setminus S} w_j g_j - \sum_i f(X_i)\right)^2 \leq \textnormal{err}(A_0, S)|f^*|_2^2.
\end{equation*}

The gradient coding literature considers two models of decoding error. One in which the set of stragglers $S$ is chosen adversarially and one where the set of stragglers $S$ is chosen uniformly at random. In the case where $S$ is an adversarially chosen $p$ fraction of the machines, we consider the adversarial decoding error of $A_0$:

$$\max_{S \in \binom{[m]}{pm}}\left( \textnormal{err}(A_0, S)\right).$$

If $S$ is a random $p$ fraction of the machines, we consider the expected decoding error of $A_0$:

$$\mathbb{E}_{S \sim \binom{[m]}{pm}}{ \textnormal{err}(A_0, S)}.$$

A good assignment matrix $A_0$ minimizes the decoding error while keeping the maximum amount of computation per machine — measured by the maximum column sparsity of $A_0$ — small. For an $n\times n$ assignment matrix with at most $d$ non-zero entries in each column, optimal lower bounds on both the adversarial and random decoding error are known. In particular, Raviv et al. ([26]) showed that the adversarial decoding error must be at least $\Omega(np/d)$. On the other hand, it is known that the random decoding error is at least $np^d$, and further, this optimal error is achieved by a design known as the Fractional Repetition Code (FRC) [28]. However, despite its optimality under random stragglers, the FRC of [28] only achieves an adversarial decoding error of $np$. Several works  [17, 8] have aimed to design assignment matrices that have small adversarial and expected decoding error, but to our knowledge, no existing assignments have achieved adversarial error that decays in $d$ (at any rate) while simultaneously achieving random error that decays faster than like $1/d$. This leads to the following natural question asked in [17]:

Does there exist an assignment matrix $A_0$ which simultaneously has near-optimal random decoding error $np^{d-o(d)}$ and near-optimal adversarial decoding error $\Theta(np/d)$?

We answer this question in the affirmative. In the rest of this section, we construct a novel gradient code called the Augmented Biregular Code (ABC), and using our structural characterization of linear dependencies, prove that it achieves an expected decoding error of $np^{d - o(d)}$ and adversarial decoding error of $\Theta(np/d)$.  In Table <ref>, we compare the adversarial and expected decoding errors of our work and existing work on gradient coding.

§.§ The ABC and Stacked-ABC Distributions

We use the following process to generate a random matrix $A_0 \in \{0, 1\}^{\gamma n \times n}$ from the distribution $\textnormal{ABC}(n, \gamma, d)$:

Define $A_0 \sim \textnormal{ABC}(n, \gamma, d)$ to be sampled in the following way. Sample a random permutation $\rho \sim \mathcal{S}_{\gamma d n}$. Create $\gamma n$ row-nodes and $n$ column-nodes and associate to each row-node $d$ half-edges and to each column node $\gamma d$ half-edges. Create a multi-graph $G$ by pairing the $i$ right half-edge to the $\rho(i)$th left half-edge. Given this bipartite graph, take $A_0 \in \{0, 1\}^{\gamma n \times n}$ to be the matrix where $(A_0)_{ij} = 1$ if and only if there is at least one edge from row-node $i$ to column-node $j$.

We define a second distribution  $\on{ABC}_{\gamma-\on{stacked}}(n,d)$ that results from stacking together several copies of the same transposed ABC matrix $A_0 \sim \textnormal{ABC}(n, \gamma, d)$ to form a square $n \times n$ matrix, pictured in Figure <ref>.

For $\gamma,d,n\in\mathbb{Z}^+$ such that $\gamma \mid d$ and $\gamma \mid n$, we define the $\gamma$-stacked Augmented Biregular Code $B$ to be an $n\times n$ matrix formed by sampling $A_0\sim \textnormal{ABC}(n/\gamma,\gamma,d/\gamma)$ and stacking $\gamma$ identical copies of $A_0^\top$. We will denote the distribution of such matrices as $\on{ABC}_{\gamma-\on{stacked}}(n,d)$.

The stacked ABC

Using this new distribution of assignment matrices, we prove the following theorem on the decoding error.

Let $c,\gamma_0,d_0$ be the universal constants from Corollary $\ref{abc_random}$. Choose any $\gamma,d\in\mathbb{Z}^+$ such that $\gamma \geq \gamma_0$, $\gamma \mid d$ and $\frac{d}{\gamma}\geq d_0$. For any $n$ divisible by $\gamma$, let $B \sim \textnormal{ABC}_{\gamma-\on{stacked}}(n, d)$. Then with constant probability over the choice of $B$:

\begin{equation*}
\frac{1}{n}\mathbb{E}_{S \sim \binom{[n]}{pn}}{ \textnormal{err}(B, S)} \leq p^{d - c\log(d)}+o(1),
\end{equation*}

\begin{equation*}
\frac{1}{n}\max_{S \in \binom{[n]}{pn}}\left( \textnormal{err}(B, S)\right) \leq  \left(\frac{8\gamma^3p}{d}\right)+o(1).
\end{equation*}

The main technical parts of Theorem <ref> follow from the following theorem, which characterizes the minimal dependencies among the columns of the matrix $A_0$ with a random $p$ fraction of rows removed. Formally, we define the ensemble of matrices $A \sim \textnormal{ABC}_p(n, \gamma, d)$ to be given by setting $A = (A_0)^{[n\gamma (1 - p)]}$, where $A_0 \sim \textnormal{ABC}(n, \gamma, d)$.

[Characterization ABC]theoremcharabc
There exist universal constants $c$ and $\gamma_0$ such that for any $p < 1/2$, $\gamma > \gamma_0$, and $d \geq d_0(\gamma)$, for $A \sim\textnormal{ABC}_p(n, \gamma, d)$, with probability $1 - o(1)$:

* All minimal dependencies of $k$ columns of $A$ are in $\mathcal{T}_k \cup \mathcal{T}_k^{+} \cup \mathcal{T}_k^C$.

* The number of columns involved in linear dependencies of $A$ is at most $np^{\gamma d - c\log(\gamma d)}$, ie.,

$$\left|\bigcup_{x : Ax = 0} \supp(x) \right| \leq np^{\gamma d + c\log_p(\gamma d)}.$$

The following corollary allows us to deduce the expected decoding error of $A_0$, leading directly to Theorem <ref>.

Let $A^\top \sim \textnormal{ABC}_p(n, \gamma, d)$. For any $p < 1/2$, there exists constants $c$, $\gamma_0$ and $d_0$ such that for $\gamma \geq \gamma_0$ and $d \geq d_0$, with probability $1 - o(1)$,

\begin{equation*}
\frac{1}{n}\min_{w}|A w - \mathbbm{1}|_2^2 \leq p^{\gamma d + c\log_p(\gamma d)}.
\end{equation*}

Let $D = \bigcup_{x : A^\top x = 0} \supp(x)$ be the set of columns involved in linear dependencies of $A^\top$. Then by Lemma <ref>, for any $i \in [n] \setminus D$, we have $e_i \in \on{span}(A)$. It follows that $\mathbbm{1}_{[n] \setminus D}$, the vector with $0$ in entries indexed by $D$, and $1$ elsewhere is in the span of $A$. Thus $\frac{1}{n}\min_{w}|A w - \mathbbm{1}|_2^2 \leq \frac{|D|}{n}$. Plugging in Theorem <ref> which give a high probability bound on the size of $D$, yields the corollary.

Corollary <ref> it tight in the sense that with probably $1 - o(1)$, $\frac{1}{n}\min_{w}|A w - \mathbbm{1}|_2^2 \geq (1 + o(1))p^{\gamma d}$. It is easy to check this by counting the number of all-zero rows in $A$.

§.§ Proof Overview

As with the main results of this paper, we split the proof of Theorem <ref> into two domains: small and large. The goal of the small case is to prove that all small minimal dependencies of columns of $A$ must be contained in $\mathcal{T}_k \cup \mathcal{T}_k^{+} \cup \mathcal{T}_k^C$ with high probability. In particular, we prove the following lemma:

Let $A \sim \textnormal{ABC}_p(n, \gamma, d)$ for $\gamma \geq 1$ and $p < \frac{1}{2}$. Let $S\subset[n]$ be any set of size $k\in[1,\frac{n}{18e\gamma^2 d^2}]$. There exists universal constants $c_{\ref{lemma:abc_small}}$ and $d_0$ such that if $d>d_0$, then:

* $\Pr[A_S \in \mathcal{M}_k \setminus \left(\mathcal{T}_k \cup \mathcal{T}_k^+ \cup \mathcal{T}_k^C \right)] = O\left(e^{-k}\left(\frac{k}{n}\right)^{k+1/2}\right)$.

* $\Pr[A_S \in \mathcal{T}_k]\leq \left(p^{\gamma d+ c_{\ref{lemma:abc_small}}\log_p(\gamma d)}\right)^k\left(\frac{k}{n}\right)^{k-1}$.

* $\Pr[A_S \in\mathcal{T}_k^+]\leq \left(p^{\gamma d+c_{\ref{lemma:abc_small}}\log_p(\gamma d)}\right)^k\left(\frac{k}{n}\right)^{k}$.

* $\Pr[A_S \in \mathcal{T}_k^C]\leq \left(p^{\gamma d+c_{\ref{lemma:abc_small}}\log_p(\gamma d)}\right)^k\left(\frac{k}{n}\right)^{k}$.

As for the previous results, the goal of the large domain will be to show that with high probability, $A$ contains no large set of columns that are linearly dependent.

[ABC Large Case]lemmaabclarge
Let $A \sim \textnormal{ABC}_p(n, \gamma, d)$ for some constant $\gamma \geq 16$. Then there exists a constant $d_0(\gamma)$ such that for $d \geq d_0$,

\begin{equation*}
\Pr\left[\exists x: Ax = 0, |\supp(x)| \geq \frac{n}{18e\gamma^2 d^2}\right] \leq o(1).
\end{equation*}

Our main tool in proving this Lemma is an anti-concentration Lemma that is based on the sparse Littlewood-Offord Theorem from [13]. While typically such anti-concentration lemmas concern the dot product of a deterministic vector and a random vector with independent entries, we derive a weaker result which concerns the dot product of a deterministic vector with a vector in which there are a fixed number of non-zero entries whose positions are random.

[Anti-concentration for Sparse Regular Vectors]lemmaacslice
Let $v\in \mathbb{R}^N$ be an arbitrary vector whose most common entry is $a$. Then for any $d \leq \sqrt{\frac{N}{2}}$, if $x \in \{0, 1\}^N$ is sampled uniformly from the set of vectors with exactly $d$ 1s, for any $w\in \mathbb{R}\backslash\{da\}$, we have:
$$\Pr\left[x\cdot v=w\right]\leq 1/2+\frac{d^2}{N}.$$

As $d \rightarrow \infty$, the anti-concentration probability approaches the smaller value of $1/e$, though $1/2$ is tight for $d = 2$.

§.§ Notation and Further Details on Construction of $A \sim \textnormal{ABC}_p(n, \gamma, d)$

The Construction of $A_0$ and $H_0$. In the pictured example, $n = 2$, $\gamma = 2$, $d = 3$.

In our proofs, we will study $A$ via the half-edge pairing process used to construction $A_0$ in Definition <ref>. To do this, we will sometimes explicitly consider the permutation $\rho \in \mathcal{S}_{\gamma d n}$ which defines the random pairing of half-edges. From $\rho$, we can can construct an additional matrix $H_0 = H_0(\rho)$, which we call the column half-edge occupancy matrix . Let $P \in \{0, 1\}^{\gamma d n \times \gamma d n}$ be the permutation matrix of $\rho^{-1}$. From $P$, construct $H_0 \in \{0, 1\}^{\gamma n \times \gamma d n}$ by summing adjacent rows of $P$ corresponding to half-edges of the same row nodes. Symbolically,

$$(H_0)_{ij} = \sum_{k=(i-1)d + 1}^{id} P_{kj}.$$

Note that $H_0$ has $\gamma n$ rows; row $i$ represents row-node $i$ in the configuration model. $H_0$ has $\gamma d n$ columns: columns $(j-1)\gamma d + 1$ through $j\gamma d$ represent the $\gamma d$ half edges of column-node $j$, for $1 \leq j \leq n$. Each row contains exactly $d$ $1$'s, corresponding to that row-node's half edges.

We may write $A_0 = A_0(\rho)$ in terms of the random matrix $H_0$. Because $(A_0)_{ij} = 1$ if and only if there is at least one edge from vertex $i$ to $j$, we have
$$(A_0)_{ij} = \mathbbm{1}(\exists k, d(j-1) < k \leq dj, H_{ik} = 1 ).$$

Recall that when generating a matrix $A \sim \textnormal{ABC}_p(n, \gamma, d)$, we sample $A_0 \sim \textnormal{ABC}(n, \gamma, d)$ and take $A := (A_0)^{[\gamma n(1 - p)]}$ to be the matrix containing the first $\gamma n(1 - p)$ rows of $A_0$. We define $H := H_0^{[\gamma n(1 - p)]}$ to be the first $\gamma n(1-p)$ rows of the row half-edge occupancy matrix associated with $A_0$. For a set $S \subset [n]$ with $|S| = k$, let $H(S) \in \mathbb{R}^{\gamma n(1-p) \times \gamma d k}$ be the matrix $H$ restricted to the $\gamma d k$ columns corresponding to half-edges of the column-nodes in $S$.

§.§.§ Further Notation

We use $\text{HypGeo}(N, K, n)$ to denote the hypergeometric distribution, the random variable which equals the number of successes in $n$ draws, without replacement, from a finite population of size $N$ that contains exactly $K$ objects which are considered successes.

§.§ Small Domain

As noted above, the goal of this section will be to prove the following lemma:

We condition on $L_S$, the number of $1$'s in $H(S)$. We observe that $L_S\sim \text{HypGeo}(\gamma d n, \gamma d(1-p)n, \gamma dk)$. Note that $L_S$ is greater than or equal to the number of entries which are $1$ in the submatrix $A_S$, with equality if and only if there does not exist a column-node in $S$ which pairs multiple half-edges to the same row-node in $[\gamma n (1 - p)]$.

Let $\mathcal{E}_S$ denote the event that there are no rows in $H(S)$ with exactly $1$ one. It follows from Observation <ref> that

$$\Pr[A_S\in \mathcal{S}_{\ell,k}]\leq \Pr[\mathcal{E}_S |L_S=\ell]\cdot\Pr[L_S=\ell].$$

Our general strategy to bound $\Pr[\mathcal{E}_S|L_S = \ell]$ relies on the following claim.

Let $X$ be the number 1s in $H(S)$ which are not the first (leftmost) 1 in their row. If $\mathcal{E}_S$ occurs, then $X \geq L_S/2$.

If $X < L_S/2$, then by the pigeonhole principle, there must be at least one row in $H(S)$ with a leftmost 1 but no 1s to the right of it, ie. this row has exactly one 1.

We will bound the probability that $X$ is large by considering a random walk which this quantity as half-edges are paired one at time. We formalize this random walk as follows.

Conditioned on $L_S$, the matrix $H(S) \in \{0, 1\}^{\gamma n(1-p)\times \gamma d k}$ is distributed like a uniformly random matrix on the set of all matrices in $\{0, 1\}^{\gamma n(1-p)\times \gamma d k}$ with exactly $L_S$ $1$'s and at most one $1$ per column. We construct $H(S)$ via the following random process $M^0, M^1, \ldots , M^{L_S} = H(S)$ on matrices in $\{0, 1\}^{\gamma d k \times \gamma n(1-p)}$, in which the $L_S$ half-edges represented in $H(S)$ are paired one at a time. Formally, at each step $i$, we construct $M^i$ from $M^{i - 1}$ by placing a $1$ in a uniformly random location in $M^{i - 1}$ without a $1$. For $i \in 0, 1, \ldots L_S$, let $X_i$ equal the number of 1s in $M^i$ which are not the first (leftmost) 1 in their row, such that $X_{L_S} = X$.

When placing the $i$-th $1$, there are at most $i-1$ non-zero rows so far. In particular, since $i \leq L_S$, there are at most $L_S$ non-zero rows throughout this process. Because $H(S)$ has $\gamma(1-p)n$ rows, we thus have the bound $\Pr[X_i - X_{i - 1} = 1] \leq \frac{L_S}{\gamma(1-p)n}$.
It follows that the random variable $X$ is first-order stochastically dominated by the random variable $\sum_{i=1}^{L_S} \textnormal{Bernoulli}(\frac{2L_S}{n})$. So in particular, we have:

\begin{align*}
\Pr\left[X\geq \lfloor L_S/2\rfloor \right] &\leq \Pr\left[\Bin\left(L_S, \frac{2L_S}{n}\right) \geq L_S/2 \right],
\end{align*}

which implies

\begin{align*}
\Pr[A_S\in \mathcal{S}_{\ell, k}]&\leq \Pr\left[\Bin\left(\ell, \frac{2\ell}{n}\right) \geq \ell/2 \right]\cdot\Pr[ L_S=\ell].
\end{align*}

We will use the following claim proved in Appendix <ref>:
Let $p<1/2$. There exists constants $c_{\ref{claim:abc1}}$, and $q_0$ such that for all $q \geq q_0$, and $K\leq \min\left(\frac{3}{2}pN, \frac{N}{18eq^2}\right)$, the following two bounds hold.

For $\ell\in \{2K-2,2K-1,2K\}$, and $j \geq \ell/2$, we have:

\begin{align*}
\Pr\left[\Bin\left(\ell, \frac{2\ell}{N}\right)\geq j\right] \Pr[\textnormal{HypGeo}(q N,q(1-p)N,q K)=\ell]\leq \left(p^{q - c_{\ref{claim:abc1}}\log_p(q)}\right)^K \left(\frac{K}{N}\right)^{j}.
\end{align*}

\begin{align*}
\sum_{\ell=2K+1}^{qK}\Pr\left[\Bin\left(\ell, \frac{2\ell}{N}\right)\geq \frac{\ell}{2}\right]\cdot\Pr[\textnormal{HypGeo}(qN,q(1-p)N,qK)=\ell]\leq e^{-k}\left(\frac{K}{N}\right)^{K+1/2}.
\end{align*}

Since $L_S \sim \textnormal{HypGeo}(\gamma d n, \gamma d(1-p)n, \gamma d k)$, it must be the case that $L_S \geq \gamma d k - p\gamma dn.$ Hence if $L_S \in \{2k-2,2k-1,2k\}$, then necessarily $k \leq \frac{p\gamma d n}{\gamma d - 2} \leq \frac{3}{2}pn,$
for $\gamma d \geq 6$, which is guaranteed if $d \geq 6$. Thus we can apply the first bound in Claim <ref> with $K = k$, $N = n$ and $q = \gamma d$ to study $\Pr[A_S\in \mathcal{S}_{\ell, k}] \leq \Pr\left[X \geq \ell/2]\cdot\Pr[ L_S=\ell\right]$, yielding:

\begin{align*}
\Pr[A_S\in \mathcal{S}_{2k-2,k} ]&=\left(p^{\gamma d-c_{\ref{claim:abc1}}\log_p(\gamma d)}\right)^k \left(\frac{k}{n}\right)^{k-1}.\\
\Pr[A_S\in \mathcal{S}_{2k-1,k} ]&=\left(p^{\gamma d- c_{\ref{claim:abc1}}\log_p(\gamma d)}\right)^k \left(\frac{k}{n}\right)^{k}.\\
\Pr[A_S\in \mathcal{S}_{2k,k}']\leq \Pr[A_S\in \mathcal{S}_{2k,k} ]&=\left(p^{\gamma d-c_{\ref{claim:abc1}}\log_p(\gamma d)}\right)^k \left(\frac{k}{n}\right)^{k}.
\end{align*}

We use the equivalences of $\mathcal{S}_{2k - 2, k} = \mathcal{T}_k$, $\mathcal{S}_{2k - 1, k} = \mathcal{T}_k^+$, and $\mathcal{S}_{2k, k}' = \mathcal{T}_k^C$ from Lemma <ref> to yield statements 2, 3, and 4 in this lemma.

Next we obtain a bound on the event that $A_S \in \mathcal{M}_k\backslash (\mathcal{T}_{k}\cup \mathcal{T}_{k}^+\cup \mathcal{T}_{k}^C)$. Observe that

\begin{equation*}
A_S \in \mathcal{M}_k\backslash (\mathcal{T}_{k}\cup \mathcal{T}_{k}^+\cup \mathcal{T}_{k}^C) \Rightarrow A_S \in \left(\mathcal{S}_{2k,k}\setminus \mathcal{S}_{2k,k}'\right) \cup \bigcup_{\ell \geq 2k + 1}\mathcal{S}_{\ell, k}.
\end{equation*}

If $A_S\in \mathcal{S}_{2k,k}\setminus \mathcal{S}_{2k,k}'$, there must be a column with at least three $1$'s. So by a similar argument to Claim <ref>, it must be the case that $X \geq k + 1$. Hence

\begin{align*}