The solution space geometry of random linear equations

Introduction

In Random Constraint Satisfaction Problems (CSPs) one has a set of $n$ variables all with the same domain $D$ and a set of independently chosen constraints, each of which binds a randomly selected subset of $k$ variables. In the most common setting, both $D$ and $k$ are $O(1)$, while $m=\Theta(n)$. Two canonical examples are random $k$-SAT and coloring sparse random graphs. A fundamental quantity in the study of random CSPs is the so-called constraint density, i.e., the ratio of constraints-to-variables $m/n$.

There has been much non-rigorous evidence from statistical physics that for many random CSPs, if the constraint density is higher than a specific value, then all but a vanishing proportion of the solutions can be partitioned into exponentially many sets (clusters) such that each set is: (i) well-separated, i.e., has linear Hamming distance from all others, and (ii) in some sense, well-connected. The solution clustering phenomenon has been a central feature of the statistical physics approach to random CSPs and is central to important algorithmic developments in the area, such as Survey Propagation .

The mathematical studying of clustering began in where it was shown that in random $k$-CNF formulas, above a certain density there exist constants $0<\alpha_{{k}}<\beta_{{k}}<1/2$ such that w.h.p. no pair of satisfying assignments has distance in the range $[\alpha_{k}n,\beta_{k}n]$. Let us say that two solutions are adjacent if they have Hamming distance 1 and consider the connected components under this notion of adjacency. In it was shown that above a certain density, there exist exponentially many connected components of solutions and, moreover, in every one of them the majority of variables are frozen, i.e., take the same value in all assignments in the connected component.

Defining a cluster-region to be the union of one or more connected components, proved that above a certain density, not only do exponentially many connected components exist, but there are exponentially many cluster-regions separated from one another by linear Hamming distance. Moreover, asymptotic bounds were given on the volume, diameter, and separation of these cluster regions. Later, in , it was shown for random $k$-SAT and random graph colouring that when clustering occurs, the emergent cluster-regions are also separated by large energetic barriers, i.e., that any path connecting solutions in different cluster-regions passes through value assignments violating linearly many constraints. This picture of cluster-regions remains unchanged if one considers two solutions to be adjacent if they have Hamming distance $o(n)$. At the same time, though, it lends little information regarding the internal organization of cluster-regions, e.g., the connectivity of each such region.

Until now, it has not been proven that any random CSP model exhibits clustering into sets that are both well-separated and well-connected. The main contribution of this paper is to prove that this phenomenon does indeed occur for random $k$-XOR-SAT, i.e., for systems of random linear equations over GF(2) where each equation contains precisely $k$ variables. We also obtain a precise description of the clusters. We remark that the cluster structure for $k$-XOR-SAT is much simpler than what is hypothesized for most CSPs, e.g., the clusters are all isomorphic and have the same set of frozen variables (see Section 4). Random $k$-XOR-SAT has long been recognized as one of the most accessible of the fundamental random CSP models, in that researchers have managed to prove difficult results for it that appear to be far beyond our current reach for, e.g., random $k$-SAT and random graph coloring. For example, the $k$-XOR-SAT satisfiability threshold was established by Dubois and Mandler for $k=3$ and by Dietzfelbinger et al. for general $k$.

We consider systems of $m=O(n)$ linear equations over $n$ Boolean variables, where each equation binds a constant number of variables. Clearly, deciding whether such a system has satisfying assignments (solutions) can be done in polynomial time by, say, Gaussian elimination. In fact, the set of solutions forms a subspace, so that the sum of two solutions is also a solution. At the same time, it seems that if one fails to exploit the underlying algebraic structure everything falls apart. For example, if the system is unsatisfiable, finding a value assignment $\sigma$ that satisfies as many equations as possible, i.e., MAX XOR-SAT, is NP-complete. Moreover, given a satisfiable system and an arbitrary $\sigma\in\{0,1\}^{n}$, finding a solution nearest to $\sigma$ is also NP-complete . Finally, random systems of linear equations appear to be extremely difficult both for generic CSP solvers and for SAT solvers working on a SAT encoding of the instance. Indeed, very recent work strongly suggests that among a wide array of random CSPs, random $k$-XOR-SAT, defined below, is the most difficult for random walk type algorithms such as WalkSat .

In random $k$-XOR-SAT, which we study here, each equation binds exactly $k\geq 3$ variables (the case $k=2$ is trivial). To form the random system of equations $Ax=b$ we take $A$ to be the adjacency matrix of a random $k$-uniform hypergraph $H$ with $n$ variables and $m$ edges and $b\in\{0,1\}^{m}$ to be a uniformly random vector. It is straightforward to see, using e.g., Gaussian elimination, that if two systems have the same matrix $A$, then their solution spaces are isomorphic as $b$ ranges over vectors for which the solution space is not empty. Since we will only be interested in properties of the set of solutions that are invariant under isomorphism, we will assume throughout that $b=\mathbf{0}$. As a result, throughout the paper we will be able to identify the system of linear equations with its underlying hypergraph. Regarding the choice of random $k$-uniform hypergraphs we will use both standard models $H_{{k}}(n,m)$ and $H_{{k}}(n,p)$, which respectively correspond to: including exactly $m$ out of the possible $\binom{n}{k}$ edges uniformly and independently, and including each possible edge independently with probability $p$. (Results transfer readily betwen the two models when $m=p\binom{n}{k}$.) Our corresponding models of random $k$-XOR-SAT are:

$X_{k}(n,m),X_{k}(n,p)$ are the systems of linear equations over $n$ boolean variables whose underlying hypergraphs are $H_{k}(n,m),H_{k}(n,p)$ and where we set $b=\mathbf{0}$.

The usual model for $k$-XOR-SAT differs from ours only in that it takes a uniformly random Boolean vector $b$. As described above, these models are equivalent up to isomorphisms of the solution space, and hence we can use our more convenient definition for the purposes of this paper. We will say that a sequence of events $\mathcal{E}_{n}$ holds with high probability (w.h.p.) for such a system if $\lim_{n\rightarrow\infty}\Pr[\mathcal{E}_{n}]=1$. We will analyze $X_{k}(n,p)$. All our theorems translate to $X_{k}(n,m)$ where $m=p\binom{n}{k}$ using a standard argument.

