The set of solutions of random XORSAT formulae

Introduction

An instance of XOR-satisfiability (XORSAT) is specified by an integer $n$ (the number of variables) and by a set of $m$ clauses of the form $x_{i_{a}(1)}\oplus\cdots\oplus x_{i_{a}(k)}=b_{a}$ for $a\in[m]\equiv\{1,\ldots,m\}$. Here, $\oplus$ denotes modulo-$2$ sum, $\underline{b}=(b_{1},\ldots,b_{m})$ is a Boolean vector, $b_{a}\in\{0,1\}$, specified by the problem instances, and $\underline{x}=(x_{1},\ldots,x_{n})$ is a vector of Boolean variables $x_{i}\in\{0,1\}$ that must be chosen to satisfy the clauses.

Since ${\mathcal{I}}$ is a random formula, ${\mathcal{S}}$ is a random subset of the Hamming hypercube. The structural properties of ${\mathcal{S}}$ are of interest for several reasons. First of all, linear systems over finite fields are combinatorial objects that emerge naturally in a number of fields. Dietzfelbinger and collaborators Cuckoo use a mapping between XORSAT and the matching problem to establish tight thresholds for the performances of Cuckoo Hashing, an archetypal load balancing scheme. Such thresholds are computed by determining thresholds above which the set of solutions ${\mathcal{S}}$ of a random XORSAT formula becomes empty. The existence of solutions is in turn related to the existence of an even-degree subgraph in a random hypergraph. Random sparse linear systems over finite fields are used to construct capacity achieving error correcting codes Luby98; Luby01; RiUBOOK. The decodability of such codes is related to the emergence of a nontrivial $2$-core in the same random hypergraph—a phenomenon that will play a crucial role in the following. Finally, structured linear systems over finite fields are generated by popular factoring algorithms Factorization.

In the present paper, we are also motivated by the close analogy between random $k$-XORSAT and other random ensembles of constraint satisfaction problems (CSPs). The prototypical example of this family is random $k$-satisfiability ($k$-SAT). The random $k$-SAT ensemble can be described in complete analogy to random $k$-XORSAT with the modification of replacing exclusive OR clauses by OR clauses among variables or their negations. Namely, in $k$-SAT each clause takes the form $(x_{i_{a}(1)}^{\prime}\vee\cdots\vee x_{i_{a}(k)}^{\prime})$,

In this paper, we obtain two sharp results characterizing the clustering phase transition for random $k$-XORSAT:

We determine the exponential growth rate of the number of clusters, that is, we show that this is w.h.p. $\exp\{n\Sigma(\alpha;k)+o(n)\}$ where $\Sigma(\alpha;k)$ is a nonrandom function which is explicitly given. We prove that each of the clusters is itself “well connected.”

This is therefore the first random CSP ensemble for which a sharp threshold for clustering is proved.

where, for a graph ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$, and any $B\subseteq{\mathcal{V}}$, we define

We define the distance between two subsets of the hypercube ${\mathcal{S}}_{1},{\mathcal{S}}_{2}\subseteq\{0,1\}^{n}$ as

For our statements, $k\geq 3$ is always fixed, together with a sequence $m(n)=\alpha n$.

For each $a\in[N]$, we have $\Phi({\mathcal{S}}_{a};(\log n)^{C})\geq 1/2$.

For each $a\neq b\in[N]$, we have $d({\mathcal{S}}_{a},{\mathcal{S}}_{b})\geq n\varepsilon$.

$\exp\{n(\Sigma-\delta)\}\leq N\leq\exp\{n(\Sigma+\delta)\}$. Further, letting $Q$ be the largest positive solution of $Q=1-\exp\{-k\alpha Q^{k-1}\}$ and $\widehat{Q}\equiv Q^{k-1}$, we have $\Sigma(\alpha,k)=Q-k\alpha\widehat{Q}+(k-1)\alpha Q\widehat{Q}$.

2 Conductance and sparse basis

Given a linear subspace ${\mathcal{S}}\subseteq\{0,1\}^{n}$, we say that it admits an $s$-sparse basis if there exist vectors $\underline{x}^{(l)}\in{\mathcal{S}}$ for $l\in\{1,\ldots,D\}$ such that $d(\underline{x}^{(l)},\underline{0})\leq s$ and $(\underline{x}^{(l)})_{l=0}^{D}$ form a basis for ${\mathcal{S}}$. The latter means that the vectors are linearly independent and ${\mathcal{S}}=\{\sum_{l=1}^{D}a_{l}\underline{x}^{(l)}\colon\;(a_{l})_{l=0}^{D}\in\{0,1\}^{D}\}$.

We say that an affine space ${\mathcal{S}}\subseteq\{0,1\}^{n}$ admits an $s$-sparse basis if, for $\underline{x}^{(0)}\in{\mathcal{S}}$, the linear subspace ${\mathcal{S}}-\underline{x}^{(0)}$ admits an $s$-sparse basis. The property of having a sparse basis indeed implies large conductance. The proof is immediate.

If the affine subspace ${\mathcal{S}}\subseteq\{0,1\}^{n}$ admits a $s$-sparse basis, then $\Phi({\mathcal{S}};s)\geq 1/2$.

Vice versa, assume that $\Phi({\mathcal{S}};s)=0$. Then ${\mathcal{S}}$ does not admit a $s$-sparse basis.

We can assume, without loss of generality, that ${\mathcal{S}}$ is a linear space. Let $d$ be its dimension. Further, given a graph ${\mathcal{G}}$, let, with a slight abuse of notation

Assume that ${\mathcal{S}}$ admits a $s$-sparse basis. This immediately implies the graph ${\mathcal{G}}({\mathcal{S}},s)$ contains a spanning subgraph that is isomorphic to the $d$-dimensional hypercube ${\mathcal{H}}_{d}$. Further, ${\mathcal{G}}\mapsto\Phi({\mathcal{G}})$ is monotone increasing in the edge set of ${\mathcal{G}}$. Therefore, $\Phi({\mathcal{S}};s)\geq\Phi({\mathcal{H}}_{d})\geq 1/2$ where the last inequality follows from the standard isoperimetric inequality on the hypercube Hoory.

The characterization of the solution space in terms of sparsity of its basis is given below.

For each $a\in[N]$, ${\mathcal{S}}_{a}$ admits a $(\log n)^{C}$-sparse basis.

For each $a\neq b\in[N]$ we have $d({\mathcal{S}}_{a},{\mathcal{S}}_{b})\geq n\varepsilon$.

$\exp\{n(\Sigma-\delta)\}\leq N\leq\exp\{n(\Sigma+\delta)\}$. Further, $\Sigma$ is given by the same expression given in Theorem 1.

Clearly, this theorem immediately implies Theorem 1 by applying Lemma 1.1. The rest of this paper is devoted to the proof of Theorem 2.

3 Further technical contributions

