# Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs

Guillaume Conchon-Kerjan

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

## To cite this version:

Guillaume Conchon-Kerjan. Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs. Electronic Journal of Probability, 2023, 28, 10.1214/23-ejp920. hal-04031187

HAL Id: hal-04031187

https://hal.science/hal-04031187v1

Submitted on 9 Sep 2024

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>
<figure><img src="image_3.png" /></figure>

Electron. J. Probab. 28 (2023), article no. 35, 1–60.
ISSN: 1083-6489 https://doi.org/10.1214/23-EJP920

# Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs*

Guillaume Conchon-Kerjan†

## Abstract

We study the level-set of the zero-average Gaussian Free Field on a uniform random $d$-regular graph above an arbitrary level $h \in (-\infty, h_*)$, where $h_*$ is the level-set percolation threshold of the GFF on the $d$-regular tree $T_d$. We prove that w.h.p as the number $n$ of vertices of the graph diverges, the GFF has a unique giant connected component $C_1^{(n)}$ of size $\eta(h)n + o(n)$, where $\eta(h)$ is the probability that the root percolates in the corresponding GFF level-set on $T_d$. This gives a positive answer to the conjecture of [4] for most regular graphs. We also prove that the second largest component has size $\Theta(\log n)$.

Moreover, we show that $C_1^{(n)}$ shares the following similarities with the giant component of the supercritical Erdős-Rényi random graph. First, the diameter and the typical distance between vertices are $\Theta(\log n)$. Second, the 2-core and the kernel encompass a given positive proportion of the vertices. Third, the local structure is a branching process conditioned to survive, namely the level-set percolation cluster of the root in $T_d$ (in the Erdős-Rényi case, it is known to be a Galton-Watson tree with a Poisson distribution for the offspring).

**Keywords:** Gaussian free field; percolation; random graphs.

**MSC2020 subject classifications:** 60K35; 60G15; 60C05; 05C80.

Submitted to EJP on October 29, 2021, final version accepted on February 13, 2023.

# 1 Introduction

## 1.1 Overview

The Gaussian Free Field (GFF) on a transient graph $\mathcal{G}$ is a Gaussian process indexed by the vertices. Its covariance is given by the Green function of the simple random walk on $\mathcal{G}$, hence the GFF carries a lot of information on the structure of $\mathcal{G}$ and on the behaviour of random walks, giving a base motivation for its study.

Level-set percolation of the GFF has been investigated since the 1980s ([10, 25]).
Lately, one important incentive has been to gain information on the vacant set of random

<footnote>*GCK is grateful to EPSRC for support through the grant EP/V00929X/1.</footnote>

<footnote>†University of Bath, United Kingdom. E-mail: galck20@bath.ac.uk</footnote>
interlacements ([24, 31]), via Dynkin-type isomorphism theorems ([19, 28]). It was subject to much attention in the last decade on $Z^d$ ([15, 16, 18, 17, 24, 26, 30]). On such a lattice where the Green function decays polynomially with the distance between vertices, it provides a percolation model with long-range interactions.

More recently, level-set percolation was studied on transient rooted trees ([3, 2, 32]). There is a phase transition at a critical threshold $h_* \in \mathbb{R}$: if $h < h_*$, the connected component of the root in the level-set above $h$ of the GFF has a positive probability to be infinite, and if $h > h_*$, this probability is zero.

One can define an analogous field on a finite connected graph, the **zero-average Gaussian Free Field**, whose covariance is given by the **zero-average Green function** (see Section 1.2). A natural question is whether some characteristics of the GFF on an infinite graph $\mathcal{G}$ can be transferred to a sequence of finite graphs $(\mathcal{G}_n)_{n \ge 0}$ whose local limit is $\mathcal{G}$. For instance, one might ask whether a phase transition for the existence of an infinite connected component of the level-set in $\mathcal{G}$ corresponds to a phase transition for the emergence of a “macroscopic” component of size $\Theta(|\mathcal{G}_n|)^1$ in the level set in $\mathcal{G}_n$. For $\mathcal{G} = Z^d$, a sharp phase transition was shown in [18], and Abächerli [1] studied the zero-average GFF on the torus.

Abächerli and Černý recently investigated the GFF on the $d$-regular tree $T_d$ [3], and the zero-average GFF on some $d$-regular graphs (large girth expanders) in a companion paper [4]. In this setting, many essential questions (such as the value of $h_*$, or the sharpness of the phase transition at $h_*$ for the zero-average GFF) remain open. In this paper, we answer some of them, and relate the percolation level-sets to other classical random graphs, in particular the Erdős-Rényi model (Section 1.4).

## 1.2 Setting

In all this work, we fix an integer $d \ge 3$. We denote $T_d$ the infinite $d$-regular tree rooted at an arbitrary vertex $\circ$, and $\mathcal{G}_n$ a uniform $d$-regular random graph of size $n$ for $n \ge 1$ (if $d$ is odd, consider only even $n$). Let $V_n$ be its vertex set and $\pi_n$ be the uniform measure on $V_n$, i.e. $\pi_n(x) = 1/n$ for every $x \in V_n$.

### Gaussian Free Field on regular trees

The GFF $\varphi_{T_d}$ on $T_d$ is a centred Gaussian field $(\varphi_{T_d}(x))_{x \in T_d}$ indexed by the vertices of $T_d$, and with covariances given by the Green function $G_{T_d}$: for all vertices $x, y \in T_d$, we set $\text{Cov}(\varphi_{T_d}(x), \varphi_{T_d}(y)) = G_{T_d}(x, y)$. Recall that

$$G_{T_d}(x, y) = \mathbf{E}_x^{T_d} \left[ \sum_{k \ge 0} \mathbf{1}_{\{X_k=y\}} \right]$$

where $(X_k)_{k \ge 0}$ is a discrete-time SRW (Simple Random Walk) on $T_d$. In general, we will denote $\mathbf{P}_\mu^\mathcal{G}$ the law of a SRW on a graph $\mathcal{G}$ with initial distribution $\mu$, and $\mathbf{E}_\mu^\mathcal{G}$ the corresponding expectation.

### Gaussian Free Field on $d$-regular graphs

Assume first that $\mathcal{G}_n$ is connected. The zero-average GFF $\psi_{\mathcal{G}_n}$ on $\mathcal{G}_n$ is a centred Gaussian field $(\psi_{\mathcal{G}_n}(x))_{x \in \mathcal{G}_n}$ indexed by the vertices of $\mathcal{G}_n$, and with covariances given by the zero-average Green function $G_{\mathcal{G}_n}$ on $\mathcal{G}_n$: for all $x, y \in \mathcal{G}_n$, we set

$$\text{Cov}(\psi_{\mathcal{G}_n}(x), \psi_{\mathcal{G}_n}(y)) = G_{\mathcal{G}_n}(x, y) := \mathbf{E}_x^{\mathcal{G}_n} \left[ \int_0^{+\infty} \left( \mathbf{1}_{\{\bar{X}_t=y\}} - \frac{1}{n} \right) dt \right]$$

<footnote n="1">¹for two sequences $(a_n)_{n \ge 1}$, $(b_n)_{n \ge 1}$, we say that $a_n = \Theta(b_n)$ if there exists $c > 0$ such that for every large enough $n$, $c < a_n/b_n < 1/c$</footnote>
where $(\bar{X}_t)_{t \ge 0}$ is a continuous time SRW on $\mathcal{G}_n$ started at $x$ with Exp(1) independent jump-times. Precisely, let $(\zeta_i)_{i \ge 1}$ be a sequence of independent exponential variables of parameter 1. Let $(X_k)_{k \ge 0}$ be a SRW started at $x$, independent of $(\xi_i)_{i \ge 1}$. Then for all $t \ge 0$, we define $\bar{X}_t := X_{k(t)}$, with $k(t) := \sup\{k \ge 0, \sum_{i=1}^k \zeta_i \le t\}$.

The function $\mathcal{G}_{\mathcal{G}_n}$ is symmetric, finite and positive semidefinite. This ensures that $\psi_{\mathcal{G}_n}$ is well-defined (see [1] for details, in particular Remark 1.2).

If $\mathcal{G}_n$ is not connected, then we set arbitrarily $\psi_{\mathcal{G}_n}(x) = 0$ a.s. for all $x \in \mathcal{G}_n$ (this will not play a significant role for our purpose, as $\mathcal{G}_n$ is connected w.h.p., see Proposition 2.1).

## Two layers of randomness

Denote $\mathbb{P}_{ann}$ and $\mathbb{E}_{ann}$ the annealed law and expectation for the joint realization of $\mathcal{G}_n$ and of $\psi_{\mathcal{G}_n}$ on it. For a fixed realization of $\mathcal{G}_n$, denote $\mathbb{P}^{\mathcal{G}_n}$ and $\mathbb{E}^{\mathcal{G}_n}$ the quenched law and expectation.

## 1.3 Results

Define the level set $E_{\varphi_{\mathbb{T}_d}}^{\ge h} := \{x \in \mathbb{T}_d | \varphi_{\mathbb{T}_d}(x) \ge h\}$. Let $C_o^h$ be the connected component of $E_{\varphi_{\mathbb{T}_d}}^{\ge h}$ containing the root $\circ$. Similarly, define the level sets $E_{\psi_{\mathcal{G}_n}}^{\ge h} := \{x \in \mathcal{G}_n | \psi_{\mathcal{G}_n}(x) \ge h\}$ for $n \ge 1$. For $i \ge 1$, let $C_i^{(n)}$ be the $i$-th largest connected component of $E_{\psi_{\mathcal{G}_n}}^{\ge h}$, by number of vertices. Break ties arbitrarily if several components have the same size (this will not play a significant role in the paper). In [32], Sznitman showed that there exists a constant $h_* \in (0, \infty)$ such that

$$ \text{if } h > h_*, \eta(h) := \mathbb{P}^{\mathbb{T}_d}(|C_o^h| = +\infty) = 0, \text{ and if } h < h_*, \eta(h) > 0. \quad (1.1) $$

In [3] (Theorems 4.3 and 5.1), Abächerli and Černý showed that if $h > h_*$, the size of $C_o^h$ has exponential moments, and if $h < h_*$, $C_o^h$ has a positive probability to grow exponentially. In [4] (Theorems 3.1 and 4.1), they found that if $\mathcal{G}_n$ satisfies some deterministic conditions, which hold w.h.p. (with high probability), then the following events hold $\mathbb{P}^{\mathcal{G}_n}$-w.h.p.: if $h > h_*$, $|C_1^{(n)}| = O(\log n)$, and if $h < h_*$, at least $\xi n$ vertices of $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ are in components of size at least $n^\delta$, for some constants $\delta, \xi > 0$ depending on $h$.

Thus, in the supercritical case $h < h_*$, a positive proportion of the vertices is in at least "mesoscopic" components (there is no explicit lower bound for $\delta$).

This work focusses exclusively on the supercritical case; recall that $d$ can be any fixed integer larger than 2. In the following results (and in the remainder of the paper), the constants $K_i, i \ge 0$ depend only on $d$ and $h$.

We first prove the existence of a giant component:

**Theorem 1.1.** Let $h < h_*$. The following holds:

$$ \frac{|C_1^{(n)}|}{n} \xrightarrow{\mathbb{P}_{ann}} \eta(h), \quad (1.2) $$

where $\xrightarrow{\mathbb{P}_{ann}}$ stands for convergence in $\mathbb{P}_{ann}$-probability as $n \to +\infty$. Moreover, there exists $K_0 > 0$ such that

$$ \mathbb{P}_{ann} \left( K_0^{-1} \log n \le |C_2^{(n)}| \le K_0 \log n \right) \xrightarrow{n \to +\infty} 1. \quad (1.3) $$

Note that by Markov's inequality, for any $\varepsilon > 0$ and any sequence of events $(\mathcal{E}_n)_{n \ge 1}$ such that $\mathbb{P}_{ann}(\mathcal{E}_n) \to 1$, w.h.p. $\mathcal{G}_n$ is such that $\mathbb{P}^{\mathcal{G}_n}(\mathcal{E}_n) \ge 1 - \varepsilon$. Thus, w.h.p. on $\mathcal{G}_n$, the conclusions of Theorem 1.1 hold with arbitrarily large $\mathbb{P}^{\mathcal{G}_n}$-probability. After a first preprint of this work, Černý [11] proved via a different approach that (1.2) also holds under the deterministic conditions of [3] and [4], see Section 1.4 for a discussion.
We also establish some structural properties of $C_1^{(n)}$. Let $C^{(n)}$ be the **2-core** of $C_1^{(n)}$, obtained by deleting recursively the vertices of degree 1 of $C_1^{(n)}$ and their edges. Let $K^{(n)}$ be the **kernel** of $C_1^{(n)}$, i.e. $C^{(n)}$ where simple paths are contracted to a single edge, so that the vertices of $K^{(n)}$ are those of $C^{(n)}$ with degree at least 3.

**Theorem 1.2. Global structure of $C_1^{(n)}$**

Fix $h < h_*$, There exist $K_1, K_2 > 0$ such that

$$ \frac{|C^{(n)}|}{n} \xrightarrow{P_{anp}} K_1 \qquad (1.4) $$

and

$$ \frac{|K^{(n)}|}{n} \xrightarrow{P_{anp}} K_2. \qquad (1.5) $$

Moreover, there exists $K_3 > 0$ such that if $D_1^{(n)}$ is the diameter of $C_1^{(n)}$, then

$$ P_{ann}(D_1^{(n)} \le K_3 \log n) \xrightarrow{n \to +\infty} 1. \qquad (1.6) $$

Last, there exists $\lambda_h > 1$ such that for every $\varepsilon > 0$,

$$ \pi_{2,n}(\{(x,y) \in (C_1^{(n)})^2, (1-\varepsilon) \log_{\lambda_h} n \le d_{C_1^{(n)}}(x,y) \le (1+\varepsilon) \log_{\lambda_h} n\}) \xrightarrow{P_{anp}} 1, \qquad (1.7) $$

where $\pi_{2,n}$ is the uniform measure on $(C_1^{(n)})^2$ and $d_{C_1^{(n)}}$ the usual graph distance on $C_1^{(n)}$.

In other words, the typical distance between vertices of $C_1^{(n)}$ is $\log_{\lambda_h} n$.

We will see in Section 3 that $\lambda_h$ is the growth rate of $C_1^h$ conditioned on being infinite.

Say that a random graph $G$ is the **local limit** of the random graph sequence $(G_n)_{n \ge 1}$ if $G_n$ converges to $G$ in distribution w.r.t to the local topology (see for instance the lecture notes of Curien [13] for a precise definition). We prove that the local limit of $C_1^{(n)}$ is $C_1^h$ conditioned to be infinite. Say that two rooted trees $T, T'$ are **isomorphic** if there is a bijection $\Phi: T \to T'$ preserving the root, and such that for all vertices $x, y \in T$, there is an edge between $x$ and $y$ if and only if there is an edge between $\Phi(x)$ and $\Phi(y)$.

**Theorem 1.3. Local limit of $C_1^{(n)}$**

Fix $h < h_*$, For every radius $k \ge 1$, for every rooted tree $T$ of height $k$, let $V_n^{(T)} := \{x \in C_1^{(n)}, B_{C_1^{(n)}}(x, k)$ is a tree isomorphic to $T\}$ and $p_T := P^{T_d}(B_{C_1^h}(\circ, k) = T | |C_1^h| = +\infty)$. Then

$$ \frac{|V_n^{(T)}|}{|C_1^{(n)}|} \xrightarrow{P_{anp}} p_T $$

## 1.4 Discussion and open questions

### GFF percolation versus bond percolation

The graph $E_{\psi_{G_n}}^{\ge h}$ undergoes the same phase transition as some classical bond percolation models for the size of the largest connected component. We draw a comparison with the Erdős-Rényi random graph (i.e. bond percolation on the complete graph), introduced by Gilbert in [21]: for a constant $c > 0$ and $n \in \mathbb{N}$, $ER(n, c/n)$ is the graph on $n$ vertices such that for every pair of vertices $x, y$, there is an edge between $x$ and $y$ with probability $c/n$, independently of all other pairs of vertices. Erdős and Rényi [20] showed that the supercritical regime corresponds to $c > 1$ and the subcritical regime to $c < 1$. Theorems 1.1, 1.2 and 1.3 hold for $ER(n, c/n)$ as $n \to +\infty$, for any fixed $c > 1$, the tree $C_1^h$ being replaced by a Galton-Watson tree whose offspring distribution is Poisson with parameter $c$, and $\lambda_h$ being replaced by $c$.
As for Bernoulli bond percolation on $G_n$ (each edge of $G_n$ is deleted with probability $1-p$, independently of the others), the same phase transition holds for the size of the largest connected component, the critical threshold being $p = 1/(d-1)$ (Theorem 3.2 of [7]).

### The structure of $C_1^{(n)}$

It was shown recently in [14] that the distribution of the giant component of $ER(n, c/n)$ is continuous w.r.t. to a random graph which can be explicitly described. Its kernel is a configuration model whose vertices have i.i.d. degrees with a Poisson distribution (conditioned on being at least 3). In particular, it is an expander. The lengths of the simple paths in the 2-core are i.i.d. geometric random variables. See Theorem 1 of [14] for details. This implies a result analogous to Theorem 1.2 for $ER(n, c/n)$.

We conjecture that the kernel $K^{(n)}$ is an expander for every $h < h_*$, The main obstacle to gathering information on its global structure is that if $\psi_{G_n}$ is revealed on a positive proportion of the vertices of $K^{(n)}$ (and hence of $G_n$), then it could affect substantially $\psi_{G_n}$ on the remaining vertices. In particular, if $h > 0$ is large enough, we could imagine that the average of $\psi_{G_n}$ on the discovered vertices is positive. But by (2.9), the average of the GFF on the remaining vertices would be negative, hence below the threshold $h$.

### Deterministic regular graphs

The results of [4] and [7] hold in fact for any deterministic sequence of large-girth expanders (conditions (I) and (II) in Proposition 2.1), which is w.h.p. the case for $G_n$. Very recently, Černý [11] gave another proof of (1.2) that holds under these deterministic conditions. He also showed that $|C_2^{(n)}| = o(n)$ w.h.p. His approach is very different, and uses notably a decomposition of the GFF as an infinite sum of fields with finite range interactions, introduced in [17].

In our proofs, averaging on the randomness of $G_n$ is a crucial ingredient to control the presence of cycles on large subgraphs of $G_n$, and allows us to extend some arguments of [4], where $\psi_{G_n}$ is locally approximated by $\varphi_{T_d}$.

We conjecture that those deterministic conditions are not sufficient for (1.3) to hold. This was shown for the Bernoulli bond percolation in [23] (Theorem 2): for every $a \in (0, 1)$, one can build a sequence $(G_n)_{n \ge 1}$ satisfying (I) and (II) such that the second largest connected component has at least $n^a$ vertices (the second largest component first grows exponentially on a tree-like ball until it has a polynomial size, and then is “trapped” in zones where the expansion of the graph is close to an arbitrarily small constant).

## 1.5 Proof outline

Our proofs rely on two main arguments:

1) An annealed exploration of $E_{\psi_{G_n}}^{\ge h}$ (Proposition 2.4), where the structure of $G_n$ is progressively revealed. There is a standard sequential construction of a uniform $d$-regular multigraph $M_n$, which, conditioned to be simple, yields $G_n$ (this conditioning has a non vanishing probability, see Section 2). Each newly discovered vertex is given an independent standard normal variable. Then $\psi_{G_n}$ is built via a recursive procedure, using these Gaussian variables (Proposition 2.3).

2) A comparison of $\psi_{G_n}$ and $\varphi_{T_d}$ (Proposition 4.1): on a tree-like subgraph $T$ of $G_n$, such that there are no cycles in $G_n$ at distance $\kappa \log \log n$ of $T$ for a large enough constant $\kappa$, there is a bijective map $\Phi$ between $T$ and an isomorphic subtree of $T_d$ and a coupling of $\psi_{G_n}$ and $\varphi_{T_d}$ so that

$$ \sup_{y \in T} |\psi_{G_n}(y) - \varphi_{T_d}(\Phi(y))| \le \log^{-1} n. $$
We stress the fact that we reveal $\psi_{\mathcal{G}_n}$ only after having explored $\mathcal{G}_n$: if we reveal $\psi_{\mathcal{G}_n}$ at a given vertex, it conditions the structure of $\mathcal{G}_n$ and thus the pairings of the still unmatched half-edges, so that we cannot use the sequential construction any more to further explore the graph. Hence, during the exploration, we will need to build an approximate version of $\psi_{\mathcal{G}_n}$, depending on the Gaussian variables of 1). This makes some proofs tedious, in particular that of (1.3).

From Section 2 onwards, we will work exclusively on $M_n$ (and with the GFF on it, $\psi_{M_n}$), proving that the statements of Theorems 1.1, 1.2 and 1.3 hold w.h.p. on $M_n$. Since the law of $\mathcal{G}_n$ is that of $M_n$ under a non-vanishing conditioning, these statements hold w.h.p. on $\mathcal{G}_n$. For convenience, we continue this Section with $\mathcal{G}_n$ and $\psi_{\mathcal{G}_n}$ instead of $M_n$ and $\psi_{M_n}$.

**The base exploration**

The exploration that we will perform in all proofs, with some modifications, is as follows: pick $x \in V_n$, and reveal its connected component $C_x^{\mathcal{G}_n, h}$ in $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ in a breadth-first way, as well as its neighbourhood up to distance $a_n = \kappa \log \log n$. Until we meet a cycle, the explored zone is a tree $T_x$, growing at least like $C_o^{h+\log^{-1} n}$, and at most like $C_o^{h-\log^{-1} n}$ by 2).