We are interested in the range $p=\Theta(n^{1-k})$ which is equivalent to $m=\Theta(n)$. We note that as $n\rightarrow\infty$, the degrees of the variables in such a random system tend to Poisson random variables with mean $\Theta(1)$. This implies that w.h.p. there will be $\Theta(n)$ variables of degree 0 and 1. Clearly, variables of degree 0 do not affect the satisfiability of the system. Similarly, if a variable $v$ appears in exactly one equation $e_{i}$, then we can always satisfy $e_{i}$ by setting $v$ appropriately for any constant $b_{i}$. Therefore, we can safely remove $e_{i}$ from consideration and only revisit it after we have found a solution to the remaining equations. Crucially, this removal of $e_{i}$ can cause the degree of other variables to drop to 1. This leads us to the definition of the core of a hypergraph.

The $r$-core of a hypergraph $H$ is the maximum subgraph of $H$ in which every vertex has degree at least $r$.

It is well known that for every fixed $r\geq 2$, as $p$ is increased, $H_{k}(n,p)$ acquires a (massive) non-empty $r$-core suddenly, around a critical edge probability $p=c^{*}_{k,r}/n^{k-1}$.

Trivially, removing any vertex of degree less than $r$ and all its incident edges from $H$ does not change its $r$-core. Therefore, the $r$-core is the (potentially empty) outcome of the following procedure: repeatedly remove an arbitrary vertex of degree less than $r$ until no such vertices remain. In the case of linear equations we will be particularly interested in 2-cores, as variables outside the 2-core can always be properly assigned.

The 2-core system is the subsystem of linear equations induced by the 2-core of the underlying hypergraph, i.e., the set of equations whose variables all lie in the 2-core. A 2-core solution is a solution to the 2-core system. An extension of a 2-core solution, $\sigma$, is a solution of the entire system of linear equations that agrees with $\sigma$ on all 2-core variables.

We will show that in the absence of a 2-core, while the diameter of the set of solutions is linear, it is w.h.p. possible to transform any solution to any other solution by changing $O(\log n)$ variables at a time. So, the set of solutions is not only well-connected but pairs of solutions exist at, essentially, every distance-scale. On the other hand, the emergence of the 2-core signals the onset of clustering, as now every pair of solutions is either very close with respect to the 2-core variables, or very far.

For every $k\geq 3$ and $c>c^{*}_{k,2}$, there exists a constant $\alpha=\alpha(c,k)>0$ such that in $X_{k}(n,p={c/n^{k-1}})$, w.h.p. every pair of solutions either disagree on at least $\alpha n$ 2-core variables, or on at most ${\xi}(n)$ 2-core variables, for any function ${\xi}(n)\rightarrow\infty$ arbitrarily slowly.

We will refine the picture of Theorem 1, to prove that as soon as the 2-core emerges, unless two solutions agree on essentially all 2-core variables, transforming one into another requires the simultaneous change of $\Omega(n)$ variables. To identify the relevant 2-core disagreements, we need to define the following notion which is central to our work.

A flippable cycle in a hypergraph $H$ is a set of vertices $S=\{v_{1},\ldots,v_{t}\}$, where $t\geq 2$, where the set of edges incident to $S$ can be ordered as $e_{1},\ldots e_{t}$ such that each vertex $v_{i}$ lies in $e_{i}$ and in $e_{i+1}$ and in no other edges of $H$ (addition mod $t$).

Note that the vertices $v_{1},\ldots,v_{t}$ must have degree exactly two in the hypergraph. The remaining vertices in edges $e_{1},\ldots,e_{t}$ can have arbitrary degree and are not part of the flippable cycle.

A core flippable cycle in a hypergraph $H$ is a flippable cycle in the subhypergraph $H_{0}\subseteq H$ induced by the 2-core of $H$.

Thus, in a core flippable cycle, the vertices $v_{1},\ldots,v_{t}$ have degree exactly two in the 2-core, but possibly higher degree in $H$. Note also that $H$ may contain flippable cycles outside the 2-core. We will prove (Lemma 35(b)) that w.h.p. the core flippable cycles are disjoint.

As discussed above, any 2-core solution can be readily extended to the remaining variables. Indeed, this can typically be done in numerous ways since the equations not in the 2-core are far less constrained, e.g., a constant fraction of the equations outside the 2-core form hypertrees very loosely attached to the 2-core. In order to understand the emergence of the clustering of solutions, we will focus on whether we can change the value of a 2-core variable without changing many other 2-core variables.

If $\sigma$ is any 2-core solution then flipping the value of all variables in a core flippable cycle readily yields another solution of the 2-core, since every equation contains either zero or two of the flipped variables. It is not hard to show that a random hypergraph often contains a handful of short core flippable cycles, implying that 2-core solutions may have Hamming distance $\Theta(1)$. At the same time, though, we will see (Lemma 35) that, for any ${\xi}(n)\rightarrow\infty$ arbitrarily slowly, the total number of vertices in core flippable cycles w.h.p. does not exceed ${\xi}(n)$, placing a corresponding upper bound on the distance between core solutions that differ only on flippable cycles.

In contrast, we will prove that w.h.p. every pair of core solutions that differ on even one 2-core variable not in a flippable cycle, differ in at least $\Omega(n)$ 2-core variables. In other words, flipping the handful of variables in potential flippable cycles, w.h.p. is the only kind of movement between 2-core solutions that does not entail the simultaneous change of a massive number of variables.

The above indicates that the following is the appropriate definition of clusters in random $k$-XOR-SAT.

Two solutions are cycle-equivalent if on the 2-core they differ only on variables in core flippable cycles (while they may differ arbitrarily on variables not in the 2-core).

The solution clusters of $X_{k}(n,p={c/n^{k-1}})$ are the cycle-equivalence classes, i.e., two solutions are in the same cluster iff they are cycle-equivalent.

Note that in the absence of a 2-core, this definition states that all solutions are in the same cluster. We can now state our main theorems in terms of connectivity properties of clusters.

Two solutions $\sigma,\tau$ of a CSP are $d$-connected if there exists a sequence of solutions $\sigma,\sigma^{\prime},\ldots,\tau$ such that the Hamming distance of every two successive elements in the sequence is at most $d$. A set $S$ of solutions is $d$-connected if every pair $\sigma,\tau\in S$ is $d$-connected. Two solution sets $S,S^{\prime}$ are $d$-separated if every pair $\sigma\in S,\tau\in S^{\prime}$ is not $d$-connected.

It appears that for many random CSP’s, there is a constant $\alpha>0$ and a function $g(n)=o(n)$ such that if the constraint density is sufficiently large, then all but a vanishing proportion of the solutions can be partitioned into clusters $S_{1},\ldots,S_{t}$ such that:

Every pair $S_{i},S_{j}$ is $\alpha n$-separated.

That is the sense in which we said earlier that each cluster is well-connected and that each pair of clusters is well-separated.