To a given a XORSAT instance ${\mathcal{I}}$, we can associate a bipartite graph (“factor graph”) with vertex sets $F$ (factor or check nodes) corresponding to equations, and $V$ (variable nodes) variables. The edge set $E$ includes those pairs $(a,i)\in F\times V$ such that variable $x_{i}$ participates in the $a$th equation. The construction of the sparse basis in Theorem 2 relies heavily on a characterization of the random factor graph associated to a random XORSAT instance. This could be gleaned from the proof of DuboisFOCS; Cuckoo that construct the $2$-core of $G$. In order to prove Theorem 2, we characterize a larger subgraph that we refer to as the backbone of $G$. This subgraph has the following interpretation: if two solutions $\underline{x}$ and $\underline{x}^{\prime}$ coincide on the core, then they coincide on every vertex of the backbone.

Our analysis of the backbone has a similar starting point, namely the study of an iterative procedure that constructs the backbone (indeed we define formally the backbone as the fixed point of this procedure). Unfortunately, the graphs generated by this procedure are not uniformly random, conditional on a small number of parameters. Hence, the techniques PittelSpencerWormald; Luby98; Molloy; DemboFSS do not apply. We overcome this difficulty by characterizing the large-$n$ limit of its fixed point using the theory of local weak convergence. This is in turn challenging because the fixed point is not, a priori, a local function of $G$.

We consider this characterization of the backbone, and its proof, to be a contribution of independent interest.

We next construct a random tree $\widetilde{\mathcal{T}}_{*}(\alpha,k)$ with marks on the directed edges as follows. Marks take values in $\{0,*\}$ and to each undirected edge we associate a mark for each of the two directions. We will refer to the direction toward the root as to the “upward” direction, and to the opposite one as to the “downward” direction. The marks correspond to fixed-point BP messages, and we will call them messages as well in what follows. First, consider only edges directed upward. This is a multitype Galton–Watson (GW) tree. At the root generate $\operatorname{Poisson}(k\alpha)$ offsprings, and mark each of the edges to $0$ independently with probability $\widehat{Q}$, and to $*$ otherwise. At a nonroot variable node, if the parent edge is marked $0$, generate $\operatorname{Poisson}(k\alpha(1-\widehat{Q}))$ descendant edges marked $*$ and $\operatorname{Poisson}_{\geq 1}(k\alpha\widehat{Q})$ descendant edges marked $0$ [here $\operatorname{Poisson}_{\mathsf{E}}(\lambda)$ denotes a Poisson random variable with parameter $\lambda$ conditional on $\mathsf{E}$]. If the parent edge is marked $*$, generate $\operatorname{Poisson}(k\alpha(1-\widehat{Q}))$ descendant edges marked $*$ and no descendant edges marked $0$. At a factor node, if the parent edge is marked $0$, generate $k-1$ descendant edges marked $0$. If the parent node is marked $*$, generate $M\sim\operatorname{Binom}_{\leq k-2}(k-1,Q)$ descendants marked $0$, and $k-1-M$ descendants marked $*$.

For edges directed downward, marks are generated recursively following the usual BP rules, cf. equations (4), (5), starting from the top to the bottom. It is easy to check that with this construction, the marks in $\widetilde{\mathcal{T}}_{*}(\alpha,k)$ correspond to a BP fixed point. Given a factor graph $G=(F,V,E)$, we use $\mathsf{B}_{G}(v,t)$ to denote the ball of radius $t$ centered at node $v\in V$. This ball is defined inductively as follows: The $\mathsf{B}_{G}(v,0)$ consists of node $v$ alone and no edges. For $t>0$, the $\mathsf{B}_{G}(v,t)$ includes $\mathsf{B}_{G}(v,t-1)$. In addition, it includes all factor nodes connected to variable nodes in $\mathsf{B}_{G}(v,t-1)$ and associated edges, and all variable nodes connected to those factor nodes and associated edges. [Thus, $\mathsf{B}_{G}(v,t)$ includes nodes and edges up to a distance $t$ from $v$, where variable nodes are said to be separated by distance $1$ if they are connected to the same factor node.]

Let $\{G_{n}\}$, $G_{n}=(F_{n},V_{n},E_{n})$ be a sequence of (random) factor graphs. Let $\mu_{n}^{(t)}$ denote the empirical probability distribution of $\mathsf{B}_{G_{n}}(v,t)$ when $v\in V_{n}$ is uniformly random. Explicitly, for any locally finite rooted graph ${\mathcal{T}}_{0}$ of depth at most $t$,

(with $\simeq$ denoting equality up to graph vertex relabeling.) We say that $\{G_{n}\}$ converges locally almost surely to the measure $\mu$ on rooted graphs if, for any finite $t$, and any locally finite rooted graph ${\mathcal{T}}_{0}$ of depth at most $t$, we have

holds almost surely with respect to the graph law. Here, $\mu^{(t)}$ denotes the marginal of $\mu$ with respect to a ball of radius $t$ around the root.

As part of our proof of Theorem 2, we obtain the following result, which may be of independent interest. (We refer to the next section for a complete definition of the underlying probability space.)

Besides this, our proof uses several other ideas:

We show that Theorem 3 can be used to extend the low weight core solutions to low weight solutions of the whole XORSAT instance (see Section 8).

We show that the periphery (the complement of the core in $G$) is uniformly random with a given degree sequence, conditioned on being “peelable.” We estimate precisely this degree distribution, and show that the periphery is indeed peelable with positive probability for that degree sequence (see Section 6).

4 Outline of the paper

In Section 2, we define some basic concepts and notation. Section 3 describes the construction of clusters and sparse bases, and uses this construction to prove Theorem 2. Several basic lemmas necessary for the proof are stated in this section.

Section 4 introduces a certain belief propagation (BP) algorithm and a technical tool called density evolution, that play a key role in our analysis: The BP algorithm naturally decomposes the linear system into a “backbone” (consisting roughly of the 2-core and the variables implied by it) and a “periphery.” Density evolution allows us to track the progress of BP, eventually facilitating a tight characterization of basic parameters (like number of nodes) of the backbone and periphery.

Section 5 bounds the number of iterations of a “peeling” algorithm (related to BP) that plays a key role in our construction of a sparse basis. Section 6 proves a sharp characterization of the periphery. Together, this yields the first (large) set of basis vectors.

Section 7 shows the 2-core has very few sparse solutions, leading to well separated, small, “core-clusters.” Section 8 shows how to produce a sparse solution of the linear system corresponding to each sparse solution of the 2-core subsystem. This yields the second (small) set of basis vectors in our construction.

Several technical lemmas are deferred to the Appendices.

A short version of this paper was presented at the ACM-SIAM Symposium on Discrete Algorithms SODA 2012.

Random kk-XORSAT: Definitions and notation