On one hand, $C_o^{h+\log^{-1} n}$ has a probability $\approx \eta(h + \log^{-1} n) = \eta(h) + o(1)$ to be infinite, with a growth rate $\lambda_h > 1$ (Section 3.2). On the other hand, the probability to create a cycle is $o(1)$ as long as we reveal $o(\sqrt{n})$ vertices (since we perform $o(\sqrt{n})$ pairings of half-edges having each a probability $o(\sqrt{n})/n$ to involve two already discovered vertices). Thus, with $\mathbb{P}_{ann}$-probability at least $\eta(h)+o(1)$, $T_x$ and $\partial T_x$ will reach a size $\Theta(\sqrt{n} \log^{-\kappa'} n)$ for some constant $\kappa' > 0$ (Proposition 5.1).

Conversely, $C_o^{h-\log^{-1} n}$ has a probability $1 - \eta(h - \log^{-1} n) = 1 - \eta(h) + o(1)$ to be finite, and with $\mathbb{P}_{ann}$-probability $1 - \eta(h) + o(1)$, $|C_x^{\mathcal{G}_n, h}| = o(\sqrt{n})$ (Proposition 5.4).

**Proof of (1.2).**

First, we show that for any two vertices $x, y \in V_n$, there is a $\mathbb{P}_{ann}$-probability $\eta(h)^2 + o(1)$ that they are connected in $E_{\psi_{\mathcal{G}_n}}^{\ge h}$. To do so, we explore $C_x^{\mathcal{G}_n, h}$ and $C_y^{\mathcal{G}_n, h}$, that we couple with independent copies of $C_o^{h+\log^{-1} n}$, so that with probability $\eta(h)^2 + o(1)$, $\partial T_x$ and $\partial T_y$ have $\Theta(\sqrt{n} \log^{-\kappa'} n)$ vertices. The explorations from $x$ and $y$ are disjoint with probability $1-o(1)$, since $o(\sqrt{n})$ vertices have been explored. Then, we draw multiple paths between $T_x$ and $T_y$ (with an "envelope" of radius $\Theta(\log \log n)$ around each of them to allow the use of the approximation 2)), the **joining balls** (Section 6.1). The probability that $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ percolates through at least one of these paths is $1-o(1)$.

Second, we prove by a second moment argument that $\mathbb{P}_{ann}$-w.h.p., the number of couples $(x, y) \in V_n^2$ such that $y \in C_x^{\mathcal{G}_n, h}$ is $(\eta(h)^2 + o(1))n^2$ (Lemma 6.5).

Third, knowing that $|C_x^{\mathcal{G}_n, h}| = o(\sqrt{n})$ with $\mathbb{P}_{ann}$-probability $1 - \eta(h) + o(1)$, we deduce in the same way that at least $(1 - \eta(h) + o(1))n$ vertices are in connected components of size $o(\sqrt{n})$ (Lemma 6.4).

Those two facts together force the existence of a connected component of size $(\eta(h) + o(1))n$.

**Proof of (1.3).**

The most difficult part is the upper bound. We show that for $K_0$ large enough, for $x \in V_n$, $\mathbb{P}_{ann}(K_0 \log n \le |C_x^{\mathcal{G}_n, h}| \le K_0^{-1} n) = o(1/n)$, and conclude by a union bound on $x$ and a corollary of the proof of (1.2), namely that $|C_2^{(n)}|/n \xrightarrow{P_{ann}} 0$.

The greater precision $o(1/n)$ requires three additional ingredients:

* the size of $C_o^h$ conditioned on being finite has exponential moments (Proposition 3.4),
in particular, $P^{\mathbb{T}_d}(|C_o^h| \ge c \log n, |C_o^h| < +\infty) = o(1/n)$ for a large enough constant $c$;

* when exploring $k$ vertices around $x$, there is a probability $\Theta(k^2/n)$ that a cycle arises, so that we will need to handle at least one cycle to fully explore $C_x^{G_n,h}$;

* we need a better approximation of $\psi_{G_n}$ than $\log^{-1} n$ in 2): with probability at least $\Theta(1/n)$, we will meet too many vertices with an approximate value of $\psi_{G_n}$ that are in $[h - \log^{-1} n, h + \log^{-1} n]$, so that we can not tell whether they are in $C_x^{G_n,h}$ or not before the end of the exploration. To remedy this, we replace the "security radius" $a_n$ in 2) by some $r_n = \Theta(\log n)$, so that we approximate $\psi_{G_n}$ up to a difference $n^{-\Theta(1)}$.

**Other proofs.**

The proofs of Theorems 1.2 and 1.3 are based on slightly modified explorations, and are much simpler.

**1.6 Plan of the rest of the paper**

In Section 2, we review some basic properties of $G_n$. In Section 3, we study the GFF on $\mathbb{T}_d$. In Section 4, we establish a coupling between recursive constructions of the GFF on $\mathbb{T}_d$ and on a tree-like neighbourhood of $G_n$. As these three sections consist of preparatory work, most of their proofs are deferred to the Appendix. The core ideas of the paper are in Sections 5 and 6. In Section 5, we explore the connected component of a vertex in $E_{\tilde{\psi}_{G_n}^h}$. In Section 6, we prove (1.2). The most technical part of this article is Section 7, in which we prove (1.3). In Section 8, we prove Theorems 1.2 and 1.3.

**1.7 Further definitions**

In this paper, graphs are undirected. For a graph $G$, denote $d_G$ the usual graph distance on its vertex set $V$, and for every vertex $x$ and every integer $R \ge 0$, let $B_G(x, R) := \{y, d_G(x, y) \le R\}$ and $\partial B_G(x, R+1) = B_G(x, R+1) \setminus B_G(x, R)$. For any $S \subseteq V$, let similarly $B_G(S, R) := \cup_{x \in S} B_G(x, R)$ and $\partial B_G(S, R+1) = B_G(S, R+1) \setminus B_G(S, R)$. If $A$ is a subgraph of $G$ with vertex set $S$, let $B_G(A, R) := B_G(S, R)$. If $x$ and $y$ are neighbours, we denote $B_G(x, y, R)$ the subgraph of $G$ obtained by taking all paths of length $R$ starting at $x$ and not going through $y$.

The **tree excess** of a finite graph $G$ is $\text{tx}(G) = e - v + 1$, where $v := |V|$ and $e$ is the number of edges in $G$, see Section A.3 for elementary facts on the tree excess that will be useful throughout the paper.

A **rooted tree** is a tree $T$ with a distinguished vertex $\circ$, the **root**. The **height** $h_T(x)$ of a vertex $x$ in $T$ is $d_T(\circ, x)$. If $T$ is finite, its **boundary** $\partial T$ is the set of vertices of maximal height. The **subtree from** $x$ is the subtree made of the vertices $y$ such that $x$ is on any path from $\circ$ to $y$. The **offspring** of $x$ is the set of vertices of its subtree. For $r \ge 0$, the $r$-**offspring** of $x$ is its offspring at distance $r$ of $x$, and its **offspring up to generation** $r$ is its offspring at distance at most $r$. If $y$ is in the 1-offspring of $x$, then $y$ is a **child** of $x$, and $x$ is its **parent**. In this case, write $x = \bar{y}$.

If $x, y$ are neighbours in $T$, the **cone from** $x$ **out of** $y$ is the rooted subtree of $T$ with root $x$ and vertex set $\{z \in T \mid y$ is not on the shortest path from $x$ to $z\}$.

Unless mention of the contrary, all random walks are in discrete time. We will write $T_A$ (resp. $H_A$) for the first exit (resp. hitting) time of a set $A$ by a SRW.

For two probability distributions $\mu, \mu'$ on $\mathbb{R}$, we write $\mu \le_{st.} \mu'$ (or $\mu' \ge_{st.} \mu$) if $\mu'$ dominates stochastically $\mu$, i.e. there exist two random variables $X \sim \mu$ and $X' \sim \mu'$ on the same probability space such that $X \le X'$ a.s.
# 2 Basic properties

## 2.1 From $\mathcal{G}_n$ to the multigraph $M_n$

The graph $\mathcal{G}_n$ can be generated sequentially as follows: attach $d$ half-edges to each vertex of $V_n$. Pick an arbitrary half-edge, and match it to another half-edge chosen uniformly at random. Then, choose a remaining half-edge and match it to another unpaired half-edge chosen uniformly at random among the remaining half-edges, and so on until all half-edges have been paired. The resulting multi-graph $M_n$ is not necessary **simple**, i.e. it might have loops and multiple edges. The probability that $M_n$ is simple has a positive limit as $n \to +\infty$, and conditionally on $\{M_n$ is simple\}, $M_n$ is distributed as $\mathcal{G}_n$ (see for instance Section 7 of [33], in particular Proposition 7.13 for a reference).

In particular, an event true w.h.p. on $M_n$ is also true w.h.p. on $\mathcal{G}_n$, so that it is enough to prove all our results on $M_n$. In the rest of the paper, we will exclusively work on $M_n$.

Note that $M_n$ is not necessarily connected, but that it is $d$-regular. The SRW on $M_n$ is as follows: if a vertex $x$ has a loop, then a SRW starting at $x$ goes through the loop with probability $2/d$, and if there is an edge with multiplicity $\ell \ge 1$ between $x$ and an other vertex $y$, the SRW moves to $y$ with probability $\ell/d$. The uniform measure $\pi_n$ on its vertices is still invariant for the SRW, and is the unique such probability measure if $M_n$ is connected. Also, the SRW is still reversible. These observations allow to transpose readily the definitions in Section 1.2 from $\mathcal{G}_n$ to $M_n$. When $M_n$ is connected, denote $G_{M_n}$ the Green function (which is still symmetric, finite and positive semidefinite), and $\psi_{M_n}$ the GFF. When $M_n$ is not connected, we also impose $\psi_{M_n}(x) = 0$ for all $x \in V_n$.

The following proposition is the main result of this Section (recall that the constants $K_i$'s implicitly depend on $d$ and $h$). We postpone its proof to the Appendix.

**Proposition 2.1.** There exists $K_3 > 0$ such that w.h.p. as $n \to +\infty$, $M_n$ satisfies:

(I) $M_n$ is a $K_3$-**expander**, i.e. the spectral gap $\lambda_{M_n}$ of $M_n$ is at least $K_3$ (the spectral gap is $1 - \lambda_2/d$, where $\lambda_2$ is the second largest eigenvalue of the adjacency matrix of $M_n$),

(II) for all $x \in M_n$, $B_{M_n}(x, \lfloor K_3 \log n \rfloor)$ contains at most one cycle.

Moreover, there exists $K_4 > 0$ such that w.h.p. on $M_n$, the following holds: for all $x \in V_n$ such that $\text{tx}(B_{M_n}(x, \lfloor K_4 \log \log n \rfloor)) = 0$,

$$ \left| G_{M_n}(x, x) - \frac{d-1}{d-2} \right| \le \log^{-6} n. \qquad (2.1) $$

If moreover $y$ is a neighbour of $x$,

$$ \left| G_{M_n}(x, y) - \frac{1}{d-2} \right| \le \log^{-6} n. \qquad (2.2) $$

Say that a given realization of $M_n$ is a **good graph** when (I), (II), (2.1) and (2.2) hold. Remark that a good graph is necessarily connected, as the spectral gap of a non-connected graph is 0 (see Section 2.3 of [22]). In particular, $M_n$ (and thus $\mathcal{G}_n$) is connected w.h.p. The equations (2.1) and (2.2) illustrate the fact that $G_{M_n}$ is close to $G_{T_d}$ on a tree-like neighbourhood: it is well-known that for all $x, y \in T_d$,

$$ G_{T_d}(x, y) = \frac{(d-1)^{1-d_{T_d}(x,y)}}{d-2}. \qquad (2.3) $$

A quick computation can be found in [34], Lemma 1.24.
By Proposition 1.1 of [4] (whose proof also works with loops and multiple edges) (I) and (II) imply that for some $K_5$, $K_6 > 0$ and for $n$ large enough, for all $x, y \in V_n$,

$$|G_{M_n}(x, y)| \le \frac{K_5}{(d-1)^{d_{M_n}(x,y)}} \lor n^{-K_6}. \quad (2.4)$$

Throughout this paper, we will often make binomial estimates, because the number of edges between two sets of vertices in $M_n$ is close to a binomial random variable, as highlighted in the Lemma below. We will use repeatedly the following classical inequalities: for $n \ge m \ge 0$ and $p \in (0, 1)$, if $Z \sim \text{Bin}(n, p)$, one has

$$\mathbb{P}(Z \ge m) \le \binom{n}{m} p^m, \quad \mathbb{P}(Z \le m) \le \binom{n}{m} (1-p)^m, \quad \binom{n}{m} \le \frac{n^m}{m!} \le n^m. \quad (2.5)$$

The following Lemma is an important consequence of the sequential construction of $M_n$.

**Lemma 2.2 (Binomial number of connections).** Let $m \in \mathbb{N}$, let $W_0, W_1$ be disjoint subsets of $V_n$. Write $m_0 := |W_0|$ and $m_1 := |W_1|$. Suppose the only information we have on $M_n$ is a set $E$ of its edges that has been revealed. Let $m_E := |E|$ and denote $\mathbb{P}^E$ the law of $M_n$ conditionally on this information. Repeat the following operation $m$ times: pick an arbitrary vertex $v \in W_0$ having at least one unmatched half-edge, and pair it with an other half-edge. Add its other endpoint $v'$ in $W_0$, if it was not already in it. Let $s$ be the number of times that $v' \in W_1$. Suppose that $m_E + m + m_1 < n$. Then

$$s \le \text{Bin} \left( m, \frac{m_1}{n - (m_E + m)} \right). \quad (2.6)$$

In particular,

a) for any fixed $k \in \mathbb{N}$, there exists $C(k) > 0$ so that for $n$ large enough, if $m_E + m < n/2$,

$$\mathbb{P}^E(s \ge k) \le C(k) \left( \frac{m_1 m}{n} \right)^k. \quad (2.7)$$

b) for $k = k(n) \to +\infty$ and $n$ large enough, if we have $m_E + m < n/2$ and $kn > 6(m_1 + m_0 + m_E)m$, then

$$\mathbb{P}^E(s \ge k) \le 0.99^k. \quad (2.8)$$

**Proof.** Pick $v \in W_0$, such that $v$ has an unmatched half-edge $e$. There are at most $m_1$ vertices in $W_1$, so that there are at most $dm_1$ unmatched half-edges that belong to its vertices. And the total number of unmatched half-edges is at least $dn - 2(|E| + m) \ge d(n - m_E - m)$. Thus, the probability that $e$ is matched with a half-edge belonging to a vertex of $W_1$ is not greater than $\frac{dm_1}{d(n-m_E-m)} = \frac{m_1}{n-(m_E+m)}$, and this bound does not depend on the outcome of the previous matchings. (2.6) follows.

Let $Z \sim \text{Bin} \left( m, \frac{m_1}{n-(m_E+m)} \right)$. By (2.5), for $k \in \mathbb{N}$, we have

$$\mathbb{P}^E(Z \ge k) \le \binom{m}{k} \left( \frac{m_1}{n-(m_E+m)} \right)^k \le \binom{m}{k} \left( \frac{m_1}{n/2} \right)^k \le \frac{2^k m_1^k m^k}{k! n^k}.$$

This yields (2.7). Moreover, if $k \to +\infty$ as $n \to +\infty$ and $kn > 6(m_1 + m_0 + m_E)m$, by Stirling's formula, we have $\mathbb{P}^E(Z \ge k) \le \left( \frac{(2e+0.1)m_1m}{kn} \right)^k < 0.99^k$ for $n$ large enough, and (2.8) follows. $\square$

It is straightforward to adapt this when $s$ counts the number of times that $v'$ was in $W_0$ (and there is no set $W_1$). $m_1$ is replaced by $m_0 + m$ in (2.6) and (2.7), and (2.8) does not change. Throughout this paper, we will refer to these equations without mentioning explicitly if we count the connections from $W_0$ to $W_1$ or from $W_0$ to itself.
## 2.2 GFF on $M_n$

The name “zero-average” for the GFF on $M_n$ (or $G_n$) comes from the fact that a.s.,

$$ \sum_{x \in V_n} \psi_{M_n}(x) = 0 \qquad (2.9) $$

since $\mathrm{Var}(\sum_{x \in V_n} \psi_{M_n}(x)) = \sum_{x,y \in V_n} G_{M_n}(x, y) = 0$.

Hence, there is no domain Markov property. However, there is a recursive construction of $\psi_{M_n}$:

**Proposition 2.3 (Lemma 2.6 in [4]).** Let $A \subsetneq V_n$ and $x \in V_n \setminus A$. Define $\sigma(A) := \sigma(\{\psi_{M_n}(y), y \in A\})$. Let $(X_k)_{k \ge 0}$ be a SRW on $M_n$ and let $H_A$ be the hitting time of A. Conditionally on $\sigma(A)$, $\psi_{M_n}(x)$ is a Gaussian variable, such that

$$ \mathrm{E}^{M_n}[\psi_{M_n}(x)|\sigma(A)] = \mathrm{E}_x^{M_n}[\psi_{M_n}(X_{H_A})] - \frac{\mathrm{E}_x^{M_n}[H_A]}{\mathrm{E}_{\pi_n}^{M_n}[H_A]} \mathrm{E}_{\pi_n}^{M_n}[\psi_{M_n}(X_{H_A})] \qquad (2.10) $$

and

$$ \mathrm{Var}^{M_n}(\psi_{M_n}(x)|\sigma(A)) = G_{M_n}(x, x) - \mathrm{E}_x^{M_n}[G_{M_n}(x, X_{H_A})] + \frac{\mathrm{E}_x^{M_n}[H_A]}{\mathrm{E}_{\pi_n}^{M_n}[H_A]} \mathrm{E}_{\pi_n}^{M_n}[G_{M_n}(x, X_{H_A})]. \qquad (2.11) $$

Combining this Lemma and the sequential construction $M_n$, we obtain the following.

**Proposition 2.4 (Joint realization of $M_n$ and $\psi_{M_n}$).** A realization of $(M_n, \psi_{M_n})$ is given by the following process. Let $(\xi_i)_{i \ge 1}$ be a sequence of i.i.d. $\mathcal{N}(0, 1)$ variables. A move consists in:

* choosing an unpaired half-edge $e$ and matching it to another unpaired half-edge chosen uniformly at random (independently of $(\xi_i)_{i \ge 1}$), or

* choosing $x \in V_n$ and $k \in \mathbb{N}$ so that $\xi_k$ has not yet been attributed, and attributing $\xi_k$ to $x$.

At each move, the choice of $e$, $x$ or $k$ might depend in an arbitrary way on the previous moves, i.e. on the matchings and on the value of the normal variables attributed before, but not on the value of the remaining normal variables. Perform moves until all half-edges are paired, and every vertex $x \in V_n$ has received a normal variable, that we denote $\xi_x$.

To generate $\psi_{M_n}$, let $x_1, \dots, x_n$ be the vertices of $V_n$, listed in the order in which they received their normal variable. Let $\psi_{M_n}(x_1) := \sqrt{G_{M_n}(x_1, x_1)}\xi_{x_1}$. For $i = 2, \dots, n$ successively, define $A_i := \{x_1, \dots, x_{i-1}\}$. Recall that we write $\sigma(A_i)$ for $\sigma(\{\psi_{M_n}(y), y \in A_i\})$. Let

$$ \psi_{M_n}(x_i) := \mathrm{E}^{M_n}[\psi_{M_n}(x_i)|\sigma(A_i)] + \xi_{x_i} \sqrt{\mathrm{Var}(\psi_{M_n}(x_i)|\sigma(A_i))}. $$

It might be confusing that $\psi_{M_n}(x_i)$ appears on both sides of the equation. Note that the conditional expectation and variance on the RHS are $\sigma(A_i)$-measurable random variables.

*Proof.* Clearly, the graph obtained after pairing all the half-edges is distributed as $M_n$. For every $i \ge 1$, $\xi_{x_i}$ is a standard normal variable independent of the realization of $M_n$, and of $\sigma(A_i)$ for $i \ge 1$, so that we can conclude by Proposition 2.3. $\square$

Last, we prove that the maximum of $|\psi_{M_n}|$ on $M_n$ has a subexponential tail.
**Lemma 2.5 (Tail for the maximum of $|\psi_{M_n}|$).** Suppose that $\max_{x \in V_n} G_{M_n}(x, x) \le K_5$. Then for all $\Delta > 0$, if $n$ is large enough,

$$ P^{M_n} \left( \max_{x \in V_n} |\psi_{M_n}(x)| \ge \log^{2/3} n \right) \le n^{-\Delta}. \qquad (2.12) $$

In particular, by Proposition 2.1 and (2.4), w.h.p. $M_n$ satisfies (2.12).

*Proof.* Let $N \sim N(0, K_5)$. If $n$ is large enough, then for all $x \in V_n$,

$$ P^{M_n}(|\psi_{M_n}(x)| \ge \log^{2/3} n) \le P^{M_n}(|N| \ge \log^{2/3} n) \le 2 \exp \left( -\frac{\log^{4/3} n}{4K_5} \right) \le n^{-\Delta-1} $$

by Markov's inequality applied to the function $u \mapsto \exp\left(\frac{\log^{2/3} n}{2K_5} u\right)$. By a union bound on all $x \in V_n$, we get $P^{M_n}\left(\max_{x \in M_n} |\psi_{M_n}(x)| > \log^{2/3} n\right) \le n^{-\Delta}$. $\square$

# 3 The Gaussian Free Field on $T_d$

In Section 3.1, we characterize $C_\circ^h$ as a branching process, with a recursive construction (Proposition 3.1). Then, in Section 3.2, we establish its exponential growth, conditionally on the event $\{|C_\circ^h| = +\infty\}$. The main results are Propositions 3.3, 3.4 and 3.6.

## 3.1 $C_\circ^h$ as a branching process

There is an alternate definition of $\varphi_{T_d}$, starting from its value at $\circ$ and expanding recursively to its neighbours. It shows that $C_\circ^h$ is an infinite-type branching process, the type of a vertex $x$ being $\varphi_{T_d}(x)$.

**Proposition 3.1 (Recursive construction of the GFF,**(1.4)-(1.9) in [3]).** Define a Gaussian field $\varphi$ on $T_d$ as follows: let $(\xi_y)_{y \in T_d}$ be a family of i.i.d. $N(0, 1)$ random variables. Let $\varphi(\circ) := \sqrt{\frac{d-1}{d-2}} \xi_\circ$. For every $y \in T_d \setminus \{\circ\}$, define recursively $\varphi(y) := \sqrt{\frac{d}{d-1}} \xi_y + \frac{1}{d-1} \varphi(\bar{y})$, where $\bar{y}$ is the parent of $y$. Then

$$ \varphi \stackrel{d.}{=} \varphi_{T_d}. $$

Proposition 3.1 is the corollary of a more general domain Markov property (see for instance Lemma 1.2 of [27] where it is stated for $Z^d$, but the proof works for any transient graph).

Write $P^{T_d}$ for the law of $\varphi_{T_d}$, and $P_a^{T_d}$ for $P^{T_d}(\cdot | \varphi_{T_d}(\circ) = a)$, $a \in \mathbb{R}$ (such conditioning is well-defined, $(\varphi_{T_d}(x))_{x \in T_d}$ being a Gaussian process). This construction gives a monotonicity property for $\varphi_{T_d}$. A set $S \subset \mathbb{R}^{T_d}$ is said to be **increasing** if for any $(\Phi_z^{(1)})_{z \in T_d}, (\Phi_z^{(2)})_{z \in T_d} \in \mathbb{R}^{T_d}$ such that $\Phi_z^{(1)} \le \Phi_z^{(2)}$ for all $z \in T_d$, $(\Phi_z^{(1)})_{z \in T_d} \in S$ only if $(\Phi_z^{(2)})_{z \in T_d} \in S$. Say that the event $\{\varphi_{T_d} \in S\}$ is **increasing** if $S$ is increasing.

**Lemma 3.2 (Conditional monotonicity).** If $E$ is an increasing event, then the map $a \mapsto P_a^{T_d}(E)$ is non-decreasing on $\mathbb{R}$.

*Proof.* Let $a_1, a_2 \in \mathbb{R}$ such that $a_1 > a_2$. It suffices to give a coupling between a GFF $\varphi_{T_d}^{(1)}$ conditioned on $\varphi_{T_d}^{(1)}(\circ) = a_1$ and a GFF $\varphi_{T_d}^{(2)}$ conditioned on $\varphi_{T_d}^{(2)}(\circ) = a_2$ such that a.s., for every $z \in T_d$, $\varphi_{T_d}^{(1)}(z) \ge \varphi_{T_d}^{(2)}(z)$. To do this, let $(\xi_y)_{y \in T_d}$ be i.i.d. standard normal variables, and define recursively $\varphi_{T_d}^{(1)}$ and $\varphi_{T_d}^{(2)}$ as in Proposition 3.1. Then for every $z \in T_d$ of height $k \ge 0$, $\varphi_{T_d}^{(1)}(z) = \varphi_{T_d}^{(2)}(z) + (a_1 - a_2)(d-1)^{-k}$. $\square$
## 3.2 Exponential growth

All proofs of this section are postponed to the Appendix, Section A.2.

Let $Z_k^h := C_\circ^h \cap \partial B_{T_d}(\circ, k)$ be the $k$-th generation of $C_\circ^h$. We first characterize the growth rate of $Z_k^h$. The first statement of the proposition below is a variant of Theorem 4.3 in [3].

**Proposition 3.3.** There exists $\lambda_h > 1$ such that

$$ \lim_{k \to +\infty} \mathbb{P}^{T_d}(|Z_k^h| > \lambda_h^k/k^2) = \eta(h) $$

and

$$ \lim_{k \to +\infty} \mathbb{P}^{T_d}(|Z_k^h| < k\lambda_h^k) = 1. $$

Moreover, $h \mapsto \lambda_h$ is a decreasing homeomorphism from $(-\infty, h_*)$ to $(1, d-1)$.

We now give finer results on the growth rate of $|C_\circ^h|$. It turns out that $|C_\circ^h|$ conditioned to be finite has exponential moments:

**Proposition 3.4.** There exists a constant $K_7 > 0$ such that as $k \to +\infty$,

$$ \max_{a \ge h} \mathbb{P}_a^{T_d}(k \le |C_\circ^h| < +\infty) = o(\exp(-K_7 k)). \quad (3.1) $$

Since $\{Z_k^h \ne \emptyset\} \subset \{|C_\circ^h| \ge k\}$, we have the following straightforward consequence:

**Corollary 3.5.** For $k$ large enough, for every $a \ge h$,

$$ \mathbb{P}_a^{T_d}(|C_\circ^h| = +\infty) \le \mathbb{P}_a^{T_d}(Z_k^h \ne \emptyset) \le \mathbb{P}_a^{T_d}(|C_\circ^h| = +\infty) + e^{-K_7 k}. $$

In addition, there are large deviation bounds for the growth rate of $Z_k^h$:

**Proposition 3.6.** For every $\varepsilon > 0$, there exists $C > 0$ such that for every $k \in \mathbb{N}$ large enough,

$$ \max_{a \ge h} \mathbb{P}_a^{T_d}(k^{-1} \log |Z_k^h| \notin [\log(\lambda_h - \varepsilon), \log(\lambda_h + \varepsilon) + k^{-1} \log \chi_h(a)] | Z_k^h \ne \emptyset) \le \exp(-Ck). \quad (3.2) $$

Let $\bar{\circ}$ be an arbitrary neighbour of $\circ$. Let $T_d^+$ be the cone from $\circ$ out of $\bar{\circ}$. Write $C_\circ^{h,+} := C_\circ^h \cap T_d^+$. For $k \ge 1$, let $Z_k^{h,+} := C_\circ^{h,+} \cap \partial B_{T_d^+}(\circ, k)$. The last proposition also holds when replacing $C_\circ^h$ by $C_\circ^{h,+}$, and $Z_k^h$ by $Z_k^{h,+}$.

# 4 Approximate recursive construction of $\psi_{M_n}$

Let $\kappa > 0$ be a constant, and let

$$ a_n := \lceil \kappa \log_{d-1} \log n \rceil. \quad (4.1) $$

The following statement is the main result of this section. It shows that a recursive construction of $\psi_{M_n}$, under some assumptions on the subset $A \subset V_n$ of vertices where $\psi_{M_n}$ is already known, is very close to the construction of $\varphi_{T_d}$ in Proposition 3.1. It is a crucial tool for comparing $\psi_{M_n}$ and $\varphi_{T_d}$ in the exploration in the next section. It is analogous to Proposition 2.7 of [4], where the assumptions on $A$ are slightly different: they are suited to a deterministic $d$-regular graph satisfying (I) and (II), while ours will be adapted to an annealed exploration, where the randomness of $M_n$ plays a role. The proof is postponed to the Appendix, Section A.3.

**Proposition 4.1.** If the constant $\kappa$ from (4.1) is large enough, then the following holds for $n$ large enough. Assume that $M_n$ is a good graph as defined in Proposition 2.1, and that $A \subset V_n$ satisfies

$$ \bullet \quad |A| \le n \log^{-8} n, $$
• $\mathrm{tx}(B_{\mathcal{M}_n}(A, a_n)) = \mathrm{tx}(A)$, and

• $\max_{z \in A} |\psi_{\mathcal{M}_n}(z)| \le \log^{2/3} n$.

For every $y \in \partial B_{\mathcal{M}_n}(A, 1)$, writing $\bar{y}$ for the unique neighbour of $y$ in A, we have:

$$ \left| \mathrm{E}^{\mathcal{M}_n}[\psi_{\mathcal{M}_n}(y)|\sigma(A)] - \frac{1}{d-1} \psi_{\mathcal{M}_n}(\bar{y}) \right| \le \log^{-3} n \quad (4.2) $$

and

$$ \left| \mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(y)|\sigma(A)) - \frac{d}{d-1} \right| \le \log^{-4} n. \quad (4.3) $$

We stress that the result holds for a fixed realization of $\mathcal{M}_n$.

<figure><img src="image_4.png" /><figcaption>Figure 1: The unicity of $\bar{y}$ comes from the fact that when building $B_{\mathcal{M}_n}(A, a_n)$ from A, no cycle appears and no connected components of A join, since $\mathrm{tx}(B_{\mathcal{M}_n}(A, a_n)) = \mathrm{tx}(A)$.</figcaption></figure>

# 5 Exploration of $\psi_{\mathcal{M}_n}$ around a vertex

## 5.1 Successful exploration

In this section, we prove that with $\mathbb{P}_{ann}$-probability arbitrarily close to $\eta(h)$ as $n \to +\infty$, $|C_x^{\mathcal{M}_n, h}| \ge n^{1/2} \log^{-\kappa-6} n$, $C_x^{\mathcal{M}_n, h}$ being the connected component of a given vertex $x$ in $E_{\psi_{\mathcal{M}_n}}^{\ge h}$ (Proposition 5.1), and $\kappa$ the constant defined in (4.1).

To do so, we explore a tree-like neighborhood $T_x$ of $x$ in $E_{\psi_{\mathcal{M}_n}}^{\ge h}$. We reveal $T_x$ generation by generation, and couple it with a realization of $C_o^{h+\log^{-1} n} \subset \mathbb{T}_d$ that is independent of the pairing of the half-edges of $\mathcal{M}_n$. By Proposition 2.4, a realization of $\psi_{\mathcal{M}_n}$ is given by a recursive construction with the same normal variables as those of the realization of $\varphi_{\mathbb{T}_d}$. When:

• that realization of $C_o^{h+\log^{-1} n}$ is infinite (which happens with probability $\eta(h + \log^{-1} n) \simeq \eta(h)$), and
* the conditions of Proposition 4.1 hold for each vertex of $T_x$, until a generation at which $|\partial T_x| \ge n^{1/2} \log^{-\kappa-6} n$ (which happens with probability $1-o(1)$, mainly because we have a probability $o(1)$ to create a cycle when pairing $o(\sqrt{n})$ half-edges),

we can apply Proposition 4.1 to bound the difference between $\varphi_{T_d}$ and $\psi_{M_n}$ by $\log^{-1} n$, ensuring that $T_x \subseteq C_x^{M_n,h}$, the connected component of $x$ in $E_{\psi_{\tilde{G}_n}}^{\ge h}$.

**The exploration.** Fix $x \in V_n$. Let

$$b_n := (d-1)^{-a_n} \log^{-6} n, \qquad (5.1)$$

where we recall the definition of $a_n$ from (4.1). Let $(\xi_y)_{y \in T_d}$ be a family of independent variables, each of law $N(0, 1)$, independent of the pairing of the half-edges in $M_n$. Define the GFF $\varphi_{T_d}$ as in Proposition 3.1.

At every step of the exploration, $T_x$ will be a tree rooted at $x$, $\mathcal{T}_x$ its respective counterpart in $T_d$, rooted at $\circ$, and $\Phi$ an isomorphism from $T_x$ to $\mathcal{T}_x$. At step $k$, we will reveal the $k$-th generation of $T_x$ and $\mathcal{T}_x$.

Precisely, the **exploration from** $x$ consists of the following steps:

* at step 0, $T_x = \{x\}$ and $\mathcal{T}_x = \{\circ\}$. Reveal the pairings of the half-edges of $B_{M_n}(x, a_n)$. Stop the exploration if $\mathrm{tx}(B_{M_n}(x, a_n)) > 0$ or if $\varphi_{T_d}(\circ) < h + \log^{-1} n$.

* at step $k \ge 1$, reveal the edges of $B_{M_n}(T_x, a_n + 1)$ that were not known at step $k-1$. Let $O_{k-1}$ be the set of the vertices of $T_x$ of height $k-1$. Stop the exploration if at least one of the following conditions holds:

C1 a cycle appears in $B_{M_n}(T_x, a_n + 1)$,

C2 $|O_{k-1}| \ge n^{1/2}b_n$,

C3 $O_{k-1} = \emptyset$ (i.e. no vertex was added to $T_x$ during the $(k-1)$-th step),

C4 $k > \log_{\lambda_h} n$.

Else, denote $x_{k,1}, x_{k,2}, \dots, x_{k,m}$ the neighbours (in $M_n$) of vertices of $O_{k-1}$ that are not in $O_{k-2}$, for some $m \in \mathbb{N}$ (note that $m = (d-1)|O_{k-1}|$, each vertex of $O_{k-1}$ having one neighbour in $O_{k-2}$, its parent, and $d-1$ other neighbours at distance $k$ of $\circ$). Add to $T_x$ the vertices $x_{k,i}$ of $O_{k-1}$ such that $\varphi_{T_d}(\Phi(x_{k,i})) \ge h + \log^{-1} n$. Add to $\mathcal{T}_x$ the corresponding vertices $\Phi(x_{k,i})$.

If the exploration is stopped at some step $k$, at which only C2 is met, say that it is **successful**. In this case, by Proposition 2.4, we can sample $\psi_{M_n}$ as follows: we reveal the remaining pairings of half-edges in $M_n$. We set $\psi_{M_n}(x) = \xi_\circ G_{M_n}(x, x)$. For all $k, i \ge 1$, if $A_{k,i} = \{x\} \cup \{x_{\ell,j} | (\ell, j) < (k, i)\}$ where $<$ is the lexicographical order on $\mathbb{N}^2$, let

$$\psi_{M_n}(x_{k,i}) = \mathbb{E}^{M_n}[\psi_{M_n}(x_{k,i})|\sigma(A_{k,i})] + \xi_{k,i} \sqrt{\mathrm{Var}(\psi_{M_n}(x_{k,i})|\sigma(A_{k,i}))}. \qquad (5.2)$$

Note that the conditional expectation and variance of the RHS are $\sigma(A_{k,i})$-measurable random variables, so that (5.2) makes sense, even if $\psi_{M_n}(x_{k,i})$ appears on both sides of the equation.

Let $S(x) := \{\text{the exploration from } x \text{ is successful}\}$. We prove the following:

**Proposition 5.1.**

$$\mathbb{P}_{ann}(S(x) \cap \{T_x \subseteq C_x^{M_n,h}\}) \underset{n \to +\infty}{\longrightarrow} \eta(h). \qquad (5.3)$$

**Remark 5.2 (Exploration size).** Denote $R_x$ the set of vertices **seen** during the exploration (i.e. such at least one of their half-edges has been paired). Note that for $n$ large enough, for every $x \in V_n$, by C2, C4 and (5.1), $T_x$ contains less than
<figure><img src="image_5.png" /><figcaption>Figure 2: Illustration of the exploration with $k = 3$, $a_n = 2$, $h = 0.3$ and $n = 148$ (so that $\log^{-1} n \simeq 0.2$). Thick vertices and edges represent $T_x$ after two steps. Red vertices have not been included in $T_x$ because $\varphi_{T_d}$ at their counterparts in $T_d$ is below $h + \log^{-1} n$. Any number near a vertex $v$ is $\varphi_{T_d}(\Phi(v))$.</figcaption></figure>

$$n^{1/2}(d-1)^{-a_n} \log^{-6} n \log_{\lambda_h} n \le n^{1/2}(d-1)^{-a_n} \log^{-4} n$$

vertices, so that

$$|R_x| \le n^{1/2}(d-1)^{-a_n} \log^{-4} n \times (1 + (d-1) + \dots + (d-1)^{a_n+1}) \le n^{1/2} \log^{-3} n.$$

In order to prove Proposition 5.1, we first show that $C_o^{h+\log^{-1} n}$ either has an exponential growth at rate $> \sqrt{\lambda_h}$ with probability close to $\eta(h)$, or dies out before reaching height $\log_{\lambda_h} n$ with probability close to $1 - \eta(h)$. Although the proof is slightly technical, it relies merely on Proposition 3.3 and on the continuity of the maps $h' \mapsto \lambda_{h'}$ and $h' \mapsto \eta(h')$. It can be skipped at first reading. Recall the definition of $\mathcal{Z}_k^h$ at the beginning of Section 3.2.

**Lemma 5.3.** Let $\mathcal{F}_k^{(n)} := \{n^{1/2}b_n \le |\mathcal{Z}_k^{h+\log^{-1} n}| \le dn^{1/2}b_n\}$ and $\mathcal{F}'_k^{(n)} := \{\mathcal{Z}_{k-1}^{h+\log^{-1} n} = \emptyset\}$ for $k \ge 1$. Let $k_0 := \inf\{k \ge 1, \mathcal{F}_k^{(n)} \text{ or } \mathcal{F}'_k^{(n)} \text{ happens}\}$, $\mathcal{F}^{*(n)} := \{k_0 \le \log_{\lambda_h} n\} \cap \mathcal{F}_{k_0}^{(n)}$ and $\mathcal{F}'^{*(n)} := \{k_0 \le \log_{\lambda_h} n\} \cap \mathcal{F}_{k_0}^{(n)}$. Then, as $n \to +\infty$:

$$P_{ann}(\mathcal{F}^{*(n)}) \to \eta(h) \quad \text{and} \quad P_{ann}(\mathcal{F}'^{*(n)}) \to 1 - \eta(h). \qquad (5.4)$$

*Proof.* Remark first that by construction, $P_{ann}$ acts like $P_{T_d}$ on events that only depend on $\varphi_{T_d}$. Note that for every $n \ge 1$, $\mathcal{F}'^{*(n)} \cap \mathcal{F}^{*(n)} = \emptyset$, implying $P_{ann}(\mathcal{F}'^{*(n)}) + P_{ann}(\mathcal{F}^{*(n)}) \le 1$. Hence it is enough to prove that

$$\liminf_{n \to +\infty} P_{ann}(\mathcal{F}^{*(n)}) \ge \eta(h) \qquad (5.5)$$

and

$$\liminf_{n \to +\infty} P_{ann}(\mathcal{F}'^{*(n)}) \ge 1 - \eta(h) \qquad (5.6)$$

Let $\varepsilon \in (0, \eta(h))$. Let $\delta > 0$ be such that $|\eta(h+\delta) - \eta(h)| \le \varepsilon$ and $\log \lambda_{h+\delta} > (9 \log \lambda_h)/10$. The map $h' \to \eta(h')$ is continuous on $\mathbb{R} \setminus \{h_*\}$ by Theorem 3.1 of [3] and the map $h' \to \lambda_{h'}$
is an homeomorphism from $(-\infty, h_*)$ to $(1, d-1)$ by Proposition 3.3, hence such $\delta$ exists.
It is clear that

$$
\begin{align*}
\liminf_{n \to +\infty} \mathbb{P}_{ann} \left( \exists k \le \log_{\lambda_h} n, |\mathcal{Z}_k^{h+\log^{-1} n}| > n^{1/2} b_n \right) & \\
&\ge \liminf_{n \to +\infty} \mathbb{P}_{ann} \left( \exists k \le \log_{\lambda_h} n, |\mathcal{Z}_k^{h+\delta}| > n^{1/2} b_n \right) \\
&\ge \liminf_{n \to +\infty} \mathbb{P}_{ann} \left( |\mathcal{Z}_{[\log_{\lambda_h} n]}^{h+\delta}| > n^{1/2} b_n \right) \\
&\ge \liminf_{n \to +\infty} \mathbb{P}_{ann} \left( |\mathcal{Z}_{[\log_{\lambda_h} n]}^{h+\delta}| > n^{9/10} / \log^2_{\lambda_h} n \right),
\end{align*}
$$

hence by the first equation of Proposition 3.3 applied to $h + \delta$,

$$
\liminf_{n \to +\infty} \mathbb{P}_{ann} \left( \exists k \le \log_{\lambda_h} n, |\mathcal{Z}_k^{h+\log^{-1} n}| > n^{1/2} b_n \right) \ge \eta(h+\delta) \ge \eta(h) - \varepsilon. \quad (5.7)
$$