Our main theorems are that for $k$-XOR-SAT, the clusters we defined in Definition 8 satisfy these conditions with $g(n)=O(\log n)$. Note that for this particular CSP, the clusters contain all the solutions, rather than all but a vanishing proportion of them.

For any constant ${c\neq c_{k,2}^{*}}$ and $k\geq 3$, there exists a constant $\alpha=\alpha(c,k)>0$ such that in $X_{k}(n,p={c/n^{k-1}})$, w.h.p. every pair of clusters is $\alpha n$-separated.

In stark contrast, we prove that clusters are internally very well connected.

For any constant ${c\neq c_{k,2}^{*}}$ and $k\geq 3$, there exists a constant $Q=Q(c,k)>0$ such that in $X_{k}(n,p={c/n^{k-1}})$, w.h.p. every cluster is $Q\log n$-connected.

Theorem 3 is nearly tight due to the following.

W.h.p. every cluster contains a pair of solutions that are not $g(n)$-connected, for some $g(n)=\Omega(\log n/\log\log n)$.

Consider any solution $\sigma$ to the 2-core, and consider any two extensions $\sigma_{0},\sigma_{1}$ of $\sigma$ to the entire system such that, for some non-core variable $v$, we have $\sigma_{0}(v)=0$ but $\sigma_{1}(v)=1$. Then $\sigma_{0},\sigma_{1}$ must differ in at least one additional variable in every equation containing $v$ implying that their Hamming distance is at least $\deg(v)+1$.

If $T$ is an acyclic (tree) component of the underlying hypergraph and $v$ is any vertex in $T$, then, clearly, $\sigma$ can be extended so that $v$ takes any desired value. Therefore, the maximum degree of any vertex in a tree component is a lower bound for $g(n)$. A tree component $T$ is a $d$-star if precisely one vertex in $T$ has degree $d$ and all other vertices have degree 1. Computing the second moment of the number of $d$-stars in a random hypergraph implies that w.h.p. there exist $g(n)$-stars, where $g(n)=\Omega(\log n/\log\log n)$. ∎

So, in a nutshell, we prove that before the 2-core emerges any solution can be transformed to any other solution along a sequence of successive solutions differing in $O(\log n)$ variables. In contrast, after the 2-core emerges, the set of solutions shatters into clusters defined by complete agreement on the 2-core, except for the handful of variables in core flippable cycles: any two solutions that disagree on even one 2-core variable not in a core flippable cycle, must disagree on $\Omega(n)$ variables. At the same time, solutions in the same cluster behave like solutions in the pre-core regime, i.e., one can travel arbitrarily inside each cluster by changing $O(\log n)$ variables at a time.

Our proof of Theorem 3 is algorithmic, giving an efficient method to travel between any pair of solutions in the same cluster. Indeed, to prove Theorem 3, we draw heavily from the linear structure of the constraints to: (1) identify a set $B$ of free variables such that the $2^{|B|}$ solutions in any cluster are determined by the $2^{|B|}$ assignments to $B$, (2) prove that we can change these free variables one-at-a-time, each time obtaining a new solution by changing only $O(\log n)$ other variables.

For $c<c_{k,2}^{*}$, there is no 2-core, and so all solutions belong to the same cluster. For $c>c_{k,2}^{*}$, but below the $k$-XOR-SAT satisfiability threshold, the number of 2-core variables exceeds the number of 2-core equations by $\Theta(n)$ (see ), and the number of variables on core flippable cycles has expectation $O(1)$ (Lemma 35); it follows that w.h.p. there are an exponential number of clusters. So Theorems 2, 3 yield:

For every $k\geq 3$ and $c$ below the $k$-XOR-SAT satisfiability threshold:

If $c<c_{k,2}^{*}$, then w.h.p. the entire solution-set of $X_{k}(n,p=c/n^{k-1})$ is $O(\log n)$-connected.

If $c>c_{k,2}^{*}$, then w.h.p. the solution-set of $X_{k}(n,p=c/n^{k-1})$ consists of an exponential number of $\Theta(n)$-separated, $O(\log n)$-connected clusters.

For $k\geq 3$, the threshold for the appearance of a non-empty 2-core was determined in (see also ) to be:

For example, when $k=3$, an exponential number of clusters emerge at $c=0.13...$ while the satisfiability threshold is at $c=0.15...$. (These values correspond to $m/n=0.818...$ and $m/n=0.917...$ in the $X_{k}(n,m)$ model.) It is not clear what happens, in terms of clustering, at density $c=c_{k,2}^{*}$; see the remarks following Theorem 5.

Our proof of Theorem 2 easily extends to all uniquely extendable CSPs.

A constraint of arity $k$ is uniquely extendable if for every set of $k-1$ variables and every value assignment to those variables there is precisely one value for the unassigned variable that satisfies the constraint.

Linear equations over GF(2) and unique games are the two most common examples of uniquely extendable (UE) CSPs, but many others exist (see, eg. ). Clearly, any instance of a UE CSP $\Phi$ is satisfiable iff its 2-core is satisfiable. Thus, it is natural to define clusters analogously to XOR-SAT, i.e., two solutions are in the same cluster if and only if their 2-core restrictions differ only on core flippable cycles. Our proof of Theorem 2 applies readily to any UE CSP, yielding a corresponding theorem, i.e., that there exists $\alpha>0$ such that if two solutions are not cycle-equivalent they are not $\alpha n$-connected (see the remark following Proposition 48). However, we do not know whether the analogue of Theorem 3 holds under this definition of clusters, i.e., whether it is possible to travel between cycle-equivalent solutions in small steps. Also, note that while in XOR-SAT changing all the variables in any flippable cycle results in another solution, this is not necessarily the case for every UE CSP $\Phi$.

Finally, we note that Theorem 1 follows immediately from Theorem 2 and the fact that w.h.p. there are fewer than ${\xi}(n)$ vertices on flippable cycles (Lemma 35). Indeed, if two solutions differ on more than ${\xi}(n)$ 2-core variables, then they disagree on a variable that is not on a flippable cycle. Thus, they are in different clusters and so disagree on at least $\alpha n$ variables, by Theorem 2. So the paper focuses on proving Theorems 2 and 3.

2 Cores of hypergraphs

The main step in our proof of Theorem 3 is to prove a property of the non-2-core vertices in a random hypergraph. As this property is of independent interest, we prove it for non-$r$-core vertices for general $r\geq 2$.

For any integers $k\geq 2,r\geq 2$ such that $r+k>4$, the threshold for the appearance of a non-empty $r$-core in a $k$-uniform random hypergraph was determined in to be:

For $r=k=2$, i.e., for cycles in graphs, the emergence of a 2-core is trivial as any constant-sized cycle has non-zero probability for all $c>0$. On the other hand, for $r+k>4$, any $r$-core has linear size w.h.p. The threshold for the emergence of a 2-core of linear size in a random graph coincides with the threshold for the emergence of a giant component , so we set $c^{*}_{2,2}=1$, consistent with the expression above after replacing $\min$ with $\inf$.

Recall that we can reach the $r$-core of a hypergraph by repeatedly removing any one vertex of degree less than $r$, until no such vertices remain. Consider a vertex $v$ not in the $r$-core, and consider the goal of repeatedly removing vertices of degree less than $r$ until $v$ is removed. We prove that w.h.p. for every non-$r$-core variable $v$, this can be achieved by removing only $O(\log n)$ vertices.

An $r$-stripping sequence is a sequence of vertices that can be deleted from a hypergraph, one-at-a-time, along with their incident hyperedges such that at the time of deletion each vertex has degree less than $r$. A terminal $r$-stripping sequence is one that contains all vertices outside the $r$-core; i.e., a sequence whose deletion leaves the $r$-core.

For any vertex $v$ not in the $r$-core, the depth of $v$ is the length of a shortest $r$-stripping sequence ending with $v$.

For any integers $k\geq 2,r\geq 2$ and any constant $c\neq c_{k,r}^{*}$, let $H=H_{k}(n,p=c/n^{k-1})$. There exists a constant $Q=Q(c,k,r)>0$ such that w.h.p., every vertex $v$ in $H$ has depth at most $Q\log n$.

It is easy to show using standard facts about $r$-cores of random hypergraphs that for every constant $\epsilon>0$, there is a constant $T=T(\epsilon)$ such that w.h.p. all but $\epsilon n$ of the non-core vertices have depth at most $T$. The challenge here is to prove that w.h.p. all non-core vertices have depth $O(\log n)$.

The case $k=r=2$, i.e. the 2-core of a random graph, follows easily from previously known work. The conclusion of Theorem 4 does not hold at $c=c^{*}_{2,2}=1$. (See the remarks following the statement of Theorem 5 below.)

Related work

To get an upper bound on the random $k$-XOR-SAT satisfiability threshold, observe that the expected number of solutions in a random instance with $n$ variables and $m$ constraints is bounded by $2^{n}(1/2)^{m}\rightarrow 0$ if $m/n>1$. As one can imagine, this condition is not tight since variables of degree 0 and 1 only contribute fictitious degrees of freedom. Perhaps the next simplest necessary condition for satisfiability is $m_{c}/n_{c}=\gamma_{c}\leq 1$, where $n_{c},m_{c}$ is the number of variables and equations in the 2-core, respectively. In Dubois and Mandler proved that, for $k=3$, this simple necessary condition for satisfiability is also sufficient by proving that for all $\gamma_{c}<1$, the number of core solutions is strongly concentrated around its (exponential) expectation. Thus, they determined the satisfiability threshold for 3-XOR-SAT. Dietzfelbinger et al. modify and extend the approach of to determine the satisfiability threshold for general $k$. A full version of has not been published, but a proof for all $k\geq 3$ appears in .

Mézard et al. were the first to study clustering in random $k$-XOR-SAT. Specifically, they defined the clusters by saying that two solutions are in the same cluster iff they agree on all variables in the 2-core. They proved that there exists a constant $\gamma>0$ such that for any $\theta\in(0,\gamma)$ and any integer $z=\theta n+o(n)$, w.h.p. no two solutions differ on exactly $z$ variables in the 2-core. Based on this fact, they claimed that the clusters they defined are $\Omega(n)$-separated, i.e., that every pair of solutions in different clusters is not $\gamma n$-connected. As we have already seen, this is false since it does not account for the effect of core flippable cycles. Performing the analysis of solutions that differ on $o(n)$ variables is what allows us to establish that 2-core solutions which differ on $o(n)$ variables must differ only on core flippable cycles. Indeed, this is the most difficult part of our proof of Theorem 2.

Mézard et al. also gave a heuristic argument that if $\sigma$ is any solution and $v$ is a non-core variable, then there exists a solution $\sigma^{\prime}$ in which $v$ takes the opposite value from the one in $\sigma$ such that the distance between $\sigma$ and $\sigma^{\prime}$ is $O(1)$. From this they concluded that clusters are well-connected. Regarding internal connectivity, the clusters of are, indeed, well-connected, i.e., the analogue of Theorem 3 holds for them, since they are subsets of the clusters defined in this paper. However their proof of this fact is flawed; it implies that their clusters are $O(1)$-connected, which is not true by the same argument used as for Observation 10. Proving that the $k$-XOR-SAT clusters are well-connected was later listed as an open problem in .

Finally, as described above, Ibrahimi, Kanoria, Kraning and Montanari have, independently, obtained similar results to ours.

Proof Outline

Given a solution $\sigma$, a flippable set is a set of variables $S$ such that flipping the value of all variables in $S$ yields another solution $\tau$. Proving Theorem 2 boils down to proving that w.h.p., in the subsystem induced by the 2-core, every flippable set other than a flippable cycle has linear size.

A common approach to proving analogous statements is to establish that every flippable set, other than a flippable cycle, must deterministically induce a dense subgraph. In particular, if one can prove that for some constant $\epsilon>0$, every such set is at least $1+\epsilon$ times as dense as a flippable cycle, then standard arguments yield the desired conclusion. Here, though, this is not the case, due to the possibility of arbitrarily long paths of degree 2 vertices. Specifically, by replacing the edges of any flippable set (that is not a flippable cycle) by 2-linked paths, one can easily create flippable sets whose density is arbitrarily close to that of a flippable cycle (for a more more precise statement, see the definition of 2-linked paths in Section 9). Thus, controlling the number and interactions of these 2-linked paths, an approach similar to that of , is crucial to our argument. In order to work on the 2-core, we carry this analysis out on hypergraphs with a given degree sequence.

The key to controlling 2-linked paths is to bound a parameter governing the degree to which they tend to branch. Lemma 32 shows that this parameter is bounded below 1, so while arbitrarily long 2-linked paths will occur, their frequency decreases exponentially with their length.

We note that if we were working on hypergraphs with minimum degree at least 3, then there would be no 2-linked paths, and the proof would have been very easy. All of the difficulties arise from the problem of degree 2 vertices. We note that our approach applies to general degree sequences of minimum degree 2.

2 Theorem 3: Connectivity inside clusters

The main step in the proof of Theorem 3 is to prove Theorem 4; i.e. that every vertex outside the $r$-core can be removed by an $r$-stripping sequence of length $O(\log n)$.