Let $F_{0}\subseteq F$. The subgraph induced by $F_{0}$ is defined as $(F_{0},V_{0},E_{0})$ where $V_{0}\equiv\{i\in V\colon\;{\partial i}\cap F_{0}\neq\varnothing\}$ and $E_{0}\equiv\{(a,i)\in E\colon\;a\in F_{0},i\in V_{0}\}$. A check-induced subgraph is the subgraph $(F_{0},V_{0},E_{0})$ induced by some $F_{0}\subseteq F$. Similarly, we can define the subgraph induced by $V_{0}\subseteq V$, and variable-induced subgraphs.

Let $F_{0}\subseteq F$, $V_{0}\subseteq V$. The subgraph induced by $(F_{0},V_{0})$ is defined as $(F_{0},V_{0},E_{0})$ where $E_{0}\equiv\{(a,i)\in E\colon\;a\in F_{0},i\in V_{0}\}$.

A stopping set is a check-induced subgraph with the property that every variable node has degree larger than one with respect to the subgraph. The $2$-core of $G$ is its maximal stopping set.

Notice that the maximal stopping set of $G$ is uniquely defined because the union of two stopping sets is a stopping set.

Note that, with this probability space, the notion of local almost sure convergence in Definition 1.2 is well defined. Note that our main results (Theorems 1 and 2) are “with high probability results,” and hence do not require the definition of a common probability space for different graph sizes. This is indeed mainly a matter of technical convenience (and is of course needed for Theorem 3).

We will often refer to the depth-$t$ neighborhood of a node $v$ in $G$.

Given a node $v\in V$ and an integer $t$, let $V^{\prime}=\{u\colon\;u\in V,d_{G}(u,v)\leq t\}$. Then the ball of radius $t$ around node $v$ is defined as the (variable-induced) subgraph $\mathsf{B}_{G}({v},{t})$ induced by $V^{\prime}$. With an abuse of notation, we will use the same notation for the set of variable nodes in $\mathsf{B}_{G}({v},{t})$. Lastly, we define $|\mathsf{B}_{G}({v},{t})|$ to be the number of variable nodes in the subgraph $\mathsf{B}_{G}({v},{t})$.

We will occasionally work with certain random infinite rooted factor graphs, with marks on the edges or vertices. (Note that a factor graph can be regarded as an ordinary graph, with additional marks on the vertices to distinguish “variable nodes” from “factor nodes.”) A useful concept in this context is the one of “unimodular” random rooted graphs, that we briefly recall next. For a more complete presentation, we refer to the overview paper by Aldous and Lyons AldousLyonsUnimodular.

Informally, a random rooted (marked) graph is unimodular if it looks the same (in distribution), when the root is moved to any other vertex. In order to formalize this notion, we denote by ${\mathcal{G}}_{*}$ the space of locally finite rooted graphs, with marks on the vertices or edges (we assume marks to belong to some fixed finite set for simplicity). We view two graphs that differ by an isomorphism as identical. This space can be endowed by a metric that metrizes local convergence, and hence a Borel $\sigma$-algera.

Analogously, we denote by ${\mathcal{G}}_{**}$ the space of doubly rooted graphs [a doubly rooted graph is a graph with two distinguished vertices, i.e., a triple $(G,u,v)$ where $G=(V,E)$ is a graph, and $u,v\in V$]. As for the simply rooted case, ${\mathcal{G}}_{**}$ can be made into a complete metric space; we regard it as a measurable space endowed with the Borel $\sigma$-algebra.

Consequences, and equivalent versions of unimodularity can be found in AldousLyonsUnimodular; MontanariStFlour.

Proof of Theorem 2

The construction of a sparse basis, which is at the heart of Theorem 2, is based on the following algorithm, formally stated in Table 1. The algorithm constructs a sequence of residual factor graphs $(J_{t})_{t\geq 0}$, starting with the instance under consideration $J_{0}=G$. At each step, the new graph is constructed by removing all variable nodes of degree one or zero, their adjacent factor nodes, and all the edges adjacent to these factor nodes. We refer to the algorithm as synchronous peeling or simply peeling.

We denote the sets of nodes and edges removed at step (or round) $t\geq 1$ by $(F_{t},V_{t},E_{t})$, so that $J_{t-1}=(F_{t},V_{t},E_{t})\cup J_{t}$. Notice that, at each step, the residual graph $J_{t}$ is check-induced. The algorithm halts when the residual graph does not contain any variable node of degree smaller than two. We let the total number of iterations be $T_{\mathtt{C}}(G)$, where we will drop the explicit dependence on $G$ when it is clear from context. The final residual graph is then $J_{T_{\mathtt{C}}}\equiv G_{\mathtt{C}}$. The following elementary fact is used in several papers on this topic Luby98; Molloy; DemboFSS.

The residual graph $G_{\mathtt{C}}$ resulting at the end of synchronous peeling is the $2$-core of $G$.

It is convenient to reorder the factors (from $1$ to $m$) and variables (from $1$ to $n$) as follows. We index the factors in increasing order according to $F_{1},F_{2},\ldots,F_{T_{\mathtt{C}}}$, choosing an arbitrary order within each $F_{t}$ for $1\leq t\leq T_{\mathtt{C}}$.

Note that $V_{t}$ is not empty and $F_{t}$ is not empty for all $t<T_{\mathtt{C}}$. On the other hand, $F_{T_{\mathtt{C}}}$ may be empty, in which case, we adopt the convention that all columns corresponding to $V_{T_{\mathtt{C}}}$ are included in ${\mathcal{C}}_{0}$.

The collapsed graph $G_{*}=(F_{*},V_{*},E_{*})$ of a graph $G=(F,V,E)$ is the graph of connected components in the subgraph induced by factor nodes of degree $2$. Formally,

where $G^{(2)}$ is the subgraph of $G$ induced by factor nodes of degree $2$. We let $n_{*}\equiv|V_{*}|$, $m_{*}\equiv|F_{*}|$. An element of $V_{*}$ is referred to as a supernode.

The following is the key deterministic lemma on the construction of the basis. We denote the size of the component of $v\in V_{*}$ in $G^{(2)}$ by $S(v)$, and for $v\in V_{*}$, $t\geq 0$ we let $S(v,t)=\sum_{w\in\mathsf{B}_{G_{*}}(v,t)}S(w)$ be the sum of sizes of vertices within distance $t$ from $v$.

Assume that $G_{*}$ has no $2$-core, then the columns of

The proof of Lemma 3.4 is presented in the Appendix A.

2 Construction of the cluster decomposition

with $\{{\mathcal{S}}({\underline{x}_{\mathtt{C}}})\}_{{\underline{x}_{\mathtt{C}}}\in{\mathcal{S}}_{\mathtt{C}}}$ forming a partition of ${\mathcal{S}}$.