Since each vertex of $T_d$ has at most $d$ children, we have $|\mathcal{Z}_k^{h+\log^{-1} n}| \le d|\mathcal{Z}_{k-1}^{h+\log^{-1} n}|$
deterministically for all $k \ge 1$. Hence, letting $k' := \inf\{k \ge 0, |\mathcal{Z}_k^{h+\log^{-1} n}| \ge n^{1/2} b_n\}$
when this set is non-empty, $\mathcal{F}_{k'}^{(n)}$ holds, so that $\{\exists k \le \log_{\lambda_h} n, |\mathcal{Z}_k^{h+\log^{-1} n}| > n^{1/2} b_n\} \subseteq$
$\cup_{k \le \log_{\lambda_h} n} \mathcal{F}_k^{(n)}$. Thus

$$
\liminf_{n \to +\infty} \mathbb{P}_{ann}(\mathcal{F}^{*(n)}) \geq \liminf_{n \to +\infty} \mathbb{P}_{ann} \left( \bigcup_{k \leq \log_{\lambda_h} n} \mathcal{F}_k^{(n)} \right) \geq \eta(h) - \varepsilon
$$

by (5.7), and this shows (5.5).

For $n \ge e^{1/\delta}$, $C_{\circ}^{h+\delta} \subseteq C_{\circ}^{h+\log^{-1} n} \subseteq C_{\circ}^{h}$. Note that for $n \ge 1$,

$$
\begin{align*}
\mathbb{P}_{ann}(\mathcal{F}^{*(n)}) & \\
&\ge \mathbb{P}_{ann}\left(\mathcal{Z}_{[\log_{\lambda_h} n]_{-1}}^{h+\log^{-1} n} = \emptyset\right) - \mathbb{P}_{ann}\left(\{\mathcal{Z}_{[\log_{\lambda_h} n]_{-1}}^{h+\log^{-1} n} = \emptyset\} \cap \{\exists k \ge 1, |\mathcal{Z}_k^{h+\log^{-1} n}| \ge n^{1/2} b_n\}\right) \\
&\ge \mathbb{P}_{ann}\left(\mathcal{Z}_{[\log_{\lambda_h} n]_{-1}}^{h} = \emptyset\right) - \mathbb{P}_{ann}\left(\{|\mathcal{C}_{\circ}^{h+\log^{-1} n}| < +\infty\} \cap \{\exists k \ge 1, |\mathcal{Z}_k^{h+\log^{-1} n}| \ge n^{1/2} b_n\}\right) \\
&\ge \mathbb{P}_{ann}\left(\mathcal{Z}_{[\log_{\lambda_h} n]_{-1}}^{h} = \emptyset\right) - \mathbb{P}_{ann}\left(|\mathcal{C}_{\circ}^{h+\log^{-1} n}| < +\infty \mid \exists k \ge 1, |\mathcal{Z}_k^{h+\log^{-1} n}| \ge n^{1/2} b_n\right). \end{align*}
$$

The first term of the RHS converges to $1 - \eta(h)$ as $n \to +\infty$. For any $k \ge 1$ and for
any $v \in B_{T_d}(\circ, k)$, denoting $T_v$ the possible subtree from $v$ in $C_\circ^{h+\log^{-1} n}$ (if $v \in \mathcal{Z}_k^{h+\log^{-1} n}$)
and $C_\circ(h, \delta)$ the connected component of $\circ$ in $(\circ \cup E_{\varphi_{T_d}}^{\ge h+\delta}) \cap T_d^+$,

$$
\mathbb{P}_{ann}(|T_v| < +\infty | v \in \mathcal{Z}_k^{h+\log^{-1} n}) \le \mathbb{P}_h^{T_d}(|C_\circ(h, \delta)| < +\infty)
$$

by Lemma 3.2, independently of the other vertices of $\mathcal{Z}_k^{h+\log^{-1} n}$. Thus,

$$
\mathbb{P}_{ann}(|\mathcal{C}_{\circ}^{h}| < +\infty | \exists k \ge 1, |\mathcal{Z}_{k}^{h}| \ge n^{1/2} b_n) \le \mathbb{P}_{h}^{T_d}(|\mathcal{C}_{\circ}(h, \delta)| < +\infty)^{n^{1/2} b_n}.
$$

By a straightforward adaptation of Remark A.3, we have $\mathbb{P}_h^{T_d}(|\mathcal{C}_o(h, \delta)| < +\infty) < 1$, and (5.6) follows. $\square$

Proof of Proposition 5.1. We first establish that C1 happens with $\mathbb{P}_{ann}$-probability $o(1)$.
Then, if there is no cycle in $B_{M_n}(T_x, a_n)$, we can apply Proposition 4.1, to bound the
difference between $\varphi_{T_d}$ and $\psi_{M_n}$.

By Remark 5.2, at most $dn^{1/2} \log^{-3} n$ matchings of half-edges are performed during
the exploration. By (2.7) with $k = m_0 = 1$, $m_E = 0$ and $m \le dn^{1/2} \log^{-3} n$, the probability
to create at least one cycle during these matchings is less than $\log^{-1} n$ for large enough
$n$. Therefore,

$$
\mathbb{P}_{ann}(\text{C1 happens}) \to 0. \qquad (5.8)
$$
Note that if C1 does not happen, then on $\mathcal{F}^{*(n)}$, (resp. $\mathcal{F}^{\prime *}(n)$), C3 (resp. C2) is satisfied, but not C4. Moreover, on $\mathcal{F}^{*(n)}$, (resp. $\mathcal{F}^{\prime *}(n)$), C2 (resp. C3) does not hold, so that we have $\mathbb{P}_{ann}(S(x)) \ge \mathbb{P}_{ann}(\mathcal{F}^{*(n)}) - \mathbb{P}_{ann}(\text{C1 happens})$. Since $\mathcal{F}^{*(n)} \cap \mathcal{F}^{\prime *}(n) = \emptyset$, we get that

$$ \mathbb{P}_{ann}(S(x)) \le \mathbb{P}_{ann}(\mathcal{F}^{*(n)}) + \mathbb{P}_{ann}(\text{C1 happens}) \le 1 - \mathbb{P}_{ann}(\mathcal{F}^{\prime *}(n)) + \mathbb{P}_{ann}(\text{C1 happens}). $$

Thus, by (5.4) and (5.8),

$$ \mathbb{P}_{ann}(S(x)) \to \eta(h). \qquad (5.9) $$

Suppose now that the exploration is over and that $S(x)$ holds. We compare $\psi_{\mathcal{M}_n}$ with $\varphi_{\mathcal{T}_d}$. Note that by C4, $T_x$ has a maximal height $\log_{\lambda_h} n$ so that by the triangle inequality,

$$ \{T_x \not\subseteq \mathcal{C}_x^{\mathcal{M}_n, h}\} \subseteq \{\exists y \in T_x, |\psi_{\mathcal{M}_n}(y) - \varphi_{\mathcal{T}_d}(\Phi(y))| \ge \log^{-1} n\} \subseteq \cup_{y \in T_x} \mathcal{E}(y), $$

where $\mathcal{E}(x) := \{|\psi_{\mathcal{M}_n}(x) - \varphi_{\mathcal{T}_d}(\Phi(x))| \ge \log^{-3} n\}$ and

$$ \mathcal{E}(y) := \{|\psi_{\mathcal{M}_n}(y) - \varphi_{\mathcal{T}_d}(\Phi(y))| \ge |\psi_{\mathcal{M}_n}(\bar{y}) - \varphi_{\mathcal{T}_d}(\bar{\Phi}(y))| + 2 \log^{-3} n\} \text{ for } y \ne x. $$

Suppose that $\mathcal{M}_n$ is a good graph. For $x_{k,i} \in T_x \setminus \{x\}$, we can apply Proposition 4.1 on the event $\mathcal{E}_{k,i}^{(n)} := \{\max_{y' \in A_{k,i}} |\psi_{\mathcal{M}_n}(y')| < \log^{2/3} n\}$, (since $\mathrm{tx}(B_{\mathcal{M}_n}(A_{k,i}, a_n)) = \mathrm{tx}(A_{k,i})$ by C1 and since $|A_{k,i}| \le n^{1/2}$ by Remark 5.2). Writing $y = x_{k,i}$ and $\xi = \xi_{\Phi(x_{k,i})}$, we get for $n$ large enough:

$$ |\psi_{\mathcal{M}_n}(y) - \varphi_{\mathcal{T}_d}(\Phi(y))| \le \left| \frac{\psi_{\mathcal{M}_n}(\bar{y}) - \varphi_{\mathcal{T}_d}(\overline{\Phi(y)})}{d-1} \right| + \log^{-3} n + \left| \left( \sqrt{\mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(y)|\sigma(A_{k,i}))} - \sqrt{\frac{d-1}{d}} \right) \xi \right| $$

and

$$ \left| \sqrt{\mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(y)|\sigma(A_{k,i}))} - \sqrt{\frac{d-1}{d}} \right| \le \left| \sqrt{\frac{d-1}{d} - \log^{-4} n} - \sqrt{\frac{d-1}{d}} \right| \\ \le \frac{11}{10} \sqrt{\frac{d-1}{d}} \frac{d}{2(d-1)} \log^{-4} n \\ \le \log^{-4} n. $$

Let $\mathcal{E}'(y) := \mathcal{E}(y) \cap \mathcal{E}_{k,i}^{(n)}$. We have