It is often useful to consider stripping the vertices in several parallel rounds.

The parallel $r$-stripping process consists of iteratively removing all vertices of degree less than $r$ at once along with any hyperedges containing any of those vertices, until no vertices of degree less than $r$ remain.

To prove that all non-core vertices can be removed by a stripping sequence of length $O(\log n)$, our approach is significantly different below and above the threshold, $c^{*}_{k,r}$, for the emergence of an $r$-core in random $k$-uniform hypergraphs. In both cases, we begin by stripping down to $H_{B}$, the hypergraph remaining after $B$ rounds of the parallel stripping process, for a sufficiently large constant $B$. A simple argument shows that for any non-core vertex $v$, the number of vertices removed during this initial phase that are relevant to the removal of $v$, is bounded. Thus, what remains is to show that any non-core vertex in $H_{B}$ can be removed from $H_{B}$ by a stripping sequence of length $O(\log n)$.

For $c<c_{k,r}^{*}$, we prove that there exists a sufficiently large constant $B=B(c,k,r)$ such that all connected components of $H_{B}$ have size at most $W=O(\log n)$; therefore, any remaining vertex can be removed with an additional $W$ strips. To do this we establish analytic expansions for the degree sequence of $H_{B}$ as $B$ grows and then apply a hypergraph extension of the main result of Molloy and Reed regarding the component sizes of a random $k$-uniform hypergraph with a given degree sequence.

For $c>c_{k,r}^{*}$, a lot more work is required. Once again, 2-linked paths are a major problem. Indeed, it is not hard to see that a long 2-linked path with one endpoint of degree 1, can create a long stripping sequence leading to the removal of its other endpoint.

We first establish that for any $\epsilon>0$, there exists a sufficiently large constant $B=B(c,k,r,\epsilon)$ such that $H_{B}$ is sufficiently close to the $r$-core for two important properties to hold in $H_{B}$: (i) there are at most $\epsilon n$ vertices of degree less than $r$, and (ii) the “branching” parameter for 2-linked paths, mentioned above, is bounded below 1. Property (ii) allows us to control long 2-linked paths. However, this does not suffice as we need to control, more generally, for large tree-like stripping sequences. To do so, we note that any large tree must either have many leaves, or long paths of degree 2 vertices. Such long paths will correspond to 2-linked paths in the random hypergraph, and so (ii) allows us to control the latter case. Leaves of the tree will have degree less than $r$, and so (i) enables us to control the former case.

An Algorithm for Traveling Inside Clusters

In this section, we show how we use Theorem 4 to prove Theorem 3. In fact, we require Theorem 5 below, which is somewhat stronger than Theorem 4.

Given a hypergraph $H$, we consider any terminal $r$-stripping sequence, $v_{1},\ldots,v_{t}$, i.e., one that removes every vertex outside of the $r$-core of $H$. Let $H_{i}$ denote the hypergraph remaining after removing $v_{1},\ldots,v_{i-1}$; so $H_{1}=H$ and $H_{t+1}$ is the $r$-core of $H$. Let $E_{i}$ denote the set of at most $r-1$ hyperedges in $H_{i}$ that contain $v_{i}$. We form a directed graph, $D$, as follows:

The vertices of $D$ are the non-$r$-core vertices $v_{1},\ldots,v_{t}$, as well as any $r$-core vertex that shares a hyperedge with a vertex not in the $r$-core. For each vertex $v_{i}$ in the stripping sequence, $D$ contains a directed arc $(u,v_{i})$ for every vertex $u\neq v_{i}$ contained in the hyperedges of $E_{i}$. Note that if $v_{i}$ has degree zero in $H_{i}$, then $E_{i}=\emptyset$, and so $v_{i}$ will have indegree zero in $D$.

For every vertex $v$ in $D$, we define $R^{+}(v)$ to be the set of vertices that can be reached from $v$. Note that if $v$ is not in the $r$-core, then the vertices of $R^{+}(v)$ can be arranged into a (not necessarily terminal) $r$-stripping sequence ending with $v$. So to prove Theorem 4, it suffices to show $|R^{+}(v)|=O(\log n)$ for every such $v$.

For any integers $k\geq 2,r\geq 2$ and any constant $c>0,c\neq c_{k,r}^{*}$, let $H=H_{k}(n,p=c/n^{k-1})$. There exists a constant $Q=Q(k,r,c)>0$ such that w.h.p. there is a terminal $r$-stripping sequence of $H$ for which in the digraph $D$ associated with the sequence:

For every vertex $v$, $|R^{+}(v)|\leq Q\log n$.

For $r=2$, for every core flippable cycle $C$,

The proof of Theorem 5 can be extended to show that w.h.p. for every vertex $v\in D$, the subgraph induced by $|R^{+}(v)|$ has at most as many arcs as vertices.

The case $r=k=2$ follows from previously known work. For $c<c^{*}_{2,2}=1$, it follows from the fact that w.h.p. every component of $G_{n,p=c/n}$ has size $O(\log n)$ below the giant component threshold $c^{*}_{2,2}$. For $c>c_{k,r}^{*}$, it follows from Lemma 5(b) of . Our proof will work for $k=r=2$, but it is convenient to assume $(k,r)\neq(2,2)$.

We think that the conclusion of Theorem 5 does not hold at $c=c^{*}_{k,r}+o(1)$. This is known to be true for the case $k=r=2$. Indeed, when $c=1-\lambda$, for $\lambda=n^{-1/3+\epsilon},\epsilon>0$, w.h.p. the size of the largest component is $\Theta(\lambda^{-2}\log n)$ and no component has more than one cycle . A simple first moment analysis yields that w.h.p. there is no cycle of length greater than $\log n/\lambda$. Furthermore, w.h.p. no vertex has degree greater than $\log n$. It follows that the largest component must contain an induced subtree, none of whose vertices are in the 2-core, which has size $\Theta(\frac{\lambda^{-2}\log n}{\log^{2}n/\lambda})=\Theta(1/(\lambda\log n))$. It is easy to see that such a subtree will contain vertices with depth $\Theta(1/(\lambda\log n))$, which can be as large as $n^{\alpha}$ for any $\alpha<1/3$.

The proof of Theorem 5 occupies Sections 7 and 8, after we set out some basic facts about cores in Section 5 and some basic calculations in Section 6. But first, we show that it yields Theorems 3 and 4:

This follows immediately from Theorem 5 because the depth of $v$ is at most $|R^{+}(v)|$. ∎

We are now ready to give our algorithm for traveling between any two assignments in the same cluster while changing $O(\log n)$ variables at a time.

