<figure><img src="image_1.png" /></figure>

HAL
open science

# Multirange percolation on oriented trees: Critical curve and limit behavior

Bernardo N B de Lima, Réka Szabó, Daniel Valesin

► To cite this version:

Bernardo N B de Lima, Réka Szabó, Daniel Valesin. Multirange percolation on oriented trees: Critical curve and limit behavior. Random Structures and Algorithms, 2022, 62 (2), pp.519-541. 10.1002/rsa.21104 . hal-04911136

HAL Id: hal-04911136

https://univ-paris-dauphine.hal.science/hal-04911136v1

Submitted on 24 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RESEARCH ARTICLE

<figure><img src="image_3.png" /></figure>

# Multirange percolation on oriented trees: Critical curve and limit behavior

Bernardo N. B. de Lima<fnref n="1" /> | Réka Szabó<fnref n="2" /> | Daniel Valesin<fnref n="3" />

**Correspondence**

Réka Szabó, CEREMADE, CNRS, Université Paris-Dauphine, PSL University, Paris, France.
Email: szabo@ceremade.dauphine.fr

**Abstract**

We consider an inhomogeneous oriented percolation model introduced by de Lima, Rolla and Valesin. In this model, the underlying graph is an oriented rooted tree in which each vertex points to each of its *d* children with “short” edges, and in addition, each vertex points to each of its *d*^k descendant at a fixed distance *k* with “long” edges. A bond percolation process is then considered on this graph, with the prescription that independently, short edges are open with probability *p* and long edges are open with probability *q*. We study the behavior of the critical curve $q_c = q_c(p, k, d)$: we find the first two terms in the expansion of $q_c$ as $k \to \infty$. We also prove limit theorems for the percolation cluster in the supercritical, subcritical and critical regimes.

**KEYWORDS**

critical curve, inhomogeneous percolation, long range percolation

# 1 | INTRODUCTION

## 1.1 | Background and motivation

This article is a continuation of the work presented in [10]. In that paper, the authors considered an oriented graph whose vertex set is that of the *d*-regular, rooted tree, containing “short edges” (with which each vertex points to its *d* children) and, for some *k* ∈ N fixed, “long edges” of range *k* (with which each vertex points to its *d*^k descendants *k* generations below). Percolation is defined on this graph by letting short edges be open with probability *p* and long edges with probability *q*. For all

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

© 2022 The Authors. *Random Structures and Algorithms* published by Wiley Periodicals LLC.

<footnote n="1">¹Universidade Federal de Minas Gerais, Belo Horizonte, Brazil</footnote>

<footnote n="2">²CEREMADE, CNRS, Université Paris-Dauphine, PSL University, Paris, France</footnote>

<footnote n="3">³Department of Statistics, University of Warwick, Coventry, United Kingdom</footnote>
fixed *q* one can define the critical percolation threshold as the supremum of the values of *p* for which there is almost surely no infinite cluster at parameters *p*, *q*. The authors of [10] study the properties of this critical curve and prove monotonicity with respect to the length of the long edges.

The work was originally motivated by the following problem. Consider the graph having $\mathbb{Z}^d$ as vertex set and all edges of the form $\{x, x \pm e_i\}$ and $\{x, x \pm k \cdot e_i\}$ for some $k \ge 2$ and $i \in \{1, \dots, d\}$. It was shown in [12] that the critical probability for Bernoulli bond percolation on this graph converges to that of $\mathbb{Z}^{2d}$ as $k \to \infty$. This result was later generalized in [14]. The convergence is conjectured to be monotone, that is, the percolation threshold for the above graph should be decreasing in the length *k* of long edges.

Percolation is mostly studied on the lattice $\mathbb{Z}^d$ in homogeneous environment (that is, each edge is open with the same probability independently of each other). Let us briefly mention some related works that consider an inhomogeneous setting. In [9] an oriented site percolation model is considered on $\mathbb{Z}_+^2$ in a random environment. Each line $l_i := \{(x, y) \in \mathbb{Z}_+^2 : x + y = i\}$ is declared to be bad with probability $\delta$, then the sites on bad lines are open with probability $p_B$ and every other site is open with probability $p_G$. It is shown that for all $p_G > p_c(\mathbb{Z}_+^2)$ and $p_B > 0$ we can choose $\delta > 0$ small enough, that there is an infinite cluster with positive probability. Another interesting paper with the same spirit is [5], about Brochette percolation. A bond percolation model is considered on $\mathbb{Z}^2$ where vertical lines of the form $l_i := \{(x, y) \in \mathbb{Z}_+^2 : x = i\}$ are selected at random with probability $\delta$, then the edges on the selected lines are open with probability *p* and every other edge is open with probability *q*. The authors show that for all $p > p_c(\mathbb{Z}^2)$ and any $\delta > 0$ we can choose $q < p_c(\mathbb{Z}^2)$ such that there is an infinite cluster with positive probability.

In [7] the authors study a nonoriented bond percolation model on $\mathbb{Z}^d$ with an *s*-dimensional defect plane $\mathbb{Z}^s$. Edges of $\mathbb{Z}^d \setminus \mathbb{Z}^s$ are open with probability *p* and edges of $\mathbb{Z}^s$ are open with probability $\sigma$. They present the phase diagram of the model and identify three regimes in which the model exhibits quantitatively different behavior. They also show that the critical curve is a strictly decreasing function for *p* with a jump discontinuity at $p_c(\mathbb{Z}^d)$.

In [6] the authors consider nonoriented percolation on the direct product of a regular tree and $\mathbb{Z}$, where tree edges and line edges are open with different probabilities. They identify three distinct phases in which the number of clusters is 0, $\infty$ and 1 respectively.

In [16] for an arbitrary connected graph $G = (V, E)$ a nonoriented and an oriented percolation model are defined on the vertex set $V \times \mathbb{Z}$. The authors examine how changing the percolation parameter on a fixed (infinite) set of edges affects the critical behavior. They show that in both cases the critical parameter changes as a continuous function of these parameters. This result was later generalized in [11].

## 1.2 | Description of the model and results

Given $d, k \in \{2, 3, \dots\}$, define an oriented graph $T = T_{d,k} = (V, E)$ in the following way. Denote

$$[d] = \{1, \dots, d\}, \quad [d]_* = \bigcup_{0 \le n < \infty} [d]^n.$$

The set $[d]^0$ consists of a single point *o*, which we will refer to as the root of the graph. Set $V = [d]_*$, that is, elements of $V$ are sequences $v = (v_1, \dots, v_m)$ with $v_i \in [d]$ (and the root *o*). Define the concatenation of $u = (u_1, \dots, u_m)$ and $v = (v_1, \dots, v_n)$ as

$$u \cdot v = (u_1, \dots, u_m, v_1, \dots, v_n);$$
$$v \cdot o = o \cdot v = v.$$

Further let $E = E_s \cup E_\ell$ be the set of oriented edges with

$$E_s = \{\langle r, r \cdot i \rangle : r \in V, i \in [d]\}, \quad E_\ell = \{\langle r, r \cdot i \rangle : r \in V, i \in [d]^k\}.$$

We will refer to these sets as the set of “short” and “long” edges, respectively. Define the out-degree of a vertex as the number of oriented edges directed out of the vertex. Note that in $T_{d,k}$ every vertex has out-degree $d + d^k$.

Consider the following percolation model on $\mathbb{T}$: every edge in $E_s$ is open with probability $p$, and every edge in $E_\ell$ is open with probability $q$, independently of each other. Denote the law of the model by $\mathbb{P}_{p,q}$. We will omit the subscript $p, q$ when it is clear from the context; we will also generally omit $d$ and $k$ from the notation. Define the cluster of the root $\mathcal{C} = \mathcal{C}_{p,q}$ as the set of vertices that can be reached by an oriented open path from $o$, and $|\mathcal{C}|$ as its cardinality. Whether or not the event $\{|\mathcal{C}_{p,q}| = \infty\}$ occurs with positive probability depends on $p, q, d$ and $k$. We define

$$q_c = q_c(p, k, d) := \inf\{q : \mathbb{P}(|\mathcal{C}_{p,q}| = \infty) > 0\}.$$

Note that the model with $q = 0$ reduces to oriented percolation on a $d$-ary tree, and the model with $p = 0$ reduces to oriented percolation on disconnected $d^k$-ary trees. This shows that $q_c(0, k, d) = d^{-k}$ and $q_c(p, k, d) = 0$ for $p > d^{-1}$.