It turns out that $\{{\mathcal{S}}({\underline{x}_{\mathtt{C}}})\}_{{\underline{x}_{\mathtt{C}}}\in{\mathcal{S}}_{\mathtt{C}}}$ is not exactly the partition of ${\mathcal{S}}$ that we seek. In our next lemma, we show that the set of solutions of the core ${\mathcal{S}}_{\mathtt{C}}$ can be partitioned in well-separated core-clusters. Moreover, the core-clusters are small and have a high conductance. We will form sets in our partition of ${\mathcal{S}}$ by taking the union of ${\mathcal{S}}({\underline{x}_{\mathtt{C}}})$ over ${\underline{x}_{\mathtt{C}}}$ that lie in a particular core-cluster.

We write $\underline{x}^{\prime}\preceq\underline{x}$ for binary vectors $\underline{x}^{\prime},\underline{x}$ if $x^{\prime}_{i}\leq x_{i}$ for all $i$. We write $\underline{x}^{\prime}\prec\underline{x}$ if $\underline{x}^{\prime}\preceq\underline{x}$ and $\underline{x}^{\prime}\neq\underline{x}$. We need the following definition:

We partition the set ${\mathcal{S}}_{\mathtt{C}}$ of core solutions in disjoint core-clusters, as follows. For $\underline{x},\underline{x}^{\prime}\in{\mathcal{S}}_{\mathtt{C}}$, we write $\underline{x}\simeq\underline{x}^{\prime}$ if $\underline{x}\oplus\underline{x}^{\prime}\in\operatorname{span}({\mathcal{L}}_{\mathtt{C}}(\varepsilon n))$. It is immediate to see that $\simeq$ is an equivalence relation. We define the core-clusters to be the equivalence classes of $\simeq$. Obviously, the core clusters are affine spaces that differ by a translation, each containing $g\leq 2^{s_{n}}$ solutions. Their number is to be denoted by $N$. Denote the core-clusters by ${\mathcal{S}}_{\mathtt{C},1},{\mathcal{S}}_{\mathtt{C},2},\ldots,{\mathcal{S}}_{\mathtt{C},N}$. Note that for any $\underline{x},\underline{x}^{\prime}\in{\mathcal{S}}_{\mathtt{C}}$ belonging to different core-clusters, we have $d(\underline{x},\underline{x}^{\prime})>n\varepsilon$, that is, the core-clusters are well separated. We use the following partition of the solution space (including noncore variables) ${\mathcal{S}}$ into clusters, based on the core-clusters defined above:

A version of Lemma 3.5 was claimed in MezRicZec_XOR; CoccoXOR; MM09. These papers capture the essence of the proof but miss some technical details, and make the erroneous claim that, w.h.p. each pair of core solutions is separated by Hamming distance $\Omega(n)$.

We next want to study the internal structure of clusters. By linearity, it is sufficient to consider only one of them, say ${\mathcal{S}}_{1}$, which we can take to contain the origin $\underline{0}$. For any $\underline{x}\in{\mathcal{S}}_{1}$, we have $P_{G}\underline{x}\in{\mathcal{S}}_{\mathtt{C},1}=\operatorname{span}({\mathcal{L}}_{\mathtt{C}}(\varepsilon n))$, and ${\mathcal{L}}_{\mathtt{C}}(\varepsilon n)$ forms a $s_{n}$-sparse basis for ${\mathcal{S}}_{\mathtt{C},1}$, which coincides with the projection of ${\mathcal{S}}_{1}$ onto the core. Consider the subset of solutions $\underline{x}\in{\mathcal{S}}$, such that $P_{G}\underline{x}={\underline{x}_{\mathtt{C}}}$ for some ${\underline{x}_{\mathtt{C}}}\in{\mathcal{S}}_{\mathtt{C},1}$. The set of variables that take the same value for all solutions in this set is strictly larger than the $2$-core. In order to capture this remark, we define the backbone (variables that are uniquely determined by the core assignment) and periphery (other variables) of a graph $G$.

The backbone $G_{\mathtt{B}}=(F_{\mathtt{B}},V_{\mathtt{B}},E_{\mathtt{B}})$ of a graph $G=(F,V,E)$ is the output of backbone augmentation procedure on $G$ with the initial subgraph $G_{\mathtt{C}}$, the 2-core of the graph $G$.

The periphery $G_{\mathtt{P}}$ of a graph $G=(F,V,E)$ is the subgraph induced by the factor nodes $F_{\mathtt{P}}=F\setminus F_{\mathtt{B}}$ and variable nodes $V_{\mathtt{P}}=V\setminus V_{\mathtt{B}}$ that are not in the backbone. Notice that there may be a few variables (w.h.p. at most a constant number) in the periphery that also are uniquely determined by the core assignment.

We can now define our basis for ${\mathcal{S}}_{1}$. This is formed by two sets of vectors. The first set has a vector corresponding to each element of ${\mathcal{L}}_{\mathtt{C}}(\varepsilon n)$. For each ${\underline{x}_{\mathtt{C}}}\in{\mathcal{L}}_{\mathtt{C}}(\varepsilon n)$, we construct a sparse solution $\underline{x}\in{\mathcal{S}}_{1}$ such that $P_{G}\underline{x}={\underline{x}_{\mathtt{C}}}$ (Lemma 3.8 below guarantees the existence of such a vector, and bounds its sparsity). This set of vectors forms a basis for the projection of ${\mathcal{S}}_{1}$ onto the backbone.

The first set of vectors is characterized as below (see Section 8 for a proof).

3 Analysis of the construction

The main challenge in proving Theorem 2 is bounding the sparsity of the bases constructed (either for the full set of solutions, when $G$ does not have a core, or for the cluster ${\mathcal{S}}_{1}$, when $G$ has a core). This involves two type of estimates: the first one uses Lemma 3.4, while the second is stated as Lemma 3.8. In the first estimate, we need to bound all the quantities involved in the sparsity upper bound: the number of iterations $T$ after which peeling (on the collapsed graph $G_{*}$) halts, and the maximum size $\max_{v\in V_{*}}S(v,T)$ of any ball of radius $T$ in the collapsed graph. In particular, we will show that, w.h.p., we have $T=O(\log\log n)$, and that $\max_{v\in V_{*}}S(v,T)\leq(\log n)^{C}$ w.h.p., which gives sparsity $s\leq(\log n)^{C}$.

Proving these bounds turns out to be a relatively simpler task when $G$ does not have a $2$-core, partly because the graph in question has no factor nodes of degree $2$, and thus the collapse procedure is not needed. A second reason is that when $G$ has a $2$-core, we need to apply Lemma 3.4 to the periphery subgraph as discussed above. Remarkably, the periphery graph admits a relatively explicit probabilistic characterization. We say that a graph is peelable if its core is empty, and hence the peeling procedure halts with the empty graph. It turns out that, conditional on the degree distribution, the periphery is uniformly random among all peelable graphs.

Such an explicit characterization is not available, however, when we consider the subgraph obtained by removing the core (the periphery is obtained by removing the entire backbone). Nevertheless, the proof of Lemma 3.8 requires the study of this more complex subgraph. We overcome this problem by using tools from the theory of local weak convergence BenjaminiSchramm; AldousSteele; AldousLyonsUnimodular.