Given an arbitrary system of linear equations consider a terminal $2$-stripping sequence $v_{1},\ldots,v_{t}$ of its associated hypergraph and let $D$ be the digraph formed from the sequence. For each core flippable cycle, $C$, we choose an arbitrary vertex $v_{C}\in C$. Let $B$ be the set consisting of each vertex $v_{C}$ and every non-2-core vertex with indegree zero in $D$.

Consider any 2-core solution $\sigma$. Consider the system of equations formed from our system by fixing the value of every 2-core variable that does not belong to a core flippable cycle to its value in $\sigma$; we call such vertices fixed vertices. Recall from Definition 4 that the edges of a flippable cycle contain vertices that are not considered to be vertices of the flippable cycle; such vertices will be fixed. Note that the solutions of this system form a cluster, and that every cluster can be formed in this way from some $\sigma$.

We will perform Gaussian elimination on this system in a manner such that $B$ will be the set of free variables that we obtain. Importantly, this set of free variables does not depend on $\sigma$, i.e., it will be the same for every cluster.

For each $v\in B$ and for each fixed vertex $v$, set $\chi(v)=\{v\}$. For each core flippable cycle $C$, we process all of the edges (i.e., equations) joining consecutive vertices of $C$ except for one of the edges containing $v_{C}$. For each vertex $v\in C$, we obtain the equation $v=v_{C}+z_{v}$ where $z_{v}$ is a constant (0 or 1) depending only on the assignment to the fixed vertices in the edges of $C$; we set $\chi(v)=\{v_{C}\}$. By Lemma 35, the core flippable cycles are vertex-disjoint, and so the equations corresponding to two core flippable cycles can overlap only on fixed variables. Thus, we can carry this out for each core flippable cycle $C$ independently.

Next, we process the edges not in the 2-core, in reverse removal order, i.e., $E_{t},\ldots,E_{1}$. Note that, since $r=2$, each $E_{i}$ contains at most one edge. When processing $E_{i}$, we set $\chi(v_{i})$ to the symmetric difference of the sets $\chi(u)$, over all $u\in E_{i}$ other than $v_{i}$. That is, a variable $z$ is in $\chi(v_{i})$ iff $z\in\chi(u)$ for an odd number of variables $u\in E_{i}$ other than $v_{i}$. Since $E_{i}$ is the equation $v_{i}=\sum_{u\in E_{i};u\neq v}u$, this is equivalent (by induction) to $v_{i}=\sum_{w\in\chi(v_{i})}w+z_{v_{i}}$, where $z_{v_{i}}$ is the sum of $z_{u}$ over all vertices $u\in\chi(v_{i})$ that belong to core flippable cycles. We now note that every non-2-core vertex $v_{i}\notin B$ has indegree at least 1 in $D$ and so $|E_{i}|=1$ and thus $\chi(v_{i})$ is defined. For each vertex $u\neq v_{i}$ in $E_{i}$, either $u\in B$, or $u$ is fixed, or $u=v_{j}$ for some $j>i$, or $u$ is in a core flippable cycle. Therefore, by induction, $\chi(v_{i})$ contains only vertices that are in $B$ or are fixed.

Finally, note that possibly $\chi(v_{i})=\emptyset$; in that case, $v_{i}=\sum_{w\in\chi(v_{i})}w+z_{v_{i}}=z_{v_{i}}$ in every solution. (It is not hard to adapt the proof of Theorem 5 to show that w.h.p. for every $i$, $\chi(v_{i})\neq\emptyset$. But that is not required for the purposes of this paper.)

At this point, all non-fixed vertices are either in $B$ or have been expressed as the sum of vertices in $B$ and fixed vertices. Therefore, the vertices in $B$ are the free variables for the system obtained by fixing the values of the fixed vertices to $\sigma$. Thus, there are exactly $2^{|B|}$ solutions to that system, one for each assignment to $B$. We can move between any two such solutions by changing the assignments to the vertices of $B$, one at a time. Each time we change the value of a non-2-core vertex $v\in B$, in order to get to another solution, we only need to change a subset of $R^{+}(v)$ in the digraph $D$, because only vertices $u\in R^{+}(v)$ can have $v\in\chi(u)$. Similarly, each time we change the value of some $v_{C}\in B$, we only need to change a subset of $\cup_{v\in C}R^{+}(v)$. Thus, by Theorem 5, we can move between any two such solutions changing at most $Q\log n$ variables at a time. This implies Theorem 3, since each cluster is such a solution set. ∎

We close this section by showing how the preceding proof extends to determine all of the frozen variables. A variable is said to be frozen in a cluster, if it takes the same value in all assignments of the cluster. In general random CSPs it is hypothesized that the set of frozen variables can differ from cluster to cluster. In random $k$-XOR-SAT, though, the set of frozen variables depends only on the underlying hypergraph, i.e., is the same for all clusters.

In every cluster, the frozen variables consist of the 2-core vertices not in core flippable cycles, and the non-2-core variables $v$ for which $\chi(v)\cap B=\emptyset$.

This follows immediately from the fact that $B$ is the set of free variables in a system of linear equations whose solution set is the cluster. ∎

Random hypergraphs and their cores

We will use the configuration model of Bollobás to generate a random $k$-uniform hypergraph $H$ with a given degree sequence. Suppose we are given the degree $d(v)$ for each vertex $v$; thus $\sum d(v)=kE$ where $E$ is the number of hyperedges. We take $d(v)$ copies of each $v$, and we take a uniformly random partition of these $kE$ vertex-copies into $E$ sets of size $k$. This naturally yields a $k$-uniform hypergraph, by mapping each $k$-set to a hyperedge on the vertices whose copies are in the $k$-set. Note that the hypergraph may contain loops (two copies of the same vertex in one hyperedge) and multiple edges (two identical hyperedges). It is well known that the probability that this partition yields a simple hypergraph (i.e., one with no loops or multiple edges) is bounded below by a constant for degree sequencesClearly, we are referring to a sequence of degree sequences $\mathcal{S}_{n}$ so that asymptotic statements are meaningful. We suppress this point though, throughout, to streamline exposition. satisfying certain conditions. Specifically:

Say that a degree sequence $\mathcal{S}$ is nice if $E=\Theta(n)$, $\sum_{v}d(v)^{2}=O(n)$ and $d(v)=o(n^{1/24})$ for all $v$.

Every degree sequence we will consider will correspond to some subgraph of $H_{k}(n,p)$ with a linear expected number of edges. Since, as is well known, the degree sequence of such random hypergraphs is nice w.h.p., all the degree sequences we will consider will be nice. With this in mind, we will make heavy use of the following standard proposition (see eg. ) and corollary, as working in the configuration model is technically much easier than working with uniformly random hypergraphs with a given degree sequence.