In [10] the authors show that $q_c$ is continuous and strictly decreasing in $p$ in the region where it is positive (namely, for $p \in [0, d^{-1}$), and there is almost surely no infinite cluster for $p \in [0, d^{-1}$] and $q = q_c$. Additionally, it is easy to see that this percolation model is stochastically dominated by a branching process with offspring distribution that is the sum of two independent binomial random variables, namely Bin($d, p$) and Bin($d^k, q$). This branching process is critical for parameters satisfying $dp+d^kq = 1$, implying $q_c \ge (1 - dp)/d^k$ for $p \in (0, d^{-1})$. By means of a useful coupling technique it can be proved that this inequality is strict (see section 3 of [17]).

We study the asymptotic behavior of $q_c$ as the length $k$ of long edges is taken to infinity, when $p < d^{-1}$ (that is, there is no percolation using only short edges). Since we have that $q_c(p, k, d) \le q_c(0, k, d) = d^{-k}$ for any $p \ge 0$, we readily obtain that $q_c \xrightarrow{k \to \infty} 0$. We find the two first asymptotic terms in this convergence (for an illustration of the curve see Figure 1).

**Theorem 1.1.** Assume $pd < 1$. Then, as $k \to \infty$,

$$q_c(p, k, d) = (1 - pd) \cdot \frac{1}{d^k} + \frac{(1 - pd)^2 p^2 d}{1 - p^2 d} \cdot \frac{1}{d^{2k}} + o\left(\frac{1}{d^{2k}}\right).$$

<figure><img src="image_4.png" /><figcaption>FIGURE 1 $(0, d^{-1}) \ni p \mapsto q_c(p, k, d)$ lies strictly above the dotted line, which has equation $dp + d^kq = 1$.</figcaption></figure>
The proof relies on comparisons between exploration processes of our percolation cluster, on the one hand, and multitype branching processes, on the other hand. With such comparisons at hand, many results from the theory of multitype branching processes can be applied to the percolation cluster; in the following theorem we collect a few that we find particularly noteworthy. Let $X_n$ denote the number of vertices of height $n$ in $\mathcal{C}_{p,q}$.

**Theorem 1.2.**

(i) If $q > q_c$, then there exists a constant $\rho = \rho(p, q)$ and a nonnegative random variable $Y$ such that $\mathbb{P}(Y > 0) > 0$ and

$$ \lim_{n \to \infty} \frac{X_n}{\rho^n} = Y \text{ a.s.} $$

(ii) If $q < q_c$, then for each $i \ge 0$ the limit

$$ P(i) := \lim_{n \to \infty} \mathbb{P}(X_n = i | X_n \neq 0) $$

exists. Moreover, $\sum_{i=0}^{\infty} P(i) = 1$.

(iii) Assume that $p \in [0, d^{-1}]$ and $q = q_c$. Then, $\mathcal{C}_{p,q}$ rooted at $o$ and conditioned on having more than $n$ vertices converges locally as $n \to \infty$ to a random rooted graph (in the Benjamini–Schramm sense [4]).

We will recall the meaning of Benjamini–Schramm local convergence of rooted graphs in Section 4.1.

**1.3 | Discussion of proofs and organization of the article**

The proofs of both theorems rely on comparisons with multitype branching processes. In Section 2 we give an overview of multitype branching processes, with the aim of fixing notation, listing common regularity and positivity assumptions on the offspring distribution, and reviewing key related objects (the mean offspring matrix and its Perron–Frobenius eigenvalue).

In Section 3 we prove Theorem 1.1. The main idea is to explore the percolation cluster by repeating a two-stage procedure which takes as input a set $B$ of vertices (all of which have a common ancestor at distance smaller than $k$ away), first explores its “short cluster” (that is, the set of vertices that can be reached from $B$ through open short edges), and secondly reveals all open long edges that start at this short cluster. The endpoints of these open long edges are then grouped into sets $B_1, B_2, \dots$, to each of which the procedure is applied again. A similar exploration method was employed in [10]. The contribution here is to take the analysis of this exploration further by studying a multitype branching process, where the set of types is the set of all possible “shapes” of the input set. A careful analysis of the mean offspring matrix of this branching process yields upper and lower bounds to the threshold $q_c$. By expanding on our method, one could try to deduce higher-order terms in the expansion of $q_c$, see Remark 3.13.

Finally, in Section 4 we prove Theorem 1.2. This relies on a much simpler exploration method, which reveals the percolation cluster by incrementing its height one unit at a time. The three parts of Theorem 1.2 are almost direct applications of corresponding branching process limit theorems, which we recall in that section.
## 2 | BASIC FACTS ABOUT MULTITYPE BRANCHING PROCESSES

In this section, we give some basic definitions and notations concerning multitype branching processes. We refer the reader to [3] for a detailed introduction to this topic.

We let $\mathcal{T}$ be a finite set, representing the space of types for our branching process. Elements of $\mathcal{T}$ will be denoted by lower-case letters such as $a$ and $b$. The state space of a multitype branching process with space of types $\mathcal{T}$ is the set $(\mathbb{N}_0)^{\mathcal{T}}$ where $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$; elements of this set will be denoted by Greek letters such as $\eta$ or $\xi$. The interpretation is that $\eta \in (\mathbb{N}_0)^{\mathcal{T}}$ corresponds to a population with $\eta(a)$ individuals of type $a$, for each $a \in \mathcal{T}$. We let $e_a \in (\mathbb{N}_0)^{\mathcal{T}}$ denote a population with a single individual of type $a$.

Next, let $\rho : \mathcal{T} \times (\mathbb{N}_0)^{\mathcal{T}} \to \mathbb{R}$ be a function such that

$$ \rho(a, \eta) \ge 0 \quad \forall a \in \mathcal{T}, \eta \in (\mathbb{N}_0)^{\mathcal{T}} \quad \text{and} \quad \sum_{\eta \in (\mathbb{N}_0)^{\mathcal{T}}} \rho(a, \eta) = 1 \quad \forall a \in \mathcal{T}. $$

We interpret $\rho(a, \eta)$ as the probability that an individual of type $a$ at generation $n$ is replaced by the population $\eta$ at generation $n+1$. In order to avoid certain pathological situations, it is common to assume that $\rho$ is such that at least one of the types has positive probability of generating a population with more than one individual, that is,

$$ \rho(a, \eta) > 0 \text{ for some } a \in \mathcal{T} \text{ and } \eta \in (\mathbb{N}_0)^{\mathcal{T}} \text{ with } \sum_b \eta(b) > 1. \quad (\star) $$

A multitype branching process with space of types $\mathcal{T}$ and offspring distribution $\rho$ is a Markov chain $Z = (Z_n)_{n \ge 0}$ on $(\mathbb{N}_0)^{\mathcal{T}}$ with transition function described as follows. Given that $Z_n = \eta$, the distribution of $Z_{n+1}$ is equal to the law of

$$ \sum_{a \in \mathcal{T}} \sum_{\ell=1}^{\eta(a)} \chi_{a, \ell}, $$

where $(\chi_{a,\ell} : a \in \mathcal{T}, \ell \in \mathbb{N})$ are independent random variables with $\chi_{a,\ell} \sim \rho(a, \cdot)$ for each $a, \ell$ for each $a, \ell$ (and the second summation above should be understood as zero if $\eta(a) = 0$). We refer to $Z_n$ as the population at generation $n$.

We say that the multitype branching process $Z$ goes extinct if the event that $Z_n = (0, \dots, 0)$ for some $n$ occurs; otherwise we say that it survives. We denote its survival probability by

$$ \zeta(a) = \mathbb{P}(Z \text{ survives} | Z_0 = e_a), \quad a \in \mathcal{T}. $$

With some abuse of notation, we can define a function from $(\mathbb{N}_0)^{\mathcal{T}}$ to $\mathbb{R}$, also denoted $\zeta$, by letting

$$ \zeta(\eta) := \mathbb{P}(Z \text{ survives} | Z_0 = \eta) = 1 - \prod_{a \in \mathcal{T}} (1 - \zeta(a))^{\eta(a)}, \quad \eta \in (\mathbb{N}_0)^{\mathcal{T}}. \quad (1) $$

We next define the mean offspring matrix

$$ M(a, b) := \mathbb{E}[Z_1(b) | Z_0 = e_a], \quad a, b \in \mathcal{T}. \quad (2) $$
A common assumption about this matrix is that

$$ \text{there exists } n \in \mathbb{N} \text{ such that } M^n(a, b) > 0 \text{ for all } a, b \in \mathcal{T}. \qquad (P) $$

If $M$ satisfies (P), then by the Perron-Frobenius theorem it has a maximal eigenvalue $\rho$ which is positive and simple.

For the rest of this section, we assume that both $(\star)$ and (P) hold; moreover, all the multitype branching processes that we consider in the rest of the article will satisfy both assumptions. When they are in place, the following holds. If $\rho \le 1$ we have $\zeta(a) = 0$ for all $a \in \mathcal{T}$, whereas if $\rho > 1$ we have $\zeta(a) > 0$ for all $a \in \mathcal{T}$ (see for example chapter V of [3]). We call the process supercritical, critical or subcritical if $\rho > 1$, $\rho = 1$ or $\rho < 1$ respectively.

Finally, let us mention that, in place of a stochastic process $(Z_n)_{n \ge 0}$ on $(\mathbb{N}_0)^{\mathcal{T}}$, a natural way to represent a multitype branching process is by means of a (random, marked, unoriented) tree, which we will call the family tree of the process, denoted $\tau$. The construction is as follows: each individual of type $a$ in $Z$ is represented by a vertex with mark $a$ in $\tau$, and an (unoriented) edge is placed for each pair {parent, child}. In case the initial population of $Z$ has a single individual, then $\tau$ consists of a single connected tree (which is infinite if and only if $Z$ survives). More generally, an initial population with $m$ individuals would give rise to $m$ disconnected trees, but we will not need to consider this case. The random tree $\tau$ is sometimes referred to as a multitype Galton-Watson tree.

# 3 | ASYMPTOTICS ON LENGTH OF LONG EDGES

The goal of this section is proving Theorem 1.1. Before going back to our percolation model on $\mathbb{T}$, we prove some results about transformations on multitype branching processes, and the effects of these transformations on the survival probability. This is done in Section 3.1; there, the main result we are after is Lemma 3.3 below. We will then appeal to this result when analyzing the mean offspring matrix associated to a branching process that arises when exploring the percolation cluster, in Section 3.2.

## 3.1 | Preliminary results on branching processes

We will now prove some auxiliary results concerning two comparison processes obtained from a multitype branching process.

Let $Z = (Z_n)_{n \ge 0}$ be a multitype branching process with set of types $\mathcal{T}$ and offspring distribution $\rho$. Let $I \subset \mathcal{T}$ be a strict subset of the set of types. Define a new multitype branching process $X = (X_n)_{n \ge 0}$ with same set of types $\mathcal{T}$, and offspring distribution $\tilde{\rho}$ given as follows. For each $a \in \mathcal{T}$, the distribution $\tilde{\rho}(a, \cdot)$ on $(\mathbb{N}_0)^{\mathcal{T}}$ is the distribution of

$$ \sum_{b \notin I} \chi(b) \cdot e_b + \sum_{b \in I} \sum_{\ell=1}^{\chi(b)} \chi'_{b, \ell}, $$

where

$$ \chi \sim \rho(a, \cdot) \quad \text{and} \quad \chi'_{b, \ell} \sim \rho(b, \cdot) \text{ for all } b \in I, \ell \in \mathbb{N}, $$

all these variables being taken independently. In words, this is described as follows. Fix an individual of type $a$ in some generation of $X$. Then, to sample the population obtained as offspring of this individual,
we first sample $\chi \sim p(a, \cdot)$, according to the law of the offspring of type $a$ in the original process $Z$. The portion of the population $\chi$ whose type does not belong to $I$ is left unaltered. Next, each individual in $\chi$ of type $b \in I$ is replaced by a further offspring sampled (independently) according to the law $p(b, \cdot)$. All these populations are then combined together.

The following can be easily proved with the aid of the family tree of $Z$; we omit the details.

**Lemma 3.1.** Let $Z$, $I$ and $X$ be as above. We then have, for any $\eta \in (\mathbb{N}_0)^{\mathcal{T}}$,

$$ \mathbb{P}(\mathbf{Z} \text{ survives} | \mathbf{Z}_0 = \eta) = \mathbb{P}(\mathbf{X} \text{ survives} | \mathbf{X}_0 = \eta). $$

We now turn to the description of our second comparison process. Again let $Z$ be a multitype branching process with set of types $\mathcal{T}$ and offspring distribution $p$. Let $a_{\star} \in \mathcal{T}$ be a distinguished type, and assume that there exists a function $\lambda : \mathcal{T} \to \mathbb{N}$ with $\lambda(a_{\star}) = 1$ and such that

$$ \mathbb{P}(\mathbf{Z} \text{ survives} | \mathbf{Z}_0 = \mathbf{e}_a) \le \mathbb{P}(\mathbf{Z} \text{ survives} | \mathbf{Z}_0 = \lambda(a) \cdot \mathbf{e}_{a_{\star}}) \quad \text{for all } a \in \mathcal{T}, \quad (3) $$

that is, the process has at least as high a chance of surviving when started from a population of $\lambda(a)$ individuals of type $a_{\star}$ than it would if started with a single individual of type $a$. We now define a (one-type) branching process $(Y_n)_{n \ge 0}$ with $Y_0 = 1$ and offspring distribution equal to the law of

$$ \sum_{a \in \mathcal{T}} \lambda(a) \cdot \chi(a), \quad \text{where } \chi \sim p(a_{\star}, \cdot). $$

We then have:

**Lemma 3.2.** Let $Z$, $a_{\star}$, $\lambda$ and $(Y_n)$ be as above. If $(Y_n)$ goes extinct with probability one, then $Z$ started from $\mathbf{Z}_0 = \mathbf{e}_{a_{\star}}$ also goes extinct with probability one.

*Proof.* Recall the definition of $\zeta$ from (1), and define $\bar{\zeta}(a) = 1 - \zeta(a)$ for $a \in \mathcal{T}$ and $\bar{\zeta}(\eta) = 1 - \zeta(\eta)$ for $\eta \in (\mathbb{N}_0)^{\mathcal{T}}$. Note that (3) can then be written

$$ \bar{\zeta}(a) \ge \bar{\zeta}(\lambda(a) \cdot \mathbf{e}_{a_{\star}}) \stackrel{(1)}{=} \bar{\zeta}(a_{\star})^{\lambda(a)}. \quad (4) $$

With some abuse of notation, we lift $\lambda$ to a function on $(\mathbb{N}_0)^{\mathcal{T}}$ by letting

$$ \lambda(\eta) := \sum_{a \in \mathcal{T}} \eta(a) \cdot \lambda(a), \quad \eta \in (\mathbb{N}_0)^{\mathcal{T}}, $$

and note that, for any $\eta$,

$$ \bar{\zeta}(\eta) \stackrel{(1)}{=} \prod_{a \in \mathcal{T}} (\bar{\zeta}(a))^{\eta(a)} \stackrel{(4)}{\ge} \prod_{a \in \mathcal{T}} (\bar{\zeta}(a_{\star}))^{\lambda(a) \cdot \eta(a)} = (\bar{\zeta}(a_{\star}))^{\lambda(\eta)}. $$

We then have

$$ \bar{\zeta}(a_{\star}) = \mathbb{E}[\bar{\zeta}(\mathbf{Z}_1) | \mathbf{Z}_0 = \mathbf{e}_{a_{\star}}] \ge \mathbb{E}[(\bar{\zeta}(a_{\star}))^{\lambda(\mathbf{Z}_1)} | \mathbf{Z}_0 = \mathbf{e}_{a_{\star}}] = \mathbb{E}[(\bar{\zeta}(a_{\star}))^{Y_1}]. \quad (5) $$

Let $G(s) := \mathbb{E}[s^{Y_1}]$ be the probability generating function of the offspring distribution of $(Y_n)$. It is easy to check recursively that
$$ \mathbb{E}[s^{Y_n}] = G^{(n)}(s), $$

where $G^{(n)}$ is the n-fold composition of $G$. Note that for $s = \bar{\zeta}(a_\star)$, (5) gives $s \ge G(s)$, which can be iterated (since $G$ is nondecreasing) to $s \ge G^{(n)}(s)$ for any $n$. Hence,

$$ \bar{\zeta}(a_\star) \ge G^{(n)}(\bar{\zeta}(a_\star)) = \mathbb{E}[(\bar{\zeta}(a_\star))^{Y_n}] \stackrel{(1)}{=} \mathbb{E}[\bar{\zeta}(Y_n \cdot e_{a_\star})]. $$

Now, if $(Y_n)$ goes extinct almost surely, then $Y_n \to 0$ almost surely as $n \to \infty$, so the right-hand side above converges to 1 as $n \to \infty$, so $\bar{\zeta}(a_\star) = 1$. ■

We now give the final form of the comparison result that will be used in the following subsection.

**Lemma 3.3.** Let $\mathbf{Z} = (\mathbf{Z}_n)_{n \ge 0}$ be a multitype branching process with set of types $\mathcal{T}$, offspring distribution $\rho$, and mean offspring matrix $M$. Let $a_\star \in \mathcal{T}$ and $I \subseteq \mathcal{T} \setminus \{a_\star\}$, and assume that $\mathbf{Z}_0 = e_{a_\star}$.

(a) If

$$ M(a_\star, a_\star) + \sum_{a \in I} M(a_\star, a) \cdot M(a, a_\star) > 1, \qquad (6) $$

then $\mathbf{Z}$ survives with positive probability;

(b) Let $\lambda : \mathcal{T} \to \mathbb{N}$ be a function satisfying $\lambda(a_\star) = 1$ and (3). Then,

$$ \sum_{a \notin I} M(a_\star, a) \cdot \lambda(a) + \sum_{a \in I} \sum_{b \in \mathcal{T}} M(a_\star, a) \cdot M(a, b) \cdot \lambda(b) < 1, \qquad (7) $$

then $\mathbf{Z}$ goes extinct almost surely.

*Proof.* For (a), first define a process $\mathbf{X}$ as the one of Lemma 3.1, start it from a single individual of type $a_\star$, and modify its offspring distribution $\bar{p}(a_\star, \cdot)$ so that all individuals of type different from $a_\star$ are discarded. This gives rise to a one-type branching process which is smaller than $\mathbf{X}$; its mean offspring is the expression on the left-hand side of (6), so it is supercritical if this expression is larger than 1. This proves that (6) implies that $\mathbf{X}$ survives with positive probability, so by Lemma 3.1, the same holds for $\mathbf{Z}$.

For (b), take the same process $\mathbf{X}$ as above. Note that, by Lemma 3.1, condition (3) holds with $\mathbf{X}$ in place of $\mathbf{Z}$. We then define a one-type branching process process $(W_n)_{n \ge 0}$ from $\mathbf{X}$ in the same way that the process $(Y_n)$ of Lemma 3.2 is constructed from $\mathbf{Z}$ (that is, in the offspring population, any individual of type $a$ is replaced by $\lambda(a)$ individuals of type $a_\star$). Then, the mean offspring of $(W_n)$ is equal to the left-hand side of (7). If this number is smaller than 1, then $(W_n)$ goes extinct with probability 1, so (by Lemma 3.2) $\mathbf{X}$ goes extinct with probability 1, so (by Lemma 3.1) $\mathbf{Z}$ goes extinct with probability 1. ■

## 3.2 | First branching process representation of percolation cluster

We now go back to the study of our percolation model on $\mathbb{T}_{d,k}$. For the rest of this section, we fix $p$ and $d$ with $pd < 1$, so that there is no percolation using only short edges.
We first introduce some notation and terminology. For a vertex $v \in V$ define the function $h$ to be its distance (in short edges) from the root:

$$h(o) := 0, \quad h((v_1, \dots, v_m)) := m,$$

and for a set $A \subseteq V$ let

$$h(A) := \sup_{v \in A} h(v).$$

For any $v \in V$ let $\mathbb{T}^v = (V^v, E^v)$ and $\Gamma^v = (V_\Gamma^v, E_\Gamma^v)$ be the subgraphs of $\mathbb{T}$ induced by the vertex sets

$$V^v = \{v \cdot s : s \in V\}, \qquad (8)$$

$$V_\Gamma^v = \{v \cdot s : s \in V, h(s) < k\}, \qquad (9)$$

that is the subgraph rooted at $v$ and the subgraph of height $k-1$ rooted at $v$.

We now define a property of sets of vertices that will be of interest in the following.

**Definition.** A set $B \subseteq V$ is called *admissible* if there exists a (necessarily unique) vertex $u \in B$ such that $B \subseteq V_\Gamma^u$. In this case, we say that $u$ is the *base* of $B$, and write $u = b(B)$. The *type* of $B$ is defined as

$$t(B) := \{v \in V_\Gamma^o : u \cdot v \in B\},$$

that is, $t(B)$ is the set of vertices which must be concatenated with $u$ in order to produce $B$.

In what follows, we let $B \subseteq V$ be an admissible set. We define $\mathscr{C}^B = \mathscr{C}^B(\omega)$ as the “cluster of $B$”, that is, the set of vertices that can be reached by an oriented open path from some vertex in $B$ (with the understanding that $B \subseteq \mathscr{C}^B$). Note that

$$\mathscr{C}^B = \bigcup_{x \in B} \mathscr{C}^{\{x\}}. \qquad (10)$$

Recall that we have defined $\mathscr{C} = \mathscr{C}^{\{o\}}$ as the cluster of the root. The following inequality will be very useful in the sequel:

$$\mathbb{P}(|\mathscr{C}^B| < \infty) \geq \mathbb{P}(|\mathscr{C}| < \infty)^{|B|}. \qquad (11)$$

This can be seen from (10), by revealing the clusters $\mathscr{C}^{\{x\}}$, for $x \in B$, one by one, and using the FKG inequality.

We now let $C_\delta^B$ be the “short cluster of $B$”, that is, the set of vertices that can be reached by an oriented open path that starts from some vertex in $B$ and uses only edges of $E_\delta$. We again adopt the convention that $B \subseteq C_\delta^B$. Note that $C_\delta^B \subseteq \mathscr{C}^B$. Now, suppose that we have revealed $C_\delta^B$ (this involves querying short edges only) and, once this is done, we reveal all open long edges that start at some point of $C_\delta^B$. Let $C_\ell^B$ be the set of vertices that are obtained as endpoints of these long edges. Equivalently,

$$C_\ell^B := \left\{ \begin{array}{l} r \in \mathscr{C}^B \setminus C_\delta^B : r \text{ is the endpoint of some} \\ \text{open long edge started from } C_\delta^B \end{array} \right\}.$$
We write $C_s^o$ and $C_\ell^o$ instead of $C_s^{\{o\}}$ and $C_\ell^{\{o\}}$ and $C_\ell^{\{o\}}$. The following lemma is an easy consequence of the assumption that $B$ is admissible, so we omit the proof.

**Lemma 3.4.** *The following statements hold:*

(i) for any $u \in C_\ell^B$, we have $V^u \cap C_s^B = \emptyset$, and

(ii) for any $u, v \in C_\ell^B$ with $v \in V^u$, we have $h(v) - h(u) < k$.

We will now decompose $C_\ell^B$ in a very useful manner. To do so, first declare that two vertices $u, v \in C_\ell^B$ are related if there exists $w \in C_\ell^B$ such that $u, v \in V^w$; it is readily seen that this is an equivalence relation. Then let $B^B$ be the collection of equivalence classes induced by this relation. Again, we write $B^o$ instead of $B^{\{o\}}$.

**Lemma 3.5.** *For any admissible set $B$,*

(i) every $B' \in B^B$ is admissible, and

(ii) the sets $V^{\mathcal{B}(B')}$, with $B'$ ranging over $B^B$, are disjoint, and disjoint from $C_s^B$.

*Proof.* It readily follows from the definition of the equivalence relation given above that for each $B' \in B^B$ there is a unique vertex $u_*(B') \in B'$ such that $B' \subseteq V^{u_*(B')}$, and also that if $B', B'' \in B^B$ are distinct, then $V^{u_*(B')}$ and $V^{u_*(B'')}$ are disjoint. The statements of the lemma readily follow from these considerations and Lemma 3.4. ■

For an example of a short cluster $C_s^o$ and the decomposition of $C_\ell^o$ see Figure 2.

Let the set $\mathcal{A}$ of possible types be the set of all admissible sets with base equal to the root $o$,

$$ \mathcal{A} = \{A \subseteq V_\Gamma^o : o \in A\}. $$

The set $\mathcal{A}$ will be the space of types of the multitype branching process that we will soon define. We emphasize that, although in Sections 2 and 3.1 we represented types by lowercase letters ($a, b$), here we will represent them by uppercase letters ($A, B$), since they are themselves sets.

<figure><img src="image_5.png" /><figcaption>FIGURE 2 An example of $\mathcal{C}$, $C_s^o$ and $C_\ell^o$ on $\mathbb{T}_{2,3}$. In this case $B^o = \{B_1, B_2, B_3\}$</figcaption></figure>
**Corollary 3.6.** Let $B \subseteq V$ be admissible. Condition on $C_s^B$ and $C_\ell^B$ (so that $B^B$ is also determined). Then, the clusters

$$ \mathcal{C}^{B'} : B' \in B^B $$

are independent. Moreover, if $B' \in B^B$ with $\beta(B') = u$ and $t(B') = A$, then the distribution of

$$ \{v : u \cdot v \in \mathcal{C}^{B'}\} $$

is equal to the (unconditioned) distribution of $\mathcal{C}^A$.

*Proof.* Fix $U, U' \subseteq V$ for which the event $\{C_s^B = U, C_\ell^B = U'\}$ has positive probability, and condition on this event. Note that its occurrence can be decided by inspecting the statuses of all edges, short and long, that begin in $U$. By Lemma 3.5, none of these edges belong to any of the subtrees induced by the vertex sets

$$ V^{\beta(B')} : B' \in B^B. $$

The claimed independence then follows from the fact, also given in Lemma 3.5, that these subtrees are disjoint. The claimed equality of distributions follows from the simple observation that the distribution of open edges in $\{\langle u \cdot v, u \cdot v' \rangle : \langle v, v' \rangle \in E\}$ is equal to that of $\{\langle v, v' \rangle : \langle v, v' \rangle \in E\}$, for any $u \in V$. ■

We now apply Lemma 3.5 and Corollary 3.6 recursively to obtain important consequences. Letting $B \subseteq V$ be admissible, define the collections $\mathcal{Z}_0^B, \mathcal{Z}_1^B, \dots$ of admissible sets recursively by letting $\mathcal{Z}_0^B = \{B\}$ and

$$ \mathcal{Z}_{n+1}^B = \bigcup_{B' \in \mathcal{Z}_n^B} B^{B'}, \quad n \ge 0. $$

Then, Lemma 3.5 gives that the sets

$$ V^{\beta(B')} : B' \in \mathcal{Z}_n^B, n \in \mathbb{N}_0 $$

are pairwise disjoint. Moreover, we have the disjoint union

$$ \mathcal{C}^B = \bigcup_{n=0}^{\infty} \bigcup_{B' \in \mathcal{Z}_n^B} C_s^{B'}. \qquad (12) $$

For each $n \in \mathbb{N}_0$, we now define $\mathbf{Z}_n \in (\mathbb{N}_0)^A$ by

$$ \mathbf{Z}_n(A) := |\{B' \in \mathcal{Z}_n^B : t(B') = A\}|, \quad A \in \mathcal{A}, $$

that is, $\mathbf{Z}_n(A)$ is the number of sets in $\mathcal{Z}_n$ that have type $A$. This gives a stochastic process $\mathbf{Z} = (\mathbf{Z}_n)_{n \ge 0}$ with state space $\mathbb{N}_0^A$, and as a consequence of Corollary 3.6 we obtain:

**Corollary 3.7.** The process $\mathbf{Z} = (\mathbf{Z}_n)_{n \ge 0}$ is a multitype branching process with set of types equal to $\mathcal{A}$, and initial population consisting of one individual with type $t(B)$.
We observe that, due to our assumption that $pd < 1$, almost surely all the short clusters that appear on the right-hand side of (12) are finite. It then readily follows that

$$ \mathbb{P}(|\mathcal{C}^B| = \infty) = \mathbb{P}(\mathbf{Z} \text{ survives}) = \zeta(B). \qquad (13) $$

It is easy to see that the mean offspring matrix $M$ of $\mathbf{Z}$, defined as in (2), satisfies the conditions (⋆) and (P), since regardless of $B$, already in generation 1 all types can occur with positive probability.

### 3.3 | Analysis of mean offspring matrix

Our interest is now in studying the behavior of $q_c = q_c(p, k, d)$ as $k \to \infty$. Specifically, we parametrize

$$ q = \frac{1 - pd}{d^k} + \frac{s}{d^{2k}}, \qquad (14) $$

define

$$ s_{\star} = \frac{(1 - pd)^2 p^2 d}{1 - p^2 d}, $$

and will prove that, on the one hand, there is no percolation when $s < s_{\star}$ and $k$ is large, and on the other hand, there is percolation when $s > s_{\star}$ and $k$ is large. Although most of the definitions we give below will depend on $p, d, k$ and $q$ (or $s$), we will omit this dependence from the notation.

**Proposition 3.8.** If $s > s_{\star}$, then for $k$ large enough we have

$$ M(\{o\}, \{o\}) + \sum_{B:|B|=2} M(\{o\}, B) \cdot M(B, \{o\}) > 1. \qquad (15) $$

If $s < s_{\star}$, then for $k$ large enough we have

$$ \sum_{B:|B|=2} M(\{o\}, B) \cdot |B| + \sum_{B:|B|=2} \sum_{B'} M(\{o\}, B) \cdot M(B, B') \cdot |B'| < 1. \qquad (16) $$

We postpone the proof of this result, and for now show how it almost immediately gives Theorem 1.1

*Proof of Theorem 1.1.* Recall from (13) that percolation occurs with positive probability if and only if $\mathbf{Z}$ has positive probability of surviving. The result then follows from combining Lemma 3.3 with Proposition 3.8. ■

In the rest of this section, we prove Proposition 3.8. Several preliminary results will be needed. We start with some simple observations.

**Lemma 3.9.** If $k$ is large enough, then for any $A \in \mathcal{A}$ we have

$$ \sum_{A'} M(A, A') \cdot |A'| \le 2|A| \quad \text{for all } A \in \mathcal{A}. \qquad (17) $$
*Proof.* For any $A \in \mathcal{A}$ we have

$$ \sum_{A'} M(A, A') \cdot |A'| = \mathbb{E} [|C_{\ell}^{A}|] \le qd^{k} \cdot \mathbb{E} [|C_{\ell}(A)|]. \quad (18) $$

Next, note that

$$ \mathbb{E} [|C_{\ell}^{A}|] \le |A| \cdot \mathbb{E} [|C_{\ell}^{o}|] = \frac{|A|}{1 - pd} $$

Using (14), the desired inequality then holds for $k$ large enough that $qd^k/(1 - pd) < 2$, ■

Next, fix $A \in \mathcal{A}$. We observe that $M(\{o\}, A)$ is equal to the expected number of vertices $v$ satisfying the following properties:

(i) $v \in C_{\ell}^o$;

(ii) $v$ is the unique vertex of $C_{\ell}^o$ in the path (of short edges) from $o$ to $v$;

(iii) we have the equality of sets

$$ C_{\ell}^{o} \cap V^{v} = \{v \cdot u : u \in A\}. $$

We now define a quantity $\overline{M}(A)$ as the expected number of vertices satisfying a weaker list of requirements (specifically, we remove requirement (ii) and replace the set equality in (iii) by a set inclusion):

**Definition.** Given $A \in \mathcal{A}$, let $\overline{M}(A)$ be the expected number of vertices $v \in C_{\ell}^o$ such that

$$ C_{\ell}^{o} \cap V^{v} \supseteq \{v \cdot u : u \in A\}. $$

Note in particular that for $A = \{o\}$, we have

$$ \overline{M}(\{o\}) = \mathbb{E}[|C_{\ell}^{o}|]. $$

Also note that $M(\{o\}, A) \le \overline{M}(A)$ for all $A$, and a moment's thought about the two quantities leads to the equality

$$ M(\{o\}, \{o\}) = \overline{M}(\{o\}) - \sum_{A: |A| \ge 2} M(\{o\}, A) \cdot |A|. \quad (19) $$

We now state three lemmas that we will need for the proof of Proposition 3.8.

**Lemma 3.10** (Formula for $\overline{M}$). For any $A \in \mathcal{A}$ we have

$$ \overline{M}(A) = (1 - p^{k-h(A)}) \cdot \frac{d^k \cdot q^{|A|} \cdot p^{h(A)}}{1 - pd}. \quad (20) $$

In particular, we have

$$ d^k \cdot (\overline{M}(\{o\}) - 1) \xrightarrow{k \to \infty} \frac{s}{1 - pd} \quad (21) $$

and, for $A \in \mathcal{A}$ with $|A| = 2$,

$$ \lim_{k \to \infty} d^k \cdot \overline{M}(A) = (1 - pd) \cdot p^{h(A)}. \quad (22) $$
**Lemma 3.11** (Estimate for types with cardinality above 2). We have

$$d^k \sum_{A: |A| \ge 3} \overline{M}(A) \cdot |A|^2 \xrightarrow{k \to \infty} 0. \qquad (23)$$

**Lemma 3.12** (Estimate for types with cardinality 2). Let $A \in \mathcal{A}$ with $|A| = 2$. We have

$$d^k \cdot M(\{o\}, A) \xrightarrow{k \to \infty} (1 - pd) \cdot p^{h(A)}. \qquad (24)$$

Moreover,

$$\sum_{A'} M(A, A') \cdot |A'| \le \frac{q \cdot d^k \cdot (2 - p^{h(A)})}{1 - pd} \qquad (25)$$

and

$$M(A, \{o\}) \xrightarrow{k \to \infty} 2 - p^{h(A)}. \qquad (26)$$

We postpone the proofs of these three lemmas, and for now we show how they can be combined to prove Proposition 3.8.

**Proof of Proposition 3.8.** Using (19) and (21) we have

$$M(\{o\}, \{o\}) = 1 + \frac{s}{(1 - pd)d^k} - \sum_{A: |A| \ge 2} M(\{o\}, A) \cdot |A| + o\left(\frac{1}{d^k}\right).$$

Combining this with the inequality $M(\{o\}, A) \le \overline{M}(A)$ and Lemma 3.11, we obtain

$$M(\{o\}, \{o\}) = 1 + \frac{s}{(1 - pd)d^k} - 2 \sum_{A: |A| = 2} M(\{o\}, A) + o\left(\frac{1}{d^k}\right). \qquad (27)$$

With this at hand, the left-hand side of (15) can be written

$$1 + \frac{1}{d^k} \left[ \frac{s}{1 - pd} + \sum_{A: |A| = 2} d^k \cdot M(\{o\}, A) \cdot (M(A, \{o\}) - 2) + o(1) \right]. \qquad (28)$$

By (24) and (26), for any $A$ with $|A| = 2$ we have

$$d^k \cdot M(\{o\}, A) \cdot (M(A, \{o\}) - 2) \xrightarrow{k \to \infty} -(1 - pd) \cdot p^{2h(A)}. $$

Moreover, using $M(\{o\}, A) \le \overline{M}(A)$ again, together with (17) and (20), we have the domination

$$\sum_{A: |A|=2} |d^k \cdot M(\{o\}, A) \cdot (M(A, \{o\}) - 2)| \\ \le \sum_{A: |A|=2} d^k \cdot \frac{d^k \cdot q^2 \cdot p^{h(A)}}{1 - pd} \cdot (2|A| - 2) = \frac{2d^{2k}}{1 - pd} \cdot \left( \frac{1 - pd}{d^k} + \frac{s}{d^{2k}} \right)^2 \cdot \sum_{h=1}^{k-1} (pd)^h,$$
which is bounded from above uniformly in $k$, by the choice of $q$ in (14) and $pd < 1$. Hence, by dominated convergence, the term inside the square brackets in (28) converges to

$$ \frac{s}{1 - pd} + \sum_{h=1}^{\infty} d^h \cdot \left( -(1 - pd) \cdot p^{2h} \right) = \frac{s}{1 - pd} - (1 - pd) \cdot \frac{p^2 d}{1 - p^2 d}. \quad (29) $$

This is strictly positive when $s > s_★$, so the expression in (28) is larger than one when $s > s_★$ and $k$ is large enough.

Next, by Lemma 3.11, the left-hand side of (16) is

$$ M(\{o\}, \{o\}) + \sum_{B: |B|=2} \sum_{B'} M(\{o\}, B) \cdot M(B, B') \cdot |B'| + \frac{1}{d^k} \cdot o(1). $$

Again using (27), this is equal to

$$ 1 + \frac{1}{d^k} \left[ \frac{s}{1 - pd} + \sum_{A: |A|=2} d^k \cdot M(\{o\}, A) \cdot \left( -2 + \sum_{A'} M(A, A') \cdot |A'| \right) + o(1) \right]. $$

Using (25), this is bounded from above by

$$ 1 + \frac{1}{d^k} \left[ \frac{s}{1 - pd} + \sum_{A: |A|=2} d^k \cdot M(\{o\}, A) \cdot \left( -2 + \frac{q \cdot d^k \cdot (2 - p^{h(A)})}{1 - pd} \right) + o(1) \right]. \quad (30) $$

Using the fact that $q = (1 - pd)d^{-k} + sd^{-2k}$ and (24), we have, for any $A$ with $|A| = 2$:

$$ d^k \cdot M(\{o\}, A) \cdot \left( -2 + \frac{q \cdot d^k \cdot (2 - p^{h(A)})}{1 - pd} \right) \xrightarrow{k \to \infty} -(1 - pd) \cdot p^{2h(A)}. $$

Arguing using dominated convergence as before, the term inside the square brackets in (30) converges to the same limit as in (29), which is negative when $s < s_★$. This completes the proof. ■

We now turn to the proofs of the three lemmas.

*Proof of Lemma 3.10.* Fix $A \in \mathcal{A}$ and $v \in V$ with $h(v) \ge k$. Write $v = (v_1, \dots, v_n)$, with $n = h(v)$, and let $v_{(i)} := (v_1, \dots, v_i)$ for $1 \le i \le n$. The event that $\{v \cdot u : u \in A\} \subseteq C_\ell^o$ occurs if and only if:

1. vertices $v_{(1)}, \dots, v_{(n-k+h(A))}$ are all in $C_\ell^o$;

2. vertex $v$ is not in $C_\ell(\{o\})$;

3. all the long edges starting from the set $\{o, v_{(1)}, \dots, v_{(n-k+h(A))}\}$ and ending at the set $\{v \cdot u : u \in A\}$ are open.

The first event says that every short edge along the path $o, v_{(1)}, \dots, v_{(n-k+h(A))}$ is open, this has probability $p^{h(v)+h(A)-k}$. The second one occurs, if there is at least one closed short edge along the path $v_{(n-k+h(A))}, \dots, v$, this has probability $(1 - p^{k-h(A)})$. Finally, the third event says that each long edge pointing to the set $\{v \cdot u : u \in A\}$ is open, which has probability $q^{|A|}$. Observe that these three events are independent, implying

$$ \mathbb{P}_{p,q}(\{v \cdot u : u \in A\} \subseteq C_{\ell}^{o}) = p^{h(v)+h(A)-k} \cdot (1 - p^{k-h(A)}) \cdot q^{|A|}. $$
The result follows from summing this over all $v$ with $h(v) \ge k$:

$$ \sum_{v: h(v) \ge k} p^{h(v)+h(A)-k} \cdot (1-p^{k-h(A)}) \cdot q^{|A|} \\ = (1-p^{k-h(A)}) \cdot q^{|A|} \cdot p^{h(A)-k} \cdot \sum_{h=k}^{\infty} d^h p^h = (1-p^{k-h(A)}) \cdot \frac{d^k \cdot q^{|A|} \cdot p^{h(A)}}{1-pd} $$

This proves (20).

For (21), we combine (20) with the equality $q = (1 - pd)d^{-k} + sd^{-2k}$ to get

$$ d^k \cdot (\overline{M}(\{o\}) - 1) = d^k \cdot \left( (1-p^k) \cdot \frac{d^k}{1-pd} \cdot \left( \frac{1-pd}{d^k} + \frac{s}{d^{2k}} \right) - 1 \right) \\ = d^k \cdot \left( \frac{s}{d^k \cdot (1-pd)} - p^k - \frac{s \cdot p^k}{d^k \cdot (1-pd)} \right) \xrightarrow{k \to \infty} \frac{s}{1-pd}, $$

since $p^k = o(1/d^k)$.

Similarly, for (22), for $|A| = 2$ we use $d^{2k} \cdot q^2 \to (1 - pd)^2$ to obtain

$$ d^k \cdot \overline{M}(A) = d^k \cdot (1 - p^{k-h(A)}) \cdot \frac{d^k q^2 \cdot p^{h(A)}}{1 - pd} \xrightarrow{k \to \infty} (1 - pd) \cdot p^{h(A)}. $$

*Proof of Lemma 3.11.* For $m, h \in \mathbb{N}$, let $\eta(m, h)$ denote the number of sets $A \in \mathcal{A}$ with $|A| = m$ and $h(A) = h$. Keeping in mind that any $A \in \mathcal{A}$ contains $\{o\}$, we bound

$$ \eta(m, h) \le \binom{d + \cdots + d^h}{m-1} \le \frac{(d + \cdots + d^h)^{m-1}}{(m-1)!} \le \frac{d^{(h+1)(m-1)}}{(m-1)!}, $$

since $(d^{h+1} - 1)/(d - 1) \le d^{h+1}$. Then, for each $m \in \mathbb{N}$,

$$ \sum_{h=1}^{k-1} \sum_{A: |A|=m, h(A)=h} \overline{M}(A)^{(20)} \le \sum_{h=1}^{k-1} \eta(m, h) \cdot \frac{d^k q^m p^h}{1 - pd} \le \frac{d^k q^m \sum_{h=1}^{k-1} (pd^{m-1})^{h+1}}{p(1 - pd)(m - 1)!}. $$

We can bound the sum in the numerator by $k - 1$ in case $pd^{m-1} \le 1$ and by $(k - 1)(pd^{m-1})^k$ otherwise, and then, bounding a maximum by a sum,

$$ \sum_{h=1}^{k-1} (pd^{m-1})^{h+1} \le (k-1) \cdot (1 + (pd^{m-1})^k). $$

We then obtain

$$ d^k \sum_{A: |A| \ge 3} \overline{M}(A) \cdot |A|^2 \le \frac{(k-1)d^{2k}}{p(1-pd)} \sum_{m \ge 3} \frac{m^2 q^m}{(m-1)!} \cdot (1 + p^k d^{k(m-1)}) \\ \le \frac{(k-1)d^{2k} q^3}{p(1-pd)} \sum_{m \ge 3} \frac{m^2}{(m-1)!} + \frac{(k-1)d^{2k} q p^k}{p(1-pd)} \sum_{m \ge 3} \frac{m^2}{(m-1)!} \cdot (qd^k)^{m-1}. $$
Using $q = O(\frac{1}{d^k})$, $p^k = o(\frac{1}{d^k})$ and $\sum_{m \ge 3} \frac{m^2}{(m-1)!} < \infty$, we see that this tends to zero as $k \to \infty$. ■

*Proof of Lemma 3.12.* Fix A with $|A| = 2$. We note that, similarly to (19), we have

$$ \bar{M}(A) \geq M(\{o\}, A) \geq \bar{M}(A) - \sum_{A' : |A'| \geq 3} \binom{|A'|}{2} \cdot M(\{o\}, A'). \quad (31) $$

The convergence (24) now follows from combining this with (22) and (23).

To prove the remaining statements, we write $A = \{o, u\}$ and compute

$$ \begin{aligned} \mathbb{E}[|C_s^A|] &= \mathbb{E}[|C_s^o|] + \mathbb{E}[|C_s^{(u)}|] - \sum_{v \in V_u} \mathbb{P}(v \in C_s^o) \\ &= \frac{2 - p^{h(u)}}{1 - pd} = \frac{2 - p^{h(A)}}{1 - pd}. \end{aligned} $$

We then have

$$ M(A, \{o\}) \leq \sum_{A'} M(A, A') \cdot |A'| \leq qd^k \cdot \mathbb{E}[|C_s^A|] = qd^k \cdot \frac{2 - p^{h(A)}}{1 - pd}. $$

This already proves (25). For (26), we need two additional statements. First,

$$ qd^k \cdot \mathbb{E}[|C_s^A|] \xrightarrow{k \to \infty} 2 - p^{h(A)}. $$

This is an immediate consequence of $q = (1 - pd)d^{-k} + sd^{-2k}$. Second,

$$ qd^k \cdot \mathbb{E}[|C_s^A|] - M(A, \{o\}) \xrightarrow{k \to \infty} 0, $$

that is the expected number of open long edges that start at $C_s^A$, but do not contribute to the value of $Z_1(\{o\})$ tends to zero as $k \to \infty$. These are exactly the long edges that either start and end at $C_s^A$ or that end at a vertex belonging to a set of $B^A$ which is not of type $\{o\}$. Using $C_s^A \le |A|/(1 - pd)$ it is easy to see that the expected number of the former type of edges can be bounded from above by

$$ \frac{2p^k q}{1 - pd} \xrightarrow{k \to \infty} 0, $$

and by an argument similar to the proof of Lemma 3.11 the expected number of the latter type of edges can be bounded from above by

$$ \sum_{h=1}^{k-1} \eta(m, h) \cdot \frac{2d^k q^m p^h}{1 - pd} \xrightarrow{k \to \infty} 0. $$

We omit the details. ■

*Remark 3.13.* One could try to deduce higher order terms in the expansion of $q_c$ by examining the evolution of the multitype branching process Z more precisely. Namely, to obtain the next term, one would need a statement similar to Proposition 3.8 summing over all sets B with $|B| = 2$ or 3 instead of sets with cardinality 2. However, the calculations to obtain the corresponding formulas in Lemmas 3.10, 3.11 and 3.12 seems to be rather long and tedious, and it is not even clear what the precise order of the next term would be.
# 4 | LIMIT THEOREMS

In this section, we prove Theorem 1.2. We will first recall some limit theorems from the literature of multitype branching processes. We will then give a second branching process representation of the percolation cluster, and readily obtain the results for the three regimes as stated in Theorem 1.2.

## 4.1 | Limit theorems for multitype branching processes

As in Section 2, we consider a multitype branching process ($Z_n$)$_{n \ge 0}$ with set of types $\mathcal{T}$, offspring distribution $\rho$ and mean offspring matrix $M$ with Perron-Frobenius eigenvalue $\rho$. We continue assuming that conditions (⋆) and (P) hold. We also let $\mu, \nu \in (\mathbb{N}_0)^{\mathcal{T}}$ respectively denote left and right eigenvectors of $M$ corresponding to $\rho$, that is,

$$ \sum_{a \in \mathcal{T}} \mu(a) \cdot M(a, b) = \rho \cdot \mu(b) \quad \forall b \in \mathcal{T}, \qquad \sum_{b \in \mathcal{T}} M(a, b) \cdot \nu(b) = \rho \cdot \nu(a) \quad \forall a \in \mathcal{T}; \quad (32) $$

these eigenvectors are uniquely determined if we require the normalization conditions

$$ \sum_{a \in \mathcal{T}} \mu(a) = 1, \qquad \sum_{a \in \mathcal{T}} \mu(a) \cdot \nu(a) = 1. \qquad (33) $$

Moreover, it follows from the Perron-Frobenius Theorem and condition (P) that $\mu(a) > 0$ and $\nu(a) > 0$ for all $a \in \mathcal{T}$.

The following result is contained in theorem 1 in chapter V, section 6 of [3], concerning the supercritical regime:

**Theorem 4.1.** Assume that $\rho > 1$ and

$$ \sum_{\eta} \eta(b) \cdot \log(\eta(b)) \cdot \rho(a, \eta) < \infty \text{ for all } a, b \in \mathcal{T}. $$

We then have

$$ \lim_{n \to \infty} \frac{\mathbf{Z}_n}{\rho^n} = Z \cdot \nu \quad \text{almost surely,} \qquad (34) $$

where $Z$ is a nonnegative random variable such that $\mathbb{P}(Z > 0) > 0$ and $Z \cdot \nu$ is computed entry-wise.

For the subcritical regime, the following statement is contained in theorem 2 in chapter V, section 4 of [3]:

**Theorem 4.2.** If $\rho < 1$, then for each $a \in \mathcal{T}$ and $\eta \in (\mathbb{N}_0)^{\mathcal{T}}$, the limit

$$ Q(\eta) := \lim_{n \to \infty} \mathbb{P}(\mathbf{Z}_n = \eta | \mathbf{Z}_0 = \mathbf{e}_a, \mathbf{Z}_n \neq \mathbf{0}) $$

exists and is independent of a. Moreover, $\sum_{\eta} Q(\eta) = 1$.
For the result concerning the critical case $\rho = 1$, we first introduce some terminology, starting with convergence in distribution (in the sense of Benjamini and Schramm [4]) for sequences of random rooted trees. A rooted tree $\tilde{t} = (\tau, \mathcal{O})$ is a tree $\tau$ with a distinguished vertex $\mathcal{O}$. For each $m \in \mathbb{N}_0$, let us denote by $B_m(\tilde{t})$ the rooted tree obtained as the subgraph of $\tau$ induced by all vertices at graph distance at most $m$ from $\mathcal{O}$, rooted again at $\mathcal{O}$. We say that a sequence of random rooted trees $\tilde{t}_n$ converges in distribution to a random rooted tree $\tilde{t}$ if, for any $m \in \mathbb{N}_0$ and any deterministic finite rooted tree $(\tilde{t}, \bar{o})$, we have

$$ \mathbb{P}(B_m(\tilde{t}_n) \cong (\bar{t}, \bar{o})) \xrightarrow{n \to \infty} \mathbb{P}(B_m(\tilde{t}) \cong (\bar{t}, \bar{o})), $$

where '$\cong$' denotes graph isomorphism between rooted trees.

We now recall some facts about convergence in distribution of family trees of critical branching processes. In [8], Kesten introduced a random tree with an infinite spine that is the local limit in distribution of the family tree of a critical (single-type) branching process conditioned on reaching generation $n$, as $n \to \infty$. In [1] the authors gave a necessary and sufficient condition for the convergence in distribution of a family tree to the corresponding Kesten's tree. Later this result was generalized for multitype branching processes in [2] and [15]. The following follows from theorem 3.1 in [15]:

**Theorem 4.3.** Assume that $\rho = 1$ and that there exists $\theta > 0$ such that

$$ \sum_{\eta \in (\mathbb{N}_0)^{\mathcal{T}}} \rho(a, \eta) \cdot \exp \left\{ \theta \cdot \sum_{b \in \mathcal{T}} \eta(b) \right\} < \infty \quad \text{for all } a \in \mathcal{T}. $$

Then, the family tree of $(\mathbb{Z}_n)_{n \ge 0}$ conditioned on having more than $n$ vertices converges in distribution, as $n \to \infty$, to a random rooted tree.

In fact, in [15] a description of the limiting tree is provided: it is again a Galton-Watson tree with an augmented space of types and an offspring distribution that is obtained from $\rho$ and the eigenvalues associated to $\rho = 1$. We refrain from recalling the details here, since we will not use them.

## 4.2 | Second branching process representation of percolation cluster

We again go back to our percolation model on $\mathbb{T} = \mathbb{T}_{d,k}$ with parameters $p, q \in [0, 1]^2$ and $q_c = q_c(p, k, d)$. Recall that $V_{\Gamma}^o = \{u \in V: 0 \le h(u) < k\}$.

**Definition.** Define the random sets

$$ S(v) := \{u \in V_{\Gamma}^{o}: v \cdot u \in \mathcal{C}\}, \quad v \in V. $$

Let $\mathcal{B}$ denote the collection of all nonempty subsets of $V_{\Gamma}^o$ and define the process $\mathbf{W} = (\mathbf{W}_n)_{n \ge 0}$ on $(\mathbb{N}_0)^{\mathcal{B}}$ by setting

$$ \mathbf{W}_n(A) := |\{v: h(v) = n, S(v) = A\}|, \quad A \in \mathcal{B}, n \in \mathbb{N}_0. $$

By considering the exploration process $(\mathcal{C} \cap \{v: h(v) \le k-1+n\})_{n \ge 0}$, it is readily seen that $\mathbf{W}$ is a multitype branching process with set of types $\mathcal{B}$. The initial population is given by a single individual of a random type, with distribution equal to that of $\mathcal{C} \cap V_{\Gamma}^o$, and

$$ \rho(a, \eta) = 0 \text{ for all } \eta \in (\mathbb{N}_0)^{\mathcal{T}} \text{ with } \sum_b \eta(b) > d, \quad (35) $$
that is each individual can generate a population of cardinality at most *d*. The mean offspring matrix of **W** will (again) be denoted **M**. We will write $M_{p,q}$ when we want to make the parameters explicit. It is not difficult to check that **M** satisfies the conditions (⋆) and (P) given in Section 2; we leave this to the reader. Moreover, observe that if $M(A, B) > 0$ for some $A, B \in \mathcal{B}$, then **A** determines **B** up to height $k-2$. We again let $\rho = \rho_{p,q}$ denote the Perron-Frobenius eigenvalue of $M_{p,q}$.

**Lemma 4.1.** We have

$$ \rho_{p,q} = \begin{cases} > 1 & \text{if } q > q_c; \\ = 1 & \text{if } q = q_c; \\ < 1 & \text{if } q < q_c. \end{cases} $$

*Proof.* Note that **W** survives if and only if $\mathcal{C}$ is infinite. Moreover, as mentioned earlier, it was proved in [10] that $\mathcal{C}$ is almost surely finite when $q = q_c$. This implies that $\rho_{p,q} > 1$ if and only if $q > q_c$. Also note that the entries of $M_{p,q}$ depend continuously on $(p, q)$. Since $\rho_{p,q}$ is a simple root of the characteristic equation of this matrix, it depends continuously (in fact smoothly) on the entries of the matrix, hence $\rho_{p,q}$ also depends continuously on $(p, q)$. This implies that $\rho_{p,q_c} = 1$.

It remains to prove that $\rho_{p,q} < 1$ when $q < q_c$. To this end, fix $(p, q)$ with $q < q_c$. Also fix $q' \in (q, q_c)$. We construct a standard coupling of the clusters $\mathcal{C}_{p,q}$ and $\mathcal{C}_{p,q'}$ using independent Uniform([0, 1]) random variables indexed by the edges of $\mathbb{T}$, $\{U_e : e \in E\}$. For both $\mathcal{C}_{p,q}$ and $\mathcal{C}_{p,q'}$, we declare a short edge $e$ to be open if $U_e \le p$. We declare a long edge $e$ to be open for $\mathcal{C}_{p,q}$ if $U_e \le q$, and we declare it to be open for $\mathcal{C}_{p,q'}$ if $U_e \le q'$. Now, in this same probability space, we define an additional cluster $\mathcal{C}^*$, which will satisfy $\mathcal{C}_{p,q} \subseteq \mathcal{C}^* \subseteq \mathcal{C}_{p,q'}$, and will give rise to a multitype branching process $\mathbf{W}^*$ with Perron-Frobenius eigenvalue $\rho^*$. We will then show that $\rho_{p,q} < \rho^* \le 1$, completing the proof.

We will define $\mathcal{C}^*$ by recursively defining $\mathcal{C}^* \cap \{v : h(v) \le n\}$ for each $n \ge k-1$. Start the recursion by setting

$$ \mathcal{C}^* \cap \{v : h(v) \le k-1\} = \mathcal{C}_{p,q} \cap \{v : h(v) \le k-1\}. $$

Now assume that $\mathcal{C}^* \cap \{v : h(v) \le n\}$ has been defined. Fix $v$ with $h(v) = n+1$; let $v'$ be the parent of $v$ (so that $\langle v', v \rangle$ is a short edge of $\mathbb{T}$) and let $v''$ be the ancestor of $v$ at distance $k$ from $v$ (so that $\langle v'', v \rangle$ is a long edge of $\mathbb{T}$). We include $v$ in $\mathcal{C}^*$ in any of the following three situations:

(a) $v' \in \mathcal{C}^*$, and $U_{\langle v', v \rangle} \le p$;

(b) $v'' \in \mathcal{C}^*$, and $U_{\langle v'', v \rangle} \le q$;

(c) $v'' \in \mathcal{C}^*$, $U_{\langle v'', v \rangle} \in (q, q']$, $U_{\langle v'', w \rangle} \in (q, 1]$ for all $\langle v'', w \rangle \in E_\ell$, and $V_\Gamma'' \cap (\mathcal{C}^* \cap \{u \in V : h(u) \in [h(v''), h(v'') + k-1]\}) = \{v''\}$ (that is, no long edge starting at $v''$ is open in $\mathcal{C}_{p,q}$ and no descendant of $v''$ with height between $h(v'')+1$ and $h(v)-1$ has been included in $\mathcal{C}^*$).

Put simply, in an exploration that adds one height unit at a time, the cluster $\mathcal{C}^*$ grows in the same way as $\mathcal{C}_{p,q}$, with the exception of rule (c) above, which prescribes that vertices that would otherwise become leaves are given extra chances (with probability $q' - q$ each) of having (long-distance) neighbors.

We now replicate Definition 4.2 by letting

$$ S^*(v) := \{u \in V_\Gamma^o : v \cdot u \in \mathcal{C}^*\}, \quad v \in V, $$
and defining $\mathbf{W}^* = (\mathbf{W}_n^*)_{n \ge 0}$ by

$$ \mathbf{W}_n^*(A) := |\{v : h(v) = n, S^*(v) = A\}|, \quad A \in \mathcal{B}, n \in \mathbb{N}_0. $$

Then, $\mathbf{W}^*$ is also a multitype branching process. Let us denote by

$$ \mathcal{B}_{k-1} := \{B \in \mathcal{B} : h(v) = k-1 \text{ for all } v \in B\}, $$

that is the subset of types that only contains vertices at height $k-1$. By the definition of $\mathbf{W}$, $M_{p,q}(\{o\}, B) > 0$ implies that $B \in \mathcal{B}_{k-1}$. Observe that for any such $B$, the long edges $\{(o, o \cdot v) : v \in B\}$ are precisely the edges that are given extra chances of being open in $\mathcal{C}^*$ in situation (c). Therefore it is immediate that the mean offspring matrix of $\mathbf{W}^*$, denoted $M^*$, satisfies:

$$ \begin{aligned} M^*(\{o\}, B) &= M_{p,q}(\{o\}, B) + (q' - q)^{|B|} (1 - q' + q)^{d^k - |B|} & \text{if } B \in \mathcal{B}_{k-1}, \\ M^*(A, B) &= M_{p,q}(A, B) & \text{otherwise.} \end{aligned} \quad (36) $$

We then have

$$ \mathbb{P}(\mathbf{W}^* \text{ survives}) = \mathbb{P}(|\mathcal{C}^*| = \infty) \le \mathbb{P}(|\mathcal{C}_{p,q'}| = \infty) = 0, $$

so the Perron-Frobenius eigenvalue $\rho^*$ of $M^*$ is at most 1. We will now show that (36) implies that $\rho^* > \rho_{p,q}$. Let $\mu, v : \mathcal{B} \to \mathbb{R}$ be left and right eigenvectors of $M_{p,q}$ associated to the eigenvalue $\rho_{p,q}$, as in (32) and (33). Recall that all entries of $\mu$ and $v$ are strictly positive. Fix any norm $\| \cdot \|$ on the space of matrices. The perturbation theory of Perron-Frobenius eigenvalues (see theorem 8 in chapter 8 of [13]) gives that the Perron-Frobenius eigenvalue of $M_{p,q} + E$, where $E$ is a matrix of sufficiently small norm, is given by

$$ \rho(M_{p,q} + E) = \rho_{p,q} + \frac{\sum_{A,B} \mu(A) \cdot E(A, B) \cdot v(B)}{\sum_A \mu(A) \cdot v(A)} + O(\|E\|^2). $$

In particular, if $E$ is a non-negative matrix with at least one strictly positive entry, then $\rho(M_{p,q} + E) > \rho_{p,q}$. The result is thus obtained by taking $E = M^* - M_{p,q}$. ■

**Proof of Theorem 1.2.** Recall that $X_n$ denotes the number of vertices $u \in \mathcal{C}_{p,q}$ with $h(u) = n$. We extract $X_n$ from $\mathbf{W}_n$ by writing

$$ X_n = \sum_{B \in \mathcal{B}} \mathbf{W}_n(B) \cdot \mathbb{1}\{o \in B\}. $$

Assume $q > q_c$. Then, by Lemma 4.1 we have $\rho > 1$ and by (35) the condition of Theorem 4.1 holds, yielding $\rho^{-n} \cdot \mathbf{W}_n \xrightarrow{n \to \infty} Z \cdot v$ for some random variable $Z$ with $\mathbb{P}(Z > 0) > 0$. We then obtain

$$ \frac{X_n}{\rho^n} \xrightarrow{n \to \infty} Z \cdot \sum_{B \in \mathcal{B}} v(B) \cdot \mathbb{1}\{o \in B\}, $$

proving the first statement of the theorem. The statement for $q < q_c$ is proved similarly.

We would like to obtain the final statement, concerning the critical case, by applying Theorem 4.3 to the family tree of $\mathbf{W}$. However, there is a problem: the cluster $\mathcal{C}$ cannot be recovered from the
family tree of W. For instance, assume that $W_0$ is the population consisting of a single individual of type $\{o\}$, and $W_1$ is the population consisting of a single individual of type $\{v\}$, where v is a vertex with $h(v) = k-1$ (so that $v = (v_1, ..., v_{k-1})$, with $v_1, ..., v_{k-1} \in [d]$). Then, $\mathcal{C} \cap \{u : h(u) \le k\}$ could be any of the sets

$$ \{o, (1, v_1, ..., v_{k-1})\}, \{o, (2, v_1, ..., v_{k-1})\}, ..., \{o, (d, v_1, ..., v_{k-1})\}. $$

To solve this issue, we modify the process W slightly, by augmenting its set of types in order to encode the information that is missing, so that the correspondence between realizations of its family tree and realizations of $\mathcal{C}$ becomes one-to-one.

To this end, first define the function $f: V \to [d]$ by defining $f(o)$ arbitrarily (say, $f(o) = 1$), and letting

$$ f(v_1, ..., v_n) = v_n \quad \text{for any } v = (v_1, ..., v_n) \in V \setminus \{o\}. $$

We then let $\hat{\mathcal{B}} := \mathcal{B} \times [d]$ and define the process $\hat{\mathbf{W}} = (\hat{\mathbf{W}}_n)_{n \ge 0}$ with space of types $\hat{\mathcal{B}}$ by letting

$$ \hat{\mathbf{W}}_n((A, i)) := |\{v : h(v) = n, S(v) = A, f(v) = i\}|, \quad A \in \mathcal{B}, i \in [d], n \in \mathbb{N}_0. $$

It should now be clear that $\hat{\mathbf{W}}$ is a multitype branching process satisfying (35), and moreover there is a natural bijection between $\mathcal{C}$ and the trajectory $(\hat{\mathbf{W}}_n)_{n \ge 0}$, so that (say) an individual of type $(A, i)$ in generation $n$ of $\hat{\mathbf{W}}$ can be associated to a unique vertex $v \in V$ with $h(v) = n$ and $S(v) = A$. Moreover, exactly the same proof as that of Lemma 4.1 shows that the Perron-Frobenius eigenvalue $\hat{\rho}$ of $\hat{\mathbf{W}}$ equals 1 when $q = q_c$. As (35) ensures that we can apply Theorem 4.3 to $\hat{\mathbf{W}}$, we obtain the desired result. ■

## ACKNOWLEDGMENTS

The research of Bernardo N. B. de Lima was supported in part by CNPq grant 305811/2018-5 and FAPEMIG (Programa Pesquisador Mineiro). He is also thankful for the hospitality of Bernoulli Institute, University of Groningen. The research of Réka Szabó was partially supported by ERC Starting Grant 680275 "MALIG". The authors would like to thank Tobias Müller for useful discussions and Aernout van Enter for suggesting useful references.

## REFERENCES

1. R. Abraham and J.-F. Delmas, *Local limits of conditioned Galton-Watson trees: The infinite spine case*, Electron. J. Probab. **19** (2014), no. 2, 19.

2. R. Abraham, J.-F. Delmas, and H. Guo, *Critical multi-type Galton-Watson trees conditioned to be large*, J. Theoret. Probab. **31** (2018), no. 2, 757-788.

3. K. B. Athreya and P. E. Ney, Branching processes, Vol **196**, Die Grundlehren der mathematischen Wissenschaften, Springer-Verlag, New York-Heidelberg, 1972.

4. I. Benjamini and O. Schramm, *Recurrence of distributional limits of finite planar graphs*, Electron. J. Probab. **6** (2001), no. 23, 13.

5. H. Duminil-Copin, M. R. Hilário, G. Kozma, and V. Sidoravicius, *Brochette percolation*, Isr. J. Math. **225** (2018), 479-501.

6. G. R. Grimmett and C. M. Newman, "Percolation in $\infty + 1$ dimensions," Disorder in physical systems, G. R. Grimmett and D. J. A. Welsh (eds.), Clarendon Press, Oxford, 1990, pp. 219-240.

7. G. K. Iliev, E. J. Janse van Rensburg, and N. Madras, *Phase diagram of inhomogeneous percolation of a defect plane*, J. Stat. Phys. **158** (2015), 255-299.
8. H. Kesten, *Subdiffusive behavior of random walk on a random cluster*, Ann. Inst. Henri Poincaré **22** (1986), no. 4, 425–487.

9. H. Kesten, V. Sidoravicius and M. E. Vares, *Oriented percolation in a random environment*, 2012, arXiv:1207.3168.

10. B. N. B. de Lima, L. T. Rolla, and D. Valesin, *Monotonicity and phase diagram for multi-range percolation on oriented trees*, Random Struct. Algorithms **55** (2019), no. 1, 160–172.

11. B. N. B. de Lima and H. C. Sanna, *A note on inhomogeneous percolation on ladder graphs*, Bull Braz Math Soc, New Series **51** (2020), 827–833.

12. B. N. B. de Lima, R. Sanchis, and R. W. C. Silva, *Critical point and percolation probability in a long range site percolation model on $Z^d$*, Stoch. Process. Appl. **121** (2011), no. 9, 2043–2048.

13. J. Magnus and H. Neudecker, Matrix differential calculus with applications in statistics and econometrics, John Wiley & Sons, New York, 2019.

14. S. Martineau and V. Tassion, *Locality of percolation for Abelian Cayley graphs*, Ann. Probab. **45** (2017), no. 2, 1247–1277.

15. R. Stephenson, *Local convergence of large critical multi-type Galton-Watson trees and applications to random maps*, J. Theoret. Probab. **31** (2018), no. 1, 159–205.

16. R. Szabó and D. Valesin, *Inhomogeneous percolation on ladder graphs*, J. Theoret. Probab. **33** (2020), 992–1010.

17. R. Szabó, *Inhomogeneous contact process and percolation*, Doctoral dissertation, University of Groningen, 2019.

**How to cite this article:** B. N. B. de Lima, R. Szabó, and D. Valesin, *Multirange percolation on oriented trees: Critical curve and limit behavior*, Random Struct. Alg. **62** (2023), 519–541.

https://doi.org/10.1002/rsa.21104