The above lemma establishes that the periphery is roughly uniform, conditional on being peelable. Its proof is in Section 6.1.

Lemma 3.11 below accomplishes steps $(1)$ and $(3)$, while Lemma 3.12 takes care of step $(2)$. In order to state these lemmas, it is convenient to introduce density evolution (the terminology comes from the analysis of sparse graph codes Luby98; Luby01; RiUBOOK).

Given $\alpha>0$, a degree profile $R$, and an initial condition $z_{0}\in$, we define the density evolution sequence $\{z_{t}\}_{t\geq 0}$ by letting for any $t\geq 1$,

Whenever not specified, the initial condition will be assumed to be $z_{0}=1$. The one-dimensional recursion (14) will be also called density evolution recursion.

We say the pair $(\alpha,R)$ is peelable at rate $\eta$ for $\eta>0$ if $z_{t}\leq(1-\eta)^{t}/\eta$ for all $t\geq 0$. We say that the pair $(\alpha,R)$ is exponentially peelable (for short peelable) if there exists $\eta>0$ such that it is peelable at rate $\eta$.

The density evolution recursion (14) describes the large graph asymptotics of a certain belief propagation algorithm that captures the peeling process, and will be described Section 4.

The graph $G$ is peelable with probability at least $\delta$. Further, if $R_{2}=0$, one can take $\delta$ arbitrary close to $1$ (in other words $G$ is peelable w.h.p.).

Conditional on $G$ being peelable, peeling on the collapsed graph $G_{*}$ terminates after $T\leq C_{1}\log\log n$ iterations, with probability at least $1-n^{-1/2}$.

Our final lemma is proved in Section 6.2 and establishes the peelability condition for the periphery.

4 Putting everything together

At this point, we can formally summarize the proof of our main result, Theorem 2, that builds on the construction and analysis provided so far.

2(a). By construction, it is sufficient to construct a basis of the cluster ${\mathcal{S}}_{1}$ containing the origin, cf. Section 3.2. The basis has two sets of vectors.

We are left with the task of proving that the second set of basis vectors is sparse. The construction in Lemma 3.4 proceeds by collapsing the periphery graph $G_{\mathtt{P}}$, and applying peeling. We thus need to bound the sparsity $s=\max_{v\in V}S(v,T_{\mathtt{C}})$. Define the event (implicitly indexed by $n$)

By Lemma 3.12, we know that $\mathsf{E}_{1}$ holds with high probability for suitable choices of $\eta=\eta(k,\alpha)>0$ and $\gamma_{*}=\gamma_{*}(\alpha,k)>0$. Further $R^{\mathtt{P}}_{0}=R^{\mathtt{P}}_{1}=0$ with probability $1$.

Since $\mathsf{E}_{1}$ holds for $G_{\mathtt{P}}$ w.h.p., and since $G^{\prime}$ is peelable with probability uniformly bounded away from zero, it follows that the same bound on the sparsity holds for $G_{\mathtt{P}}$ as well. In other words, w.h.p., we have that

Here, $V_{\mathtt{P,*}}$ is the set of super-nodes resulting from the collapse of $G_{\mathtt{P}}$. Finally, using Lemma 3.4, we deduce that the second set of basis vectors obtained from this construction is $s$-sparse for $s=(\log n)^{C}$.

2(b). By Lemma 3.5, w.h.p., for any two core solutions ${\underline{x}_{\mathtt{C}}}\in{\mathcal{S}}_{\mathtt{C},1}$, ${\underline{x}_{\mathtt{C}}}^{\prime}\in{\mathcal{S}}_{\mathtt{C},b}$, $b\neq 1$ we have $d({\underline{x}_{\mathtt{C}}},{\underline{x}_{\mathtt{C}}}^{\prime})\geq n\varepsilon$. This immediately implies $d(\underline{x},\underline{x}^{\prime})\geq n\varepsilon$, for any two solutions $\underline{x}\in{\mathcal{S}}_{1}$, $\underline{x}^{\prime}\in{\mathcal{S}}\setminus{\mathcal{S}}_{1}$. By linearity, we conclude $d({\mathcal{S}}_{a},{\mathcal{S}}_{b})\geq n\varepsilon$ for all $a,b$.

A belief propagation algorithm and density evolution

A useful analysis tool is provided by a belief propagation algorithm [cf. equations (4) and (5)] that refines the peeling algorithm introduced in Section 3.1. The same algorithm is also of interest in iterative coding; see RiUBOOK; MM09.

We restate the BP update rules for the convenience of the reader.

The belief propagation algorithm introduced here enjoys an important monotonicity property. More precisely, define a partial ordering between message vectors by letting $0\succ*$ and $\underline{\nu}\succeq\underline{\nu}^{\prime}$ if $\nu_{{v}\rightarrow{a}}\succeq\nu_{{v}\rightarrow{a}}^{\prime}$ and $\widehat{\nu}_{{a}\rightarrow{v}}\succeq\widehat{\nu}_{{a}\rightarrow{v}}$ for all $(a,v)\in E$.

Given two states $\underline{\nu}^{t}_{1}\succeq\underline{\nu}^{t}_{2}$, we have $\underline{\nu}^{t^{\prime}}_{1}\succeq\underline{\nu}^{t^{\prime}}_{2}$ and $\underline{\widehat{\nu}}^{t^{\prime}}_{1}\succeq\underline{\widehat{\nu}}^{t^{\prime}}_{2}$ at all $t^{\prime}\geq t$.

$v\in V_{\mathtt{C}}$ if and only if $v$ receives two or more incoming $0$ messages under $\underline{\widehat{\nu}}^{\infty}$,

$v\in V_{\mathtt{B}}\setminus V_{\mathtt{C}}$ if and only if $v$ receives exactly one incoming $0$ message under $\underline{\widehat{\nu}}^{\infty}$,

$v\in V_{\mathtt{P}}$ if and only if $v$ receives no incoming $0$ messages under $\underline{\widehat{\nu}}^{\infty}$.

$a\in F_{\mathtt{C}}$ if and only if $a$ receives no incoming $*$ message under $\underline{{\nu}}^{\infty}$,

$a\in F_{\mathtt{B}}\setminus F_{\mathtt{C}}$ if and only if $a$ receives one incoming $*$ message under $\underline{{\nu}}^{\infty}$,

$a\in F_{\mathtt{P}}$ if and only if $a$ receives two or more incoming $*$ messages under $\underline{{\nu}}^{\infty}$.

Finally, $G_{\mathtt{C}}$ is the subgraph induced by $(F_{\mathtt{C}},V_{\mathtt{C}})$ and similarly for $G_{\mathtt{B}}$ and $G_{\mathtt{P}}$.

The proofs of the last two lemmas are based on a straightforward case-by-case analysis, and we omit them. (In fact, this correspondence is well known in iterative coding, albeit in a somewhat different language RiUBOOK.)