If $\mathcal{S}$ is a nice degree sequence, then there exists $\epsilon>0$ such that the probability that a random hypergraph with degree sequence $\mathcal{S}$ drawn from the configuration model is simple is at least $\epsilon$.

If $\mathcal{S}$ is a nice degree sequence then:

If property $Q$ holds w.h.p. for $k$-uniform hypergraphs with degree sequence $\mathcal{S}$ drawn from the configuration model, then $Q$ holds w.h.p. for uniformly random simple hypergraphs with degree sequence $\mathcal{S}$.

For any random variable $X$, if $E(X)=O(1)$ for $k$-uniform hypergraphs with degree sequence $\mathcal{S}$ drawn from the configuration model, then $E(X)=O(1)$ for uniformly random simple hypergraphs with degree sequence $\mathcal{S}$.

The following lemma will be very useful. Its exponential term is not tight, but will suffice for our purposes.

since $i\leq k$. So the probability that each of the $L$ tuples is chosen to be in a hyperedge is less than

Recall from Section 4 that Theorem 5 is already known for $k=r=2$. So we will assume that $k+r>4$. It is well known that the $r$-core of a random $k$-uniform hypergraph is uniformly random conditional on its degree sequence. See for the case $k=2$, and for the nearly identical proof for general $k$. In fact, the same is true of the graph remaining after any number of iterations of the parallel stripping process.

Let $H=H_{k}(n,p)$ be a random $k$-uniform hypergraph and let ${H}=H_{0},H_{1},\ldots$ be the sequence of hypergraphs produced by the parallel $r$-stripping process. It is well known how (see e.g., ) to show the following propositions.

For every $i\geq 0$, $H_{i}$ is uniformly random with respect to its degree sequence.

There exist functions $\rho_{0},\rho_{1},\ldots$ such that for any fixed integer $i$, w.h.p. $H_{i}$ contains ${\rho_{j}(i)}n+o(n)$ vertices of degree $j$ and $\frac{1}{k}(\sum_{j\geq 1}j{\rho_{j}(i)})n+o(n)$ edges.

The functions $\rho_{j}(i)$ have explicit recursive expressions, which we give in Section 8. An approximation is stated in Proposition 31 below.

Proposition 25 allows us to use the configuration model to study $H_{i}$. We will begin by showing that we can uniformly approximate the total degree of $H_{i}$.

Proposition 25 implies that $\sum_{j\geq 1}j\rho_{j}(i)$ is convergent, else w.h.p. $H_{i}$, and hence $H$, would have a superlinear number of edges.

The following similar bound will also be useful:

For every constant $d$ and fixed integer $i>0$:

The proof is almost identical to that of Lemma 27 but exploits the concentration of the number of $d$-stars in $H$, rather than of the number of hyperedges. (A $d$-star is a set of $d$ hyperedges which contain a common vertex.) The concentration of the number of $d$-stars in $H$ is easily established, e.g., by the Second Moment Method or Talagrand’s Inequality. (Indeed, Lemma 27 and its proof are special cases of this lemma and its proof for $d=1$.) ∎

For any fixed integers $k,r$ and real number $\lambda>0$, we write

Recall that for $k+r>4$, the threshold for the appearance of an $r$-core in a random $k$-uniform hypergraph $H_{k}(n,p)$ with $p=c/n^{k-1}$ is

We will see that $f^{\prime}$ has a unique root and, thus, for $c>c^{*}_{k,r}$ the equation $f(\lambda)=c$ has two solutions.

For $c>c^{*}_{k,r}$, let $\mu=\mu(c)$ denote the larger of the two solutions of $f(\lambda)=c$.

The following two propositions are standard; see e.g., for proofs.

For every fixed $j\geq r$, w.h.p. the $r$-core contains $(e^{-\mu}\mu^{j}/j!)n+o(n)$ vertices of degree $j$. Furthermore, w.h.p. the $r$-core contains $(\mu/k)\Psi_{r}(\mu)n+o(n)$ edges.

For every $c\neq c_{k,r}^{*}$ and $\theta>0$, there exists $B=B(\theta)$ such that w.h.p.

$H_{B}$ contains fewer than $\theta n$ vertices not in the $r$-core;

For each $j\geq r$, $|\rho_{j}(B)-e^{-\mu}\mu^{j}/j!|<\theta$.

The following lemma will be critical for our analysis.

For every $c>c^{*}_{k,r}$, there exists $\zeta=\zeta(k,r,c)>0$ such that

where $\mu$ is the larger of the two roots of the equation $f_{k,r}(\lambda)=c$.

Equation (3) yields $c^{*}_{k,r}=f(\lambda^{*})$ for some $\lambda^{*}$ satisfying the last equation in (3). For $c>c^{*}_{k,r}$, since $\mu=\mu(c)$ is the larger of the two roots of $f(\lambda)=c$, it follows that $\mu>\lambda^{*}$. The lemma now follows by noting that the RHS of (2) divided by the LHS is proportional to $\sum_{i\geq r-1}\frac{\mu^{i-r+1}}{i!}$, which is clearly increasing with $\mu$. ∎

Preliminaries to the proof of Theorem 5

Recall that we assume $k+r>4$ and let $H=H_{k}(n,p)$ be a random $k$-uniform hypergraph with $p=c/n^{k-1}$. Let $H=H_{0},H_{1},\ldots$ be the sequence of hypergraphs produced by the parallel $r$-stripping process.

As we said above, we will choose a sufficiently large constant $B$, strip down to $H_{B}$, and then focus on $R^{+}(u)\cap H_{B}$, making use of the fact that $H_{B}$ is very close to the 2-core (by Proposition 31). The following will be used to bound the number of vertices that are removed from $R^{+}(u)$ when stripping down to $H_{B}$. For integer $s\geq 0$, we use $N^{s}(v)$ to denote the $s$-th neighborhood of $v$, i.e., the set of vertices within distance $s$ from $v$. For any set of vertices $A$, $N^{s}(A)=\bigcup_{v\in A}N^{s}(v)$. We consider a single vertex to be a connected set. A straightforward induction yields the following.

For any integer $i$ and vertex $u\in H_{i}$, $R^{+}(u)\subseteq N^{i}(R^{+}(u)\cap H_{i})$.

For any $c,s\geq 0$, there exists $\Gamma=\Gamma(c,s)$ such that in a random graph $G(n,p)$ with $p=c/n$, w.h.p. for every connected subset $A$ of vertices $|N^{s}(A)|\leq\Gamma(|A|+\log n)$.