$$ \mathbb{P}^{\mathcal{M}_n}(\mathcal{E}'(y)) \le \mathbb{P}(|\xi| \log^{-4} n \ge \log^{-3} n) \le n^{-3} \qquad (5.10) $$

by the exponential Markov inequality used as in the proof of Lemma 2.5. Moreover, by (2.1), if $\kappa$ is large enough, we obtain in the same manner:

$$ \mathbb{P}^{\mathcal{M}_n}(\mathcal{E}(x)) \le \mathbb{P}^{\mathcal{M}_n}(|\xi_0| \log^{-4} n \ge \log^{-3} n) \le n^{-3}. \qquad (5.11) $$

By Remark 5.2, we have $|T_x| \le n^{1/2}$. By (5.10), (5.11) and a union bound on $y \in T_x$, we have that $\mathbb{P}^{\mathcal{M}_n}(\cup_{y \in T_x} \mathcal{E}'(y)) \le n^{-5/2}$ with $\mathcal{E}'(x) := \mathcal{E}(x)$. And $\mathbb{P}^{\mathcal{M}_n}(\cup_{(k,i):x_{k,i} \in T_x} \mathcal{E}_{k,i}^{(n)}) \le n^{-2}$ for large enough $n$, by Lemma 2.5.

Thus for $n$ large enough, if $\mathcal{M}_n$ is a good graph,

$$ \mathbb{P}^{\mathcal{M}_n}(T_x \not\subseteq \mathcal{C}_x^{\mathcal{M}_n, h}) \le \mathbb{P}^{\mathcal{M}_n}(\cup_{y \in T_x} \mathcal{E}(y)) \le n^{-5/2} + n^{-2} \le n^{-1}, $$

so that by Proposition 2.1 and (5.9):

$$ \mathbb{P}_{ann}(S(x) \cap \{T_x \subseteq \mathcal{C}_x^{\mathcal{M}_n, h}\}) \to \eta(h). \qquad \square $$
## 5.2 Aborted exploration

For $x \in V_n$, the **lower exploration** is the exploration of Section 5.1, modified by replacing $h + \log^{-1} n$ by $h - \log^{-1} n$, so that we compare $T_x$ and $C_o^{h-\log^{-1} n}$. If it is stopped at some step $k$ at which only C3 is met, say that it is **aborted**. Write $\mathcal{A}(x) := \{\text{the lower exploration from } x \text{ is aborted}\} \cap \{C_x^{M_n,h} \subseteq T_x\}$.

**Proposition 5.4.**

$$ \mathbb{P}_{ann}(\mathcal{A}(x)) \underset{n \to +\infty}{\longrightarrow} 1 - \eta(h). \qquad (5.12) $$

The proof follows from a direct adaptation of Lemma 5.3 and Proposition 5.1. Note in particular that $\mathbb{P}_{ann}(\mathcal{C}(x)) = o(1)$, and that $\mathbb{P}_{ann}(\mathcal{A}(x)) = \mathbb{P}_{ann}(Z_{k_0-1}^{h-\log^{-1} n} = \emptyset) + o(1) = 1 - \eta(h) + o(1)$.

# 6 Existence of a giant component

In Section 6.1, we prove that two vertices $x, y \in V_n$ are in the same connected component of $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ with $\mathbb{P}_{ann}$-probability $\underset{n \to +\infty}{\longrightarrow} \eta(h)^2$ (Proposition 6.2). Then in Section 6.2, we use a second moment argument to get concentration and to show (1.2).

## 6.1 Connecting two successful explorations

Let us describe our strategy to establish Proposition 6.2. We perform explorations as in Section 5.1 from $x$ and $y$. If they are both successful and do not meet (which happens with probability $\simeq \eta(h)^2$), we develop disjoint balls, denoted “joining balls”, from $\partial T_x$ to $\partial T_y$ (Section 6.1.1). Each of them is rooted at a vertex of $\partial T_x$, hits $\partial T_y$ at exactly one vertex, and has a “security radius” of depth $a_n$ around its path from $\partial T_x$ to $\partial T_y$ (see Figure 3). The construction of the joining balls only depends on the structure of $M_n$, and not on the values of $\psi_{M_n}$. Then, we realize $\psi_{M_n}$ on $T_x, T_y$ and those balls (Section 6.1.2). If they are all disjoint and tree-like, once we have revealed $\psi_{M_n}$ on $T_x$ and $T_y$, this security radius allows us to apply Proposition 4.1 to approximate $\psi_{M_n}$ on the paths from $\partial T_x$ to $\partial T_y$ by $\varphi_{T_d}$.

Let us explain with a back-of-the-envelope computation how the joining balls allow to connect $T_x$ and $T_y$ in $E_{\psi_{\mathcal{G}_n}}^{\ge h}$. Since $|T_y| \simeq n^{1/2}b_n$ by C2, the probability that for a given $z \in \partial T_x$, exactly one of the vertices at distance $\lfloor \gamma \log_{d-1} \log n \rfloor$ (and no vertex at distance $< \lfloor \gamma \log_{d-1} \log n \rfloor$) from $z$ is in $\partial T_y$ is

$$ \simeq \mathbb{P}(\text{Bin}((d-1)^{\gamma \log_{d-1} \log n}, \frac{n^{1/2}b_n}{dn}) = 1) \simeq \log^\gamma n \times n^{-1/2}b_n. $$

And there are $\simeq n^{1/2}b_n$ vertices in $\partial T_x$, hence we can expect that the number of joining balls is at least $\simeq n^{1/2}b_n \times \log^\gamma n \times n^{-1/2}b_n = b_n^2 \log^\gamma n$, provided that we can control some undesirable events (such as an intersection between balls, or a cycle in a ball). This is the purpose of Lemma 6.1.

Moreover, we know that for large $r \in \mathbb{N}$ and $v \in \partial B_{T_d}(\circ, r)$, $\mathbb{P}^{T_d}(v \in C_o^h)$ is of order $(\lambda_h/(d-1))^r$, by Proposition 3.6. Taking $r = \gamma \log_{d-1} \log n$, the probability that $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ percolates from $\partial T_x$ to $\partial T_y$ through a given joining ball is $\simeq \log^{\gamma(\log_{d-1} \lambda_h - 1)} n$, if we can approximate $\psi_{M_n}$ by $\varphi_{T_d}$. For $\gamma$ large enough w.r.t $\kappa$ (recall (5.1) and (4.1), and recall that $\lambda_h > 1$),

$$ b_n^2 \log^\gamma n \times \log^{\gamma(\log_{d-1} \lambda_h - 1)} n \ge \log^{-2\kappa-13} n \times \log^{\gamma \log_{d-1} \lambda_h} n \gg 1, $$

so that with high probability, $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ percolates through at least one joining ball from $\partial T_x$ to $\partial T_y$.
### 6.1.1 The joint exploration

For $x, y \in V_n$, write $x \stackrel{h}{\leftrightarrow} y$ if $y \in C_x^{M_n,h}$. Let $(\xi_{z,v})_{z \in \{x,y\}, v \in T_d}$ be an array of i.i.d. standard normal variables independent from everything else. Define the **joint exploration from** $x$ **and** $y$ as the exploration from $x$ (with the $(\xi_{x,v})$'s), then the exploration from $y$ (with the $(\xi_{y,v})$'s), as in Section 5.1, with the additional condition

C5 the exploration is stopped as soon as $R_x \cap R_y \neq \emptyset$,

where $R_x$ (resp. $R_y$) is the set of vertices seen during the exploration from $x$ (resp. from $y$), as defined in Remark 5.2. Note that the families $(\xi_{x,v})_{v \in T_d}$ and $(\xi_{y,v})_{v \in T_d}$ generate two independent copies of $\phi_{T_d}$.

If both explorations are successful and C5 does not happen (denote $S(x, y)$ this event), we add the following steps to the joint exploration. Let $\gamma > 0$ and

$$a'_{n} := \lfloor \gamma \log_{d-1} \log n \rfloor. \qquad (6.1)$$

Denote $z_1, \dots, z_{|\partial T_x|}$ the vertices of $\partial T_x$. For $j = 1, 2, \dots, |\partial T_x|$ successively, build $B^*(z_j, a'_n)$ the subgraph of $M_n$ obtained as follows (see Figure 3 for an illustration). Write

$$B_j^* := \cup_{j' < j} B^*(z_{j'}, a'_n) \text{ and } Q_j := R_x \cup R_y \cup B_j^*, \qquad (6.2)$$

so that $Q_j$ is the set of vertices seen in the exploration before the construction of $B^*(z_j, a'_n)$.

Let initially $B^*(z_j, a'_n)$ be the subtree from $z_j$ of height $a_n$ in the tree $B_{M_n}(T_x, a_n)$ (in blue in Figure 3). For $k \le a'_n$, write $B^*(z_j, k) := B^*(z_j, a'_n) \cap B_{M_n}(z_j, k)$. If $B^*(z_j, a_n) \cap B_j^* \neq \emptyset$, say that $j$ is **spoiled**, and the construction of $B^*(z_j, a'_n)$ stops.

Else, for $k = a_n, a_n + 1, \dots, a'_n - 2a_n - 2$ successively, while $\mathrm{tx}(B^*(z_j, k) \cup Q_j) = \mathrm{tx}(Q_j)$ (i.e. no cycle has been discovered) and $B^*(z_j, k) \cap B_{M_n}(T_y, a_n) = \emptyset$, add to $B^*(z_j, a'_n)$ the neighbours of $B^*(z_j, k)$ and the corresponding edges (in red in Figure 3). If for some $k \in \{a_n, \dots, a'_n - 2a_n - 2\}$, $\mathrm{tx}(B^*(z_j, k) \cup Q_j) > \mathrm{tx}(Q_j)$ (i.e. at least one cycle is discovered) or $B^*(z_j, k) \cap B_{M_n}(T_y, a_n) \neq \emptyset$, the construction of $B^*(z_j, a'_n)$ stops.

If the construction has not been stopped for some $k < a'_n - 2a_n - 1$, add the neighbours of $B^*(z_j, a'_n - 2a_n - 1)$ to $B^*(z_j, a'_n)$ (also in red in Figure 3). If

$$|B^*(z_j, a'_n - 2a_n) \cap B_{M_n}(T_y, a_n)| \neq 1,$$

the construction of $B^*(z_j, a'_n)$ stops.

Else, let $v_j(0)$ be the unique vertex of $B^*(z_j, a'_n - 2a_n) \cap B_{M_n}(T_y, a_n)$. If

$$\mathrm{tx}((B^*(z_j, a'_n - 2a_n) \cup Q_j) \setminus \{v_j(0)\}) > \mathrm{tx}(Q_j),$$

the construction of $B^*(z_j, a'_n)$ stops.

Else, for $k = a'_n - 2a_n, \dots, a'_n - 1$ successively, while $\mathrm{tx}(B^*(z_j, k) \cup Q_j) = \mathrm{tx}(B^*(z_j, a'_n - 2a_n) \cup Q_j)$, add the neighbours of $B^*(z_j, k)$ to $B^*(z_j, a'_n)$ (in green in Figure 3). Then, the construction of $B^*(z_j, a'_n)$ is completed. In this case only, and if

$$\mathrm{tx}(B^*(z_j, a'_n) \cup Q_j) = \mathrm{tx}(B^*(z_j, a'_n - 2a_n) \cup Q_j),$$

say that $B^*(z_j, a'_n)$ is a **joining ball**. In other words, we obtain a joining ball if, revealing the offspring up to generation $a'_n$ of $z_j$, the $(a'_n - 2a_n)$ offspring of $z_j$ intersects $\partial T_y$ at a unique vertex $v_j(0)$, and no cycle is discovered in the whole construction (except when $B^*(z_j, a'_n)$ reaches $\partial B_{M_n}(T_y, a_n)$ at $v_j(0)$, if $T_x$ and $T_y$ were already connected in $Q_j$ by $B^*(z_{j'}, a'_n)$ for some $j' < j$).

Write $J := \{j \le |\partial T_x|, B^*(z_j, a'_n)$ is a joining ball$\}$. Recall the definition of $S(x, y)$ above (6.1). Let $S'(x, y) := S(x, y) \cap \{|J| \ge \log^{\gamma-3\kappa-18} n\}$.
<figure><img src="image_6.png" /><figcaption>Figure 3: Illustration of a joining ball $B^*(z_j, a'_n)$. Here $a_n = 2$ and $a'_n = 9$. Dashed lines represent subtrees that have not been fully pictured. The blue tree has total height $a_n$, the red trees $a'_n - 3a_n$, and the green trees $2a_n$.</figcaption></figure>

**Lemma 6.1.** Fix $\gamma > 3\kappa + 18$.

$$ \mathbb{P}_{ann}(S'(x, y)) \underset{n \to +\infty}{\longrightarrow} \eta(h)^2. $$

*Proof.* Denote $\mathcal{F}^{*(n)}(x)$ (resp. $\mathcal{F}^{*(n)}(y)$) the event $\mathcal{F}^{*(n)}$ for $x$ (resp. $y$). Remark that the realization of $\mathcal{F}^{*(n)}(x)$ (resp. $\mathcal{F}^{*(n)}(y)$) only depends on the version of $\varphi_{\mathbb{T}_d}$ defined by $(\xi_{x,v})_{v \in \mathbb{T}_d}$ (resp. by $(\xi_{y,v})_{v \in \mathbb{T}_d}$) and not on the pairings of $\mathcal{M}_n$. Hence, $\mathcal{F}^{*(n)}(x)$ and $\mathcal{F}^{*(n)}(y)$ are independent. As in the proof of Lemma 5.3, we get that

$$ \mathbb{P}_{ann}(\mathcal{F}^{*(n)}(x) \cap \mathcal{F}^{*(n)}(y)) = \mathbb{P}_{ann}(\mathcal{F}^{*(n)}(x))\mathbb{P}_{ann}(\mathcal{F}^{*(n)}(y)) \to \eta(h)^2 $$

and $\mathbb{P}_{ann}(\mathcal{F}^{l*(n)}(x) \cup \mathcal{F}^{l*(n)}(y)) \to 1 - \eta(h)^2$.

Moreover, $\mathbb{P}_{ann}(\text{C1 or C5 happens}) \to 0$. Indeed, by Remark 5.2, less than $2dn^{1/2} \log^{-3} n$ half-edges are revealed during the explorations from $x$ and $y$, which allows to control C5 as we did for C1 in (5.8). Thus,

$$ \limsup_{n \to +\infty} |\mathbb{P}_{ann}(S'(x, y)) - \eta(h)^2| \le \limsup_{n \to +\infty} \mathbb{P}_{ann}(S(x, y) \cap \{|J| < \log^{\gamma-3\kappa-18} n\}) $$

and it remains to prove that

$$ \limsup_{n \to +\infty} \mathbb{P}_{ann}(S(x, y) \cap \{|J| < \log^{\gamma-3\kappa-18} n\}) = 0. \quad (6.3) $$
We proceed in two steps: in step 1, we control the number of spoiled vertices, and the number of vertices of $\partial B_{M_n}(T_y, a_n)$ that are hit when building the $B^*(z_j, a'_n)$'s (if a large proportion of those vertices are in $Q_j$, then it significantly affects the probability that $B^*(z_j, a'_n)$ is a joining ball). In step 2, we estimate the probability that for a given $j$, $B^*(z_j, a'_n)$ is a joining ball, provided that the bounds of step 1 hold. This gives a binomial lower bound for $|J|$.

**Step 1.** By Remark 5.2 and (4.1), $|\partial B_{M_n}(T_x, a_n)| + |\partial B_{M_n}(T_y, a_n)| \le 2n^{1/2} \log^{-1} n$. Note also that for every $j \le |\partial T_x|$, $B^*(z_j, a'_n)$ contains less than $(d-1)^{a'_n} \le \log^\gamma n$ half-edges. Hence:

at every moment of the exploration, less than $n^{1/2} \log^\gamma n$ half-edges have been seen. (6.4)

Let

$$B^* := \cup_{j \le |\partial T_x|} B^*(z_j, a'_n). \quad (6.5)$$

To reveal the edges of $B^*$, one proceeds to at most $n^{1/2} \log^\gamma n$ pairings of half-edges by (6.4). Any pairing that results in an edge $e$ between some $B^*(z_j, k)$ and $B_{M_n}(T_y, a_n)$ then leads to at most

$$1 + (d-1) + \dots + (d-1)^{2a_n} \le 3(d-1)^{2a_n} \le \log^{2\kappa+1} n \le \log^{\gamma-1} n$$

vertices of $B^*(z_j, a'_n) \cap B_{M_n}(T_y, a_n)$, since the construction of $B^*(z_j, a'_n)$ stops if such an edge happens at distance less than $a'_n - 2a_n$ of $z_j$ (and recall that we choose $\gamma > 3\kappa + 18 > 2\kappa + 2$).

Thus, by (2.8) with $k = \lfloor \log^{2\gamma+1} n \rfloor$, $m < n^{1/2} \log^\gamma n$ and $m_1 + m_0 + m_E < n^{1/2} \log^\gamma n$ (due to (6.4)), for $n$ large enough:

$$\mathbb{P}_{ann}(S(x, y) \cap \{|B_{M_n}(T_y, a_n) \cap B^*| \ge \log^{3\gamma} n\}) \le 0.99^{\log^2 n} \le n^{-3}. \quad (6.6)$$

Let $N$ be the total number of spoiled vertices. By (2.8) with the same parameters,

$$\mathbb{P}_{ann}(S(x, y) \cap \{N \ge \log^{3\gamma} n\}) \le n^{-3}. \quad (6.7)$$

**Step 2.** Recall the definition of $B_j^*$ from (6.2). For $j \le m$, denote

$$S_j := S(x, y) \cap \{|B_{M_n}(T_y, a_n) \cap B_j^*| \le \log^{3\gamma} n\} \cap \{z_j \text{ is not spoiled}\}, \quad (6.8)$$

and let $\mathcal{F}_j$ be the sigma-algebra of the whole exploration until $B_{j-1}^*$ has been constructed. Suppose that for every $j \ge 1$ and every $\mathcal{F}_j$-measurable event $\mathcal{E}_j \subseteq S_j$,

$$\mathbb{P}_{ann}(B^*(z_j, a'_n) \text{ is a joining ball } |\mathcal{E}_j) \ge n^{-1/2} \log^{\gamma-2\kappa-10} n. \quad (6.9)$$

On $\mathcal{E} := \{|B_{M_n}(T_y, a_n) \cap B^*| < \log^{3\gamma} n\} \cap \{N < \log^{3\gamma} n\}$, the number of $j$'s such that $S_j$ holds is at least

$$|\partial T_x| - \log^{3\gamma} n \ge n^{1/2} \log^{-\kappa-7} n$$

by (C2) and (5.1). Thus, if $Z \sim \text{Bin}(\lfloor n^{1/2} \log^{-\kappa-7} n \rfloor, n^{-1/2} \log^{\gamma-2\kappa-10} n)$,

$$\mathbb{P}_{ann}(S(x, y) \cap \{|J| \le \log^{\gamma-3\kappa-18} n\}) \le \mathbb{P}(Z \le \log^{\gamma-3\kappa-18} n) + \mathbb{P}_{ann}(S(x, y) \cap \mathcal{E}^c).$$

For large enough $n$, $\mathbb{P}_{ann}(S(x, y) \cap \mathcal{E}^c) = o(n^{-2})$ by (6.6) and (6.7). Moreover, one checks easily (using $\gamma > 3\kappa + 18$ and (2.5)) that for $n$ large enough, for all $k \le \log^{\gamma-3\kappa-18} n$:

$$\begin{align*}
\mathbb{P}(Z = k) &\le (\lfloor n^{1/2} \log^{-\kappa-7} n \rfloor)^k (n^{-1/2} \log^{\gamma-2\kappa-10} n)^k (1 - n^{-1/2} \log^{\gamma-2\kappa-10} n)^{\frac{n^{1/2}}{2 \log^{\kappa+7} n}} \\
&\le \exp(k \log(\log^{\gamma-3\kappa-17} n) - (\log^{\gamma-3\kappa-17} n)/2) \\
&\le 1/n.
\end{align*}$$

This yields (6.3). Hence, it only remains to prove (6.9).

Remark that $\mathbb{P}_{ann}(B^*(z_j, a'_n)$ is a joining ball $|\mathcal{E}_j| \ge p_1 p_2 p_3$ where:
• $p_1 := \mathbb{P}_{ann}(\hat{\mathcal{E}}_1|\mathcal{E}_j)$ and $\hat{\mathcal{E}}_1 := \mathcal{E}_j \cap \{\text{no cycle is created and no connection to } Q_j \text{ is made when revealing } B^*(z_j, a'_n - 2a_n - 1)\}$,

• $p_2 := \mathbb{P}_{ann}(\hat{\mathcal{E}}_2|\hat{\mathcal{E}}_1)$ where $\hat{\mathcal{E}}_2 := \hat{\mathcal{E}}_1 \cap \{\text{exactly one edge connects } B^*(z_j, a'_n - 2a_n - 1) \text{ and } D := \partial B_{M_n}(T_y, a_n) \setminus \{B_{M_n}(B_{M_n}(T_y, a_n) \cap B_j^*, 2a_n)\} \cap \{\text{no cycle is created and no connection to } \partial B_{M_n}(T_y, a_n) \cup B_j^* \text{ is made when revealing the other edges of } B^*(z_j, a'_n - 2a_n)\}$,

• $p_3 := \mathbb{P}_{ann}(\hat{\mathcal{E}}_3|\hat{\mathcal{E}}_2)$ where we set $\hat{\mathcal{E}}_3 := \hat{\mathcal{E}}_2 \cap \{\text{no cycle is created and no connection to } \partial B_{M_n}(T_y, a_n) \cup B_j^* \text{ is made when revealing the remaining edges of } B^*(z_j, a'_n)\}$.

This definition of $D$ guarantees that $B^*(z_j, a'_n)$ will not intersect a previously realized joining ball when growing the subtree from $v_j(0)$ in $B_{M_n}(T_y, a_n)$.

(2.7) with $k = 1$, $m_0$, $m \le \log^\gamma n$ and $m_E$, $m_1 \le n^{1/2} \log^\gamma n$ due to (6.4) yields for $n$ large enough:

$$p_i \ge 1 - C(1) \log^\gamma n \frac{\max(n^{1/2} \log^\gamma n, 2 \log^\gamma n)}{n} \ge 1 - n^{-1/3} \quad (6.10)$$

for $i \in \{1, 3\}$. Therefore, $p_1p_3 \ge 1/2$ for $n$ large enough.

On $\hat{\mathcal{E}}_1$, reveal the pairings of the half-edges of $\partial B^*(z_j, a'_n - 2a_n - 1)$ one by one. $\hat{\mathcal{E}}_2$ holds if:

• a given half-edge is matched to a half-edge of $D$, which has probability at least $|D|/dn$, and

• each other half-edge is matched to a half-edge that had not been seen before (by (6.4), for each half-edge this happens with probability at least $1 - \frac{n^{1/2} \log^\gamma n}{dn - n^{1/2} \log^\gamma n} \ge 1 - \frac{n^{1/2} \log^\gamma n}{n}$).

Since $\partial B^*(z_j, a'_n - 2a_n - 1)$ has $(d-1)|\partial B^*(z_j, a'_n - 2a_n - 1)|$ unpaired half-edges,

$$p_2 \ge (d-1)|\partial B^*(z_j, a'_n - 2a_n - 1)| \frac{|D|}{dn} \left(1 - \frac{n^{1/2} \log^\gamma n}{n}\right)^{|\partial B^*(z_j, a'_n - 2a_n - 1)|-1}$$

By (4.1) and (6.1), one checks easily that on $\hat{\mathcal{E}}_1$,

$$\log^{\gamma-2\kappa-1} n \le |\partial B^*(z_j, a'_n - 2a_n - 1)| \le \log^\gamma n,$$

and that on $S_j$ (defined in (6.8)),

$$|D| \ge \frac{|\partial B_{M_n}(T_y, a_n)|}{2} \ge n^{1/2} \log^{-7} n$$

by (5.1) and C2. Hence for $n$ large enough,

$$p_2 \ge (d-1) \log^{\gamma-2\kappa-1} n \frac{n^{1/2} \log^{-7} n}{dn} \left(1 - \frac{n^{1/2} \log^\gamma n}{dn}\right)^{\log^\gamma n} \ge \frac{1}{2} n^{-1/2} \log^{\gamma-2\kappa-9} n.$$

With (6.10), this entails for $n$ large enough (uniformly on $j$ and on $\mathcal{E}_j$):

$$\mathbb{P}_{ann}(B^*(z_j, a'_n) \text{ is a joining ball } |S_j) \ge p_1 p_2 p_3 \ge n^{-1/2} \log^{\gamma-2\kappa-10} n.$$

Then (6.9) follows, so that the proof of the Lemma is complete. □
### 6.1.2 The field $\psi_{M_n}$ on the joint exploration

Suppose that we are on $S'(x, y)$. By Proposition 2.4, we can realize $\psi_{M_n}$ on $T_x$ as in (5.2) with the $(\xi_{x,v})_{v \in T_d}$ (hence we first reveal the remaining edges of $M_n$). Then we can realize it in a similar way on $T_y$ with the $(\xi_{y,v})_{v \in T_d}$, letting recursively

$$ \psi_{M_n}(y_{k,i}) = \mathbb{E}^{M_n}[\psi_{M_n}(y_{k,i})|\sigma(A_{k,i})] + \xi_{y,\Phi(y_{k,i})} \sqrt{\mathrm{Var}(\psi_{M_n}(y_{k,i})|\sigma(A_{k,i}))} $$

where $A_{k,i} := T_x \cup \{y_{\ell,j} | (\ell, j) < (k, i)\}, <$ being the lexicographical order on $\mathbb{N}^2$, and $\Phi$ is the isomorphism between $T_y$ and $\mathfrak{T}_y$.

Recall that $J = \{j \ge 1, B^*(z_j, a'_n)$ is a joining ball$\}$ and that for $j \in J$, we denote $v_j(0)$ the unique vertex of $B^*(z_j, a'_n - 2a_n) \cap B_{M_n}(T_y, a_n)$. Since no cycle is discovered when revealing $B^*(z_j, a'_n) \setminus B^*(z_j, a'_n - 2a_n)$, the intersection of $B^*(z_j, a'_n - a_n)$ and $T_y$ is a unique vertex $v_j(a_n)$, which is in the $a_n$-offspring of $v_j(0)$ in the tree $B^*(z_j, a'_n)$ rooted at $z_j$. Then we realize $\psi_{M_n}$ on $B^*(z_j, a'_n - 2a_n)$ and on the shortest path $P_j$ from $v(0)$ to $v(a_n)$ as in (5.2), via a family of i.i.d. $\mathcal{N}(0, 1)$ random variables $(\xi_{j,k,i})_{k,i \ge 0}$. In the tree $T_j := B^*(z_j, a'_n - 2a_n) \cup P_j$ with root $z_j$, denoting $z_{j,k,i}$ the $i$-th vertex at generation $k$ and

$$ A_{j,k,i} := T_x \cup T_y \cup \{\cup_{j'<j} T'_j\} \cup \{y_{j,k',i'} | (k', i') < (k, i)\} \quad (6.11) $$

the set of vertices where $\psi_{M_n}$ has already been revealed before $z_{j,k,i}$, we let

$$ \psi_{M_n}(z_{j,k,i}) = \mathbb{E}^{M_n}[\psi_{M_n}(z_{j,k,i})|\sigma(A_{j,k,i})] + \xi_{j,k,i} \sqrt{\mathrm{Var}(\psi_{M_n}(y_{j,k,i})|\sigma(A_{j,k,i}))}. \quad (6.12) $$

Write $S^*(x, y) \subseteq S'(x, y)$ the event that there exists $j_0 \ge 1$ and a path from $z_{j_0}$ to $v_{j_0}(a_n)$ such that $\psi_{M_n}(v) \ge h$ for every vertex $v$ of that path. In particular, on $S^*(x, y)$, $x$ and $y$ are in the same connected component of $E_{\psi_{M_n}}^{\ge h}$. Recall the definitions of $\kappa$ (4.1) and $\gamma$ (Lemma 6.1).

**Proposition 6.2.** If $\kappa$ and $\gamma/\kappa$ are large enough, then

$$ P_{ann}(S^*(x, y)) \underset{n \to +\infty}{\longrightarrow} \eta(h)^2. $$

*Proof of Proposition 6.2.* Let $\gamma > 3\kappa + 18$. By Lemma 6.1,

$$ \limsup_{n \to +\infty} P_{ann}(S^*(x, y)) \le \limsup_{n \to +\infty} P_{ann}(S'(x, y)) = \eta(h)^2. $$

Let $\mathcal{E}_n := \{M_n$ is not a good graph$\} \cup \{\max_{z \in V_n} |\psi_{M_n}(z)| \ge \log^{2/3} n\}$. By Proposition 2.1 and Lemma 2.5, $P_{ann}(\mathcal{E}_n) \to 0$. Therefore, it is enough to show that

$$ \limsup_{n \to +\infty} P_{ann}(\mathcal{E}_n^c \cap (S'(x, y) \setminus S^*(x, y))) = 0. $$

By a straightforward adaptation of the reasoning below (5.9),

$$ \limsup_{n \to +\infty} P_{ann}(\mathcal{E}_n^c \cap (S'(x, y) \setminus S''(x, y))) = 0, $$

where $S''(x, y) := S'(x, y) \cap \{\forall z \in T_x \cup T_y, \psi_{M_n}(z) \ge h + (\log^{-1} n)/2\}$. Hence, we are left with proving that

$$ \limsup_{n \to +\infty} P_{ann}(\mathcal{E}_n^c \cap (S''(x, y) \setminus S^*(x, y))) = 0. \quad (6.13) $$

We use again a binomial argument. Fix a realization of $M_n$ which is a good graph (recall that $x$ and $y$ have already been fixed at the beginning of Section 6.1.1). For $j \in J$ in increasing order, generate the GFF on $T_j$ as in (6.12). Denote $E_j$ the event that $z_j$ and $v_j(a_n)$ are in the same connected component of $E_{\psi_{M_n}}^{\ge h} \cap T_j$. Note that on $S''(x, y)$, $T_x \subseteq C_x^{M_n,h}$ and $T_y \subseteq C_y^{M_n,h}$, so that $S''(x, y) \cap (\cup_{j' \in J} E_{j'}) \subseteq S^*(x, y)$.

Note that $A_{j,0,1} = T_x \cup T_y \cup \{\cup_{j'<j} T_{j'}\}$ by (6.11). By Lemma 6.3 below, if $n$ is large enough, then for any good graph $M_n$, for any $j \in J$ and any event $\mathcal{E}'_j \subseteq S''(x, y) \cap \{\max_{z \in A_{j,0,1}} |\psi_{M_n}(z)| \le \log^{2/3} n\}$ that is measurable w.r.t. the exploration until the revealment of $\psi_{M_n}$ on $T_{j-1}$, we have
Anatomy of a Gaussian giant

$$ \mathbb{P}^{\mathcal{M}_n}(E_j | \mathcal{E}'_j) \geq \log^{\gamma(K_8/3-1)} n. $$

Then, letting $Z \sim \text{Bin}(|\log^{\gamma-3\kappa-18} n|, \log^{\gamma(K_8/3-1)} n)$, we have

$$ \mathbb{P}_{ann}(\mathcal{E}_n^c \cap (S''(x, y) \setminus S''(x, y))) \leq \mathbb{P}_{ann}(\mathcal{E}_n) + \mathbb{P}(Z=0). $$

If $\kappa$ and $\gamma/\kappa$ are large enough so that $\gamma - 3\kappa - 18 + \gamma(K_8/3 - 1) = \gamma K_8/3 - 3\kappa - 18 > 0$, we have $\lim_{n \to +\infty} \mathbb{P}(Z=0) = 0$. Since $\mathbb{P}_{ann}(\mathcal{E}_n) \to 0$, this yields (6.13). $\square$

It remains to prove the following. For a good graph $\mathcal{M}_n$, denote $\mathcal{F}_j^{\mathcal{M}_n}$ the sigma-algebra of the exploration until the revealment of $\psi_{\mathcal{M}_n}$ on $T_{j-1}$. In particular, note that $\mathcal{F}_j'$ contains the information on $\sigma(A_{j,0,1})$, and that the structure of $J$ is $\mathcal{F}_j$-measurable.

**Lemma 6.3.** Let $K_8 := \log_{d-1}((1 + \lambda_h)/2)$. For $n$ large enough, we have for any good graph $\mathcal{M}_n$, any $j \in J$ and any $\mathcal{F}_j^{\mathcal{M}_n}$-measurable event

$$ \mathcal{E}'_j \subseteq S''(x, y) \cap \{\max_{z \in A_{j,0,1}} |\psi_{\mathcal{M}_n}(z)| \le \log^{2/3} n\}: $$

$$ \mathbb{P}^{\mathcal{M}_n}(E_j | \mathcal{E}'_j) \geq \log^{\gamma(K_8/3-1)} n. \qquad (6.14) $$

*Proof.* All the inequalities in this proof hold for $n$ large enough, uniformly in the choice of a good graph $\mathcal{M}_n$, $j \in J$ and $\mathcal{E}'_j \in \mathcal{F}^{\mathcal{M}_n}$. We proceed in two steps. First, we prove that

$$ \mathbb{P}^{\mathcal{M}_n}(v_j(0) \in \mathcal{C}_{z_j} | \mathcal{E}'_j) \geq \log^{(\gamma-2\kappa)(K_8/2-1)} n, \qquad (6.15) $$

where $\mathcal{C}_{z_j}$ is the connected component of $z_j$ in $E_{\psi_{\mathcal{M}_n}}^{\ge h} \cap B^*(z_j, a'_n - 2a_n)$. Second, we show that for some constant $K_9 > 0$ (uniquely depending on $d$ and $h$),

$$ \mathbb{P}^{\mathcal{M}_n}(\forall v \in P_j, \psi_{\mathcal{M}_n}(v) \geq h \mid (\mathcal{E}'_j \cap \{v_j(0) \in \mathcal{C}_{z_j}\}) \geq \log^{-K_9\kappa} n. \qquad (6.16) $$

We prove that both hold for $n$ large enough, uniformly in $v \in T_j$ and on $\mathcal{E}'_j$.

If $\gamma/\kappa$ is large enough, (6.15) and (6.16) imply (6.15), since in this case, we have

$$ \mathbb{P}^{\mathcal{M}_n}(E_j | \mathcal{E}'_j) \geq \log^{(\gamma-2\kappa)(K_8/2-1)-K_9\kappa} n \geq \log^{\gamma(K_8/3-1)} n. $$

**Part 1: proof of (6.15).**

Since $|A_{j,k,i}| \le n^{2/3}$ and $\text{tx}(B_{\mathcal{M}_n}(A_{j,k,i}, a_n)) = \text{tx}(A_{j,k,i})$ for all $k, i \ge 0$, we can apply Proposition 4.1 as below (5.9) to bound the difference between $\psi_{\mathcal{M}_n}$ on $\mathcal{C}_{z_j}$ and $\varphi_{T_d}$ on an isomorphic subtree of $T_d$, with the following coupling: $\varphi_{T_d}(\circ) := \psi_{\mathcal{M}_n}(z_j)$, and then $\varphi_{T_d}$ is defined as in Proposition 3.1 via $(\xi_{j,k,i})_{k,i \ge 0}$. Recall that on $S''(x, y)$, we have that $\psi_{\mathcal{M}_n}(z_j) \ge h + (\log^{-1} n)/2$. By Proposition 3.6, for any $\delta > 0$ and for large enough $n$,

$$ \min_{a \ge h + (\log^{-1} n)/2} \mathbb{P}_a^{T_d} \left( |\mathcal{Z}_{a'_n - 2a_n}^{h + (\log^{-1} n)/2 +}| \ge (\lambda_h - \delta)^{a'_n - 2a_n} \right) \ge \frac{p \mathbb{P}_{T_d}(\mathcal{E}^+)}{2} $$

where $\mathbb{P}^{T_d}(\mathcal{E}^+) > 0$ (recall (A.3)) and

$$ p := \min_{a \ge h + (\log^{-1} n)/2} \mathbb{P}_a^{T_d} (\exists v \in B_{T_d}^+(\circ, 1), \varphi_{T_d}(z) \ge h + 1) > 0. $$

Note in particular that for $\delta' > \frac{\log^{-1} n}{2}$ such that $\lambda_{h+\delta'} > \lambda_h - \delta$ (such $\delta'$ exists by Proposition 3.3, if $n$ is large enough), $\mathcal{Z}_{a'_n - 2a_n}^{h+\delta',+} \subseteq \mathcal{Z}_{a'_n - 2a_n}^{h+(\log^{-1} n)/2,+}$. Since $\mathcal{M}_n$ is a good graph an $\mathcal{E}'_j \subseteq \{\max_{z \in A_{j,0,1}} |\psi_{\mathcal{M}_n}(z)| \le \log^{2/3} n\}$, we can apply Proposition 4.1 as below (5.9) to bound the difference between $\psi_{\mathcal{M}_n}$ on $B^*(z_n, a'_n - 2a_n)$ and $\varphi_{T_d}$ on $T_d$, and we get:

$$ \mathbb{P}_{ann} \left( |\partial \mathcal{C}_{z_j}| \ge (\lambda_h - \delta)^{a'_n - 2a_n} |\mathcal{E}'_j| \right) \ge \frac{p \mathbb{P}(\mathcal{E}^+)}{2} + o(1) \ge \frac{p \mathbb{P}(\mathcal{E}^+)}{3}. $$
By cylindrical symmetry of $B_{T_d^+}(\circ, a'_n - 2a_n)$, we even have

$$ \mathbb{P}^{\mathcal{M}_n} \left( v(0) \in \partial \mathcal{C}_{z_j} \middle| \mathcal{E}'_j \right) \ge \frac{p \mathbb{P}(\mathcal{E}^+)}{3} \frac{(\lambda_h - \delta)^{a'_n - 2a_n}}{|\partial B_{T_d^+}(\circ, a'_n - 2a_n)|} \ge \frac{p \mathbb{P}(\mathcal{E}^+)}{3} \left( \frac{\lambda_h - \delta}{d-1} \right)^{a'_n - 2a_n} . $$

Since $K_8 = \log_{d-1}((1 + \lambda_h)/2)$, taking $\delta$ small enough yields (6.15).

**Part 2: proof of (6.16).**

Denote $v_j(1), \dots, v_j(a_n - 1)$ the vertices from $v_j(0)$ to $v_j(a_n)$ on the path $P_j$. Remark that it suffices to prove that there exists a constant $K_9 > 0$ such that for $n$ large enough, for every $k \in \{1, \dots, a_n\}$,

$$ \mathbb{P}^{\mathcal{M}_n} \left( \psi_{\mathcal{M}_n}(v_j(k)) \ge h \middle| (\mathcal{E}'_j \cap \{\psi_{\mathcal{M}_n}(v_j(k-1)) \ge h\}) \right) \ge (d-1)^{-K_9}. \quad (6.17) $$

In the notation of (6.12), $v_j(k) = y_{j,k+a'_n-2a_n,1}$ for $1 \le k \le a_n$. Write $A_k := A_{j,k+a'_n-2a_n,1}$. Suppose that for $n$ large enough and all $k \in \{1, \dots, a_n\}$, on $\mathcal{E}'_j \cap \{\psi_{\mathcal{M}_n}(v_j(k-1)) \ge h\}$:

$$ \mathbb{E}^{\mathcal{M}_n}[\psi_{\mathcal{M}_n}(v_j(k))|\sigma(A_k)] > -|h| - 1, \quad \text{and} \quad (6.18) $$

$$ \mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(v_j(k))|\sigma(A_k)) > \frac{1}{d-1}. \quad (6.19) $$

Then (6.17) holds with

$$ K_9 := -\log_{d-1} \mathbb{P}\left(Y \ge \left(\frac{|h| + \frac{|h|+1}{d-1}}{\sqrt{d-1}}\right)\right), $$

where $Y \sim \mathcal{N}(0, 1)$. Thus, it is enough to establish (6.18) and (6.19).

For $k \ge 1$, note that by construction of $B^*(z_j, a'_n)$, $v_j(k-1)$ and $v_j(a_n)$ are the only vertices of $\partial A_k$ at distance less than $a_n$ of $v_j(k)$. Let $(X_s)_{s \ge 0}$ be a discrete time SRW started at $v_j(k)$, and $\tau := \inf\{s \ge 0, d_{\mathcal{M}_n}(v_j(k), X_s) \ge a_n\}$. Write $H$ for the hitting time of $A_k$ by $(X_s)$. Letting

$$ a_1 := \mathbf{P}_{v_j(k)}^{\mathcal{M}_n}(X_H = v_j(k-1), H < \tau) \text{ and } a_2 := \mathbf{P}_{v_j(k)}^{\mathcal{M}_n}(X_H = v_j(a_n), H < \tau), $$

we get as in the proof of Proposition 4.1 that for $\psi_{\mathcal{M}_n}(A_k)$ in $\mathcal{E}'_j \cap \{\psi_{\mathcal{M}_n}(v_j(k-1)) \ge h\}$:

$$ \mathbb{E}^{\mathcal{M}_n}[\psi_{\mathcal{M}_n}(v_j(k))|\sigma(A_k)] > a_1 \psi_{\mathcal{M}_n}(v_j(k-1)) + a_2 \psi_{\mathcal{M}_n}(v_j(a_n)) - \log^{-1} n. $$

Since $0 \le a_1 + a_2 \le 1$ and $\min(\psi_{\mathcal{M}_n}(v_j(k-1)), \psi_{\mathcal{M}_n}(v_j(a_n))) \ge h \ge -|h|$, (6.18) follows.

Using Proposition 2.3, we split $V := \mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(v_j(k))|\sigma(A_k))$ in the following way:

$$ V = G_{\mathcal{M}_n}(v_j(k), v_j(k)) - \mathbf{E}_{v_j(k)}^{\mathcal{M}_n} [G_{\mathcal{M}_n}(v_j(k), X_H) \mathbf{1}_{\{H<\tau\}}] \\ - \mathbf{E}_{v_j(k)}^{\mathcal{M}_n} [G_{\mathcal{M}_n}(v_j(k), X_H) \mathbf{1}_{\{H\ge\tau\}}] + \frac{\mathbf{E}_{v_j(k)}^{\mathcal{M}_n}[H]}{\mathbf{E}_{\pi_n}^{\mathcal{M}_n}[H]} \mathbf{E}_{\pi_n}^{\mathcal{M}_n} [G_{\mathcal{M}_n}(v_j(k), X_H)]. $$

By (2.4), (2.1) and (2.2), if $\kappa$ is large enough, for $n$ large enough,

$$ \begin{align*} G_{\mathcal{M}_n}(v_j(k), v_j(k)) - a_1 G_{\mathcal{M}_n}(v_j(k), v_j(k-1)) - a_2 G_{\mathcal{M}_n}(v_j(k), v_j(a_n)) & \\ &> \frac{d-1}{d-2} - \frac{a_1 + a_2}{d-2} - \log^{-1} n \\ &\ge \frac{1}{d-2} - \log^{-1} n. \end{align*} $$

As below (A.20), we get that

$$ \left| \mathbf{E}_{v_j(k)}^{\mathcal{M}_n} [G_{\mathcal{M}_n}(v_j(k), X_H) \mathbf{1}_{\{H<\tau\}}] - a_1 G_{\mathcal{M}_n}(v_j(k), v_j(k-1)) - a_2 G_{\mathcal{M}_n}(v_j(k), v_j(a_n)) \right| \le \log^{-1} n $$
and that

$$ \left| \mathbf{E}_{v_j(k)}^{\mathcal{M}_n} [G_{\mathcal{M}_n}(v_j(k), X_H) \mathbf{1}_{\{H \ge \tau\}}] - \frac{\mathbf{E}_{v_j(k)}^{\mathcal{M}_n}[H]}{\mathbf{E}_{\pi_n}^{\mathcal{M}_n}[H]} \mathbf{E}_{\pi_n}^{\mathcal{M}_n}[G_{\mathcal{M}_n}(v_j(k), X_H)] \right| \le \log^{-1} n. $$

These three inequalities imply that for $\psi_{\mathcal{M}_n}(A_k)$ in $\mathcal{E}'_j \cap \{\psi_{\mathcal{M}_n}(v_j(k-1)) \ge h\}$:

$$ \mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(v_j(k))|\sigma(A_k)) \ge \frac{1}{d-2} - 3 \log^{-1} n > \frac{1}{d-1}. $$

This shows (6.19) and the proof is complete. □

## 6.2 Average number of connections in $E_{\psi_{\mathcal{G}_n}}^{\ge h}$

Write $x \stackrel{h}{\leftrightarrow} y$ if $x$ and $y$ are in the same connected component of $E_{\psi_{\mathcal{G}_n}}^{\ge h}$, for $x, y \in V_n$. In this section, we prove (1.2) of Theorem 1.1 via an argument on the number of pairs of vertices such that $x \stackrel{h}{\leftrightarrow} y$. Let $S_n$ be the set of pairs of distinct $x, y \in V_n$ such that $x \stackrel{h}{\leftrightarrow} y$. Let $A_n \subset V_n$ be the set of vertices $x$ such that $|C_x^{\mathcal{M}_n, h}| \le n^{1/2}$.

We first suppose that the following two lemmas hold, and show (1.2). Then, we derive them from Propositions 5.4 and 6.2, using a second moment argument.

**Lemma 6.4.** For every $\varepsilon > 0$, $\lim_{n \to +\infty} \mathbb{P}_{ann}(|A_n| \ge (1 - \eta(h) - \varepsilon)n) = 1$.

**Lemma 6.5.** For every $\varepsilon > 0$, $\lim_{n \to +\infty} \mathbb{P}_{ann}(|S_n| \ge (\eta(h)^2/2 - \varepsilon)n^2) = 1$.

**Proof of (1.2).** Fix $\varepsilon > 0$. Remark that every connected component of $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ is either included in $A_n$, or does not intersect $A_n$. Let $(\hat{\gamma}_i^{(n)})_{i \ge 1}$ (resp. $(\gamma_i^{(n)})_{i \ge 1}$) be the sizes of the connected components in $A_n$ (resp. not in $A_n$), listed in decreasing order of size (break ties arbitrarily).

Let $\mathcal{E}_n := \{|A_n| \ge (1 - \eta(h) - \varepsilon)n\} \cap \{|S_n| \ge (\eta(h)^2/2 - \varepsilon)n^2\}$. On $\mathcal{E}_n$, we have that

$$ \sum_{i \ge 1} \hat{\gamma}_i^{(n)} (\hat{\gamma}_i^{(n)} - 1) + \sum_{i \ge 1} \gamma_i^{(n)} (\gamma_i^{(n)} - 1) = 2|S_n| \ge \eta(h)^2 n^2 - 2\varepsilon n^2. $$

Moreover, we have by definition of $A_n$:

$$ \sum_{i \ge 1} \hat{\gamma}_i^{(n)} (\hat{\gamma}_i^{(n)} - 1) \le \sum_{i \ge 1} \hat{\gamma}_i^{(n)} \sqrt{n} \le n^{7/4}. $$

Thus, for $n$ large enough,

$$ \gamma_1^{(n)}(|V_n| - |A_n|) \ge \sum_{i \ge 1} \gamma_i^{(n)} (\gamma_i^{(n)} - 1) \ge (\eta(h)^2 - 3\varepsilon)n^2. $$

But $|V_n| - |A_n| \le (\eta(h) + \varepsilon)n$, so that

$$ \gamma_1^{(n)} \ge \frac{\eta(h)^2 - 3\varepsilon}{\eta(h) + \varepsilon} n \ge ((\eta(h) - 4\eta(h)^{-1}\varepsilon)n. $$

Since $\gamma_1^{(n)}$ is the cardinality of a set included in $V_n \setminus A_n$, one has $\gamma_1^{(n)} \le (\eta(h) + \varepsilon)n$. Note that for $n$ large enough, $\gamma_1^{(n)} > \sqrt{n} \ge \hat{\gamma}_1^{(n)}$. Therefore, $\gamma_1^{(n)} = |C_1^{(n)}|$, and we have on $\mathcal{E}_n$:

$$ ((\eta(h) - 4\eta(h)^{-1}\varepsilon)n \le |C_1^{(n)}| \le (\eta(h) + \varepsilon)n. $$

By Lemmas 6.4 and 6.5, $\lim_{n \to +\infty} \mathbb{P}_{ann}(\mathcal{E}_n) = 1$. Since $\varepsilon$ was arbitrary, the proof is complete. □

**Remark 6.6.** Note that we have $|C_2^{(n)}| = \max(\gamma_2^{(n)}, \hat{\gamma}_1^{(n)})$. Since on $\mathcal{E}_n$, $\hat{\gamma}_1^{(n)} \le \sqrt{n}$ and $\gamma_2^{(n)} \le |V_n| - |A_n| - \gamma_1^{(n)} \le (1 + 4\eta(h)^{-1})\varepsilon n$, we get that $|C_2^{(n)}|/n \stackrel{P_{ann}}{\to} 0$.
Proof of Lemma 6.4. Let $A'_n$ be the set of vertices such that their lower exploration (Section 5.2) is aborted. By Remark 5.2, for $n$ large enough, $A'_n \subseteq A_n$, and it is enough to prove the result for $A'_n$ instead of $A_n$.

Let $\varepsilon \in (0, 1)$. By Proposition 5.4, for $n$ large enough and every $x \in V_n$, we have

$$|\mathbb{P}_{ann}(x \in A'_n) - (1 - \eta(h))| \le \varepsilon. \qquad (6.20)$$

We claim that for $n$ large enough, for all distinct $x, y \in V_n$,

$$|\mathrm{Cov}_{ann}(\mathbf{1}_{x \in A'_n}, \mathbf{1}_{y \in A'_n})| \le 4\varepsilon. \qquad (6.21)$$

Indeed, $\mathrm{Cov}_{ann}(\mathbf{1}_{x \in A'_n}, \mathbf{1}_{y \in A'_n}) = \mathbb{P}_{ann}(x, y \in A'_n) - \mathbb{P}_{ann}(x \in A'_n)\mathbb{P}_{ann}(y \in A'_n)$. On one hand, by (6.20), we have

$$|\mathbb{P}_{ann}(x \in A'_n)\mathbb{P}_{ann}(y \in A'_n) - (1 - \eta(h))^2| \le 2\varepsilon + \varepsilon^2 \le 3\varepsilon.$$

On the other hand, perform successively the lower explorations from $x$ and then from $y$ as in Section 5.2 (with the additional condition C5). We get $\mathbb{P}_{ann}(\text{C5 happens}) = o(1)$ as in (5.8). Then, revealing $\psi_{M_n}$ on $R_x \cup R_y$ and comparing it to $\varphi_{T_d}$ as below (5.9), we obtain

$$|\mathbb{P}_{ann}(x, y \in A'_n) - (1 - \eta(h))^2| \le \varepsilon.$$

This shows (6.21). We now apply Bienaymé-Chebyshev's inequality:

$$\begin{aligned} \mathbb{P}_{ann}(|A'_n| \le (1 - \eta(h) - 2\varepsilon^{1/4})n) &\le \mathbb{P}_{ann}(|A'_n| - \mathbb{E}_{ann}[|A'_n|] \ge \varepsilon^{1/4}n) \\ &\le \frac{1}{\sqrt{\varepsilon n^2}} \left( \sum_{x,y \in V_n} \mathrm{Cov}_{ann}(\mathbf{1}_{x \in A'_n}, \mathbf{1}_{y \in A'_n}) \right) \\ &\le \frac{n + n(n-1)4\varepsilon}{\sqrt{\varepsilon n^2}} \\ &\le 5\sqrt{\varepsilon} \end{aligned}$$

for $n$ large enough. Since $\varepsilon$ can be taken arbitrarily small, the proof is complete. $\square$

Proof of Lemma 6.5. Let $\varepsilon \in (0, 1)$. Denote $S_n^*$ the set of pairs $x, y \in V_n$ such that $S^*(x, y)$ holds. Since $S_n^* \subseteq S_n$, it is enough to prove the Lemma for $S_n^*$ instead of $S_n$. First, by Proposition 6.2,

$$\mathbb{E}_{ann}[|S_n^*|] \ge (\eta(h)^2 - \varepsilon) \frac{n(n-1)}{2} \ge (\eta(h)^2/2 - \varepsilon)n^2$$

for large enough $n$. Second, we show that for $n$ large enough and all distinct $x, y, w, t \in V_n$,

$$|\mathrm{Cov}_{ann}(\mathbf{1}_{S^*(x,y)}, \mathbf{1}_{S^*(w,t)})| \le 2\varepsilon, \qquad (6.22)$$

from which we conclude by a second moment computation as in Lemma 6.4. We have

$$\mathrm{Cov}_{ann}(\mathbf{1}_{S^*(x,y)}, \mathbf{1}_{S^*(w,t)}) = \mathbb{P}_{ann}(S^*(x, y) \cap S^*(w, t)) - \mathbb{P}_{ann}(S^*(x, y))\mathbb{P}_{ann}(S^*(w, t)).$$

By Proposition 6.2, for $n$ large enough,

$$|\mathbb{P}_{ann}(S^*(x, y))\mathbb{P}_{ann}(S^*(w, t)) - \eta(h)^4| \le \varepsilon. \qquad (6.23)$$

Now, perform successively the exploration of Section 5.1 from $x$, then from $y$, then from $z$ and finally from $t$ (via an array of i.i.d. standard normal variables $(\xi_{u,v})_{u \in \{x, y, w, t\}, v \in T_d}$). We add the following condition: for any $u \in \{x, y, w, t\}$, the exploration from $v$ is stopped as soon as it meets a vertex seen in a previous exploration. The probability that this happens is $o(1)$ by Remark 5.2 and (2.7), since $o(\sqrt{n})$ vertices
and half-edges are revealed during these four explorations. Therefore, as for (5.9), we get that for $n$ large enough,

$$ P_{ann}(\text{the explorations from } x, y, z, t \text{ are all successful}) \in (\eta(h)^4 - \varepsilon/2, \eta(h)^4 + \varepsilon/2). \qquad (6.24) $$

If these explorations are successful, develop balls from $\partial T_x$ to $\partial T_y$ as described in Section 6.1, with $Q_j := R_x \cup R_y \cup R_w \cup R_t \cup B_j^*$ for $z_j \in \partial T_x$. Then do the same from $\partial T_w$ to $\partial T_t$, this time with $Q_j := R_x \cup R_y \cup (\cup_{z \in \partial T_x} B^*(z, a'_n)) \cup R_w \cup R_t \cup B_j^*$ for $z_j \in \partial T_w$. Finally, reveal $\psi_{M_n}$ on $T_x, T_y, T_w, T_t$ and on the joining balls from $T_x$ to $T_y$ and from $T_w$ to $T_t$, in that order.

One can adapt readily the proof of Lemma 6.1 to show that with $P_{ann}$-probability $1 - o(1)$, if the four explorations are successful then there are at least $\log^{\gamma-3\kappa-18} n$ joining balls from $\partial T_x$ (resp. $\partial T_w$) to $\partial T_y$ (resp. $\partial T_t$). Note in particular that the estimates of (6.4), (6.6) and (6.7) still hold. It is also straightforward to adapt the proof of Proposition 6.2, and we finally have

$$ |P_{ann}(S^*(x, y) \cap S^*(w, t)) - P_{ann}(\text{the explorations from } x, y, w, t \text{ are all successful})| \le \varepsilon/2. $$
Together with (6.23) and (6.24), this yields (6.22). \hfill $\square$

# 7 Uniqueness of the giant component

In this Section, we prove (1.3). We start by the lower bound in Section 7.1, showing the existence $P_{ann}$-w.h.p. of a component (different from $C_1^{(n)}$) having $\Theta(\log n)$ vertices.

Then, to show that $|C_2^{(n)}| = O(\log n) P_{ann}$-w.h.p., we perform an exploration of a new kind, starting from some $x \in V_n$. It consists of three phases (Sections 7.2 to 7.4), during which we assign a **pseudo-GFF** $\tilde{\psi}_{M_n}$ to the vertices that we visit. $\tilde{\psi}_{M_n}$ is defined via a recursive construction that mimics Proposition 3.1, as long as there are no cycles (like $\phi_{T_d}$ on $\mathcal{T}_x$ in Section 5). If we meet one cycle, which can happen in the first phase (Section 7.2, we use an ad hoc modification of these recursive formulas. Finally, in Section 7.5, we reveal the true values of $\psi_{M_n}$ one by one on the set of vertices we have explored via Proposition 2.4, and check that they are close to $\tilde{\psi}_{M_n}$. We show that either $|C_x^{M_n,h}| = O(\log n)$, or $|C_x^{M_n,h}| = \Theta(n)$, in which case $C_x^{M_n,h} = C_1^{(n)}$ by Remark 6.6. Contrary to Section 5, we need this alternative to hold for every $x \in V_n$, $P_{ann}$-w.h.p. By a union bound, it is enough to prove that

$$ \text{for } x \in V_n, P_{ann}(\{|C_x^{M_n,h}| = O(\log n)\} \cup \{|C_x^{M_n,h}| = \Theta(n)\}) = o(1/n). \qquad (7.1) $$

Let us sketch this exploration in the lines below.

**First phase (Section 7.2).** We explore the connected component $C$ of $x \in V_n$ in the set $\{y \in V_n, \widehat{\psi_{M_n}}(y) \ge h - n^{-a}\}$ for some constant $a > 0$. More precisely, we give a mark to each vertex $y$ such that $|\widehat{\psi_{M_n}}(y) - h| \le n^{-a}$, and explore each connected component $C'$ of $C \setminus M$, where $M$ is the set of marked vertices, until

- (i) $C'$ is fully explored and has no more than $O(\log n)$ vertices, or

- (ii) $\lfloor K_{10} \log n \rfloor$ vertices of $C'$ have been seen but not yet explored, for some constant $K_{10}$ fixed in the second phase.

We replace $a_n$ of (4.1) by a "security radius" $r_n = \Theta(\log n)$. Adapting Proposition 4.1 (see Lemma 7.6), this will allow us in Section 7.5 to bound the difference between $\widehat{\psi}_{M_n}$ and $\psi_{M_n}$ by $n^{-a}$ with probability $1 - o(1/n)$, so that for every connected component $C'$ of $C \setminus M$, either $C' \subseteq C_x^{M_n,h}$ or $C' \cap C_x^{M_n,h} = \emptyset$.

If we kept $a_n$, $\widehat{\psi}_{M_n}$ would approximate $\psi_{M_n}$ only with precision $\log^{-\Theta(1)} n$. With probability $\Theta(1/n)$, there would be too many vertices $y$ such that $|\widehat{\psi}_{M_n}(y) - h| \le \log^{-\Theta(1)} n$, hence for which we cannot know by anticipation whether they will be in $C_x^{M_n,h}$ or not.
Moreover, we do not have $\mathbb{P}(\text{C1 happens}) = O(1/n)$ as soon as the number of vertices explored goes to infinity with $n$. We will need to accept the possible occurrence of one cycle. When this happens, we have to define $\tilde{\psi}_{\mathcal{M}_n}$ in a slightly different manner. In Section 7.5, we need a variant of Lemma 7.6 to control the difference between $\tilde{\psi}_{\mathcal{M}_n}$ and $\psi_{\mathcal{M}_n}$ in that case (Lemma 7.7).

**Second phase (Section 7.3).** If (i) happens for every component $\mathcal{C}'$, the exploration is over. In this case, $|\mathcal{C}| = O(\log n)$ (see D2 and Proposition 7.2) and thus $|\mathcal{C}_x^{\mathcal{M}_n, h}| = O(\log n)$. For each $\mathcal{C}'$ such that (ii) happens, we explore its $\lfloor K_{10} \log n \rfloor$ remaining vertices, this time in a fashion similar to Section 5.1. Each of these explorations has a probability bounded away from 0 to be successful. If $K_{10}$ is large enough, with probability at least $1 - o(1/n)$, at least one of these explorations is successful, and has a boundary of size $\Theta(n^{1/2}b_n)$.

**Third phase (Section 7.4).** For every $\mathcal{C}'$ such that (ii) happens, we show that the successful exploration of the second phase is connected to a positive proportion of the vertices of $V_n$, via an adaptation of the joint exploration in Section 6.1. This yields (7.1).

## 7.1 Lower bound

In this section, we prove the existence of $K_0 > 0$ such that

$$ \mathbb{P}_{ann}(|\mathcal{C}_2^{(n)}| \geq K_0^{-1} \log n) \to 1. \qquad (7.2) $$

To do so, we first show that if $K_0$ is large enough, then with probability at least $n^{-1/4}$, $\mathcal{C}_0^h$ consists of a unique “line” $L_n$ of length $\lfloor 2K_0^{-1} \log n \rfloor$ (each vertex of $\mathcal{C}_0^h$ having one child, except the last one which has no children, Lemma 7.1). Thus, if we take $n^{1/3}$ vertices of $V_n$ and assign to each of them an independent copy of $\mathcal{C}_0^h$, the probability that at least one of them is isomorphic to $L_n$ is $1 - o(1)$. Then, we realize the component of the corresponding vertex in $E^{\ge h}$, and check that it is indeed isomorphic to $L_n$ with $\mathbb{P}_{ann}$-probability $1 - o(1)$, so that $|\mathcal{C}_2^{(n)}| \geq \lfloor 2K_0^{-1} \log n \rfloor \geq K_0^{-1} \log n$.

**Lemma 7.1.** For $n \ge 1$, let $\mathcal{E}_{line,n}$ be the event that $\mathcal{C}_0^h$ has $m := \lfloor 2K_0^{-1} \log n \rfloor$ vertices $x_1, \dots, x_m$ with $x_1 = \circ$ and for $2 \le i \le m$ $x_i$ is the child of $x_{i-1}$, and that for $1 \le i \le m$, for any other child $y$ of $x_i$ in $\mathbb{T}_d$, $\varphi_{\mathbb{T}_d}(x_i) \in [h+1, h+2]$, $\varphi_{\mathbb{T}_d}(y) < h-1$. If $K_0$ is large enough, then for $n$ large enough,

$$ \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}_{line,n}) \geq n^{-1/4}. $$

*Proof.* Let $v_1, \dots, v_d$ be the children of $\circ$ in $\mathbb{T}_d$. Remark that for $n$ large enough,

$$ \mathbb{P}_{ann}(\mathcal{E}_{line,n}) \geq \mathbb{P}^{\mathbb{T}_d}(\varphi_{\mathbb{T}_d}(\circ) \in [h+1, h+2]) pp'^{\lfloor 2K_0^{-1} \log n \rfloor} p'', \text{ where} $$

$$ p := \inf_{a \in [h+1, h+2]} \mathbb{P}_a^{\mathbb{T}_d}(\{\varphi_{\mathbb{T}_d}(v_1) \in [h+1, h+2]\} \cap \{\forall i \in \{2, \dots, d\}, \varphi_{\mathbb{T}_d}(v_i) < h-1\}), $$

$$ p' := \inf_{a \in [h+1, h+2]} \mathbb{P}_a^{\mathbb{T}_d}(\{\varphi_{\mathbb{T}_d}(v_1) \in [h+1, h+2]\} \cap \{\forall i \in \{2, \dots, d-1\}, \varphi_{\mathbb{T}_d}(v_i) < h-1\}), $$

$$ p'' := \inf_{a \in [h+1, h+2]} \mathbb{P}_a^{\mathbb{T}_d}(\forall i \in \{1, \dots, d-1\}, \varphi_{\mathbb{T}_d}(v_i) < h-1). $$

Using Proposition 3.1, one checks that $p, p', p'' > 0$. Taking $K_0 > -8 \log p'$ yields the result. $\square$

*Proof of (7.2).* Fix $K_0 > 12 \log(d-1)$ large enough such that the conclusion of Lemma 7.1 holds. Let $x_1, \dots, x_{\lfloor n^{1/3} \rfloor} \in V_n$. For all $1 \le i \le \lfloor n^{1/3} \rfloor$, attach a family $(\xi_y^{(i)})_{y \in \mathbb{T}_d}$ of i.i.d. $\mathcal{N}(0, 1)$ variables, these families being themselves independent. For each $i$, let $\mathcal{C}_0^h(i)$ be the associated realization of $\mathcal{C}_0^h$ built with the family $(\xi_y^{(i)})$, using Proposition 3.1.

Then, pick a realization of $\mathcal{M}_n$, and let $\mathcal{E}_{1,n}$ be the event that $\mathcal{M}_n$ is a good graph and that the balls $B_{\mathcal{M}_n}(x_i, \lfloor 2K_0^{-1} \log n \rfloor + 2a_n))$, $1 \le i \le \lfloor n^{1/3} \rfloor$ are disjoint and have no cycle.
By Proposition 2.1 and (2.7) with $m_0 = \lfloor n^{1/3} \rfloor$, $m \le \lfloor n^{1/3} \rfloor \times (d-1)^{\lfloor 2K_0^{-1} \log n \rfloor+2a_n+10}$ and $k=1$, $P_{ann}(\mathcal{E}_{1,n}) = 1-o(1)$.

On $\mathcal{E}_{1,n}$, realize $\psi_{\mathcal{M}_n}$ on $B_{\mathcal{M}_n}(x_i, \lfloor 2K_0^{-1} \log n \rfloor)$ for $i=1, \dots, \lfloor n^{1/3} \rfloor$ successively, using the random variables $(\xi_y^{(i)})_{y \in B_{T_d}(\circ, \lfloor 2K_0^{-1} \log n \rfloor)}$ and the construction of Proposition 2.4. For $1 \le i \le \lfloor n^{1/3} \rfloor$, let $\Phi^{(i)}$ be a rooted isomorphism between $B_{C_{x_i}^{\mathcal{M}_n, h}}(x_i, \lfloor 2K_0^{-1} \log n \rfloor)$ and $B_i := B_{C_{x_i}^{h}}(x_i, \lfloor 2K_0^{-1} \log n \rfloor)$. Let $\mathcal{E}_{2,n} := \{\sup_{1 \le i \le \lfloor n^{1/3} \rfloor, y \in B_i} |\psi_{\mathcal{M}_n}((\Phi^{(i)})^{-1}(y)) - \varphi_{T_d}(y)| < 1/2\}$. A direct adaptation of the reasoning below (5.9) to show that $P_{ann}(\mathcal{E}_{2,n}) = 1-o(1)$.

Let $\mathcal{E}_{3,n} := \{\exists i_0 \in \{1, \dots, \lfloor n^{1/3} \rfloor\}, B_{i_0}$ is isomorphic to $L_n\}$. By Lemma 7.1, we have that $P_{ann}(\mathcal{E}_{3,n}) \ge 1 - (1 - n^{-1/4})^{\lfloor n^{1/3} \rfloor} = 1 - o(1)$.

Finally, by (1.2), we have $P_{ann}(\mathcal{E}_{4,n}) = 1 - o(1)$, with $\mathcal{E}_{4,n} = \{|C_1^{(n)}| \ge 10 \log n\}$.

All in all, we have shown that $P_{ann}(\mathcal{E}_{1,n} \cap \mathcal{E}_{2,n} \cap \mathcal{E}_{3,n} \cap \mathcal{E}_{4,n}) = 1 - o(1)$. And on $\mathcal{E}_{1,n} \cap \mathcal{E}_{2,n} \cap \mathcal{E}_{3,n} \cap \mathcal{E}_{4,n}$ for $n$ large enough, $|C_{x_{i_0}}^{\mathcal{M}_n, h}| \ge K_0^{-1} \log n$ and $C_{x_{i_0}}^{\mathcal{M}_n, h} \ne C_1^{(n)}$, so that $|C_2^{(n)}| \ge K_0^{-1} \log n$. $\square$

## 7.2 First phase

In this section, we define the first phase of the exploration, and show that it is successful with $P_{ann}$-probability $1 - n^{-5/4}$ (Proposition 7.2).

Let $a > 0$. For every $n \in \mathbb{N}$, define

$$r_n := \lfloor 0.05 \log_{d-1} n \rfloor \qquad (7.3)$$

Let $\delta \in (0, h_* - h)$ and $\ell \in \mathbb{N}$ be such that the conclusion of Remark A.3 holds.

**The first phase of the exploration.** Let $x \in V_n$. Let $\mathcal{M}$ be the set of marked vertices. Initially, $\mathcal{M} = \{x\}$. While $\mathcal{M} \ne \emptyset$, pick $y \in \mathcal{M}$ in an arbitrary way and proceed to its **subexploration**, as detailed below.

There are three possible scenarios, according to the number of cycles discovered during the first phase (zero, one, or more).

**I** - We first assume that we do not meet any cycle throughout the first phase of the exploration of $x$.

Assume we have picked some vertex $y \in \mathcal{M}$. We now define the **subexploration from** $y$. Let $T_y$ be the subexploration tree, that we will build by adding subtrees of depth $\ell$ in a breadth-first way. Initially $T_y = \{y\}$.

While $1 \le |\partial T_y| \le K_{10} \log n$, perform a **step**: take $y_1 \in \partial T_y$ of minimal height and if $y_1 \ne x$, let $\overline{y_1}$ be its only neighbour where $\widehat{\psi_{\mathcal{M}_n}}$ has already been defined. Note that if $y_1 \ne y$, $\overline{y_1}$ is the parent of $y_1$ in $T_y$. Reveal all the edges of $B_{\mathcal{M}_n}(y_1, \overline{y_1}, r_n + \ell)$, where we recall that $B_{\mathcal{M}_n}(y_1, \overline{y_1}, r_n + \ell)$ is the graph obtained by taking all paths of length $r_n + \ell$ starting at $y_1$ and not going through $\overline{y_1}$. Since we suppose that no cycle arises, $B_{\mathcal{M}_n}(y_1, \overline{y_1}, \ell)$ is a tree, that we root at $y_1$.

If $y_1 = y = x$, replace $B_{\mathcal{M}_n}(y_1, \overline{y_1}, r_n + \ell)$ and $B_{\mathcal{M}_n}(y_1, \overline{y_1}, \ell)$ by $B_{\mathcal{M}_n}(x, r_n + \ell)$ and $B_{\mathcal{M}_n}(x, \ell)$ respectively. Let $\widehat{\psi_{\mathcal{M}_n}}(x) \sim \mathcal{N}(0, \frac{d-1}{d-2})$. If $\varphi_{T_d}(\circ) < h - n^{-a}$, then the whole exploration (not only the first phase) is over.

We construct $T_y(y_1)$, the subtree of $B_{\mathcal{M}_n}(y_1, \overline{y_1}, \ell)$ in $\{z, \widehat{\psi_{\mathcal{M}_n}}(z) \ge h + n^{-a}\}$. We start with $T_y(y_1) = \{y_1\}$.

For $k = 1, 2, \dots, \ell - 1$ successively, denote $y_{k,1}, \dots, y_{k,m}$ the children of the $(k-1)$-th generation of $T_y(y_1)$. Let $(\xi_{y_1,k,i})_{k,i \ge 0}$ be an array of i.i.d. variables of law $\mathcal{N}(0, 1)$,
independent of everything else. Set

$$ \widehat{\psi}_{M_n}(y_{k,i}) := \frac{1}{d-1} \widehat{\psi}_{M_n}(\overline{y_{k,i}}) + \sqrt{\frac{d}{d-1}} \xi_{y_1,k,i}. \quad (7.4) $$

Add $y_{k,i}$ to $T_y(y_1)$ if $\widehat{\psi}_{M_n}(y_{k,i}) \ge h + n^{-a}$, and give a mark to $y_{k,i}$ (and thus add it to $M$) if $h - n^{-a} \le \widehat{\psi}_{M_n}(y_{k,i}) < h + n^{-a}$.

Finally, include $T_y(y_1)$ in $T_y$, add the vertices of $\partial T_y(y_1)$ to $N_y$ and take $y_1$ away from $\partial T_y$. The step is then over.

If $|\partial T_y| \notin [1, K_{10} \log n]$, the subexploration is finished. Say that it is **fertile** if $|\partial T_y| > K_{10} \log n$, and **infertile** else (hence if $\partial T_y = \emptyset$).

## II - Suppose now that a unique cycle C arises in the subexploration of some vertex y, when revealing the pairings of $B_{M_n}(y_1, \overline{y_1}, r_n + \ell)$ in the step from $y_1$, for some $y \in V_n$ and $y_1 \in V_n \setminus \{x\}$ (we treat the special case $x = y_1$ below). Let $m := |C|$ be the number of vertices in C. There are two cases.

**Case 1:** When C is discovered, there are already $k$ consecutive vertices $y_1, \dots, y_k$ of C where $\widehat{\psi}_{M_n}$ has been defined, for some $1 \le k \le m-1$. Reveal $B_{M_n}(C, r_n)$. Denote $z_1, \dots, z_{m-k}$ the remaining vertices of C, such that $z_1 \ne y_2$ is a neighbour of $y_1$, and $z_i$ is a neighbour of $z_{i-1}$ for $i \ge 2$. Give a mark to $z_1, \dots, z_{m-k}$ and $y_1$. Take $y_1$ away from $\partial T_y$. If $y_k$ was in $\partial T_{\tilde{y}}$ for some $\tilde{y}$ whose subexploration was performed previously, take it away from that set.

<figure><img src="image_7.png" /><figcaption>Figure 4: Case 1. Marked vertices are in red. C consists of the thick edges. $T_y$ and $T_{\tilde{y}}$ are delimited by the purple contours. Remark that we could have $y = \tilde{y}$ (it is not the case here).</figcaption></figure>

We now define $\widehat{\psi}_{M_n}$ on the $z_i$'s. To do so, we mimic a recursive construction of the GFF on $G_m$, the infinite connected $d$-regular graph $G_m$ having a unique cycle $C_m$ of length $m$ (such a construction always exists on a transient graph, see for instance Lemma 1.2 in [27]). $G_m$ consists of a cycle $C_m$ of length $m$, with $d-2$ copies of $T_d^+$ attached to each vertex of $C_m$, thus it is clear that the SRW is transient and that the Green function $G_{G_m}$ and the GFF are well-defined.

Let $u_k, \dots, u_1, v_1, \dots, v_{m-k}$ be the vertices of $C_m$, listed consecutively. Let $U := G_m \setminus \{u_1, \dots, u_k\}$, $(X_j)_{j \ge 0}$ a SRW on $G_m$ and recall that $T_U$ is the exit time of $U$. Define

$$ \alpha := \mathbf{P}_{v_1}^{G_m}(X_{T_U} = u_1, T_U < +\infty), \quad \beta := \mathbf{P}_{v_1}^{G_m}(X_{T_U} = u_k, T_U < +\infty) \mathbf{1}_{\{k>1\}} $$
Anatomy of a Gaussian giant

$$ \text{and } \gamma := \mathbf{E}_{v_1}^{G_m} \left[ \sum_{j=0}^{T_U-1} \mathbf{1}_{\{X_j=v_1\}} \right], $$

and let $(\xi_i)_{i \ge 1}$ be a family of i.i.d standard normal variables, independent of everything else. Define

$$ \widehat{\psi}_{M_n}(z_1) := \alpha \widehat{\psi}_{M_n}(y_1) + \beta \widehat{\psi}_{M_n}(y_k) + \sqrt{\gamma} \xi_1. $$

Then for $i \ge 2$, define recursively

$$ \widehat{\psi}_{M_n}(z_i) := \alpha_{m-(k+i-1)} \widehat{\psi}_{M_n}(z_{i-1}) + \beta_{m-(k+i-1)} \widehat{\psi}_{M_n}(y_k) + \sqrt{\gamma_{m-(k+i-1)}} \xi_i \quad (7.5) $$

where we set

$$ U_i := G_m \setminus \{u_1, \dots, u_k, v_1, \dots, v_{i-1}\}, \quad \alpha_{m-(k+i-1)} := \mathbf{P}_{v_i}^{G_m}(X_{T_{U_i}} = v_{i-1}, T_{U_i} < +\infty), $$

$$ \beta_{m-(k+i-1)} := \mathbf{P}_{v_i}^{G_m}(X_{T_{U_i}} = u_k, T_{U_i} < +\infty) \text{ and } \gamma_{m-(k+i-1)} := \mathbf{E}_{v_i}^{G_m} \left[ \sum_{j=0}^{T_{U_i}-1} \mathbf{1}_{\{X_j=v_i\}} \right]. $$

**Case 2:** $\widehat{\psi}_{M_n}$ has not been defined on any vertex of C. There exists a unique path of consecutive vertices $y_1, \dots, y_j$ for some $j \ge 2$ such that $y_j \in C$, and for $2 \le i \le j - 1$, $\widehat{\psi}_{M_n}(y_i)$ has not been defined and $y_i \notin C$. Reveal $B_{M_n}(\{y_1, \dots, y_{j-1}\} \cup C, r_n)$. Give a mark to the vertices of $\{y_1, \dots, y_{j-1}\} \cup C$. Take $y_1$ away from $\partial T_y$.

<figure><img src="image_8.png" /><figcaption>Figure 5: Case 2. Marked vertices are in red.</figcaption></figure>

We define $\widehat{\psi}_{M_n}$ on $\{y_1, \dots, y_{j-1}\} \cup C$ in a way similar to Case 1. Let $(\xi_i)_{i \ge 1}$ be a sequence of i.i.d. standard normal variables, independent of everything else. For $i = 1, 2, \dots, j$, set

$$ \widehat{\psi}_{M_n}(y_i) := \alpha'_{j-i} \widehat{\psi}_{M_n}(y_{i-1}) + \sqrt{\gamma'_{j-i}} \xi_i, \quad (7.6) $$

where $\alpha'_{j-i} := \mathbf{P}_z^{G_m}(H_{\{z'\}} < +\infty)$ and $\gamma'_{j-i} := \mathbf{E}_z^{G_m} \left[ \sum_{l=0}^{H_{\{z'\}}-1} \mathbf{1}_{\{X_l=z\}} \right]$, $z, z'$ being two neighbours in $G_m$ such that $z$ (resp. $z'$) is at distance $j-i$ (resp. $j-i+1$) of $C_m$. Then, define $\widehat{\psi}_{M_n}$ on C as in Case 1 with $k=1$.

If C is discovered while revealing $B_{M_n}(x, r_n + \ell)$, give a mark to all vertices of C, and, if $x \notin C$, all vertices on the unique shortest path from x to C. Let $k := d_{M_n}(x, C)$. Let $u_k \in G_m$ be at distance k of the cycle $C_m$. Let $\widehat{\psi}_{M_n}(x) \sim \mathcal{N}(0, G_{G_m}(u_k, u_k))$. If $\varphi_{T_d}(0) < h - n^{-a}$, then the whole exploration (not only the first phase) is over.

**After the discovery of C.** Assume that no other cycle will be discovered during the first phase of the exploration from x. Resume the subexploration from y, by picking a new vertex $y' \in \partial T_y$ (recall that we have taken $y_1$ away from $\partial T_y$) and proceeding to the step from $y'$, and so on until the subexploration from y is over. After that, as long as $M \neq \emptyset$,
pick a vertex $y''$ in $\mathcal{M}$ and proceed to its subexploration as described in I (recall that no new cycle is discovered), with the following amendment, if $y''$ has several neighbours $y_1'', \dots, y_k''$ (for some $k \ge 2$) on which $\tilde{\psi}_{\mathcal{M}_n}$ has already been defined (see for instance $y_2$ or $y_j$ in Figure 5). In this case, in the step from $y''$ (the first step of the subexploration from $y''$), reveal only $\cap_{1 \le i \le k} B_{\mathcal{M}_n}(y'', y_i'', r_n + \ell)$ instead of $B_{\mathcal{M}_n}(y'', \bar{y}'', r_n + \ell)$ (not by the way that $\bar{y}''$ is not properly defined). In words, perform the subexploration only in the direction of non-marked vertices.

**III -** If a second cycle arises, the whole exploration from $x$ is over, and is not successful.

We have now fully described how the first phase can unfold. Say that the first phase is successful if at some point, the following holds:

D1 $\mathcal{M} = \emptyset$,

D2 $\tilde{\psi}_{\mathcal{M}_n}$ has been defined on at most $\lfloor K_{11} \log n \rfloor$ vertices, and

D3 at most one cycle has been discovered.

Denote $S_1(x)$ this event. If all subexploration trees were infertile, then the whole exploration from $x$ is over, and said to be successful. Denote $S_{1,\text{stop}}(x)$ this event.

**Proposition 7.2.** Fix $a > 0$. For any fixed value of $K_{10} > 0$, if $K_{11}$ is large enough, then for large enough $n$ and every $x \in V_n$, $P_{\text{ann}}(S_1(x)) \ge 1 - n^{-5/4}$.

*Proof.* In a nutshell, the argument is as follows. We first show that with probability $1 - o(n^{-5/4})$, we see at most one cycle after having explored $n^{3/10}$ vertices (which will turn out to be more than the number of vertices seen in the first phase). Then, we show that for some large constant $K > 0$, with probability $1 - o(n^{-5/4})$, the first $K \log n$ subexplorations encompass less than $K^2 \log n$ vertices. To this end, we use the fact that during any subexploration, say of some vertex $y$, the increment of $|\partial T_y|$ during a step of the subexploration from $y$ has a positive expectation if $\ell$ is large enough, since $C_o^\ell$ has a positive probability to have an exponential growth (see Lemma A.2 and Remark A.3, this is why we explore subtrees of depth $\ell$ instead of individual vertices). Finally, we show that with probability $1 - o(n^{-5/4})$, the first $K \log n$ subexplorations generate less than $K \log n$ marks. In particular, note that except for cycles, each vertex where $\tilde{\psi}_{\mathcal{M}_n}$ is defined has a chance $O(n^{-a})$ to get a mark, and a cycle brings less than $2d^\ell r_n = \Theta(\log n)$ marked vertices. This in turn ensures that there are indeed no more than $K \log n$ subexplorations in the first phase.

We now proceed to the proof itself. Let $\mathcal{E}_{1,n}$ be the event that two cycles are discovered before $n^{3/10}$ vertices have been seen during the exploration from $x$. By (2.7) with $k = 2$, $m_0 = 1$, $m_E = 0$ and $m \le n^{3/10}$,

$$P_{\text{ann}}(\mathcal{E}_{1,n}) \le n^{-4/3}. \qquad (7.7)$$

Next, let $K > 0$ be a constant; we bound the number $N$ of steps during the first $\lfloor K \log n \rfloor$ subexplorations (or on all subexplorations if there are less than $\lfloor K \log n \rfloor$ of them). Let $\mathcal{E}_{2,n} := \{N \ge K^2 \log n\}$, we now show that if $K$ is large enough, then we have for $n$ large enough:

$$P_{\text{ann}}(\mathcal{E}_{2,n}) \le n^{-2}. \qquad (7.8)$$

Suppose that we perform the subexploration from some vertex $y$. Let $y_1 \in \partial T_y$, with $y_1 \ne y$. If no cycle arises when revealing the $(r_n + \ell)$-offspring of $y_1$, then $|\partial T_y(y_1)| - 1$, the increment of $|\partial T_y|$ during that step, dominates stochastically $\rho_{\ell,h,\delta} - 1$, by definition of $\rho_{\ell,h,\delta}$ at Remark A.3, as soon as $n^{-a} < \delta$. If a cycle arises (which happens at most once on $\mathcal{E}_{1,n}^c$), at most two vertices are marked and taken away from $\partial T_y$. If the subexploration
is not over after $j$ steps, then $|\partial T_y| \ge S_{j-1} - 2$, where $S_{j-1}$ is the sum of $j-1$ i.i.d. random variables of law $\rho_{\ell,h,\delta} - 1$, hence taking values in the bounded interval $[0, d^\ell]$, and with a positive expectation by Remark A.3. The $-1$ in $j-1$ comes from the fact that we do not include the step from $y$ (as it might be that we only explore a reduced number of vertices once we have discovered a cycle, if $y$ is a marked vertex with at least two marked neighbours). The $+2$ comes from the possibility that up to two vertices can be taken away from $\partial T_y$ if there is a cycle (see Case 1 in particular). Hence

$$ \mathbb{P}_{ann}(\text{the subexploration from } y \text{ lasts more than } j \text{ steps}) \le \mathbb{P}(S_{j-1} \le K_{10} \log n + 2) $$

By the exponential Markov inequality, there exist constants $c, c' > 0$ such that

$$ \text{for every } j \ge 2K_{10}(\mathbb{E}[\rho_{\ell,h,\delta}] - 1)^{-1} \log n, \quad \mathbb{P}(S_{j-1} \le K_{10} \log n + 2) \le c e^{-c'j}. $$

Therefore, $N$ is stochastically dominated by a sum $S$ of $\lfloor K \log n \rfloor$ i.i.d. variables of some law $\mu$ (independent of $n$) such that

$$ \text{for every } j \ge 2K_{10}(\mathbb{E}[\rho_{\ell,h,\delta}] - 1)^{-1} \log n, \quad \mu([j, +\infty)) \le c e^{-c'j}. $$

Hence, letting $\mathcal{E}_{2,n} := \{N \ge K^2 \log n\}$, by the exponential Markov inequality,

$$ \mathbb{P}_{ann}(\mathcal{E}_{2,n} \cap \mathcal{E}_{1,n}^c) \le \mathbb{P}_{ann}(S \ge K \lfloor K \log n \rfloor) \le (\mathbb{E}[e^{c'Y/2}]e^{-c'K\mu/2})^{\lfloor K \log n \rfloor} $$

for large enough $n$ and for $Y \sim \mu$. Thus (7.8) follows.

Finally, let $\mathcal{E}_{3,n}$ be the event that more than $3r_n + \frac{K}{2} \log n$ marks are given during the first $\lfloor K \log n \rfloor$ subexplorations. Suppose that for $n$ large enough,

$$ \mathbb{P}_{ann}(\mathcal{E}_{1,n}^c \cap \mathcal{E}_{2,n}^c \cap \mathcal{E}_{3,n}) \le n^{-2}. \quad (7.9) $$

Taking $K > 1$, on $\mathcal{E}_{1,n}^c \cap \mathcal{E}_{2,n}^c \cap \mathcal{E}_{3,n}^c$ (which holds with $\mathbb{P}_{ann}$-probability $1 - o(n^{-5/4})$ by (7.7), (7.8) and (7.9)), less than $1 + 3r_n + \frac{K}{2} \log n \le \lfloor K \log n \rfloor$ vertices receive a mark during the first $\lfloor K \log n \rfloor$ subexplorations, so that $M = \emptyset$ after at most $\lfloor K \log n \rfloor$ subexplorations. Moreover, in a step of a subexploration, less than $d^\ell$ vertices are added to the subexploration tree. Hence if $K_{11} > K^2 d^\ell$, on $\mathcal{E}_{2,n}^c$, D2 holds. In addition, less than $(d-1)^{2r_n} \le n^{1/10}$ new vertices are seen in a step of a subexploration. When a cycle $C$ is revealed, there are at most $2r_n$ new vertices in $C$ (and on the path leading to $C$, in Case 2), so that less than $3r_n(d-1)^{r_n} \le n^{1/10}$ new vertices are seen. Therefore, on $\mathcal{E}_{1,n}^c \cap \mathcal{E}_{2,n}^c$, less than $n^{3/10}$ vertices are seen during the first $\lfloor K \log n \rfloor$ subexplorations. Thus, on $\mathcal{E}_{1,n}^c \cap \mathcal{E}_{2,n}^c \cap \mathcal{E}_{3,n}^c$, conditions D1, D2 and D3 are satisfied and this yields the conclusion.

Therefore, it only remains to show (7.9), which we now do. When a cycle $C$ appears, our construction implies that less than $3r_n$ vertices receive a mark. When performing $m$ steps in a subexploration, the number of marked vertices obtained is stochastically dominated by a binomial random variable $\text{Bin}(m, d^\ell n^{-a})$. Indeed, at each step, we reveal $\widehat{\psi}_{M_n}$ (and thus $\varphi_{T_d}$) on less than $d^\ell$ vertices. And for any vertex $y \in T_d \setminus \{\circ\}$, by Proposition 3.1,

$$ \max_{a' \ge h} \mathbb{P}_{T_d}(\varphi_{T_d}(y) \in [h - n^{-a}, h + n^{-a}] | \varphi_{T_d}(\bar{y}) = a') \le \frac{2n^{-a}}{\sqrt{2\pi d/(d-1)}} \le n^{-a}. $$

Hence, if $Z \sim \text{Bin}(\lfloor K^2 \log n \rfloor, C_2 d^\ell n^{-a})$,

$$ \mathbb{P}_{ann}(\mathcal{E}_{1,n}^c \cap \mathcal{E}_{2,n}^c \cap \mathcal{E}_{3,n}) \le \mathbb{P}\left(Z \ge \frac{K}{2} \log n\right) \le \left(\frac{\lfloor K^2 \log n \rfloor}{\frac{K}{2} \log n}\right) (C_2 d^\ell n^{-a})^{\frac{K}{2} \log n}. $$

But by (2.5), for large enough $n$, $\left(\frac{\lfloor K^2 \log n \rfloor}{\frac{K}{2} \log n}\right) \le \lfloor K^2 \log n \rfloor^{\frac{K}{2} \log n}$. This yields (7.9), and the conclusion follows. $\square$
## 7.3 Second phase

If $S_{1,stop}(x)$ holds, i.e. all subexploration trees are infertile, the exploration is over. In this Section, we suppose that $S_1(x) \setminus S_{1,stop}(x)$ holds. For every fertile tree, we perform an exploration similar to that of Section 5.1 from each vertex of its boundary, and show that with probability at least $1 - n^{-6/5}$, at least one exploration per fertile tree is successful, and hence has a boundary of size $\Theta(n^{1/2}b_n)$ (Proposition 7.3). We illustrate this second phase in Figure 6 below.

Let $T_1, \dots, T_m$ be the fertile subexploration trees for some positive integer $m$. For every $q \in \{1, \dots, m\}$, denote $y_{q,1}, y_{q,2}, \dots$ the vertices of $\partial T_q$. For $q = 1, 2, \dots$ successively, we perform the explorations from $y_{q,i}$, $i \ge 1$ as defined in Section 5.1 (using an array of independent standard normal variables $(\xi_{y_{q,i},k,j})_{k,j \ge 0}$). If $y$ is the $j$-th vertex of the $k$-th generation in the exploration tree of $y_{q,i}$, let recursively

$$ \widehat{\psi}_{M_n}(y) := \frac{\widehat{\psi}_{M_n}(\bar{y})}{d-1} + \sqrt{\frac{d}{d-1}} \xi_{y_{q,i},k,j}, $$

so that $\widehat{\psi}_{M_n}$ plays the role of $\varphi_{T_d}$ on $T_d$ in Section 5.1. We implement three modifications:

* we do not explore towards $\bar{y}_{q,i}$, the parent of $y_{q,i}$ in $T_q$ (hence we generate $\widehat{\psi}_{M_n}$ as the GFF on a subtree of $T_d^+$ instead of $T_d$),

* we do not stop the exploration if $\widehat{\psi}_{M_n}(y_{q,i}) < h + \log^{-1} n$ (we only know a priori from the first phase that $\widehat{\psi}_{M_n}(y_{q,i}) \ge h + n^{-a}$), and

* we stop the exploration if it meets a vertex already discovered in the first phase or during the previous exploration of some $y_{q',j}$ (thus with $q' < q$, or $q' = q$ and $j < i$).

A vertex $y_{q,i}$ whose exploration is successful is **back-spoiled** if one vertex of its exploration is seen later during the exploration of $y_{q',j}$. Let

$$ \mathcal{E}_{4,n} := \{ \exists q \le m, \text{ all successful explorations of } y_{q,1}, y_{q,2}, \dots, \text{ are back-spoiled} \} $$

On $S_2(x) := (S_1(x) \setminus S_{1,stop}(x)) \cap \mathcal{E}_{4,n}^c$, say that the second phase is successful.

**Proposition 7.3.** If $K_{10}$ is large enough (depending only on $d$ and $h$), then for $n$ large enough and every $x \in V_n$,

$$ P_{ann}(S_2(x) \cup S_{1,stop}(x)) \ge 1 - n^{-6/5} \qquad (7.10) $$

*Proof.* Say that $y_{q,i}$ is **spoiled** if it is met during the previous exploration of some $y_{q',j}$. Define $\mathcal{E}_{5,n} := \{\text{at least } \lfloor 1000 \log n \rfloor \text{ vertices are spoiled or back-spoiled}\}$. We claim that for $n$ large enough,

$$ P_{ann}(\mathcal{E}_{5,n}) \le n^{-2}, \qquad (7.11) $$

and for some constant $K_{12} > 0$ (that only depends on $d$ and $h$), for all $q \le m$ and $i \le |\partial T_q|$, for every event $\mathcal{E}_{q,i} \subseteq \{y_{q,i} \text{ is not spoiled}\}$ that is measurable w.r.t. the whole exploration until $y_{q,i-1}$ (or $y_{q-1,|\partial T_{q-1}|}$ if $i = 1$) has been explored:

$$ P_{ann}(\text{the exploration from } y_{q,i} \text{ is successful } | \mathcal{E}_{q,i}) \ge K_{12}. \qquad (7.12) $$

On $\mathcal{E}_{5,n}^c$, there are at least $(K_{10} - 1000) \log n$ non-spoiled vertices on each $\partial T_q$ (and at most $(K_{10} + 1) \log n$ since each step of a subexploration brings less than $\log n$ vertices to $\partial T_q$). And, if more than $\lfloor 1000 \log n \rfloor$ vertices of each $\partial T_q$ are successful, one of them will be successful and not back-spoiled, thus fulfilling the requirement of $S_2(x)$.

By (7.12), if $K_{10}$ is large enough, for $n$ large enough, the probability that no more than $\lfloor 1000 \log n \rfloor$ explorations from $\partial T_q$ are successful is at most
<figure><img src="image_9.png" /><figcaption>Figure 6: Marked vertices are in red. There are four fertile subexploration trees ($T_1$ rooted at $y_1$, $T_2$ rooted at $y_2$, $T_3$ rooted at $x$ and $T_4$ rooted at $y_4$), and two infertile ones. Lightgray areas correspond to the explorations of the $y_{q,i}$'s in the second phase. $y_{2,2}$ is spoiled by $y_{1,2}$. $y_{3,2}$ is back-spoiled by $y_{3,3}$. Each of the subxploration trees will be either included in $C_x^{M_{n,h}}$ or have no common vertex with $C_x^{M_{n,h}}$, depending on the value of $\psi_{M_n}$ on the marked vertices.</figcaption></figure>

$$ \left( \frac{\binom{(K_{10}+1) \log n}{1000 \log n} (1-K_{12})^{(K_{10}-1000) \log n}}{\frac{(K_{10}+1)^{K_{10}+1}}{1000^{1000}(K_{10}-999)^{K_{10}-999}} (1-K_{12})^{K_{10}-1000}} \right)^{\log n} \le n^{-4} $$

by Stirling's formula. Hence by a union bound on $1 \le q \le m$, noticing that $m \le 2K_{11}/K_{10}$ for $n$ large enough by D2, we have:

$$ \mathbb{P}_{ann}((S_2(x) \cup S_{1,stop}(x))^c) \le \mathbb{P}_{ann}(S_1(x)^c) + \mathbb{P}_{ann}(\mathcal{E}_{5,n}^c) + mn^{-4} \le 2n^{-5/4} $$

by Proposition 7.2 and (7.11), and this concludes the proof. Hence, it remains to establish (7.11) and (7.12).

**Proof of (7.11).** Note that by D2, by Remark 5.2 and by (7.3),

less than $n^{1/2} \log^{-1} n$ vertices and half-edges have been seen in the first two phases. (7.13)

In particular, less than $n^{1/2} \log^{-1} n$ edges are built during second phase. Since by D2, we have that $|\{y_{q,i}, q \le m, i \le |\partial T_q|\} \le K_{11} \log n$, each new edge has a probability at most

$$ K_{11} \log n/(n - n^{1/2} \log^{-1} n) \le 2K_{11} n^{-1} \log n $$
to spoil a vertex. Thus, the number of spoiled vertices is stochastically dominated by a random variable $Z \sim \text{Bin}(n^{1/2} \log^{-1} n, 2K_{11}n^{-1} \log n)$. For $n$ large enough,

$$P(Z \ge 10) \le \left( n^{1/2} \log^{-1} n \right) \left( \frac{2K_{11} \log n}{n} \right)^{10} \le n^5 \frac{\log^{20} n}{n^{10}} \le n^{-3}.$$

Moreover, by (2.8) with $k = \lfloor 999 \log n \rfloor$ and $m_0, m_1, m_E, m \le n^{1/2} \log^{-1} n$ due to (7.13),

$$P_{ann}(\text{more than } \lfloor 999 \log n \rfloor \text{ vertices are back-spoiled}) \le n^{-3}.$$

(7.11) follows.

**Proof of (7.12).** By (7.13) and (2.7) with $k = 1$ and $m_0, m_1, m_E, m \le n^{1/2} \log^{-1} n$, for $n$ large enough,

$$P_{ann}(\text{a cycle is created during the exploration from } y_{q,i}) \le \log^{-1} n.$$

The law of $\widehat{\psi_{M_n}}$ on the exploration tree from $y_{q,i}$ is that of $\varphi_{T_d}$ on an isomorphical subtree of $T_d^+$ (and not $T_d$, since we do not explore towards $\overline{y_{q,i}}$), with $\varphi_{T_d}(\circ) = \widehat{\psi_{M_n}}(y_{q,i})$. Denote $\mathcal{L}_\circ^n$ the connected component of $\circ$ in $E_{\varphi_{T_d}}^{\ge h+\log^{-1} n,+} \cup \{\circ\}$, and $\mathcal{Z}_k$ its $k$-th generation for every $k \ge 0$. Then for any event $\mathcal{E}_{q,i} \subseteq \{y_{q,i} \text{ is not spoiled}\}$ that only depends on the exploration before we inspect $y_{q,i}$,

$$P_{ann}(\text{the exploration from } y_{q,i} \text{ is successful} | \mathcal{E}_{q,i}) \ge p_n - \log^{-1} n,$$

where $p_n := \min_{b \ge h+n^{-a}} P_b^{T_d}(\exists k \le \log_{\lambda_h} n, |\mathcal{Z}_k| \ge n^{1/2} b_n)$ (recall that $\widehat{\psi_{M_n}}(y_{q,i}) \ge h + n^{-a}$).

Let $\delta \in (0, h_* - h)$. Clearly, there exists $p' > 0$ such that for $n$ large enough,

$$\min_{b \ge h+n^{-a}} P_b^{T_d}(\exists v \in \mathcal{Z}_1, \varphi_{T_d}(v) \ge h + \delta) > p'$$

For $\varepsilon > 0$ small enough so that $\log_{d-1}(\lambda_{h+\delta} - \varepsilon) \ge (3 \log_{d-1} \lambda_h)/4$ (such $\varepsilon$ exists by continuity of $h' \mapsto \lambda_{h'}$, Proposition 3.3), for $n \in \mathbb{N}$,

$$\begin{align*}
p_n'' &:= \min_{b \ge h+\delta} P_b^{T_d}(\exists k \le \log_{\lambda_h} n - 1, |\mathcal{Z}_k^{h+\log^{-1} n,+}| \ge n^{1/2} b_n) \\
&\ge \min_{b \ge h+\delta} P_b^{T_d}(|\mathcal{Z}_{[\log_{\lambda_h} n]}^{h+\delta,+}| - 1) \ge n^{1/2} b_n) \\
&\ge \min_{b \ge h+\delta} P_b^{T_d}(|\mathcal{Z}_{[\log_{\lambda_h} n]}^{h+\delta,+}| - 1) \ge (\lambda_{h+\delta} - \varepsilon)^{[\log_{\lambda_h} n]} - 1).
\end{align*}$$

By Proposition 3.6, $\liminf_{n \to +\infty} p_n'' =: p'' > 0$. Since $p_n \ge p'p_n''$ for all $n \ge 1$,

$P_{ann}(\text{the exploration from } y_{q,i} \text{ is successful} | y_{q,i} \text{ is not spoiled}) \ge p_n - \log^{-1} n \ge \frac{p'p''}{2}$
for $n$ large enough, and we can take $K_{12} = \frac{p'p''}{2}$. This shows (7.12). $\square$

## 7.4 Third phase

Suppose now that we are on $S_2(x)$. For $1 \le q \le m$, denote $y_q$ one vertex of $\partial T_q$ whose exploration was successful and not back-spoiled in the second phase, $T_{y_q}$ its exploration tree, and $B_q$ the boundary of $T_{y_q}$. In this section, we connect each $B_q$ to $\Theta(n)$ vertices in a fashion similar to Section 6.1. However, revealing the GFF on a positive proportion of the vertices would prevent us to use an approximation of the GFF as in Proposition 4.1.

To circumvent this difficulty, denote $R_{1,2}$ the set of vertices seen in the first two phases, and partition $V_n \setminus R_{1,2}$ arbitrarily in sets $D_1, D_2, \dots, D_r$ for some $r \in \mathbb{N}$ such that

$$|D_1| = |D_2| = \dots = |D_{r-1}| = \lfloor K_{14} \log n \rfloor, \qquad (7.14)$$
for some constant $K_{14} > 0$ to be determined in Proposition 7.4. We will connect each $B_q$ to a positive proportion of the vertices of $D_1$ only, with $P_{ann}$-probability $1 - n^{-3}$ (Proposition 7.4), before revealing the GFF on the vertices of the first two phases, and on the connection from $D_1$ to $B_q$ in Section 7.5. The result will follow by symmetry of the $D_i$'s and a union bound on $1 \le i \le r - 1$.

**The exploration.**

**1) The w-explorations.** Let $w_1, \dots, w_{\lfloor K_{14} \log n \rfloor}$ be the vertices of $D_1$. We proceed successively to the w-explorations of $w_1, w_2, \dots$, i.e. for $i \ge 1$, we perform the exploration from $w_i$ as in Section 5.1, but stop it if we reach a vertex seen in the first two phases or in the w-exploration of some $w_j$, $j \le i - 1$. In particular, if $w_i$ was discovered during the exploration of some $w_j$, $j \le i - 1$, say then that $w_i$ is w-spoiled and do not proceed to its w-exploration. Denote $R_w$ the set of vertices seen during all the w-explorations.

For $i \ge 1$, if we explore $w_i$ and C2 happens, say that the w-exploration from $w_i$ is w-successful. Let $s_0$ be the number of w-successful vertices. Let $w_{i_1}, \dots, w_{i_{s_0}}$ be the w-successful vertices with $i_1 < \dots < i_{s_0}$. Let $T_{w_{i_j}}$ be the exploration tree of $w_{i_j}$, for $j \in \{1, \dots, s_0\}$. Take away

* from each $\partial T_{w_{i_j}}$: the vertices that are seen in the w-exploration of some $w_i$, for $i > i_j$,

* from each $B_q$: the vertices $z$ such that $B_{M_n}(z, \bar{z}, a_n)$ intersects $R_w$.

Say that those vertices are w-back-spoiled.

**2) The joining balls.** For $q = 1, \dots, m$ successively, we develop balls from $B_q$ to the $\partial T_{w_{i_j}}$'s, $1 \le j \le s_0$, with a few modifications w.r.t the construction of Section 6.1.1: let $z_{1,q}, z_{2,q}, \dots$ be the vertices of $B_q$. For $z_{i,q} \in B_q$, let

$$B_{i,q}^* := \cup (i',q'): q' < q \text{ or } q'=q, i' < i B^*(z_{i'},q',a_n'),$$

and let $R_{i,q} := R_{1,2} \cup R_w \cup B_{i,q}^*$ be the vertices seen before building $B^*(z_i, a_n')$.

Replace $B_j^*$, $Q_j$ and $B_{M_n}(T_y, a_n)$ of Section 6.1 by $B_{i,q}^*$, $R_{i,q}$ and $\cup_{j=1}^{s_0} B_{M_n}(T_{w_{i_j}}, a_n)$ respectively.

Say that $B^*(z_{i,q}, a_n')$ is a J-joining ball if it hits $B_{M_n}(T_{w_{i_j}}, a_n)$ at one vertex after $a_n' - 2a_n$ steps, and no other intersection with vertices seen previously is created.

**Proposition 7.4.** For $n$ large enough, we have

$$P_{ann}(S_2(x) \cap \{\exists (J,q), \text{ there are less than } \log^{\gamma-3\kappa-18} n \text{ J-joining balls from } B_q\}) \le n^{-4} \quad (7.15)$$

and if $K_{14}$ is large enough, then for large enough $n$:

$$P_{ann}(S_2(x) \cap \{s_0 \le \log n\}) \le n^{-4}. \quad (7.16)$$

**Proof.** **Proof of (7.15).** We adapt the proof of Lemma 6.1. Since there are less than $\log^2 n$ $w_i$'s (and $|R_{1,2}|$ is controlled by (7.13)), we can replace (6.4) by

$$\text{less than } n^{1/2} \log^{\gamma+2} n \text{ vertices are seen during the three phases.} \quad (7.17)$$

$$\text{Let } B^* := \cup_{q=1}^m \cup_{z \in B_q} B^*(z, a_n'). \quad (6.6) \text{ becomes}$$

$$P_{ann}(S_2(x) \cap \{ |B^* \cap (\cup_{j=1}^{s_0} B_{M_n}(T_{z_{i_j}}, a_n))| \ge \log^{3\gamma} n \}) \le n^{-5} \quad (7.18)$$

Let $N$ be the number of vertices of $\cup_{q=1}^m B_q$ that are spoiled, i.e. the vertices $z$ such that $B^*(z, a_n) = B_{M_n}(z, \bar{z}, a_n)$ is hit by a previously constructed $B^*(z', a_n')$. (6.7) becomes

$$P_{ann}(S_2(x) \cap \{N \ge \log^{3\gamma} n\}) \le n^{-5}. \quad (7.19)$$
$$
\text{In addition, by (2.8) with } k = \log^2 n, m_0 = 1, m_1, m_E, m \le n^{1/2} \log^{-1/2} n,
$$
$$
\mathbb{P}_{ann}(\mathcal{E}_{6,n}) \le n^{-5}, \qquad (7.20)
$$

where $\mathcal{E}_{6,n} := S_2(x) \cap \{\text{more than } \log^2 n \text{ vertices are w-back-spoiled}\}$. Then, define

$$
S_{i,q} := S_2(x) \cap \mathcal{E}_{6,n}^c \cap \left\{ \left( \bigcup_{j=1}^{s_0} B_{M_n}(T_{w_{ij}}, a_n) \right) \cap B_{i,q}^* \mid \log^{3\gamma} n \right\} \cap \{z_{i,q} \text{ is not spoiled}\}.
$$

It is straightforward to adapt the proof of (6.9) to get that for every $1 \le J \le s_0$, the probability that $B^*(z_{i,q}, a'_n)$ is a $J$-joining ball, conditionally on $S_{i,q}$, is at least $n^{-1/2} \log^{\gamma-2\kappa-10} n$. On $S_2(x) \cap \{N \le \log^{3\gamma} n\} \cap \mathcal{E}_{6,n}^c$, at least

$$
n^{1/2}b_n - \log^2 n - \log^{3\gamma} n \ge n^{1/2}[\log^{-\kappa-7} n]
$$

z_{i,q}'s are neither spoiled nor w-back-spoiled by (5.1). As in the end of the proof of Lemma 6.1, if $\gamma > 3\kappa + 18$, we get that for $n$ large enough: for every $(J, q) \in (\{1, \dots, s_0\} \cap \{1, \dots, m\})$ and $Z \sim \text{Bin}(n^{1/2}[\log^{-\kappa-7} n], n^{-1/2} \log^{\gamma-2\kappa-10} n)$:

$$
\mathbb{P}_{ann}(S_2(x) \cap \{\text{there are less than } \log^{\gamma-3\kappa-18} n \text{ J-joining balls from } B_q\})
$$

$$
\le \mathbb{P}_{ann} \left( S_2(x) \cap \left( \left\{ |B^* \cap \left( \cup_{j=1}^{s_0} B_{M_n}(T_{z_{ij}}, a_n) \right)| \ge \log^{3\gamma} n \right\} \cup \{N \ge \log^{3\gamma} n\} \cup \mathcal{E}_{6,n} \right) \right) \\
+ \mathbb{P}(Z \le \log^{\gamma-3\kappa-18} n)
$$

$$
\le 3n^{-5} + \log^{\gamma} n \max_{k \le \log^{\gamma-3\kappa-18} n} \mathbb{P}(Z = k) \text{ by (7.18), (7.19) and (7.20)}
$$

$$
\le 4n^{-5}
$$

as below (6.9). Since $s_0 \le |D_1| \le \log^2 n$ by (7.14) and $m \le K_{11} \log n$ by D2, a union bound
on $(J,q)$ yields (7.15).

**Proof of (7.16).** We now estimate the probability that at most $\log n$ w-explorations are w-successful. Note that by Remark 5.2 and (7.13),

$$
|R_{1,2}| + |R_w| \le n^{1/2} \log^{-1/2} n. \qquad (7.21)
$$

Hence if $C > 0$ is large enough, by (2.8) with $k = \lfloor C \log n \rfloor$ and $m_0, m_1, m_E, m \le n^{1/2} \log^{-1/2} n$,

$$
\mathbb{P}_{ann} (S_2(x) \cap \{\text{more than } C \log n w_i \text{'s are w-spoiled}\}) \le n^{-5}. \quad (7.22)
$$

Moreover, for every $i \ge 1$, conditionally on the fact that $w_i$ is not w-spoiled, the probability that the w-exploration from $w_i$ is stopped because it reaches a vertex of $R_{1,2}$ or a vertex seen in the exploration of some $w_j$, $j < i$ is $o(1)$ by (2.7) with $k = 1$, $m_0 = 1$, $m_1$, $m_E$, $m \le n^{1/2} \log^{-1/2} n$. Hence, a straightforward adaptation of the proof of (5.9) yields

$$
\mathbb{P}_{ann}(\text{the exploration from } w_i \text{ is w-successful} | S_2(x) \cap \{w_i \text{ is not w-spoiled}\}) \ge \eta(h)/2. \tag{7.23}
$$

Take $K_{14} > 3C$. By (7.22), (7.23) and (7.14), if $Z \sim \text{Bin}(\lfloor (K_{14} \log n)/2 \rfloor, \eta(h)/2)$ and $n$ is large enough,

$$
\mathbb{P}_{ann}(S_2(x) \cap \{s_0 \le \log n\}) \le n^{-5} + \mathbb{P}(Z \le \log n).
$$

One checks via Stirling's formula that if $K_{14}$ is large enough, then for large enough $n$,

$$
\begin{align*}
\mathbb{P}(Z \le \log n) &\le 2 \log n \max_{k \le \log n} \mathbb{P}(Z = k) \\
&\le 2 \log n \binom{K_{14} \log n}{\log n} (1 - \eta(h)/2)^{(K_{14}-1) \log n} \\
&\le n^{-5},
\end{align*}
$$

and (7.16) follows.

<figure><img src="image_10.png" /></figure>
## 7.5 Revealing $\psi_{M_n}$ on the three phases

Let $R_1^\psi$ (resp. $R_2^\psi$) be the set of vertices where $\widehat{\psi_{M_n}}$ has been defined during the first (resp. second) phase, and $R_3^\psi$ be the set of vertices in the w-successful w-explorations and on the J-joining balls, for all $1 \le J \le m$, on which we will realize $\psi_{M_n}$ on the third phase.

By Proposition 2.4, we can realize $\psi_{M_n}$ jointly with $M_n$ by

* proceeding to the three phases of the exploration from $x$,

* revealing the remaining pairings of half-edges of the $M_n$,

* defining $\psi_{M_n}$ on $R_1^\psi \cup R_2^\psi$, in the same order as $\widehat{\psi_{M_n}}$ has been defined, using the same standard normal variables: we let

$$ \psi_{M_n}(x) := \widehat{\psi_{M_n}}(x) \sqrt{\frac{d-2}{d-1}} \sqrt{G_{M_n}(x, x)} $$

if $B_{M_n}(x, r_n + \ell)$ has no cycle, and $\psi_{M_n}(x) = \widehat{\psi_{M_n}}(x) \sqrt{G_{M_n}(x, x)/G_{G_m}(u_k, u_k)}$ if it has one cycle $C$, and $d_{M_n}(x, C) = k$. For every $y$, we define the event $A_y := \{z \in V_n, \widehat{\psi_{M_n}}(z)$ was defined before $\widehat{\psi_{M_n}}(y)\}$ and

$$ \psi_{M_n}(y) := E^{M_n}[\psi_{M_n}(y)|\sigma(A_y)] + \xi_y \sqrt{\mathrm{Var}(\psi_{M_n}(y)|\sigma(A_y))}, $$

for every $y \in R_1^\psi$, where $\xi_y$ is the normal variable used when defining $\widehat{\psi_{M_n}}(y)$,

* revealing $\psi_{M_n}$ on $R_3^\psi$, and finally on $V_n \setminus (R_1^\psi \cup R_2^\psi \cup R_3^\psi)$.

Let $\mathcal{E}_{7,n} := \{M_n$ is a good graph$\} \cap \{\max_{z \in V_n} |\psi_{M_n}(z)| \le \log^{2/3} n\}$,
$S_1^\psi(x) := S_1(x) \cap \{\sup_{y \in R_1^\psi} |\psi_{M_n}(y) - \widehat{\psi_{M_n}}(y)| \le n^{-a}/2\}$,
$S_2^\psi(x) := S_2(x) \cap S_1^\psi(x) \cap \{\sup_{y \in R_2^\psi} |\psi_{M_n}(y) - \widehat{\psi_{M_n}}(y)| \le (\log^{-1} n)/2\}$, and
$S_{3,i}^\psi(x) := S_2^\psi(x) \cap (\bigcap_{q=1}^m \text{ at least } \log n \text{ vertices of } D_i \text{ are connected to } T_q \text{ in } E_{\widehat{\psi_{M_n}}(y)}^{\ge h})$ for every $i \ge 1$.

Suppose that for $a > 0$ (defined in the beginning of Section 7.2) small enough (depending only on $d$ and $h$), and for $n$ large enough:

$$ P_{ann}((S_1(x) \setminus S_1^\psi(x)) \cap \mathcal{E}_{7,n}) \le n^{-3}, \qquad (7.24) $$

$$ P_{ann}((S_2(x) \setminus S_2^\psi(x)) \cap \mathcal{E}_{7,n}) \le n^{-3}, \qquad (7.25) $$

and for every $1 \le i \le r - 1$,

$$ P_{ann}((S_2(x) \setminus S_{3,i}^\psi(x)) \cap \mathcal{E}_{7,n}) \le n^{-3}. \qquad (7.26) $$

Letting $S_{1,stop}^\psi(x) := S_{1,stop}(x) \cap S_1^\psi(x)$, (7.24), (7.25), (7.26) and (7.10) imply that

$$ P_{ann}((S_{1,stop}^\psi(x) \cup (\cap_{i=1}^{r-1} S_{3,i}^\psi(x))) \cap \mathcal{E}_{7,n}) \ge 1 - n^{-7/6}. \qquad (7.27) $$

On $S_{1,stop}^\psi(x) \cup (\cap_{i=1}^{r-1} S_{3,i}^\psi(x))$, we have the following alternative:

* either $C_x^{M_n,h}$ contains a subexploration tree $T_q$ whose exploration was fertile, the exploration from $y_q$ is successful and connected to at least $\log n$ vertices of every $D_i$, $1 \le i \le r - 1$ in $E_{\widehat{\psi_{M_n}}(y)}^{\ge h}$;
• or $\mathcal{C}_x^{\mathcal{M}_n,h}$ contains no such tree, and $\mathcal{C}_x^{\mathcal{M}_n,h} \subseteq R_1^\psi$, so that $|\mathcal{C}_x^{\mathcal{M}_n,h}| \le K_0 \log n$, where we take $K_0 \ge K_{11}$.

Note that the second case comprises $S_{1,\text{stop}}^\psi(x)$ but is a priori not included in it: there could exist fertile subexploration trees not connected to $x$ in $E_{\psi_{\mathcal{G}_n}^h}^{\ge h}$ if $\psi_{\mathcal{M}_n}$ is below $h$ on the appropriate marked vertices.

In the first case, $\mathcal{C}_x^{\mathcal{M}_n,h}$ contains at least $\log n$ vertices of each $D_i$, $1 \le i \le r-1$, so that by (7.13) and (7.14) for $n$ large enough:

$$|\mathcal{C}_x^{\mathcal{M}_n,h}| \ge (r-1) \log n \ge \log n \frac{n - |R_{1,2}| - |D_r|}{K_{14} \log n} \ge \frac{n}{2K_{14}}.$$

Letting thus $K_{15} := (2K_{14})^{-1}$, we have on $S_{1,\text{stop}}^\psi(x) \cup (\cap_{i=1}^{r-1} S_{3,i}^\psi(x))$, for every $n$ large enough:

$$|\mathcal{C}_x^{\mathcal{M}_n,h}| \le K_0 \log n \text{ or } |\mathcal{C}_x^{\mathcal{M}_n,h}| \ge K_{15}n.$$

By (7.27) and a union bound on all $x \in V_n$,

$$P_{\text{ann}}(K_0 \log n \le |\mathcal{C}_2^{(n)}| \le K_{15}n) \le n^{-1/6} + P_{\text{ann}}(\mathcal{E}_{7,n}^c).$$

By Remark 6.6, $|\mathcal{C}_2^{(n)}| \le K_{15}n P_{\text{ann}}$-w.h.p. By Proposition 2.1 and Lemma 2.5, we have $P_{\text{ann}}(\mathcal{E}_{7,n}^c) \to 0$ so that

$$P_{\text{ann}}(|\mathcal{C}_2^{(n)}| \le K_0 \log n) \to 1,$$

yielding (1.3). Hence, it remains to show (7.24), (7.25) and (7.26).

### 7.5.1 The field $\psi_{\mathcal{M}_n}$ on the first phase: proof of (7.24)

**Proposition 7.5.** Let $a, K_0, \ell$ be such that Proposition 7.2 holds with $K_{11} = K_0$ and $K_{10}$ as in Proposition 7.3, and such that the conclusion of Lemmas 7.6 and 7.7 hold. Then for $n$ large enough, (7.24) holds.

To prove Proposition 7.5, we need two variants of Proposition 4.1, whose proofs are postponed to the Appendix, Section A.4. The first consists in replacing the “security radius” $a_n = \Theta(\log \log n)$ by $r_n = \Theta(\log n)$.

**Lemma 7.6.** If $a > 0$ is small enough (depending only on $d$ and $h$), then the following holds for $n$ large enough. Assume that $\mathcal{M}_n$ is a good graph, that $A \subset V_n$ satisfies

• $|A| \le n^{2/3}$,

• $\text{tx}(B_{\mathcal{M}_n}(A, r_n)) = \text{tx}(A)$, and

• $\max_{z \in A} |\psi_{\mathcal{M}_n}(z)| \le \log^{2/3} n$.

For every $y \in \partial B_{\mathcal{M}_n}(A, 1)$, writing $\bar{y}$ for the unique neighbour of $y$ in $A$, we have:

$$\left| \mathrm{E}^{\mathcal{M}_n} [\psi_{\mathcal{M}_n}(y) | \sigma(A_y)] - \frac{1}{d-1} \psi_{\mathcal{M}_n}(\bar{y}) \right| \le n^{-2a} \quad (7.28)$$

and

$$\left| \mathrm{Var}^{\mathcal{M}_n} (\psi_{\mathcal{M}_n}(y) | \sigma(A_y)) - \frac{d}{d-1} \right| \le n^{-2a}. \quad (7.29)$$
The second variant of Proposition 4.1 corresponds to Case 1 and Case 2 of the first phase of the exploration. Let us introduce some notations before stating the Lemma. Recall that for $m \ge 3$, $G_m$ is the connected (and infinite) $d$-regular graph with a unique cycle $C_m$ of length $m$. Recall the definitions of $\alpha_k, \beta_k, \gamma_k, \alpha'_k$ and $\gamma'_k$ from (7.5) and (7.6).

For $k \ge 0$, let $z_k$ be a vertex at distance $k$ of the cycle $C_m$ in $G_m$, and $\bar{z}_k$ be a neighbour of $z_k$ at distance $k+1$ of $C_m$. Note that $B_{G_m}(z_k, \bar{z}_k, r_n)$ (the subgraph of $G_m$ obtained by taking all paths of length $r_n$ starting at $z_k$ and not going through $\bar{z}_k$) contains $C_m$ if and only if $k \le r_n - \lfloor m/2 \rfloor$.

**Lemma 7.7.** If $a > 0$ is small enough (depending only on $d$ and $h$), then the following holds for $n$ large enough (uniformly in $m \ge 3$).

Assume that $\mathcal{M}_n$ is a good graph, that $A \subseteq V_n$ is such that

* $|A| \le n^{2/3}$,

* $A$ is a tree, and

* $\max_{z \in A} |\psi_{\mathcal{M}_n}(z)| \le \log^{2/3} n$.

**Case 1.** Let $y \in V_n$, and suppose that

- $y$ has a neighbour $\bar{y}$ in $A$,

- for some $1 \le k < m$, there exists $\hat{y}$ in $A$, a path $P$ of length $m-k$ from $y$ to $\hat{y}$ whose only vertex in $A$ is $\hat{y}$, and a path $P'$ in $A$ of length $k-1$ from $\hat{y}$ to $\bar{y}$, so that $C := P \cup P' \cup (\bar{y}, y)$ is a cycle of length $m$ (and $\hat{y} = \bar{y}$ if $k=1$), and

- $\text{tx}(B_{\mathcal{M}_n}(A \cup C, r_n)) = 1$.

Then

$$|\mathrm{E}^{\mathcal{M}_n}[\psi_{\mathcal{M}_n}(y)|\sigma(A)] - \alpha_k \psi_{\mathcal{M}_n}(\bar{y}) - \beta_k \psi_{\mathcal{M}_n}(\hat{y})| \le n^{-2a} \quad (7.30)$$

and

$$|\mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(y)|\sigma(A)) - \gamma_k| \le n^{-2a}. \quad (7.31)$$

**Case 2.** Let $y \in V_n$, and suppose that

- $y$ has a unique neighbour $\bar{y}$ in $A$,

- for some $1 \le k \le r_n - \lfloor m/2 \rfloor$, $B_{\mathcal{M}_n}(y, \bar{y}, r_n)$ is isomorphic to $B_{G_m}(z_k, \bar{z}_k, r_n)$, and

- $\text{tx}(B_{\mathcal{M}_n}(A \cup P \cup C, r_n)) = 1$, where $C$ is the cycle in $B_{\mathcal{M}_n}(y, \bar{y}, r_n)$ and $P$ the path from $y$ to $C$.

Then

$$|\mathrm{E}^{\mathcal{M}_n}[\psi_{\mathcal{M}_n}(y)|\sigma(A)] - \alpha'_k \psi_{\mathcal{M}_n}(\bar{y})| \le n^{-2a} \quad (7.32)$$

and

$$|\mathrm{Var}^{\mathcal{M}_n}(\psi_{\mathcal{M}_n}(y)|\sigma(A)) - \gamma'_k| \le n^{-2a}. \quad (7.33)$$

**Proof of Proposition 7.5.** We proceed as below (5.9) in the proof of Proposition 5.1. Denote

$$\mathcal{E}_n := \{\exists y \in R_1^\psi, |\psi_{\mathcal{M}_n}(y) - \widehat{\psi_{\mathcal{M}_n}}(y)| \ge n^{-a}\} \cap \mathcal{E}_{7,n} \cap S_1(x).$$

On $\mathcal{E}_n$, $\widehat{\psi_{\mathcal{M}_n}}$ is defined on at most $K_0 \log n$ vertices by D2 (and our choice of $K_{11} = K_0$), so that by the triangle inequality, either $|\widehat{\psi_{\mathcal{M}_n}}(x) - \psi_{\mathcal{M}_n}(x)| \ge n^{-a} \log^{-2} n$, or there exists $y$ such that

$$|\widehat{\psi_{\mathcal{M}_n}}(y) - \psi_{\mathcal{M}_n}(y)| \ge n^{-a} \log^{-2} n + \sup_{\bar{y} \in R_y^\psi} |\widehat{\psi_{\mathcal{M}_n}}(\bar{y}) - \psi_{\mathcal{M}_n}(\bar{y})|,$$
where $R_y^\psi$ is the set of vertices where $\widehat{\psi_{M_n}}$ has been defined before $\widehat{\psi_{M_n}}(y)$. Let

$$ \mathcal{E}(y) := \{ |\widehat{\psi_{M_n}}(y) - \psi_{M_n}(y)| \ge n^{-a} \log^{-2} n + \sup_{\bar{y} \in R_y^\psi} |\widehat{\psi_{M_n}}(\bar{y}) - \psi_{M_n}(\bar{y})| \} \cap \mathcal{E}_n $$

For $y \neq x$, we can apply Lemma 7.7 (if $\widehat{\psi_{M_n}}(y)$ is defined in Case 1 or Case 2) or Lemma 7.6 (in the other cases), so that

$$ P_{ann}(\mathcal{E}(y)) \le P_{ann}(n^{-2a} |\xi_y| \ge n^{-a} \log^{-2} n - n^{-2a}) \le P_{ann}(|\xi_y| \ge n^{a/2}) \le n^{-4} $$

by the exponential Markov inequality, and $P_{ann}(\mathcal{E}(x)) \le n^{-4}$ by the same argument, where we set $\mathcal{E}(x) := \{|\widehat{\psi_{M_n}}(x) - \psi_{M_n}(x)| \ge n^{-a} \log^{-2} n\} \cap \mathcal{E}_n$. For the particular case that there is a cycle $C$ in $B_{M_n}(x, r_n + \ell)$, at distance $k \ge 0$ from $x$, a computation similar to that of the variance in Lemma 7.7 shows that for a small enough (depending on $d$ and $h$ only), $\max_{k \ge 0} |G_{G_m}(u_k, u_k) - G_{M_n}(x, x)| \le n^{-2a}$. Hence, we get by a union bound on $y \in R_1^\psi$ that for large enough $n$,

$$ P_{ann}(\mathcal{E}_n) \le n^{-4} K_0 \log n \le n^{-3}. $$

The conclusion follows. $\square$

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

### 7.5.2 The field $\psi_{M_n}$ on the second phase: proof of (7.25)

It is enough to show that for each $y_{q,i}$ whose exploration in the second phase is successful,

$$ P_{ann} \left( \left\{ \sup_{z \in T_{y_{q,i}}} \setminus \{y_{q,i}\} \mid \widehat{\psi_{M_n}}(z) - \psi_{M_n}(z) \ge \frac{\log^{-1} n}{2} \right\} \cap \mathcal{E}_{7,n} \right) \le n^{-4}, $$

where $T_{y_{q,i}}$ is its exploration tree, and to conclude by a union bound on $y_{q,i}$. This follows from a straightforward adaptation of the reasoning below (5.9). Note that the $n^{-3}$ in the RHS of (5.10) can be replaced by any polynomial in $n$.

### 7.5.3 The field $\psi_{M_n}$ on the third phase: proof of (7.26)

By symmetry, it is enough to consider the case $i = 1$. Following readily the argument of the proof of (6.14), we get that the probability that $E_{\widehat{\psi}_{G_n}}^{\ge h}$ percolates through a given $J$-joining ball is at least $\log^{\gamma(K_8/3-1)} n$, for any $J$. By (7.15) and (7.16), and a union bound on every couple $(J, q) \in \{1, \dots, s_0\} \times \{1, \dots, m\}$,

$$ P_{ann}((S_2(x) \setminus S_{3,1}^\psi(x)) \cap \mathcal{E}_{7,n}) \le 2n^{-4} + s_0 m P(Z = 0), $$

where $Z \sim \text{Bin}(\lfloor \log^{\gamma-3\kappa-18} n \rfloor, \log^{\gamma(K_8/3-1)} n)$. If $\kappa$ and $\gamma/\kappa$ are large enough, then

$$ P(Z = 0) = (1 - \log^{\gamma(K_8/3-1)} n)^{\lfloor \log^{\gamma-3\kappa-18} n \rfloor} \le n^{-4} $$

for $n$ large enough, and (7.26) follows.

# 8 Properties of $C_1^{(n)}$

## 8.1 The local limit: proof of Theorem 1.3

*Proof of Theorem 1.3.* The proof mimics the reasoning of Lemma 6.4. Let $k \ge 0$ and let $T$ be a rooted tree of height $k$, with no vertex of degree more than $d$. Let $x \in V_n$. We perform an exploration as in Section 5.1. Denote $S_T(x)$ the event that the exploration is successful, that $S_T(x) \subseteq C_x^{M_n,h}$ and that $B_{M_n}(x, k)$ is isomorphic to $T$. We claim that

$$ P_{ann}(S_T(x)) \underset{n \to +\infty}{\longrightarrow} P^{T_d}(B_{T_d}(\circ, k) = T, |C_\circ^h| = +\infty). \quad (8.1) $$

The proof goes as those of Lemma 5.3 and Proposition 5.1. In the proof of Lemma 5.3, replace $\mathcal{F}_j^{(n)}$ by $\mathcal{F}_j^{(n)} := \mathcal{F}_j^{(n)} \cap \{B_{C_\circ^h}(\circ, k) = T\}$ and $\mathcal{F}'_j^{(n)}$ by $\mathcal{F}'_j^{(n)} := \mathcal{F}'_j^{(n)} \cup \{B_{C_\circ^h}(\circ, k) \ne T\}$, for every $j \ge 1$. We also check easily that
Anatomy of a Gaussian giant

$$ \mathbb{P}^{\mathbf{T}_d}(\mathcal{C}_{\circ}^{h+\log^{-1} n} \cap B_{\mathbf{T}_d}(\circ, k) = \mathcal{C}_{\circ}^{h-\log^{-1} n} \cap B_{\mathbf{T}_d}(\circ, k)) \to 1 $$

in order to determine $B_{M_n}(x, k) \mathbb{P}_{ann}$-w.h.p., as Proposition 5.1 only ensures that we have w.h.p. the inclusion $\mathcal{C}_{\circ}^{h+\log^{-1} n} \cap B_{\mathbf{T}_d}(\circ, k) \subseteq B_{M_n}(x, k)$. Moreover, we get as for (6.21):

$$ \sup_{x,y \in V_n} |\mathrm{Cov}_{ann}(S_T(x), S_T(y))| \underset{n \to +\infty}{\longrightarrow} 0. \qquad (8.2) $$

Let $\varepsilon > 0$. Applying Bienaymé-Chebyshev's inequality as in Lemma 6.4, we get

$$ \mathbb{P}_{ann}(|S_T| - \mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty)n| \le \varepsilon n) \underset{n \to +\infty}{\longrightarrow} 1, \qquad (8.3) $$

where $S_T$ is the set of vertices $x \in V_n$ such that $S_T(x)$ holds. Let $S \subset V_n$ be the set of vertices such that their exploration is successful. By Theorem 1.1 and a reasoning as in the proof of Lemma 6.4, with $\mathbb{P}_{ann}$-probability $1-o(1)$,

$$ (i) \quad |\mathcal{C}_2^{(n)}| \le n^{1/3}, \text{ so that } S_T \subseteq S \cap \mathcal{C}_1^{(n)}, $$

$$ (ii) \quad |\mathcal{C}_1^{(n)}| - \eta(h)n \le \varepsilon n, $$

$$ (iii) \quad |S| - \eta(h)n \le \varepsilon n. $$

By (i), $S_T = S \cap V_n^{(T)}$. Thus, $|S_T| \le |V_n^{(T)}| \le |S_T| + |\mathcal{C}_1^{(n)} \cap S^c|$, so that by (ii), (iii) and (8.3),

$$ (\mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty) - \varepsilon)n \le |V_n^{(T)}| \le (\mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty) + 3\varepsilon)n. $$

Moreover, $|\mathcal{C}_1^{(n)}| - \eta(h)n \le \varepsilon n$ by (ii), so that for $\varepsilon$ small enough,

$$ \frac{\mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty)}{\eta(h)} - \sqrt{\varepsilon} \le \frac{|V_n^{(T)}|}{|\mathcal{C}_1^{(n)}|} \le \frac{\mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty)}{\eta(h)} + \sqrt{\varepsilon}. $$

Since $\eta(h) = \mathbb{P}^{\mathbf{T}_d}(|\mathcal{C}_{\circ}^h| = +\infty)$, we have

$$ \frac{\mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T, |\mathcal{C}_{\circ}^h| = +\infty)}{\eta(h)} = \mathbb{P}^{\mathbf{T}_d}(B_{\mathbf{T}_d}(\circ, k) = T | \mathcal{C}_{\circ}^h| = +\infty). $$

And since we can take $\varepsilon$ arbitrarily small, the conclusion follows. $\square$

## 8.2 The core and the kernel: proof of (1.4) and (1.5)

We now prove (1.4) and (1.5) of Theorem 1.2, starting with (1.4). Let $K_1$ (resp. $K_2$) be the probability that $\circ$ has at least 2 (resp. 3) children with an infinite offspring in $\mathcal{C}_{\circ}^h$, under $\mathbb{P}^{\mathbf{T}_d}$. Then (1.4) follows by a second moment argument as in Lemma 6.4 once we show that for $x, y \in V_n$,

$$ \mathbb{P}_{ann}(x \in \mathbf{C}^{(n)}) \underset{n \to +\infty}{\longrightarrow} K_1, \text{ and} \qquad (8.4) $$

$$ \mathrm{Cov}_{ann}(\mathbf{1}_{x \in \mathbf{C}^{(n)}}, \mathbf{1}_{y \in \mathbf{C}^{(n)}}) \underset{n \to +\infty}{\longrightarrow} 0. \qquad (8.5) $$

*Proof of (8.4).* We proceed in three steps: first, we show that with probability $\simeq K_1$, the exploration of Section 5.1 is successful for two children of $x$. Second, we prove that some vertex $w$ is connected to these two explorations, forming a cycle with $x$. Third, we adapt the lower exploration of Section 5.2 to show reciprocally that $x$ is not in $\mathbf{C}^{(n)}$ with probability $\gtrsim 1 - K_1$.

**First step.** For $x \in V_n$, we perform the exploration in Section 5.1 from $x$, replacing C2 by the following condition: for every neighbour $v$ of $x$, stop exploring the subtree from $v$
at step $k+1$ if the $k$-offspring of $v$ has at least $n^{1/2}b_n$ vertices. Stop the exploration if this happens for at least two neighbours of $x$. In this case, say that the exploration is successful.

We adapt easily the proofs of Lemma 5.3 and Proposition 5.1 to show that for $x \in V_n$,

$$ \mathbb{P}_{ann}(\text{the exploration from } x \text{ is successful}) \underset{n \to +\infty}{\longrightarrow} K_1. \qquad (8.6) $$

Indeed, $K_1$ is the probability that the realization of $\varphi_{T_d}$ to which we couple $\psi_{\mathcal{M}_n}$ is such that $\circ$ has at least two children with an infinite offspring. Then, as in Lemma 5.3, there is a probability $1-o(1)$ that the offspring of these children grows at an exponential rate close to $\lambda_h$ (Proposition 3.6). Thus, letting

$$ \mathcal{F}_{v,k}^{(n)} := \bigcup_{1 \le j \le k} \{\text{the } j\text{-offspring of } v \text{ has at least } n^{1/2}b_n \text{ vertices}\} $$

for every child $v$ of $\circ$, and $\mathcal{F}_{\text{core},k}^{(n)} := \bigcup_{v_1,v_2 \text{ children of } \circ} (\mathcal{F}_{v_1,k-1}^{(n)} \cap \mathcal{F}_{v_2,k-1}^{(n)})$, we get that

$$ \mathbb{P}_{ann}(\bigcup_{1 \le k \le \lfloor \log_{\lambda_h} n \rfloor} \mathcal{F}_{\text{core},k}^{(n)}) \underset{n \to +\infty}{\longrightarrow} K_1, \text{ and} $$

$$ \mathbb{P}_{ann}(\bigcup_{1 \le k \le \lfloor \log_{\lambda_h} n \rfloor} \{\text{at most one child of } \circ \text{ has a non-empty } k\text{-offspring}\}) \underset{n \to +\infty}{\longrightarrow} 1 - K_1. $$

As for (5.8), we do not meet any cycle with $\mathbb{P}_{ann}$-probability $1-o(1)$. This yields (8.6). **Second step.** If the exploration from $x$ is successful, let $x_1, x_2$ be two children of $x$ such that the exploration subtrees $T_{x_1}$ and $T_{x_2}$ from $x_1$ and $x_2$ satisfy $\min(|\partial T_{x_1}|, |\partial T_{x_2}|) \ge n^{1/2}b_n$. Then, let $K > 0$ and let $w_1, \dots, w_{\lfloor K \log n \rfloor} \in V_n$ be vertices that have not been met in the exploration from $x$. Proceed to their $w$-exploration as described in the first part of the construction in Section 7.4. By Remark 5.2, $o(\sqrt{n})$ vertices are seen during the exploration from $x$ and the $w$-explorations. By (2.7) with $k = 1, m_0, m_1, m_E, m = o(\sqrt{n})$, with $\mathbb{P}_{ann}$-probability $1-o(1)$, no $w$-exploration intersects the exploration from $x$, and no $w_i$ is spoiled or back-spoiled.

As in (7.23), we get that for each $w_i$, its $w$-exploration has probability at least $\eta(h)/2$ to be $w$-successful. Hence with $\mathbb{P}_{ann}$-probability at least $1 - (1 - \eta(h)/2)^{\lfloor K \log n \rfloor} = 1 - o(1)$, there exists $i_0$ such that the $w$-exploration from $w_{i_0}$ is successful. Denote $\partial T_{w_{i_0}}$ the boundary of its exploration tree. Write

$$ S_{\text{core}}(x) := \{\text{the exploration from } x \text{ is successful}\} \cap \{\exists i_0 \ge 1, \text{ the } w\text{-exploration from } w_{i_0} \text{ is successful}\}. $$

We have just shown that

$$ \liminf_{n \to +\infty} \mathbb{P}_{ann}(S_{\text{core}}(x)) \ge \liminf_{n \to +\infty} \mathbb{P}_{ann}(\text{the exploration from } x \text{ is successful}) \ge K_1. \quad (8.7) $$

Next, we grow joining balls from $\partial T_{x_1}$ to $\partial T_{w_{i_0}}$, and then from $\partial T_{x_2}$ to $\partial T_{w_{i_0}}$. We proceed as in the second part of the construction in Section 7.4 with $m = 2$ and $s_0 = 1$. Similarly to (7.15), we get that

$$ \mathbb{P}_{ann}(S_{\text{core}}(x) \cap (S_{\text{core, joining},1} \cup S_{\text{core, joining},2})) = o(1), $$

with $S_{\text{core, joining},i} := \{\text{ there are less than } \log^{\gamma-3\kappa-18} n \text{ joining balls from } \partial T_{x_i} \text{ to } \partial T_{w_{i_0}} \}$, for $i = 1, 2$.

Finally, we reveal $\psi_{\mathcal{M}_n}$ on the exploration from $x$, on the $w$-exploration from $w_{i_0}$, on the joining balls from $\partial T_{x_1}$ to $\partial T_{w_{i_0}}$, and on the joining balls from $\partial T_{x_2}$ to $\partial T_{w_{i_0}}$, in that order. Denote $S_{\text{core, connect}}$ the event that there exists a joining ball $B_1$ from $\partial T_{x_1}$ to $\partial T_{w_{i_0}}$ and another $B_2$ from $\partial T_{x_2}$ to $\partial T_{w_{i_0}}$ such that $\min_{y \in T_{x_1} \cup T_{x_2} \cup T_{w_{i_0}} \cup B_1 \cup B_2} \psi_{\mathcal{M}_n}(y) \ge h$. As in the proof of Proposition 6.2, we get that $\mathbb{P}_{ann}(S_{\text{core}}(x) \cap S_{\text{core, connect}}^c) = o(1)$. Hence
$$
\begin{align*}
\liminf_{n \to +\infty} \mathbb{P}_{ann}(x, x_1, x_2, z \text{ are in a cycle of } \mathcal{C}_x^{\mathcal{M}_n} \text{ and } |\mathcal{C}_x^{\mathcal{M}_n}| \ge n^{1/3}) & \\
\ge \liminf_{n \to +\infty} \mathbb{P}_{ann}(\mathcal{S}_{core}(x)).
\end{align*}
$$

If $|C_2^{(n)}| < n^{1/3}$, this cycle is in $C_1^{(n)}$, and thus in $C^{(n)}$ so that by (1.3), for large enough $n$ and any $x \in V_n$, one has by (8.7):

$$
\liminf_{n \to +\infty} \mathbb{P}_{ann}(x \in \mathbf{C}^{(n)}) \geq \liminf_{n \to +\infty} \mathbb{P}_{ann}(\mathcal{S}_{core}(x)) \geq K_1.
$$

**Third step.** For $x \in V_n$, turn the exploration into a lower exploration, replacing $h + \log^{-1} n$ by $h - \log^{-1} n$ (as in Section 5.2). Say that the lower exploration from $x$ is aborted if for some $k \le \log \log n$, at most one child of $x$ has a non-empty $(k-1)$-offspring. Let $\mathcal{A}_{core}(x) := \{\text{the lower exploration from } x \text{ is aborted}\}$. We get as in the proof of (8.6):

$$
\mathbb{P}_{ann}(\mathcal{A}_{core}(x)) \underset{n \to +\infty}{\longrightarrow} 1 - K_1. \qquad (8.8)
$$

Moreover, revealing $\psi_{M_n}$ on $T_x$, we can apply Proposition 4.1 as below (5.9) to get
that

$$
\mathbb{P}_{ann}(\mathcal{A}_{core}(x) \cap \{C_x^{M_n,h} \cap B_{M_n}(x, [\log \log n]) \subseteq T_x\}) \underset{n \to +\infty}{\longrightarrow} 1 - K_1. \quad (8.9)
$$

For each neighbour $y$ of $x$, denote $C_y$ its connected component in $C_x^{M_n} \setminus \{x\}$. If the exploration is aborted and $C_x^{M_n,h} \cap B_{M_n}(x, [\log \log n]) \subseteq T_x$, then $x$ has at most one neighbour $y$ such that $C_y \cup \{x\}$ is not a tree and $x \notin C^{(n)}$. Thus $\liminf_{n \to +\infty} \mathbb{P}_{ann}(x \notin C^{(n)}) \ge 1 - K_1$ and (8.4) follows. $\square$

Proof of (8.5). By (8.4), for $x, y \in V_n$,

$$
\mathbb{P}_{ann}(x \in \mathbf{C}^{(n)}) \mathbb{P}_{ann}(y \in \mathbf{C}^{(n)}) \xrightarrow{n \to +\infty} K_1^2.
$$

It remains to show that $\mathbb{P}_{ann}(x, y \in \mathbf{C}^{(n)}) \xrightarrow{n \to +\infty} K_1^2$.

Perform the exploration from $x$ as in the beginning of the proof of (8.4), then do the same from $y$ (and stop the latter if it reaches a vertex of the exploration from $x$). Since $o(\sqrt{n})$ vertices are revealed during these explorations (see Remark 5.2), then by (2.7), the probability that the exploration from $y$ meets that of $x$ is $o(1)$. Thus by (8.6),

$$
\mathbb{P}_{ann}(\text{the explorations from } x \text{ and } y \text{ are both successful}) \xrightarrow{n \to +\infty} K_1^2.
$$

Then, let $x_1, x_2$ (resp. $y_1, y_2$) be the children of $x$ (resp. $y$) whose exploration is successful. We complete the exploration in a fashion similar to that above (8.7). Let $K > 0$ and let $w_1, \dots, w_{\lfloor K \log n \rfloor} \in V_n$ be vertices that have not been met in the explorations from $x$ and $y$, and proceed to their $w$-exploration. If there exists $i_0 \ge 1$ such that the $w$-exploration from $w_{i_0}$ is successful, build joining balls from $\partial T_{x_1}, \partial T_{x_2}, \partial T_{y_1}$ and $\partial T_{y_2}$ to $T_{w_{i_0}}$. Finally, reveal $\psi_{M_n}$ on $T_x$, on $T_y$, on $T_{w_{i_0}}$ and on the joining balls from $\partial T_{x_1}, \partial T_{x_2}, \partial T_{y_1}$ and $\partial T_{y_2}$, in that order. As in the proof of (8.7) and below, we get that

$$
\liminf_{n \to +\infty} \mathbb{P}_{ann}(x, y \in \mathbf{C}^{(n)}) \geq K_1^2. \qquad (8.10)
$$

Conversely, if we perform the lower explorations from $x$ and $y$ as defined in the end of the proof of (8.4), we easily get that

$$
\mathbb{P}_{ann}(\exists z \in \{x, y\}, \text{ the lower exploration from } z \text{ is aborted}) \xrightarrow{n \to +\infty} 1 - K_1^2.
$$

Then, we reveal $\psi_{M_n}$ on $T_z$. Following the reasoning below (5.9), we get that $\mathbb{P}_{ann}$-w.h.p., $B_{C_z^{M_n,h}}(z, [\log \log n]) \subseteq T_z$, and thus

$$
\mathbb{P}_{ann}(\{\text{the lower exploration from } z \text{ is aborted}\} \cap \{z \in \mathbf{C}^{(n)}\}) = o(1).
$$
This yields

$$ \liminf_{n \to +\infty} \mathbb{P}_{ann}(\exists z \in \{x, y\}, z \notin C^{(n)}) \ge 1 - K_1^2. $$

Together with (8.10), this concludes the proof. □

This reasoning can be readily adapted to prove (1.5), with a modification of the exploration (requiring that at least three children of $x$ have a successful exploration).

## 8.3 The typical distance: proof of (1.7)

The proof of (1.7) goes as that of (1.2), with a slight modification of the explorations of Section 5. Those explorations were indeed stopped after at most $\log_{\lambda_h} n$ steps. But since around $\sqrt{n}$ vertices were explored, and since the growth rate of $C_\circ^h$ is close to $\lambda_h$, we can expect that a successful exploration lasts in fact $(1/2 + o(1)) \log_{\lambda_h} n$ steps. Then, connecting two such explorations as in Proposition 6.2 (adding an additional distance $\Theta(\log \log n) = o(\log n)$) yields the typical distance (reciprocally, explorations lasting less steps will be too small to be connected).

**Proof of (1.7).** Fix $\varepsilon \in (0, 1)$.

**Upper bound.** In the exploration of Section 5.1, replace C4 by the following condition: stop the exploration if $k \ge (1/2 + \varepsilon/3) \log_{\lambda_h} n$. By Proposition 3.6,

$$ \lim_{n \to +\infty} \mathbb{P}^{\mathbb{T}_d} \left( \left| \mathcal{Z}_{\lfloor (1/2+\varepsilon/3) \log_{\lambda_h} n \rfloor}^{h+\log^{-1} n} \right| > n^{1/2} b_n \middle| \left| \mathcal{C}_{\circ}^{h+\log^{-1} n} \right| = +\infty \right) = 1. $$

Thus, Propositions 5.1, 6.2 and Lemma 6.5 remain unchanged. And if $x, y$ are connected in $E_{\psi_{\mathcal{G}_n}}^{\ge h}$ via successful explorations from $x$ and $y$ and joining balls from $\partial T_x$ to $\partial T_y$, then

$$ d_{E_{\psi_{\mathcal{G}_n}}^{\ge h}} (x, y) \le 2(1/2 + \varepsilon/3) \log_{\lambda_h} n + a'_n \le (1 + \varepsilon) \log_{\lambda_h} n $$

for $n$ large enough. Then, Lemma 6.5 implies that

$$ \mathbb{P}_{ann}(\mathcal{E}_{1,n}) \xrightarrow{n \to +\infty} 1, $$

$$ \text{where } \mathcal{E}_{1,n} := \left\{ \left| \left\{ (x, y) \in V_n^2, d_{E_{\psi_{\mathcal{G}_n}}^{\ge h}} (x, y) \le (1 + \varepsilon) \log_{\lambda_h} n \right\} \right| \ge (\eta(h)^2 - \varepsilon)n^2 \right\}. $$

We have to check that only $o(n^2)$ of the couples $(x, y)$ described in $\mathcal{E}_{1,n}$ are not in $C_1^{(n)}$, and that $|C_1^{(n)}|/n$ is indeed close to $\eta(h)$. Note that by (1.2) and (1.3),

$$ \mathbb{P}_{ann}(\mathcal{E}_{1,n} \cap \mathcal{E}_{2,n} \cap \mathcal{E}_{3,n}) \xrightarrow{n \to +\infty} 1, $$

$$ \text{where } \mathcal{E}_{2,n} := \{\forall i \ge 2, |C_i^{(n)}| \le K_0 \log n\} \text{ and } \mathcal{E}_{3,n} := \{(\eta(h) - \varepsilon)n \le |C_1^{(n)}| \le (\eta(h) + \varepsilon)n\}. $$

On $\mathcal{E}_{2,n}$, we have $|\{(x, y) \in V_n^2 \setminus (C_1^{(n)})^2, d_{E_{\psi_{\mathcal{G}_n}}^{\ge h}}(x, y) \le (1 + \varepsilon) \log_{\lambda_h} n\}| \le n^{3/2}$, so that on $\mathcal{E}_{1,n} \cap \mathcal{E}_{2,n}$,

$$ |\{(x, y) \in (C_1^{(n)})^2, d_{C_1^{(n)}}(x, y) \le (1 + \varepsilon) \log_{\lambda_h} n\}| \ge (\eta(h)^2 - 2\varepsilon)n^2. $$

Thus, on $\mathcal{E}_{1,n} \cap \mathcal{E}_{2,n} \cap \mathcal{E}_{3,n}$:

$$ \begin{aligned} \pi_{2,n} \left( \left\{ (x, y) \in (C_1^{(n)})^2, d_{C_1^{(n)}}(x, y) \le (1 + \varepsilon) \log_{\lambda_h} n \right\} \right) & \ge \frac{\eta(h)^2 - 2\varepsilon}{(\eta(h) + \varepsilon)^2} \ge 1 - \frac{2\varepsilon + 2\eta(h)\varepsilon + \varepsilon^2}{(\eta(h) + \varepsilon)^2} \\ & \ge 1 - \frac{(3 + 2\eta(h))}{\eta(h)^2} \varepsilon. \end{aligned} $$
**Lower bound.** It remains to show that the typical distance in $C_1^{(n)}$ is at least $(1-\varepsilon) \log_{\lambda_h} n$. Modify the lower exploration of Section 5.2 by saying that it is aborted if

* C1 did not happen, and

* it is stopped at some step $k \le (1/2 - \varepsilon/2) \log_{\lambda_h} n$, or less than $n^{1/2-\varepsilon/10}$ vertices and half-edges have been seen at step $\lfloor(1/2 - \varepsilon/2) \log_{\lambda_h} n \rfloor$.

By Lemma 8.1 below,

$$ \mathbb{P}_{ann}(\text{the lower exploration from } x \text{ is aborted}) = 1 - o(1). \quad (8.11) $$

For $x, y \in V_n$, perform the lower exploration from $x$, then that from $y$, and stop it if it meets a vertex of the exploration from $x$. This happens with $\mathbb{P}_{ann}$-probability $o(1)$ by (2.7) with $k = 1, m_0, m_1, m, m_E = o(\sqrt{n})$ (recall Remark 5.2). Hence by (8.11):

$$ \mathbb{P}_{ann}(\mathcal{E}_{ab}(x, y)) = 1 - o(1), \text{ with} \\ \mathcal{E}_{ab}(x, y) := \{\text{the lower explorations from } x \text{ and } y \text{ are aborted}\}, $$

Then, reveal $\psi_{M_n}$ on the exploration trees $T_x$ and $T_y$. Applying Proposition 4.1 as below (5.9), we get that:

$$ \mathbb{P}_{ann}(\mathcal{E}_{ab}(x, y) \cap \mathcal{E}_x \cap \mathcal{E}_y) = 1 - o(1), $$

$$ \text{with } \mathcal{E}_z := \{B_{C_z^{M_n, h}}(z, \lfloor(1/2 - \varepsilon/2) \log_{\lambda_h} n \rfloor) \subseteq T_z\} \text{ for } z \in \{x, y\}. $$

On $\mathcal{E}_{ab}(x, y) \cap \mathcal{E}_x \cap \mathcal{E}_y$, if $x, y \in C_1^{(n)}$, then $d_{C_1^{(n)}}(x, y) \ge (1-\varepsilon) \log_{\lambda_h} n$. Therefore, for every $x, y \in V_n$, $\mathbb{P}_{ann}(\mathcal{E}_{x,y}) = o(1)$, with

$$ \mathcal{E}_{x,y} := \{x, y \in C_1^{(n)}, d_{C_1^{(n)}}(x, y) < (1 - \varepsilon) \log_{\lambda_h} n\}. $$

Similarly, for all distinct $x, y, z, t \in V_n$, we get that $\mathbb{P}_{ann}(\mathcal{E}_{x,y} \cap \mathcal{E}_{z,t}) = o(1)$, so that

$$ \mathrm{Cov}_{ann}(\mathbf{1}_{\mathcal{E}_{x,y}}, \mathbf{1}_{\mathcal{E}_{z,t}}) = o(1). $$

Thus by Bienaymé-Chebyshev's inequality,

$$ \mathbb{P}_{ann}(\mathcal{E}_{3,n} \cap \{|\{(x, y) \in V_n^2, d_{C_1^{(n)}}(x, y) \le (1 - \varepsilon) \log_{\lambda_h} n\}| \ge \varepsilon n^2\}) \xrightarrow{n \to +\infty} 1. $$

For $\varepsilon > 0$ small enough and $n$ large enough, on

$$ \mathcal{E}_{3,n} \cap \{|\{(x, y) \in V_n^2, d_{C_1^{(n)}}(x, y) \le (1 - \varepsilon) \log_{\lambda_h} n\}| \ge \varepsilon n^2\}, $$

$$ \pi_{2,n} \left( \left\{ (x, y) \in (C_1^{(n)})^2, d_{C_1^{(n)}}(x, y) \le (1 - \varepsilon) \log_{\lambda_h} n \right\} \right) \le \frac{2\varepsilon}{\eta(\bar{h})^2}. \text{ This concludes the proof of (1.7).} \quad \square $$

It remains to establish the lemma below.

**Lemma 8.1.** We have

$$ \lim_{n \to \infty} \mathbb{P}_{ann}(\text{the lower exploration from } x \text{ is aborted}) = 1. $$

*Proof.* Note first that $\mathbb{P}_{ann}(\text{C1 happens}) = o(1)$ by (2.7) with $k = 1, m_0 = 1, m_E = 0$ and $m = o(\sqrt{n})$ by Remark 5.2. Therefore, it is enough to prove that

$$ \mathbb{P}^{\mathbb{T}_d}(|B_{C_0^{h-\log^{-1}n}}(0, \lfloor(1/2 - \varepsilon/2) \log_{\lambda_h} n \rfloor + a_n)| < n^{1/2-\varepsilon/8}) \to 1, $$
since if this event happens, less than $n^{1/2-\epsilon/10}$ vertices and half-edges have been seen at step $\lfloor(1/2 - \epsilon/2) \log_{\lambda_h} n\rfloor$. By (4.1), it suffices to show that

$$ \mathbb{P}^{\mathrm{T}_d}(|B_{C_o^{h-\log^{-1} n}}(\circ, \lfloor(1/2 - \epsilon/2) \log_{\lambda_h} n\rfloor)| < n^{1/2-\epsilon/7}) \to 1, \quad (8.12) $$

To do so, we first prove that for $n$ large enough and every $\log \log n \le k \le (1/2 - \epsilon/2) \log_{\lambda_h} n$,

$$ \mathbb{P}^{\mathrm{T}_d}(|\mathcal{Z}_k^{h-\log^{-1} n}| \ge n^{1/2-\epsilon/6}) \le e^{-Ck} + n^{-3}. \quad (8.13) $$

Let $\delta > 0$ such that $\lambda_h \le \lambda_{h-\delta} \le \lambda_h + \epsilon/10$ ($h' \mapsto \lambda_{h'}$ being continuous, Proposition 3.3). Since $\mathcal{Z}_k^{h-\log^{-1} n} \subseteq \mathcal{Z}_k^{h-\delta}$ for $n$ large enough and all $k$, a direct computation shows that

$$ \mathbb{P}_a^{\mathrm{T}_d}(|\mathcal{Z}_k^{h-\log^{-1} n}| \ge n^{1/2-\epsilon/5}\chi_{h-\delta}(a)) \le \mathbb{P}_a^{\mathrm{T}_d}(\log|\mathcal{Z}_k^{h-\delta}| \ge \lambda_{h-\delta}(1+\epsilon/5)k + \log \chi_{h-\delta}(a)). $$

Then by Proposition 3.6, there exists $C > 0$ (depending on $\epsilon$) such that for $n$ large enough, for every $\log \log n \le k \le (1/2 - \epsilon/2) \log_{\lambda_h} n$ and $a \ge h$,

$$ \mathbb{P}_a^{\mathrm{T}_d}(|\mathcal{Z}_k^{h-\log^{-1} n}| \ge n^{1/2-\epsilon/5}\chi_{h-\delta}(a)) \le e^{-Ck}. $$

By Proposition 2.1 of [4], there exists $c > 0$ such that for all $h' \le h_*$ and $a \ge d - 1$, one has $\chi_{h'}(a) \le ca^{1-\log_{d-1} h'} \le ca$. Since $\chi_{h'}$ is continuous on $[h, +\infty)$ (Lemma A.1), we have for $n$ large enough $\max_{h \le a \le \log^2 n} \chi_{h-\delta}(a) < n^{\epsilon/30}$, so that

$$ \mathbb{P}^{\mathrm{T}_d}(|\mathcal{Z}_k^{h-\log^{-1} n}| \ge n^{1/2-\epsilon/6}) \le e^{-Ck} + \mathbb{P}^{\mathrm{T}_d}(\varphi_{\mathrm{T}_d}(\circ) \ge \log^2 n) $$

Using the exponential Markov inequality as in Lemma 2.5, we get $\mathbb{P}^{\mathrm{T}_d}(\varphi_{\mathrm{T}_d}(\circ) \ge \log^2 n) \le n^{-3}$. This yields (8.13). Then, for $n$ large enough, this implies

$$ \begin{aligned} & \mathbb{P}^{\mathrm{T}_d}(|B_{C_o^{h}}(\circ, \lfloor(1/2 - \epsilon/2) \log_{\lambda_h} n\rfloor)| \ge n^{1/2-\epsilon/7}) \\ & \le \mathbb{P}^{\mathrm{T}_d}(\exists k \in [\log \log n, (1/2 - \epsilon/2) \log_{\lambda_h} n], |\mathcal{Z}_k^{h-\log^{-1} n}| \ge n^{1/2-\epsilon/6}) \\ & \le \sum_{k=\lfloor \log \log n \rfloor}^{\lfloor(1/2 - \epsilon/2) \log_{\lambda_h} n\rfloor} (e^{-Ck} + n^{-3}) \\ & \le 1/\log \log n. \end{aligned} $$

(8.12) and the conclusion follow. □

## 8.4 The diameter: proof of (1.6)

Recall that $D_1^{(n)}$ is the diameter of $C_1^{(n)}$. In Section 7, we have in fact proven that there exists a constant $K_{16} > 0$ such that for $\mathcal{E}_n := \{\forall x \in C_1^{(n)}, |B_{C_1^{(n)}}(x, \lfloor K_{16} \log n \rfloor)| \ge K_{15}n\}$, we have

$$ \mathbb{P}_{ann}(\mathcal{E}_n) \xrightarrow{n \to +\infty} 1. $$

Namely, one can take $K_{16} = K_0 + 3\log^{-1} \lambda_h$.

Hence it is enough to show that on $\mathcal{E}_n$, $D_1^{(n)} \le 6K_{12}^{-1}K_{13} \log n$, which will imply (1.6). We do this by a short deterministic argument.

Let $x_1 \in C_1^{(n)}$. If $\partial B_{C_1^{(n)}}(x_1, 2\lfloor K_{16} \log n \rfloor + 1) = \emptyset$, then $D_1^{(n)} \le 4K_{16} \log n + 2$.

Else, let $x_2 \in \partial B_{C_1^{(n)}}(x_1, 2\lfloor K_{16} \log n \rfloor + 1)$. For $i = 1, 2$, we have

$$ |B_{C_1^{(n)}}(x_i, \lfloor K_{16} \log n \rfloor)| \ge K_{15}n \text{ and } B_{C_1^{(n)}}(x_i, \lfloor K_{16} \log n \rfloor) \subseteq B_{C_1^{(n)}}(x_1, 4\lfloor K_{16} \log n \rfloor). $$
Moreover, $B_{C_1^{(n)}}(x_1, \lfloor K_{16} \log n \rfloor) \cap B_{C_1^{(n)}}(x_2, \lfloor K_{16} \log n \rfloor) = \emptyset$. Thus, we have

$$|B_{C_1^{(n)}}(x_1, 4\lfloor K_{16} \log n \rfloor)| \geq 2K_{15}n.$$

For $i \geq 2$, if $\partial B_{C_1^{(n)}}(x_1, (3i-4)\lfloor K_{16} \log n \rfloor + 1) = \emptyset$, then $D_1^{(n)} \leq 2(3i-4)K_{16} \log n + 2$. Else, let $x_i \in \partial B_{C_1^{(n)}}(x_1, (3i-4)\lfloor K_{16} \log n \rfloor + 1)$. As for $i=2$, we get that

$$|B_{C_1^{(n)}}(x_1, (3i-2)\lfloor K_{16} \log n \rfloor)| - |B_{C_1^{(n)}}(x_1, (3i-5)\lfloor K_{16} \log n \rfloor)| \geq |B_{C_1^{(n)}}(x_i, K_{16} \log n)| \\ \geq K_{15}n.$$

Since $|V_n| = n$, $\partial B_{C_1^{(n)}}(x_1, (3i_0 - 4)\lfloor K_{16} \log n \rfloor + 1) = \emptyset$ for some $i_0 \leq K_{15}^{-1}$, and

$$D_1^{(n)} \leq 6K_{15}^{-1}K_{16} \log n.$$

This shows (1.6).

# A Appendix

## A.1 Proof of Proposition 2.1

*Proof of Proposition 2.1.* By Theorem 1 of [8], there exists $c = (d) > 0$ such that $M_n$ has an expansion ratio at least $c(d)$ w.h.p., and thus satisfies (I) with $K_3 = (c(d)/d)^2/2$ by the Cheeger bound (see for instance Theorem 2.4 in [22], the expansion ratio being defined in Definition 2.1 of [22]).

As for (II), fix $K_3 > 0$. For all $x \in V_n$, one obtains $B_{M_n}(x, \lfloor K_3 \log n \rfloor)$ by proceeding to at most $d(d-1)^{\lfloor K_3 \log n \rfloor}$ pairings of half-edges. If $K_3$ is small enough, $d(d-1)^{\lfloor K_3 \log n \rfloor} < n^{1/5} - 1$ so that by (2.7) with $m_0 = 1$, $m_E = 0$, $m = d(d-1)^{\lfloor K_3 \log n \rfloor}$ and $k = 2$, for $n$ large enough:

$$\mathbb{P}(\mathrm{tx}(B_{M_n}(x, \lfloor K_3 \log n \rfloor)) \geq 2) \leq C(2) \left(\frac{n^{2/5}}{n}\right)^2 \leq n^{-11/10}.$$

By a union bound on $x \in V_n$, w.h.p. $M_n$ is such that for all $x \in V_n$,

$$\mathrm{tx}(B_{M_n}(x, \lfloor K_3 \log n \rfloor)) \leq 1.$$

In the remainder of the proof, we fix a realization of $M_n$ such that (I) and (II) hold. In particular, $M_n$ is connected and $G_{M_n}$ is well-defined.

Let us establish (2.1). Let $x \in V_n$ be such that $\mathrm{tx}(B_{M_n}(x, K_4\lfloor \log \log n \rfloor)) = 0$. Note that $U := B_{M_n}(x, \lfloor K_4 \log \log n \rfloor)$ and $W := B_{T_d}(\circ, \lfloor K_4 \log \log n \rfloor)$ are isomorphic. Then $G_{M_n}^U(x, x) = G_{T_d}^W(\circ, \circ)$, where we let

$$G_{M_n}^A(y, z) := \mathbf{E}_y^{M_n}[\sum_{k=0}^{T_A} \mathbf{1}_{\{X_k=z\}}] \quad \text{for every } y, z \in V_n \text{ and } A \subsetneq V_n.$$

Recall that $T_A$ is the exit time of A by the SRW $(X_k)_{k \geq 0}$. Similarly for every $B \subsetneq T_d$ and $y, z \in T_d$, we define

$$G_{T_d}^B(y, z) := \mathbf{E}_y^{T_d} \left[ \sum_{k=0}^{T_B} \mathbf{1}_{\{X_k=z\}} \right]. \qquad (A.1)$$

On one hand, by the strong Markov property applied to the exit time $T_W$,

$$G_{T_d}^W(\circ, \circ) = G_{T_d}(\circ, \circ) - \mathbf{E}_\circ^{T_d}[G_{T_d}(\circ, X_{T_W})] = \frac{d-1}{d-2} - \mathbf{E}_\circ^{T_d}[G_{T_d}(\circ, X_{T_W})].$$
On the other hand, by Lemma 1.4 of [1], for all $y, z \in V_n$ and $A \subsetneq V_n$:

$$G_{\mathcal{M}_n}^A(y, z) = G_{\mathcal{M}_n}(y, z) - \mathbf{E}_y^{\mathcal{M}_n}[G_{\mathcal{M}_n}(z, X_{T_A})] + \frac{\mathbf{E}_y^{\mathcal{M}_n}[T_A]}{n}, \quad (A.2)$$

so that $G_{\mathcal{M}_n}^U(x, x) = G_{\mathcal{M}_n}(x, x) - \mathbf{E}_x^{\mathcal{M}_n}[G_{\mathcal{M}_n}(x, X_{T_U})] + \frac{\mathbf{E}_x^{\mathcal{M}_n}[T_U]}{n}$. Therefore,

$$\left| G_{\mathcal{M}_n}(x, x) - \frac{d-1}{d-2} \right| \leq \left| \mathbf{E}_{\circ}^{\mathcal{T}_d}[G_{\mathcal{T}_d}(\circ, X_{T_W})] \right| + \left| \mathbf{E}_x^{\mathcal{M}_n}[G_{\mathcal{M}_n}(x, X_{T_U})] \right| + \frac{\mathbf{E}_x^{\mathcal{M}_n}[T_U]}{n}.$$

By (2.3) and (2.4), if $K_4$ is large enough, then for large enough $n$:

$$\left| \mathbf{E}_{\circ}^{\mathcal{T}_d}[G_{\mathcal{T}_d}(\circ, X_{T_W})] \right| + \left| \mathbf{E}_x^{\mathcal{M}_n}[G_{\mathcal{M}_n}(x, X_{T_U})] \right| \leq \log^{-7} n.$$

Note that $T_U$ is stochastically dominated by the hitting time $H$ of $\lfloor K_4 \log \log n \rfloor$ by a SRW $(Z_k)_{k \geq 0}$ on $\mathbb{Z}$ starting at 0, whose transition probabilities from any vertex are $\frac{d-1}{d}$ towards the right and $1/d$ towards the left. By Markov's exponential inequality, there exists a constant $c > 0$ such that for $n$ large enough and every $k > n^{1/10}$,

$$\mathbb{P}(H \geq k) \leq \mathbb{P}(Z_k \leq \lfloor K_4 \log \log n \rfloor) \leq \mathbb{P}(Z_k \leq (\frac{d-2}{d} - 1/100)k) \leq e^{-ck}.$$

Hence for $n$ large enough, $\mathbf{E}_x^{\mathcal{M}_n}[T_U] \leq \mathbb{E}[H] \leq n^{1/10} + \sum_{k \geq n^{1/10}} k e^{-ck} \leq n^{1/2}$. Thus,

$$\left| G_{\mathcal{M}_n}(x, x) - \frac{d-1}{d-2} \right| \leq \log^{-7} n + n^{-1/2} \leq \log^{-6} n$$

for large enough $n$, and this yields (2.1). One proves (2.2) by the same reasoning. $\square$

## A.2 Proof of Propositions 3.3, 3.4 and 3.6

We start with the proof of Proposition 3.3. We will need the following Lemma (whose proof is immediate from Propositions 3.1 and 3.3 of [32] and Proposition 2.1 (ii) of [3]), from which $\lambda_h$ originates.

**Lemma A.1.** Fix $h < h_*$.

There exist $\lambda_h > 1$ and a function $\chi_h$ that is continuous with a positive minimum $\chi_{h, \min}$ on $[h, +\infty)$, that vanishes on $(-\infty, h)$ and such that

$$M_k^h := \lambda_h^{-k} \sum_{x \in \mathcal{Z}_k^{h,+}} \chi_h(\varphi_{\mathcal{T}_d}(x))$$

is a martingale w.r.t. the filtration $\mathcal{F}_k := \sigma(\varphi_{\mathcal{T}_d}(x), x \in B_{\mathcal{T}_d^+}(\circ, k))$, $k \geq 0$, and has an a.s. limit $M_\infty^h$.

**Proof of Proposition 3.3.** We first establish that $\lim_{k \to +\infty} \mathbb{P}^{\mathcal{T}_d}(|\mathcal{Z}_k^h| > \lambda_h^k/k^2) = \eta(h)$. Clearly,

$$\limsup_{k \to +\infty} \mathbb{P}^{\mathcal{T}_d}(|\mathcal{Z}_k^h| > \lambda_h^k/k^2) \leq \mathbb{P}^{\mathcal{T}_d}(|\mathcal{C}_\circ^h| = +\infty) = \eta(h).$$

Conversely, denote $\mathcal{E}^+ = \{|\mathcal{C}_\circ^{h,+}| = +\infty\}$ and $\mathcal{E}_k^+ = \{|\mathcal{Z}_k^{h,+}| \geq \lambda_h^k/k^2\}$. By Theorem 4.3 of [3],

$$\lim_{k \to +\infty} \mathbb{P}^{\mathcal{T}_d}(\mathcal{E}_k^+) = \mathbb{P}^{\mathcal{T}_d}(\mathcal{E}^+) > 0. \quad (A.3)$$

Hence, for any $\varepsilon > 0$, for $k$ large enough,

$$\mathbb{P}^{\mathcal{T}_d}(\mathcal{E}_k^+) \geq \mathbb{P}^{\mathcal{T}_d}(\mathcal{E}^+) - \varepsilon. \quad (A.4)$$
Let $\mathbb{T}_d^-$ be the cone from $\bar{\mathcal{O}}$ out of $\circ$, $\mathcal{C}_{\bar{\mathcal{O}}}^{h,-} := \mathcal{C}_{\bar{\mathcal{O}}}^h \cap \mathbb{T}_d^-$, and $\mathcal{Z}_k^{h,-} := \mathcal{C}_{\bar{\mathcal{O}}}^{h,-} \cap \partial B_{\mathbb{T}_d^-(\bar{\mathcal{O}}, k)}$ for $k \ge 1$. Let $\mathcal{E}^- = \{|\mathcal{C}_{\bar{\mathcal{O}}}^{h,-}| = +\infty\}$ and $\mathcal{E}_k^- = \{|\mathcal{Z}_{k-1}^{h,-}| \ge \lambda_h^k/k^2\}$. Define $\mathcal{E} := \{\varphi_{\mathbb{T}_d}(\circ) \ge h\} \cap \{\mathcal{C}_{\bar{\mathcal{O}}}^{h,+} \text{ is finite}\}$ and $\mathcal{E}_k := \{\varphi_{\mathbb{T}_d}(\circ) \ge h\} \cap \{\mathcal{Z}_k^{h,+} = \emptyset\}$. We have

$$ \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}_k^- \cap \mathcal{E}_k) \ge \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap \mathcal{E}) - \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap \mathcal{E} \cap (\mathcal{E}_k)^c) - \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap \mathcal{E} \cap (\mathcal{E}_k)^c). $$

Define $M_{\infty}^{h,-}$ on $\mathcal{C}_{\bar{\mathcal{O}}}^{h,-}$ as $M_{\infty}^h$ on $\mathcal{C}_{\bar{\mathcal{O}}}^{h,+}$. From the proof of Theorem 4.3 in [3], we get that $\mathbb{P}^{\mathbb{T}_d}(\{M_{\infty}^{h,-} > 0\} \cap (\mathcal{E}_k^-)^c) \to 0$. And, by Proposition 4.2 in [3], $\mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap \{M_{\infty}^{h,-} = 0\}) = 0$, so that $\mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap (\mathcal{E}_k^-)^c) \to 0$. Moreover, $(\mathcal{E}_k)_{k \ge 0}$ is an increasing sequence of events and $\mathcal{E} = \cup_{k \ge 1} \mathcal{E}_k$, so that $\mathbb{P}^{\mathbb{T}_d}(\mathcal{E} \cap (\mathcal{E}_k)^c) \to 0$. Hence, for $k$ large enough,

$$ \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}_k^- \cap \mathcal{E}_k) \ge \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}^- \cap \mathcal{E}) - 2\varepsilon. \quad (A.5) $$

Note that $\{|\mathcal{C}_{\bar{\mathcal{O}}}^h| = +\infty\} = \mathcal{E}^+ \cup (\mathcal{E}^- \cap \mathcal{E})$, so that $\mathbb{P}(\mathcal{E}^+) + \mathbb{P}(\mathcal{E}^- \cap \mathcal{E}) = \eta(h)$. And for all $k \ge 2$, $\mathcal{E}_k^+ \cup (\mathcal{E}_k^- \cap \mathcal{E}_k) \subseteq \{|\mathcal{Z}_k^h| > \lambda_h^k/k^2\}$, therefore, if $k$ is large enough, by (A.4) and (A.5), one has

$$ \mathbb{P}^{\mathbb{T}_d}(|\mathcal{Z}_k^h| > \lambda_h^k/k^2) \ge \eta(h) - 3\varepsilon. $$

Since $\varepsilon > 0$ was arbitrary, $\lim_{k \to +\infty} \mathbb{P}^{\mathbb{T}_d}(|\mathcal{Z}_k^h| > \lambda_h^k/k^2) = \eta(h)$.

Now, we show that $\mathbb{P}^{\mathbb{T}_d}(|\mathcal{Z}_k^h| < k\lambda_h^k) \to 1$. For all $k \ge 1$, by definition of $M_k^h$,

$$ M_k^h \ge \chi_{h,\min} \lambda_h^{-k} |\mathcal{Z}_k^{h,+}|. $$

From the proof of Proposition 3.3 in [32], $M_{\infty}^h$ is a.s. finite. Therefore, $k^{-1}\lambda_h^{-k} |\mathcal{Z}_k^{h,+}| \to 0$ a.s., and

$$ \mathbb{P}^{\mathbb{T}_d}(|\mathcal{Z}_k^{h,+}| \ge k\lambda_h^k/2) \to 0. $$

In the same way, $\mathbb{P}^{\mathbb{T}_d}(|\mathcal{Z}_{k-1}^{h,-}| \ge k\lambda_h^k/2) \to 0$. Since $\mathcal{Z}_k^h \subseteq \mathcal{Z}_k^{h,+} \cup \mathcal{Z}_{k-1}^{h,-}$, we are done.

The last part of the Proposition comes directly from Propositions 3.1 and 3.3 in [32]. □

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

A crucial idea to prove Propositions 3.4 and 3.6 is to make a finite scaling, in order to get a branching process that is uniformly supercritical w.r.t. to the value of $\varphi_{\mathbb{T}_d}(\circ)$. Indeed, the fact $\lambda_h > 1$ does not ensure that the expected number of children of $\circ$ in $\mathbb{T}_d^+$ (or even in $\mathbb{T}_d$) conditionally on $\varphi_{\mathbb{T}_d}(\circ) = a$ is more than one for every $a \ge h$, in particular if $a$ is small. However, due to the exponential growth of $\mathcal{C}_{\bar{\mathcal{O}}}^h$ (and $\mathcal{C}_{\bar{\mathcal{O}}}^{h,+}$) of Proposition 3.3, it turns out that for $\ell \in \mathbb{N}$ large enough, even conditionally on $\varphi_{\mathbb{T}_d}(\circ) = h$, the expected number of vertices in the $\ell$-offspring of $\circ$ is more than one, as stated in the Lemma below.

**Lemma A.2.** There exists $\ell \in \mathbb{N}$ such that for every $a \ge h$,

$$ E_a^{\mathbb{T}_d}(|\mathcal{Z}_\ell^h|) \ge E_a^{\mathbb{T}_d}(|\mathcal{Z}_\ell^{h,+}|) \ge E_h^{\mathbb{T}_d}(|\mathcal{Z}_\ell^{h,+}|) > 1. $$

We will use it in the proofs of Propositions 3.4 and 3.6, looking at the branching process whose vertices are those of $\mathcal{C}_{\bar{\mathcal{O}}}^h$ at height 0, $\ell$, $2\ell$, etc.

*Proof of Lemma A.2.* Write $\mathcal{E}_k := \{|\mathcal{Z}_k^{h,+}| \ge \lambda_h^k/k^2\}$. By (A.3), there exists $\varepsilon > 0$ small enough such that for every $k \ge \varepsilon^{-1}$, $\mathbb{P}^{\mathbb{T}_d}(\mathcal{E}_k) \ge \varepsilon$. For $a_1$ large enough, $\mathbb{P}^{\mathbb{T}_d}(\varphi_{\mathbb{T}_d}(\circ) \ge a_1) < \varepsilon/2$. Note that $\mathcal{E}_k$ is an increasing event, so that by Lemma 3.2, the map $a' \mapsto \mathbb{P}_{a'}^{\mathbb{T}_d}(\mathcal{E}_k)$ is non-decreasing. Therefore, for every $a' \ge a_1$ and $k \ge M$, if $\nu \sim \mathcal{N}(0, \frac{d-1}{d-2})$ denotes the law of $\varphi_{\mathbb{T}_d}(\circ)$,

$$ \mathbb{P}_{a'}^{\mathbb{T}_d}(\mathcal{E}_k) \ge \mathbb{P}_{a_1}^{\mathbb{T}_d}(\mathcal{E}_k) \ge \int_{-\infty}^{a_1} \mathbb{P}_b^{\mathbb{T}_d}(\mathcal{E}_k)\nu(db) \ge \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}_k) - \mathbb{P}^{\mathbb{T}_d}(\varphi_{\mathbb{T}_d}(\circ) \ge a_1) \ge \varepsilon/2. \quad (A.6) $$
From the construction of Proposition 3.1, it is straightforward that

$$p := \mathbb{P}_h^{\mathbb{T}_d}(\circ \text{ has one child } z \text{ in } \mathcal{C}_o^{h,+}, \text{ and } \varphi_{\mathbb{T}_d}(z) \ge a_1) > 0. \quad (A.7)$$

Hence for $\ell \in \mathbb{N}$ large enough,

$$\mathbb{E}_h^{\mathbb{T}_d}[|\mathcal{Z}_\ell^{h,+}|] \ge \frac{p\varepsilon}{2} \times \frac{\lambda_h^{\ell-1}}{(\ell-1)^2} > 1.$$

In addition, for every $M \in \mathbb{R}$, $\{|\mathcal{Z}_\ell^{h,+}| \ge M\}$ is an increasing event. By Lemma 3.2, for every $a \ge h$, $\mathbb{E}_a^{\mathbb{T}_d}[|\mathcal{Z}_\ell^{h,+}|] \ge \mathbb{E}_h^{\mathbb{T}_d}[|\mathcal{Z}_\ell^{h,+}|]$. Since $\mathcal{Z}_\ell^{h,+} \subseteq \mathcal{Z}_\ell^h$ a.s., the conclusion follows. $\square$

**Remark A.3.** By a direct adaptation of this proof, in particular (A.6) and (A.7), one has $\mathbb{P}_a^{\mathbb{T}_d}[|\mathcal{C}_o^h| = \infty] \ge \mathbb{P}_h^{\mathbb{T}_d}[|\mathcal{C}_o^h| = \infty] > 0$ for all $a \ge h$. Also, the conclusion of the Lemma still holds if for a fixed $\delta \in [0, h_* - h)$, $\mathcal{Z}_\ell^{h,+}$ now denotes the $\ell$-th generation of the connected component of $\circ$ in $(\{\circ\} \cup E_{\varphi_{\mathbb{T}_d}}^{\ge h+\delta}) \cap \mathbb{T}_d^+$: denoting $\rho_{\ell,h,\delta}$ the law of $|\mathcal{Z}_\ell^{h,+}|$ conditionally on $\varphi_{\mathbb{T}_d}(\circ) = h$, we have $\mathbb{E}_h^{\mathbb{T}_d}[\mathcal{Z}_\ell^{h,+}] = \mathbb{E}[\rho_{\ell,h,\delta}] > 1$ if $\ell$ is large enough (depending on $h$ and $\delta$).

*Proof of Proposition 3.4.* Fix $a \ge h$, and let $\ell \in \mathbb{N}$ be such that the conclusion of Lemma A.2 holds. Let $F_1 := \partial B_{\mathcal{C}_o^h}(\circ, \ell)$. For $j \ge 1$, if $F_j \ne \emptyset$, choose an arbitrary vertex $z_j \in F_j$. Let $O_j$ be the $\ell$-offspring of $z_j$ in $\mathcal{C}_o^h$ and let $F_{j+1} := O_j \cup F_j \setminus \{z_j\}$. Thus, we explore $\mathcal{C}_o^h$ by revealing subtrees of height $\le \ell$, so that at each step, we see at most $(d-1) + \dots + (d-1)^\ell \le d^{\ell+1}$ new vertices. Hence, if $|\mathcal{C}_o^h| \ge k$ for some $k \in \mathbb{N}$, there will be at least $\lfloor k/d^{\ell+1} \rfloor$ steps before $\mathcal{C}_o^h$ is fully explored.

By Lemma 3.2 (applied to $\{|\mathcal{Z}_\ell^{h,+}| \ge k\}$ for every $k \ge 1$), for every $j \ge 1$, $|F_j|$ dominates stochastically a sum $S_j$ of $j$ i.i.d. random variables of law $\rho_{\ell,h} - 1$, where

$$\rho_{\ell,h} \text{ is the law of } |\mathcal{Z}_\ell^{h,+}| \text{ conditionally on } \varphi_{\mathbb{T}_d}(\circ) = h. \quad (A.8)$$

Therefore,

$$\mathbb{P}_a^{\mathbb{T}_d}(k \le |\mathcal{C}_o^h| < +\infty) \le \sum_{j=\lfloor k/d^{\ell+1} \rfloor}^{+\infty} \mathbb{P}(S_j \le 0).$$

But a variable of law $\rho_{\ell,h} - 1$ is bounded and has a positive expectation by Lemma A.2, therefore there exist $c, c' > 0$ such that $\mathbb{P}(S_j \le 0) \le c e^{-c'j}$ for all $j \ge 1$. Hence,

$$\mathbb{P}_a^{\mathbb{T}_d}(k \le |\mathcal{C}_o^h| < +\infty) \le c \sum_{j=\lfloor k/d^{\ell+1} \rfloor}^{+\infty} e^{-c'j} \le \frac{c \exp(-c' \lfloor k/d^{\ell+1} \rfloor)}{1 - e^{-c'}}$$

and (3.1) follows. $\square$

*Proof of Proposition 3.6.* Let $\varepsilon > 0$. By definition of $M_k^h$ and Lemma A.1,

$$\{|\mathcal{Z}_k^{h,+}| \ge \chi_h(a)(\lambda_h + \varepsilon)^k\} \subset \{M_k^h \ge \lambda_h^{-k} \chi_{h,\min} \chi_h(a)(\lambda_h + \varepsilon)^k\}$$

so that by Markov's inequality, for any $a \ge h$,

$$\begin{align*}
\mathbb{P}_a^{\mathbb{T}_d}(|\mathcal{Z}_k^{h,+}| \ge \chi_h(a)(\lambda_h + \varepsilon)^k) &\le \mathbb{P}_a^{\mathbb{T}_d} \left( M_k^h \ge \chi_{h,\min} \chi_h(a) \left( \frac{\lambda_h + \varepsilon}{\lambda_h} \right)^k \right) \\
&\le \chi_{h,\min}^{-1} \left( \frac{\lambda_h}{\lambda_h + \varepsilon} \right)^k \chi_h(a)^{-1} \mathbb{E}_a^{\mathbb{T}_d} [M_k^h] \\
&\le \chi_{h,\min}^{-1} \left( \frac{\lambda_h}{\lambda_h + \varepsilon} \right)^k .
\end{align*}$$
This yields the upper large deviation for $\mathbb{Z}_k^{h,+}$ (and for $\mathbb{Z}_k^h$, using the facts that $\mathbb{Z}_k^h \subseteq \mathbb{Z}_k^{h,+} \cup \mathbb{Z}_{k-1}^{h,-}$ and that $|\mathbb{Z}_k^{h,-}|$ and $|\mathbb{Z}_{k-1}^{h,+}|$ have the same law).

It remains to prove that for some $C > 0$ and $k$ large enough,

$$ \max_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d} (k^{-1} \log |\mathbb{Z}_k^h| \le \log(\lambda_h - \varepsilon) |\mathbb{Z}_k^h \ne \emptyset) \le \exp(-Ck). \quad (A.9) $$

We proceed in two steps. We first initiate the growth of $C_\circ^h$ by showing that if $\mathbb{Z}_{\ell n} \ne \emptyset$, the probability that $|\mathbb{Z}_{\ell n}| = o(n)$ decays exponentially with $n$, where $\ell$ is such that Lemma A.2 holds. Then, if $\mathbb{Z}_{\ell n}$ has at least $\Theta(n)$ vertices, each of them has a positive probability to have a $Kn$-offspring of size at least $\lambda_h^{Kn}/n^3 \ge (\lambda_h - \varepsilon)^k$ with $k := (K + \ell)n$ and for a large enough constant $K$, independently of the others vertices. Hence the probability that $|\mathbb{Z}_k| \le (\lambda_h - \varepsilon)^k$ decays exponentially with $n$, and thus with $k$.

**First step.** Recall the exploration of $C_\circ^h$ of the proof of Proposition 3.4, but perform it in a breadth-first way: reveal first the $\ell$-offspring of $\circ$, then the $\ell$-offspring of each vertex of $\mathbb{Z}_\ell^h$, then the $\ell$-offspring of each vertex of $\mathbb{Z}_{2\ell}^h$, and so on. For $n \ge 1$, if $\mathbb{Z}_{\ell n}^h \ne \emptyset$, let $j + 1$ be the first step at which we explore the offspring of a vertex of $\mathbb{Z}_{\ell n}$. Note that $j \ge n$. As in the proof of Proposition 3.4, there exist $\epsilon, c, c' > 0$ such that $\mathbb{P}(S_i \le \epsilon i) \le c e^{-c' i}$ for every $i \ge 1$. Hence, for every $n \ge 1$,

$$ \min_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d} (|\mathbb{Z}_{\ell n}^h| \ge \epsilon n |\mathbb{Z}_{\ell n}^h \ne \emptyset) \ge 1 - \sum_{i \ge n} c e^{-c' i} \ge 1 - \frac{c}{1 - e^{-c'}} e^{-c'n}. \quad (A.10) $$

**Second step.** Let $K$ be a positive integer constant, and let $F$ be the set of vertices $z \in \mathbb{Z}_{\ell n}^h$ such that the $Kn$-offspring of $z$ has at least $\lambda_h^{Kn}/n^3$ vertices. This step mainly comes down to showing that the probability that $F$ is empty decays exponentially with $n$. Define the events

$$ \mathcal{E}_n := \{|\mathbb{Z}_{Kn}^{h,+}| \ge \lambda_h^{Kn}/n^3\} \text{ and } \mathcal{E}'_n := \{|\mathbb{Z}_{Kn-1}^{h,+}| \ge \lambda_h^{Kn}/n^3\}. $$

We first show that

$$ p := \min_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d}(\mathcal{E}_n) > 0. \quad (A.11) $$

By (A.3), $\lim_{n \to +\infty} \mathbb{P}^{\mathbb{T}_d}(\mathcal{E}'_n) =: p' > 0$. Let $a_1$ be such that $\mathbb{P}(\varphi_{\mathbb{T}_d}(\circ) \ge a_1) < p'/4$. For $n$ large enough,

$$ \int_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d}(\mathcal{E}'_n) \nu(da) > p'/2, \text{ hence } \int_{h}^{a_1} \mathbb{P}_a^{\mathbb{T}_d}(\mathcal{E}'_n) \nu(da) > p'/4, $$

where we recall that $\nu$ is the density of $\varphi_{\mathbb{T}_d}(\circ)$. Since $\mathcal{E}'_n$ is an increasing event, by Lemma 3.2:

$$ \min_{a \ge a_1} \mathbb{P}_a^{\mathbb{T}_d}(\mathcal{E}'_n) \ge p'/4. $$

By Lemma 3.2 again,

$$ \min_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d}(\exists z \in \mathbb{Z}_1^{h,+}, \varphi_{\mathbb{T}_d}(z) \ge a_1) = \mathbb{P}_h^{\mathbb{T}_d}(\exists z \in \mathbb{Z}_1^{h,+}, \varphi_{\mathbb{T}_d}(z) \ge a_1) =: p'' > 0. $$

Hence $p \ge p'p''/4$ and (A.11) is proved. Note that $|F| \ge \text{Bin}(|\mathbb{Z}_{\ell n}^h|, p'')$. Thus by (A.10),

$$ \min_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d} (|F| \ge 1 |\mathbb{Z}_{\ell n}^h \ne \emptyset) \ge 1 - \mathbb{P}_a^{\mathbb{T}_d} (|\mathbb{Z}_{\ell n}^h| \le \epsilon n |\mathbb{Z}_{\ell n}^h \ne \emptyset) - (1 - p'')^{\epsilon j} \ge 1 - c e^{-c'n} $$

for $n$ large enough, up to changing the values of the constants $c$ and $c'$. Therefore,

$$ \max_{a \ge h} \mathbb{P}_a^{\mathbb{T}_d} \left( |\mathbb{Z}_{(K+\ell)n}^h| < \lambda_h^{Kn}/n^3 \mid \mathbb{Z}_{\ell n}^h \ne \emptyset \right) \le c e^{-c'j} \le c e^{-c'n}. $$