An important tool in the following will be the notion of almost sure local convergence of graph sequences. We made this notion precise in Definition 1.2, following DemboMontanariBrazil.

We now return to the distribution of BP messages and density evolution.

Then for any fixed $t\geq 0$, the following occurs almost surely:

where $X_{0}\sim\operatorname{Poisson}(R^{\prime}(1)\alpha\widehat{z}_{t})$, $X_{*}\sim\operatorname{Poisson}(R^{\prime}(1)\alpha(1-\widehat{z}_{t}))$ are two independent Poisson random variables.

Messages are local functions of the graph, hence their distribution converges to the one on the limit tree. In particular, incoming messages on the same node are asymptotically independent because they depend on distinct subtrees. The message distribution can be computed through a standard tree recursion (see RiUBOOK; MM09) that coincides with the density evolution recursion (14).

For the sake of simplicity, let us consider $n_{1}(J_{t})$. By Lemma 4.2, a node $v$ has degree $1$ in the residual graph $J_{t}$ if and only if there is one incoming $0$ message to $v$ at time $t$, and there were two or more incoming $0$ messages to $v$ at time $t-1$. By Lemma 4.5, the number of incoming $0$ messages to $v$ at time $t$ converges in distribution to $Z_{1}\sim\operatorname{Poisson}(\omega\widehat{z}_{t})$. Using monotonicity of the algorithm, and again Lemma 4.5, the number of incident edges such that the message incoming to $v$ at time $t-1$ is $0$ but changes to $*$ at time $t$, converges to $Z_{2}\sim\operatorname{Poisson}(\omega(\widehat{z}_{t-1}-\widehat{z}_{t}))$, and is asymptotically independent of the number of $0$ messages (converging to $Z_{1}$). Therefore, $n_{1,t}/n$ converges as $n\to\infty$ to

2 BP fixed points

Let $\{z_{t}\}_{t\geq 0}$ be the density evolution sequence defined by equation (14) with initial condition $z_{0}=1$. Then $t\mapsto z_{t}$ is monotone decreasing, and hence has a limit $Q\equiv\lim_{t\to\infty}z_{t}$ which is given by

Monotonicity follows from the fact that $z\mapsto f(z)\equiv 1-\penalty\exp\{-\alpha R^{\prime}(z)\}$ is monotone increasing, and that $z_{1}=1-\exp\{-\alpha R^{\prime}(1)\}<z_{0}$, whence $z_{2}=f(z_{1})\leq f(z_{0})=z_{1}$, and so on. Notice that the definition of $Q$ given in this lemma is consistent with the one in Theorem 1, that corresponds to the special case of regular, degree-$k$ check nodes, that is, $R(x)=x^{k}$. We further let $\widehat{Q}\equiv R^{\prime}(Q)/R^{\prime}(1)$.

The following occurs with probability $1$:

where $X_{0}\sim\operatorname{Poisson}(k\alpha\widehat{Q})$, $X_{*}\sim\operatorname{Poisson}(k\alpha(1-\widehat{Q}))$ are two independent Poisson random variables.

Our final lemma is a straightforward consequence of Lemmas 4.5 and 4.8 above.

Let $N^{t}(n)$ be the fraction of variable-to-check messages that are equal to $0$ after $t$ iterations on $G_{n}$ (with $t=\infty$ corresponding to the fixed point). Then equations (15) and (22) imply that

3 Proof of Lemma 4.8

Throughout this section, the notion of convergence adopted is convergence locally (cf. Definition 1.2).

With probability $1$ with respect to the choice of $(G_{n})_{n\geq 0}$, we have for all $l\geq 0$,

Using Lemma 4.5 (and using the fact that $L_{l}\leq C\exp(-l/C)$ for all $l$ holds eventually almost surely, for some $C<\infty$) we have,

Fix an arbitrary $\delta>0$. Lemma 4.7 implies that, for $t$ large enough,

holds almost surely. Since $\delta$ is arbitrary, we obtain the claimed result.

Let $\mu_{n}\equiv\mu(G_{n})$ be the measure on rooted factor graphs with marks (called “networks” in AldousLyonsUnimodular), constructed as follows: Choose a uniformly random variable node $i\in V_{n}$ as root. Mark variable nodes with mark $\mathsf{c}$ if they are in the 2-core of $G_{n}$.

The sequence $\{\mu_{n}\}_{n\geq 0}$ converges locally to the measure on random rooted tree with marks, ${\mathcal{T}}_{*}(\alpha,k)$, defined as follows. Construct a random bipartite Galton–Watson tree rooted at $\varnothing$ with offspring distribution $\operatorname{Poisson}(k\alpha)$ at variable nodes and deterministic $k-1$ at factor notes. Let $V_{\mathtt{C}}({\mathcal{T}}_{*})$ be the maximal subset of its vertices such that each variable node has degree at least $2$ and each factor node has degree $k$ in the induced subgraph. Mark with $\mathsf{c}$ all vertices in $V_{\mathtt{C}}({\mathcal{T}}_{*})$.

We will prove the thesis by a standard weak convergence argument Kallenberg: We will show that for any subsequence of $\{\mu_{n})\}_{n\geq 0}$, there is a sub-subsequence that converges locally weakly to the measure on ${\mathcal{T}}_{*}(\alpha,k)$.

Recall that a stopping set is any subset of variable nodes of a factor graph, such that each variable node has degree at least $2$ in the induced subgraph. The $2$-core of the factor graph is the maximal stopping set and is a superset of any stopping set. These notions are well defined for infinite graphs as well.

Now, the marks in ${\mathcal{T}}_{*}$ correspond to the core by definition. The marks in ${\mathcal{O}}_{*}$ form a stopping set, since the measure on ${\mathcal{O}}_{*}$ is the local weak limit of $\mu_{n}$, and in any graph drawn from $\mu_{n}$, w.p. 1 a vertex is marked only if at least two of its neighboring checks have all marked neighboring variable nodes. Moreover, one can show that both ${\mathcal{T}}_{*}$ and ${\mathcal{O}}_{*}$ are unimodular. Indeed ${\mathcal{T}}_{*}$ is unimodular since the unmarked tree is clearly unimodular, and the marking process does not make any reference to the root. Unimodularity of ${\mathcal{O}}_{*}$ is clear since it is the local weak limit of a marked random graph AldousLyonsUnimodular. Thus, in order to prove our thesis it suffices to show that the density of marks is the same in ${\mathcal{T}}_{*}$ and ${\mathcal{O}}_{*}$. (Because the subset of nodes that is marked in ${\mathcal{T}}_{*}$ contains the subset marked in ${\mathcal{O}}_{*}$ and the density of their difference is equal to the difference of the densities. Finally, for unimodular network, if a mark type has density $0$, then the set of marked nodes is empty by union bounds.)

Proceeding analogously to the proof of BalPerPete06, Proposition 1.2, we obtain