We prove this for the case $s=1$, i.e., that there is a constant $\gamma>1$ such that w.h.p. every connected subset of vertices $A$ satisfies $|N(A)|\leq\gamma(|A|+\log n)$. By iterating, we obtain that for every $s\geq 1$, every connected subset of vertices $A$ satisfies $|N^{s}(A)|\leq f_{s}(|A|)$ where

A simple induction yields $f_{i}(x)\leq\gamma^{i}(x+i\log n)$ and that yields the lemma with $\Gamma=s\gamma^{s}$.

For any $\gamma>2$, if $|N(A)|>\gamma(|A|+\log n)$, then we must have $|N(A)\backslash A|>{1\over 2}\gamma(|A|+\log n)$. Taking $\gamma>4ec$, the expected number of connected sets $A$ satisfying this last inequality is at most

for $\gamma$ sufficiently large. Multiplying by the $n$ choices for $a$ yields the lemma. ∎

Fix $k\geq 3$ and let $H=H_{k}(n,p)$ be a random $k$-uniform hypergraph with $p=c/n^{k-1}$, where $c>c^{*}_{k,2}$.

The expected number of vertices in core flippable cycles of $H$ is $O(1)$.

W.h.p. no vertex lies in two core flippable cycles.

Let ${\cal D}$ be the degree sequence of the 2-core of $H$. By Corollary 23, we can work in the configuration model. Recalling Definition 29, Proposition 30 and Lemma 32, w.h.p.

${\cal D}$ has total degree $\gamma n+o(n)$, where $\gamma=\mu\Psi_{r}(\mu)$,

${\cal D}$ has $\lambda_{2}n+o(n)$ vertices of degree 2, where $\lambda_{2}=e^{-\mu}\mu^{2}/2$,

there exists $\zeta>0$ such that $2(k-1)\lambda_{2}<(1-\zeta)\gamma$.

We first bound the expected number of core flippable cycles of size $a$. Let $\Lambda=\gamma n+o(n)$ be the total number of vertex copies, and let $L=\lambda_{2}n+o(n)$ be the number of copies of degree 2 vertices.

There are ${L\choose a}$ choices for the connecting vertices, $\frac{(a-1)!}{2}$ ways to order them into a cycle, and $2^{a}$ ways to align their vertex-copies. This yields $a$ pairs $\{y_{1},z_{1}\},\ldots,\{y_{a},z_{a}\}$ of vertex copies, each of which must land in a hyperedge. We process these pairs one-at-a-time, halting if we ever find that the pair does not land in a hyperedge. To process pair $i$, we ask only whether $z_{i}$ lands in the same hyperedge as $y_{i}$; if it does we do not expose the other vertex-copies in that hyperedge. Thus, prior to processing pair $i$, we have exposed exactly $2i-2$ vertex-copies, all of degree 2. There are $k-1$ other copies appearing in the same hyperedge as $y_{i}$. Each of the $\Lambda-(2i-1)$ unexposed copies (not including $y_{i}$) is equally likely to be one of those copies (and, for $k\geq 3$, the exposed copies also have positive probability). So the probability that $z_{i}$ is one of them is at most $(k-1)/(\Lambda-2i+1)$. So the expected number of core flippable cycles of length $a$ is at most:

By condition (iii) above, $2(k-1)L/(\Lambda-1)<1-{1\over 2}\zeta$, and so $2(k-1)(L-i+1)/(\Lambda-2i+1)<1-{1\over 2}\zeta$ for each $i$, since $L\leq{1\over 2}(\Lambda-1)$. So the expected number is at most \mbox{\frac{1}{2a}}(1-{1\over 2}\zeta)^{a}, and so the expected total number of vertices on core flippable cycles is at most ${1\over 2}\sum_{a\geq 1}(1-{1\over 2}\zeta)^{a}=O(1)$. This establishes part (a).

We now prove part (b) by using a first moment calculation. We start by showing that if two core flippable cycles have a common vertex, then their union must contain a simple structure: a flippable cycle plus a path. The proof will then follow since w.h.p. any such structure in a sparse random hypergraph must be larger than what is permitted by part (a). Intuitively, this is straightforward, but the details are tedious.

for $a+b\leq{1\over 2}\log n$. Thus w.h.p. there is no such subgraph with $a+b\leq{1\over 2}\log n$. Since $|S|\geq|S^{\prime}|$, if $a+b>{1\over 2}\log n$ then |S|=a>\mbox{\frac{1}{4}}\log n. But part (a) and Markov’s Inequality imply that w.h.p. there is no core flippable cycle of size at least \mbox{\frac{1}{4}}\log n. This proves (b).

Proof of Theorem 5 above the r𝑟r-core threshold

Recall that we can assume $k+r>4$. We let $H=H_{k}(n,p)$ be a random $k$-uniform hypergraph with $p=c/n^{k-1}$. Let $H=H_{0},H_{1},\ldots$ be the sequence of hypergraphs produced by the parallel $r$-stripping process. We will choose a terminal $r$-stripping sequence that is consistent with the parallel process; i.e., in our stripping sequence: for every $i<j$, the vertices deleted in round $i$ of the parallel process come before the vertices deleted in round $j$ of the parallel process.

Let $D$ be the digraph associated with this terminal $r$-stripping sequence and recall that $R^{+}(u)$ denotes the set of vertices reachable from a vertex $u$ in $D$.

Our main challenge is to prove the following lemma. The idea is that we will take $B$ large enough so that by stripping down to $H_{B}$, Proposition 31 gives us control of the degree sequence that remains, and Lemma 32 allows us to prove that a certain branching process involving long paths in a graph constructed from $H_{B}$ dies out.

For every $c>c_{k,r}^{*}$ there exists $B=B(c,k,r)$ and $Q=Q(c,k,r)$ such that w.h.p. for every vertex $u$, $|R^{+}(u)\cap H_{B}|\leq Q\log n$.

Consider any vertex $u$. If $u\notin H_{B}$, then by Proposition 33, $R^{+}(u)\subseteq N^{B}(u)$ in which case Lemma 34 immediately implies that $|R^{+}(u)|<\Gamma(1+\log n)$ for some constant $\Gamma=\Gamma(c,B)$.

If $u\in H_{B}$, then $R^{+}(u)\subseteq N^{B}(R^{+}(u)\cap H_{B})$, by Proposition 33. Since, by Lemma 36, $|R^{+}(u)\cap H_{B}|\leq Q\log n$, Lemma 34 now implies that $|R^{+}(u)|<\Gamma(Q\log n+\log n)=Z\log n$ for $Z=\Gamma Q+1=Z(c,B)=Z(c,k,r)$. ∎