For edges directed downward, marks are generated recursively following the usual BP rules, cf. equations (4), (5), starting from the top to the bottom. It is easy to check that with this construction, the marks in $\widetilde{\mathcal{T}}_{*}(\alpha,k)$ correspond to a BP fixed point.

We extend the unmarking operator $\mathsf{U}$ by allowing it to act on graphs with marks on edges (and removing the marks).

$\mathsf{U}(\widetilde{\mathcal{T}}_{*})$ and $\mathsf{U}({\mathcal{T}}_{*})$ have the same distribution.

For this, we construct $\mathsf{U}(\widetilde{\mathcal{T}}_{*})$ (which is $\widetilde{\mathcal{T}}_{*}$ without the marks revealed) in a “breadth first” manner as follows: First, we draw a $\operatorname{Poisson}(\alpha k)$ number of factor descendants for the root node. Let $a$ be a factor descendant of the root. Then $a$ has $k-1$ variable node descendants. The message $\widehat{\nu}_{a\rightarrow\varnothing}$ is 0 with probability $\widehat{Q}$. It immediate to check from our construction and $\widehat{Q}=Q^{k-1}$ that:

Now, we draw the number of descendants for each neighbor of $a$. Using fact 1, together with the definition of $\widetilde{\mathcal{T}}$, one can check that:

$\widetilde{\mathcal{T}}_{*}$ is unimodular.

Let $\mathsf{F}$ be a map from “trees with marked edges” to “trees with marked variable nodes” defined as follows: $\mathsf{F}({\mathcal{T}})$ is obtained from ${\mathcal{T}}$ by putting a $\mathsf{c}$ mark on vertex $i$ if and only if at least two incoming edges have a $0$ mark.

We let $B$ be the subset of variable nodes $v$ of $\widetilde{\mathcal{T}}_{*}(\alpha,k)$ such that at least one message incoming to $v$ is equal to $0$. Then this set has density

In light of Lemma 4.15, we further denote the set of variable nodes in $\widetilde{\mathcal{T}}_{*}$ having two or more incoming $0$ messages by $V_{\mathtt{C}}(\widetilde{\mathcal{T}}_{*})$.

This result is immediate from Lemmas 4.12 and 4.15.

The following is immediate from the construction of $\widetilde{\mathcal{T}}_{*}$.

If $\varnothing\in B$, then there exists a subtree of $\widetilde{\mathcal{T}}_{*}$ rooted at $\varnothing$ with the following properties: (i) If $j$ is a variable node in the subtree, either $j\in V_{\mathtt{C}}(\widetilde{\mathcal{T}}_{*})$ or at least one descendant factor node is in the subtree; (ii) If $a$ is a factor node in the subtree, all its descendants are also in the subtree.

We call the subtree just defined a witness for $\varnothing$ (there might be more than one in principle). Notice that a priori a witness can be finite [if it ends up with nodes in $V_{\mathtt{C}}(\widetilde{\mathcal{T}}_{*})$], or infinite.

Almost surely any node $i\in B$ has a finite witness. Thus, $\lim_{t\rightarrow\infty}\widetilde{\mathcal{T}}_{*}^{t}=\widetilde{\mathcal{T}}_{*}$.

It is sufficient to prove that the following event has zero probability: $\varnothing\in B$ and $\varnothing$ only has infinite witnesses. Suppose $\varnothing\in B$. We will look for a minimal witness for $\varnothing$. If $\varnothing\in V_{\mathtt{C}}(\widetilde{\mathcal{T}}_{*})$, then it is itself a witness and we are done. If not then, there is exactly one incoming $0$ message, say from factor $a$. Then factor $a$ has $k-1$ incoming $0$ messages from descendants. The subtrees corresponding to these descendants are independent. Consider a descendant $i$ of $a$. We have

Conditioned on $i\in B\setminus V_{\mathtt{C}}(\widetilde{\mathcal{T}}_{*})$, the node $i$ has exactly $k-1$ descendant variable nodes (via one check node). Thus, conditioned on $\varnothing\in B$, the minimal witness is a Galton–Watson tree with offspring distributed as $Z$, whereby $Z=(k-1)$ with probability $\exp(-\alpha k\widehat{Q})\alpha kQ^{k-2}$, and $Z=0$ otherwise. The branching factor of this tree is $\exp(-\alpha k\widehat{Q})\alpha k(k-1)Q^{k-2}<1$ (cf. Lemma 6.6 below). The lemma follows.

Consider the setting of Lemma 4.8. We have

almost surely with respect to the choice of $G_{n}$.

Let $B_{t}$ be the subset of variable nodes in $\widetilde{\mathcal{T}}_{*}^{t}$ that receive at least one $0$ message. Let $y_{t}$ be the density of nodes in $B_{t}$. From Lemma 4.18, we have immediately

almost surely with respect to the choice of $G_{n}$.

It follows from Lemmas 4.12 and 4.15 that

[Proof of Lemma 4.8] Equation (23) follows from Lemmas 4.11, 4.19 and 4.20. Equation (22) follows from a completely analogous argument.

For any $d\geq 0$ and any $\delta>0$, there exists $t<\infty$ such that almost surely,

holds almost surely. Now, we can choose ${\varepsilon}$ small enough such that eventually (in $n$) almost surely, for any set of ${\varepsilon}n$ edges in $G_{n}$, the union of balls of radius $d$ around these edges contains no more than $\delta n$ nodes. Combining with equation (31), at least $(1-\delta)$ fraction of nodes have all messages in a ball of radius $d$ unchanged after iteration $t$, almost surely. This yields the result.

almost surely. Since $\delta$ is arbitrary, we obtain, for every $d$, that

Proof of Lemma 3.11: Peelability implies a sparse basis

Let us begin by describing the proof strategy.

Instead of analyzing peeling on the collapsed graph $G_{*}$, we analyze a different peeling process. We first run synchronous peeling on $G$ for a large constant $\tau$ number of iterations. We then collapse the resulting graph, as discussed in Section 3.1, that is, coalescing variables connected to each other via degree 2 factors (cf. Definition 3.3). Finally, we run synchronous peeling on the collapsed graph until it gets annihilated. We show that this process takes at least as many iterations as synchronous peeling on $G_{*}$ (Lemma 5.1 below). In order to bound the number of iterations under this new two-stages process, we proceed as follows. We choose the constant $\tau$ such that the residual graph $J_{\tau}$ is subcritical, and hence consists of trees and unicyclic components of size $O(\log n)$ w.h.p. As a consequence, the collapsed graph—to be denoted by ${\mathsf{T}}(J_{\tau})$—contains only checks of degree $3$ or more, and consists of trees and unicyclic components of size $O(\log n)$. It is not hard to show that it takes only $O(\log\log n)$ additional rounds of peeling to annihilate ${\mathsf{T}}(J_{\tau})$ under this condition (see Lemma 5.4 below).

Several technical lemmas follow, which are proved in the Appendix B, except Lemma 5.1, which we prove below. At the end of the subsection, we provide a proof of Lemma 3.11, parts (i) and (ii).

Consider the peeling algorithm and define ${\mathsf{J}}$ to be the peeling operator corresponding to one round of synchronous peeling (cf. Table 1). Thus, for a bipartite graph $G$, the residual graph after $t$ rounds of peeling is ${\mathsf{J}}^{t}(G)$. Denote by ${\mathsf{J}}^{\infty}(G)$ the graph produced by the peeling procedure after it halts: this is the empty graph if $G$ is peelable, and the core of $G$ otherwise. Recall that $T_{\mathtt{C}}(G)$ denotes the number of rounds of peeling performed before halting at ${\mathsf{J}}^{\infty}(G)$. Further, define ${\mathsf{T}}$ to be the collapse operator as per Definition 3.3. For instance $G_{*}={\mathsf{T}}(G)$. The next lemma bounds from above the number of rounds of peeling required to annihilate $G_{*}$, in terms of the modified peeling process (consisting of $\tau$ rounds of peeling, followed by collapse, and then peeling until annihilation).

For any constant $\tau\geq 0$ and any peelable bipartite graph $G$,

Peelability of a pair $(\alpha,R)$ immediately implies some useful properties.

For a factor degree profile $(\alpha,R)$ that is peelable at rate $\eta>0$, we have:

Notice that the factor graph induced by degree $2$ check nodes is in natural correspondence with an ordinary graph (replace every check node by an edge) which is uniformly random given the number of edges. The average degree of this graph is $2\alpha R_{2}$, and Lemma 5.2(i) implies that it is subcritical, as we would expect for a peelable degree distribution.

Recall that $n_{1}(G)$ denotes the number of variable nodes of degree $1$ in $G$, and $n_{2+}(G)$ denotes the number of variable nodes of degree $2$ or more in $G$. Let

In the lemma below, we slightly modify the peeling process, choosing to retain all variable nodes $V$ in the residual graph (check nodes are eliminated as usual). With a slight abuse of notation, we keep denoting by $J_{t}$ the residual graph, although this is obtained from $J_{t}$ by adding a certain number of isolated variable nodes.

Our final technical lemma bounds the number of peeling rounds needed to annihilate a tree or unicyclic component.

Consider a factor graph $G=(F,V,E)$ with no check nodes of degree $1$ or $2$, and that is a tree or unicyclic. Then $G$ is peelable and $T_{\mathtt{C}}(G)\leq 2\lceil\log_{2}|V|\rceil$.

for $z\leq 1$. Choose $\tau=\tau(\eta,k)<\infty$ such that $z_{\tau}\leq\eta/(3\alpha k(k-1))$. Then we have $\alpha R^{\prime}(1)\rho^{\prime}(z_{\tau})\leq 2\alpha R_{2}+\eta/3$. But Lemma 5.2 tells us that $2\alpha R_{2}\leq 1-\eta$. It follows that $\alpha R^{\prime}(z_{\tau})\leq 1-2\eta/3$.

In particular, the branching factor $\theta=\theta(J_{\tau})$ associated with the random graph $J_{\tau}$ satisfies $\theta\leq 1-\eta/3$, with probability at least $1-1/n^{2}$. Following a standard argument Bollo where we explore the neighborhood of $v$ by breadth first search, we obtain that with probability at least $1-1/n^{1.7}$ for $n\geq N_{1}(\eta,k)$, the connected component containing $v$ is a tree or unicyclic, with size less than $C_{4}\log n$, for some $C_{4}=C_{4}(\eta,k)<\infty$. Applying a union bound, we obtain that for $n\geq N_{2}=N_{2}(\eta,k)$, with probability at least $1/n^{0.7}$, the event $\mathsf{E}_{n}$ occurs, where

For (ii), notice that in collapsing a connected component of $J_{\tau}$, the number of variable nodes does not increase. Further, a tree component collapses to a tree and a unicyclic component collapses either to a tree or a unicyclic components. Thus, we can use Lemma 5.4 with $N\leq C_{4}\log n$ to obtain the a bound of $(C_{1}/2)\log\log n\leq C_{1}\log\log n-\tau$ on the number of additional peeling rounds needed, with probability at least $1-1/n^{0.6}$. Since the probability of peelability is uniformly bounded away from zero as $n\to\infty$, the probability that the same bound on the number of peeling rounds holds conditioned on peelability is at least (for some $\delta>0$) $1-1/(\delta n^{0.6})\geq 1-1/n^{0.5}$ for $n\geq N_{5}$, as required.

2 Proof of Lemma 3.11(iii)

The following lemma bounds the size of a supercritical Galton–Watson tree, observed up to finite depth. The proof is in the Appendix B.

[Proof of Lemma 3.11(iii)] From Lemma 5.2(ii), we know that $\alpha\leq 1$. The following occurs in the collapse process: Let $G^{(2)}=(F^{(2)},V,E^{(2)})$ be the subgraph of $G$ induced by the degree $2$ factor nodes (with isolated vertices retained). We have $F_{*}=F\setminus F^{(2)}$. All variable nodes that belong to a single connected component of $G^{(2)}$ coalesce into a single supernode $v^{\prime}\in V_{*}$ in $G_{*}$, with a neighborhood that consists of the union of the individual neighborhoods restricted to $F_{*}$ (cf. Definition 3.3). As mentioned above, $G^{(2)}$ is a random factor graph with $\alpha R_{2}n$ factor nodes of degree 2, and is in one-to-one correspondence with a uniformly random graph. For $v^{\prime}\in V_{*}$, we denote by $S(v^{\prime})$ the number of variable nodes in $V$ in the component $v^{\prime}$. Lemma 5.2(i) implies that the branching factor of $G^{(2)}$ obeys $2\alpha R_{2}\leq 1-\eta$, that is, $G^{(2)}$ is subcritical. This leads to the following claim that follows immediately from a well-known result on the size of the largest connected component in a subcritical random graph Bollo.

Claim 1: There exists $C_{2}=C_{2}(\eta)<\infty$, $N_{2}=N_{2}(\eta)<\infty$ such that the following occurs for all $n>N_{2}$. No component $v^{\prime}\in V_{*}$ is composed of more than $C_{2}\log n$ variable nodes, that is, $\max_{v^{\prime}\in V_{*}}S(v^{\prime})\leq C_{2}\log n$, with probability at least $1-1/n$.

Let $G^{\sim 2}\equiv(F_{*},V,E\setminus E^{(2)})$, that is, $G^{\sim 2}$ is the subgraph of $G$ induced by factors of degree greater than $2$ (with isolated vertices retained).

From Poisson estimates on the node degree distribution, we get the following.

Note that we used $\alpha<1$ [from Lemma 5.2(i)] to avoid dependence on $\alpha$ in the above claim.

Using claims 1 and 2 above and a union bound, we deduce that $\mathsf{E}_{n}$ holds with probability at least $1-2/n$ for $n>N_{4}$, for some $N_{4}=N_{4}(\eta,k)<\infty$.