# Quantitative Russo–Seymour–Welsh for random walk on random graphs and
decorrelation of UST

Gourab Ray University of Victoria, supported in part by NSERC 50311-57400,
<EMAIL_ADDRESS>Tingzhou Yu University of Victoria<EMAIL_ADDRESS>
###### Abstract

We prove a quantitative Russo–Seymour–Welsh (RSW) type result for random walks
on two natural examples of random planar graphs: the supercritical percolation
cluster in $\mathbb{Z}^{2}$ and the Poisson Voronoi triangulation in
$\mathbb{R}^{2}$. More precisely, we prove that the probability that a simple
random walk crosses a rectangle in the hard direction with uniformly positive
probability is stretched exponentially likely in the size of the rectangle. As
an application we prove a near optimal decorrelation result for uniform
spanning trees for such graphs. This is the key missing step in the
application of the proof stretegy of [4] for such graphs (in [4], random walk
RSW was assumed to hold with probability 1). Applications to almost sure
Gaussian free field scaling limit for dimers on Temperleyan type modification
on such graphs are also discussed.

##  1 Introduction

It is now an established fact that the Russo–Seymour–Welsh theory lies at the
heart of two dimensional statistical physics models, particularly those which
are believed to be conformally invariant in their scaling limits. Although the
major application of this idea has been in percolation theory (see e.g. [10,
7, 8] for a broad overview), recently, this concept was used in [4] to study
decorrelation of uniform spanning trees in a general setting. Very roughly,
this type of estimate leads to rough Harnack type inequality and also Beurling
type hitting estimates. This ultimately led to a result which establishes
scaling limits of dimer height functions to a Gaussian free field on a fairly
general class of graphs. This is later extended to graphs on multiply
connected Riemann surfaces as well [5, 3].

In this program, two key assumptions are made on the graph. The first
assumption is that random walk on the graph must converge to Brownian motion,
which can be thought of as an assumption on the macroscopic symmetries of the
random walk under conformal mappings. This assumption is usually robust under
reasonable perturbations of the underlying graph. The second assumption is
that for any rectangle larger than a _fixed scale_ , a random walker crosses
it without exiting the rectangle with a probability uniform in the scale and
location, and depending only on the aspect ratio (see Definition 2.1). The
second assumption was called a Russo–Seymour–Welsh (RSW) type assumption in
[4]. It can be checked that this holds for all standard lattices (more
generally for isoradial graphs with unifomly elliptic angles), and even holds
if we put some uniformly elliptic random environment on them (see [4, Section
1.1] for a detailed discussion). Let us remark that the RSW assumption is in
some sense related to the uniformity in the rate of convergence of the random
walk to a Brownian motion depending on the location of the graph. Indeed, for
this reason, RSW for the square lattice for example is a simple consequence of
the invariance principle. On the other hand in the presence of some local
irregularities, it is not clear at all if such an estimate is even true.

The goal of this article is to extend the random walk RSW result to random
planar graphs (with a natural embedding in $\mathbb{Z}^{2}$) which are not
necessarily ‘uniformly elliptic’ in the sense of the examples considered so
far. The key examples we handle in this article are the unique infinite
cluster of a Bernoulli bond percolation on $\mathbb{Z}^{2}$ and a Poisson
Voronoi triangulation. It can be easily seen that in both these cases, RSW
does not hold deterministically for rectangles larger than any fixed scale
uniformly over the location of the graph (for example, an arbitrarily large
rectangle is empty at some location almost surely). However, we show in
Theorems 4.1 and 3.1 that RSW holds with a probability which is stretched
exponentially high in the scale.

One major application of the RSW assumption in [4, Theorem 4.21] was to prove
a macroscopic decorrelation result for uniform spanning trees in the following
sense. Suppose $D$ is a simply connected domain and we take a Uniform spanning
tree $\mathcal{T}$ with wired boundary condition for a graph with small ‘mesh
size’ $\delta$ in it. Fix two points $x,y$ in $D$. Then one can couple two
independent USTs $\mathcal{T}_{1},\mathcal{T}_{2}$ (on a possibly bigger
domain) with $\mathcal{T}$ so that $\mathcal{T}_{1}$ and $\mathcal{T}$ agree
on a small but random neighbourhood of $x$, and $\mathcal{T}_{2}$ and
$\mathcal{T}$ agree on a small but random neighbourhood of $y$. Furthermore,
this random neighbourhood has macroscopic radius, in the sense that the radius
dominates a random variable which is independent of $\delta$ for all small
enough $\delta$. Furthermore, one can obtain a polynomial bound on the lower
tail of the radius. The same result holds not just for two but for any finite
number of points. In this article, we extend this result to UST on random
graphs in Theorem 5.1. In particular, we show that a similar coupling can be
obtained for a collection of graphs which has high probability (this can be
extended to an a.s. statement along a subsequence of $\delta$, see Remark 5.2)

Another consequence of the quantitative RSW and Theorem 5.1 is a scaling limit
result for dimer height function on such random planar graphs. Suppose we take
a random planar graph satisfying the quantitative RSW and some other mild
assumptions (which are satisfied by the infinite cluster of Bernoulli bond
percolation and $\mathbb{Z}^{2}$ and the Poisson Voronoi triangulation). There
is a natural way to add a dual to this graph so that we obtain a _Temperleyan
graph_ which admits a dimer cover. Then following the stratregy of [4], it can
be shown that almost surely on the graph the height function of this dimer
model converges to Gaussian free field. More details and discussions on this
can be found in Section 6.

The main input for the random walk RSW results is a result by Barlow [2],
which states that a quadratic volume growth and Poincaré inequality ensures a
good heat kernel bound for random walks. The Poincaré inequality is an
analytic criterion. One can establish this inequality with a good control on
the volume growth and isoperimetric constant on the graph. We collect these
geometric criterions in Lemma 2.5. We need to be a bit more careful than the
treatment in Barlow [2] as there is no uniform bound on degree in our
assumption (which was assumed in [2] as the main motivation there was to study
heat kernel bounds for percolation in $\mathbb{Z}^{d}$). Next, we show that
the criterions in Lemma 2.5 hold for the main two applications in this
article: unique infinite cluster of Bernoulli percolation and Voronoi
triangulation. A key input is a quantitative isoperimetric inequality for
Voronoi triangulation (Lemma 4.11), which we consider to be another novel
contribution of this article. The coupling result of Section 5 is established
by first proving that the diameters of the ‘bad regions’ where RSW does not
hold is small with high probability, and then applying the techniques
established in [4]. Finally in Section 6 we explain how the results in this
article can be used to prove a Gaussian free field scaling limit of the dimer
model on random graphs, which hold a.s. on the graph chosen.

#### Acknowledgement:

We thank Benoit Laslier for several useful discussions.

#### Notation:

Given a graph $G$, we denote by $V(G)$ its vertex set and $E(G)$ its edge set.
Let $\Lambda_{n}$ denote the square $[-n,n]^{2}$ with
$\Lambda_{n}(x)=x+\Lambda_{n}$. Sometimes we will also deal with rectangles
$\Lambda_{m,n}=[-m,m]\times[-n,n]$ and similarly
$\Lambda_{m,n}(z)=z+\Lambda_{m,n}$. For $S\subset V(G)$, denote by $|S|_{E}$
the sum of the weights of the edges incident to vertices of $G$ in $S$, while
$|S|$ simply denotes the number of vertices in $S$. With a slight abuse of
notation, for any $S\subset\mathbb{R}^{2}$, we use $|S|_{E}$ to denote the sum
of the weights of the edges which is incident to a vertex in $S$, and $|S|$ to
denote the cardinality of the set of vertices in $S$. Let $\deg(v)$ denotes
the degree of the vertex $v$.

##  2 A general criterion for RSW

In this section, we work with a fixed graph $G=(V,E)$ embedded in
$\mathbb{R}^{2}$. The goal of this article is to summarize certain geometric
properties of the graph which ensures that a simple random walk on it behaves
in a nice manner. The main quantity of interest is the following.

######  Definition 2.1.

For $c>0$, we say that $\Lambda_{3m,m}(z)$ is $c$-crossable if for every $x\in
B_{1}:=\Lambda_{m/2}(z+(-2m,0))$ and with $B_{2}:=\Lambda_{m/2}(z+(2m,0))$,

$\mathbb{P}(Y\text{ started from $x$ enters $B_{2}$ before exiting
$\Lambda_{3m,m}(z)$})\geq c.$ (2.1)

where $Y$ is a simple random walk.

See Figure 1. Notice that although the event is stated in terms of a random
walk, it is in fact a statement about the geometry of the graph inside the
rectangle. We point out that in [4], it was assumed that there exists a $c>0$
depending only on the graph such that every rectangle beyond a certain scale
$m\geq\delta_{0}^{-1}$ centred at any $z$ was $c$-crossable, and this
assumption was called ‘ _uniform crossing_ ’.

Figure 1: The rectangle is $c$ crossable if an event like the above has
probability at least $c$.

Let $G=(V,E)$ be a finite planar graph, properly embedded in $\mathbb{R}^{2}$.
For a function $f:V\mapsto\mathbb{R}$, denote by $\nabla f$ to be a function
from the oriented edges of the graph to $\mathbb{R}$, satisfying

$\nabla f((e_{-},e_{+}))=f(e_{+})-f(e_{-}).$

We will denote by $|\nabla f|$ the function which takes absolute value of
$\nabla f$ for each unoriented edge in $E$. We now borrow the notions of
‘good’ and ‘very good’ from [2]. Let $o$ denote the vertex in $G$ which is
closest to the origin in $\mathbb{R}^{2}$. Also let $d_{G}$ denote the graph
distance in $G$ and let $B(x,r)$ denote the graph distance ball of radius $r$
centred around the vertex $x$.

######  Definition 2.2.

([2, Definition 1.7]) Let $C_{P},C_{V}>0$ and $C_{W}\geq 1$ be fixed. We say
that $B(o,n)$ is $(C_{P},C_{V},C_{W})$-good if it satisfies

$|B(o,n)|_{E}\geq C_{V}n^{2}.$ (Vol)

and every $f:B(o,C_{W}n)\mapsto\mathbb{R}$ satisfies the weak Poincaré
inequality, i.e.,

$\sum_{v\in B(o,n)}(f(v)-\bar{f})^{2}\deg(v)\leq C_{P}n^{2}\sum_{e\in
E(B(o,C_{W}n))}\lvert\nabla f(e)\rvert^{2}$ (P)

where $\bar{f}=|V(B(o,n))|_{E}^{-1}\sum_{v\in B(o,n)}f(v)\deg(v)$. We say
$B(o,n)$ is $(C_{P},C_{V},C_{W})$-very good if there exists an integer
$N_{B(o,n)}\leq n^{1/4}$ such that every $B(y,r)\subset B(o,n)$ is good for
every $N_{B}\leq r\leq n$.

We will sometimes drop the constants in the definition of good and very good
when they are clear from the context.

We now extend the notion of good and very good to Euclidean squares. We say
$\Lambda_{n}$ is $(C_{\textsf{Euc}},C_{P},C_{V},C_{W})$-very good if and only
if

$B(o,C_{\textsf{Euc}}^{-1}n)\subset\Lambda_{n}\subset B(o,C_{\textsf{Euc}}n)$
(2.2)

and $B(o,C_{\textsf{Euc}}n)$ is $(C_{P},C_{V},C_{W})$-very good. The above
inclusion is interpreted as follows: if a vertex of $G$ is outside
$B(o,C_{\textsf{Euc}}n)$ (resp. inside $B(o,C_{\textsf{Euc}}^{-1}n)$) then it
is outside (resp. inside) $\Lambda_{n}$.

######  Lemma 2.3.

Suppose there exist constants $C_{\textsf{Euc}},C_{P},C_{V},C_{W},c_{0},d$
such that for all $n\geq 1$ the following is true.

  1. a.

$\Lambda_{n\log n}$ is $(C_{\textsf{Euc}},C_{P},C_{V},C_{W})$-very good with
$N_{\Lambda_{n\log n}}\leq n^{1/8}$.

  2. b.

$|B_{2}|\geq dn^{2}$ where $B_{2}$ is as in Definition 2.1 and $m=n/4$.

  3. c.

The graph distance between any vertex in $\Lambda_{2.5m,m/2}$ and any vertex
outside $\Lambda_{3m,m}$ is at least $c_{0}n$ and $m=n/4$.

Then there exists a constant $c=c(C_{P},C_{V},C_{W},C_{\textsf{Euc}},c_{0},d)$
such that $\Lambda_{3m,m}$ is $c$-crossable.

###### Proof.

Let $Y$ be the continuous time random walk with $q_{t}^{0}$ denoting its
density killed upon exiting $\Lambda_{3m,m}$. More precisely, denoting $\tau$
to be the infimum over times when $Y$ is not in $\Lambda_{3m,m}$,

$q_{t}^{0}(x,y)=\mathbb{P}(Y_{t}=y,Y_{0}=x,\tau>t);\qquad
x,y\in\Lambda_{3m,m}.$

Using the same argument as in [2, Lemma 5.8], we can show that there exists a
constant $c=c(C_{P},C_{V},C_{W},C_{\textsf{Euc}},c_{0})$ such that for any
$x\in B_{1}$ and $y\in B_{2}$,

$q_{t}^{0}(x,y)\geq\frac{c}{t}\text{ for all }cn^{2}\leq t\leq c^{-1}n^{2}$

Let us provide some details of this fact. We can write for any
$z\in\Lambda_{2.5m,m/2}$ and any $t>0$,

$\displaystyle q_{t}^{0}(x,z)$ $\displaystyle\geq
q_{t}(x,z)-\mathbb{E}_{x}(1_{\tau<t}q_{t-\tau}(Y_{\tau,z}))$
$\displaystyle\geq q_{t}(x,z)-\sup_{0\leq s\leq
t}\sup_{w\in\partial^{\prime}}q_{s}(w,z).$

where $\partial^{\prime}$ denote the set of vertices outside $\Lambda_{3m,m}$
with at least one neighbour in $\Lambda_{3m,m}$. Now fix
$\varepsilon\in(0,1/8)$, $z\in B(x,\delta n)$ and $t=\delta^{2}n^{2}$. This
allows us to apply the heat kernel bound of [2, Theorem 5.3] to lower bound
the first term $q_{t}(x,z)$ by $t^{-1}ce^{-c^{\prime}}$ (for ease of
reference, we point out that we choose $x_{0}=x_{1}=o$, $R\log
R=C_{\textsf{Euc}}n\log n$ in the notations of that theorem). On the other
hand since the graph distance between any $w\in\partial^{\prime}$ and
$z\in\Lambda_{2.5m,m/2}$ is at least $c_{0}n$ by the third item above, we can
use [2, Theorem 3.8] to upper bound the second term. Namely, writing $s=\theta
t$,

$\sup_{0\leq s\leq
t}\sup_{w\in\partial^{\prime}}q_{s}(w,z)\leq\sup_{0\leq\theta\leq
1}\frac{1}{\theta
t}e^{-\frac{c^{\prime}c_{0}^{2}n^{2}}{\theta\delta^{2}n^{2}}}=\sup_{0\leq\theta\leq
1}\frac{1}{\theta}e^{-\frac{c^{\prime}c^{2}_{0}}{\theta\delta^{2}}}.$

(Again for ease of reference, we point out that we choose $x_{0}=o$,
$R=C_{\textsf{Euc}}n\log n$ in the notations of [2, Theorem 3.8].) Actually to
be more precise for very small values of $\theta$ we go outside the range of
times when [2, Theorem 3.8] is applicable, in which case we use the upper
bound [2, Lemma 1.1] instead. Choosing $\delta$ small enough we obtain

$q_{t}^{0}(x,z)\geq\frac{c(\delta)}{t}=\frac{c(\delta)}{\delta^{2}n^{2}}.$

Now we use the standard chaining argument. Namely, we choose a sequence of
balls inside $\Lambda_{2.5m,m}$ of Volume $O(\delta^{2}n^{2})$ such that on
the event that the walk iteratively lands on these sequence of balls without
leaving $\Lambda_{2.5m,m}$, the walk enters $B_{2}$. Using the Markov property
of the walk, this event has probability at least $c(\delta)^{O(\delta^{-1})}$.
The proof is complete as the probability of crossing is at least this
constant. ∎

In light of Lemma 2.3, it is clear that in the setting of random graphs, we
require a box to be very good with high probability. To that end, it is useful
to find a geometric condition for a box being very good. While (Vol) is a very
simple geometric condition, (P) is analytic. We present below a lemma which
essentially states that a relevant Isoperimetric inequality implies (P).

We now recall some relevant definitions regarding isoperimetry of general
graphs. Take a finite, connected graph $H$. For any $A\subset V(H)$, let

$i_{H}(A):=\frac{\partial_{E}(A,H\setminus A)}{|A|_{E}}.$

where $\partial_{E}(A,H\setminus A)$ denotes the collection of edges with one
endpoint in $A$ and another in $H\setminus A$. We say $A$ is connected if the
subgraph induced by $A$ is connected. Define the isoperimetric constant
$I_{H}$ as

$I_{H}:=\inf\\{i_{H}(A):0<|A|_{E}\leq\frac{1}{2}|H|_{E}:A\text{ and
}H\setminus A\text{ are connected}\\}.$

A subgraph $H^{\prime}$ of $H$ is a graph induced by a subset of vertices of
$H$. Notice that the definition of $I_{H^{\prime}}$ ignores the edges not
present in $E(H^{\prime})$. Observe the assertion of connectedness in $A$ and
$H\setminus A$ being connected is slightly non-standard, however [2, Lemma
1.3] ensures that removing this connectedness assertion only changes the
constant by a factor of 2. This leads us to the following rephrasing of [2,
Proposition 1.4(a)]:

######  Lemma 2.4.

Then there exists $c>0$ such that for any subgraph $H$ of $G$ and any function
$f:V(H)\mapsto\mathbb{R}$,

$\sum_{v\in
V(H)}(f(v)-\bar{f_{H}})^{2}\deg_{H}(v)\leq\frac{c}{I^{2}_{H}}\sum_{e\in
E(H)}\lvert\nabla f(e)\rvert^{2}$

where $\bar{f_{H}}=|V(H)|_{E(H)}^{-1}\sum_{v\in V(H)}f(v)\deg_{H}(v)$ and
$\deg_{H}(v)$ is the degree of $v$ and $|V(H)|_{E(H)}$ is the sum over degrees
of vertices in $V(H)$ counting edges only in $H$.

This allows us to describe an equivalent geometric criterion which will ensure
a crossing estimate.

######  Lemma 2.5.

Suppose there exist constants
$C_{\textsf{Euc}},C_{V},C_{V}^{\prime},C_{W},C_{I},d,c_{0}$ such that for all
$n\geq 1$,

  1. (i)

$B(o,C_{\textsf{Euc}}^{-1}n\log n)\subset\Lambda_{n\log n}\subset
B(o,C_{\textsf{Euc}}n\log n)$.

  2. (ii)

For all $n^{1/9}\leq r\leq C_{\textsf{Euc}}n\log n+1$,

$C_{V}r^{2}\leq|B(y,r)|_{E}\leq C_{V}^{\prime}r^{2}$

for all $B(y,r)\subset B(o,C_{\textsf{Euc}}n\log n+1)$.

  3. (iii)

For all set of vertices $A\subseteq V(B(y,r))\subseteq
V(B(o,C_{\textsf{Euc}}n\log n+1))$ inducing a connected subgraph such that
$n^{1/9}\leq|A|_{E}\leq\frac{|B(y,r)|_{E}}{2},$

$i_{B(y,r)}(A)\geq\frac{C_{I}}{\sqrt{|A|_{E}}}$ (2.3)

  4. (iv)

$|B_{2}|_{E}\geq dn^{2}$ where $B_{2}$ is as in eq. 2.1.

  5. (v)

Let $m=\frac{3n}{12}$. The graph distance between any vertex in
$\Lambda_{2.5m,m/2}$ and any vertex outside $\Lambda_{3m,m}$ is at least
$c_{0}n$.

Then there exists a constant $c>0$ (depending only on the constants above)
such that for all $n\geq 1$, $\Lambda_{3m,m}$ is $c$-crossable.

###### Proof.

This is an application of Lemmas 2.3 and 2.4. Indeed, if
$B(o,C_{\textsf{Euc}}n\log n)$ is very good then items (i), (iv) and (v) imply
c-crossability by Lemma 2.3. The lower bound of item (ii) establishes (Vol),
so we only need to establish (P) for every $B(y,r)\subset
B(o,C_{\textsf{Euc}}n\log n)$ for $n^{1/9}\leq r\leq C_{\textsf{Euc}}n\log n$
(i.e., we choose $N_{B(o,C_{\textsf{Euc}}n\log n)}=n^{1/9}$).

Fix $y$ with $B(y,r)\subseteq B(o,C_{\textsf{Euc}}n\log n)$, and write $B_{r}$
for $B(y,r)$ to minimize notation. Notice that for any $B_{r}\subseteq
B(o,C_{\textsf{Euc}}n\log n)$ with $n^{1/9}\leq r\leq C_{\textsf{Euc}}n\log n$
and any connected set $A\subseteq B_{r+1}$ with
$n^{1/9}<|A|_{E}\leq|B_{r+1}|_{E}/2$, we have

$i_{B_{r+1}}(A)\geq
C_{I}|A|^{-1/2}_{E}\geq\frac{C_{I}\sqrt{2}}{\sqrt{C_{V}^{\prime}}(r+1)}$

by the upper bound of item (ii) and the isoperimetric inequality (iii). On the
other hand, if $|A|_{E}\leq n^{1/9}$, then trivially
$i_{B_{r+1}}(A)\geq|A|^{-1}_{E}\geq n^{-1/9}\geq r^{-1}$. Thus, by possibly
decreasing $C_{I}$ and increasing $C^{\prime}_{V}$ if needed, we obtain that

$I_{B_{r+1}}\geq\tilde{C}r^{-1}$

with $\tilde{C}=C_{I}\sqrt{2/C^{\prime}_{V}}$.

Now choose $C_{W}=2$, and for any function $f:B_{2r}\mapsto\mathbb{R}$.
Restrict $f$ to the graph induced by $B_{r}$ union all the vertices in
$\partial_{E}(B_{r},G\setminus B_{r})$.

$\displaystyle\sum_{v\in V(B_{r})}(f(v)-\bar{f})^{2}\deg_{G}(v)$
$\displaystyle\leq\sum_{v\in V(B_{r})}(f(v)-\bar{f}_{B_{r+1}})^{2}\deg_{G}(v)$
$\displaystyle\leq\sum_{v\in
V(B_{r+1})}(f(v)-\bar{f}_{B_{r+1}})^{2}\deg_{B_{r+1}}(v)$
$\displaystyle\leq\frac{cr^{2}}{\tilde{C}^{2}}\sum_{e\in
E(B_{r+1})}\lvert\nabla f(e)\rvert^{2}.$

where $c$ is as in Lemma 2.4. Notice that cannot directly use Lemma 2.4 as the
degrees are counted in $G$ which could potentially be large as we have no
assumption on the degree bound. The first inequality follows from the fact
that $\bar{f}$ is the minimum over $a$ of $\sum_{v\in
V(B_{r})}(f(v)-a)^{2}\deg_{G}(v)$. The second inequality is a trivial addition
of nonnegative terms along with the fact that $\deg_{G}(v)=\deg_{B_{r+1}(v)}$
if $v\in B_{r}$. The final inequality follows from Lemma 2.4 applied to
$B_{r+1}$. Thus, we have established (P) with $C_{P}=c\tilde{C}^{-2}$ since
adding $|\nabla f(e)|^{2}$ over the rest of the edges of $B_{2r}$ only
increases the right hand side. ∎

##  3 RSW for Bernoulli Percolation

In this section, we focus on Bernoulli bond percolation on $\mathbb{Z}^{2}$.
For $p\in[0,1]$ let $\mathbb{P}_{p}$ denote the Bernoulli bond percolation
probability measure induced by i.i.d. coin flips, one for each edge of
$\mathbb{Z}^{2}$. We call an edge open if the edge is present, and closed
otherwise. A cluster denotes a connected component of open edges. It is well
known that for $p>p_{c}:=1/2$ (i.e. the percolation is supercritical) there
exists a unique infinite cluster almost surely (see e.g. [10]), call it
$\mathcal{C}_{\infty}$. We refer to [8] for relevant history and references of
this very popular model. Our main result in this section is an RSW type result
for random walk on $\mathcal{C}_{\infty}$. Recall the definition of
$c$-crossable from (2.1).

######  Theorem 3.1.

Fix $p>p_{c}=1/2$ and let $\mathcal{C}_{\infty}$ be the unique infinite
cluster for supercritical bond percolation in $\mathbb{Z}^{2}$ induced by the
probability measure $\mathbb{P}_{p}$. There exist constants
$c_{p},c,\alpha\in(0,1]$ such that for all $n\geq 1$,

$\mathbb{P}(\Lambda_{3n,n}\text{ is $c_{p}$-crossable})\geq
1-e^{-cn^{\alpha}}$

In the rest of the section, we fix $p>p_{c}$. We also denote by $B(x,r)$ the
graph distance balls in $\mathcal{C}_{\infty}$. Theorem 3.1 will be a quick
application of a combination of results in Barlow [2] and Lemma 2.3. Let us
begin with a standard lemma:

######  Lemma 3.2.

There exist constants $C_{\textsf{euc}}:=C_{\textsf{euc}}(p),c>0$ such that
for all $n\geq 1$,

$\mathbb{P}_{p}(B(o,C_{\textsf{euc}}^{-1}n)\subseteq\Lambda_{n}\subset
B(o,C_{\textsf{euc}}n))\geq 1-e^{-cn}.$

where recall that $o$ is the vertex of $\mathcal{C}_{\infty}$ nearest to the
origin.

###### Proof.

It is easy to see by triangle inequality and the fact that graph distance in
$\mathcal{C}_{\infty}$ is bigger than that in $\mathbb{Z}^{2}$, that for any
point $x\in B(o,C_{\textsf{euc}}^{-1}n$), $|x|\leq|o|+C_{\textsf{euc}}^{-1}n$
where $|\cdot|$ is the $\ell_{1}$-norm. On the other hand, by [9, eq. (4) and
references therein], $|o|\leq n/2$ with exponentially high probability in $n$.
Thus the first inclusion is satisfied for a large enough choice of
$C_{\textsf{euc}}$ with exponentially high probability in $n$. The other
inclusion is a similar standard application of [1, Theorem 1.1]. ∎

######  Lemma 3.3.

There exist positive constants $C_{P},C_{V},C_{W},c,c^{\prime},\alpha,d$ such
that for all $n\geq 1$, the following events hold with probability at least
$1-ce^{-c^{\prime}n^{\alpha}}$.

  * •

$|B_{2}|\geq dn^{2}$ where $B_{2}$ is the square as in Lemma 2.3 with
$z=(0,0)$.

  * •

$\Lambda_{n\log n}$ is $C_{\textsf{euc}},C_{P},C_{V},C_{W}$-very good with
$N_{B}\leq n^{1/4}$ with $C_{\textsf{euc}}$ as in Lemma 3.2.

###### Proof.

We apply Lemma 3.2 to first obtain a constant $C_{\textsf{euc}}$ as required.
By translation invariance, we can also assume $C_{\textsf{euc}}$ is large
enough so that $B(b,C_{\textsf{Euc}}^{-1}n)\subset B_{2}$ where $b$ is the
closest point to $(n/2,0)$ (i.e. the center of $B_{2}$ with $z=0$). Thus we
assume $B(o,C_{\textsf{Euc}}^{-1}n\log n)\subset\Lambda_{n\log n}$ and
$B(b,C_{\textsf{Euc}}^{-1}n)\subset B_{2}$ for the rest of the proof admitting
a cost exponentially small in $n$.

We now show that $B(o,C_{\textsf{euc}}n\log n)$ is $C_{P},C_{V},C_{W}$ very
good with stretched exponentially high probability and
$B(b,C_{\textsf{Euc}}^{-1}n)$. This is essentially a combination of [2,
Theorem 2.18 and Lemma 2.19], let us provide a brief explanation of the
results there. In [2, Theorem 2.18], it is proved for a box $Q$ of any size,
if certain events $H(Q,\alpha)$ and $D(Q,\alpha)$ hold, then the items in this
lemma are satisfied. (The events $H(Q,\alpha)$ and $D(Q,\alpha)$ are certain
geometric conditions whose exact definitions will not be important for us.)
Later in [2, Lemma 2.19], it is shown that $H(Q,\alpha)$ and $D(Q,\alpha)$
hold on the box $Q$ with stretched exponentially high probability in the size
of $Q$.

To be more precise, we apply [2, Theorem 2.18] for
$Q=\Lambda_{C_{\textsf{euc}}Cn\log n}$ for $C=3C_{\textsf{euc}}/2$ and
$\alpha=1/8$. With this choice, the first item in this lemma holds with
stretched exponentially high probability in $n$ as per item (a) of [2, Theorem
2.18] (with $r=C_{\textsf{Euc}}^{-1}n$, $y=b$) since
$|B_{2}|\geq|B_{C_{\textsf{Euc}}^{-1}}n|$. Also, the second item holds with
stretched exponentially high probability in $n$ as per item (c) of [2, Theorem
2.18] (with $R=C_{\textsf{euc}}n\log n$ and $y=o$). This finishes the proof. ∎

###### Proof of Theorem 3.1.

We apply Lemma 2.3. Lemma 3.2 justifies the existence of $C_{\textsf{euc}}\geq
1$ with $B(o,C_{Euc}^{-1}n)\subseteq B(o,n)\subseteq\Lambda_{n}\subset
B(o,C_{\textsf{euc}}n)$ losing a probability exponentially small in $n$.
Furthermore, Lemma 3.3 justifies the requirement the very good condition and
the lower bound on the volume of $B_{2}$ only losing a probability which is
stretched exponentially small in $n$. The lower bound on the distance between
the inner rectangle and the outer one is trivial since distances only increase
in $\mathcal{C}_{\infty}$ (choosing $c_{0}=0.1$ suffices). An application of
union bound on the above estimates finish the proof. ∎

##  4 RSW for Delaunay triangulation

Let $\Pi$ be a Poisson point process in $\mathbb{R}^{2}$ with intensity 1.
Recall that a Voronoi cell of $x\in\Pi$ is the set of points in
$\mathbb{R}^{2}$ whose closest point (in Euclidean distance) in $\Pi$ is $x$.
Let $\mathbb{T}$ denote the Voronoi triangulation which is formed by joining
two points in $\Pi$ by a straight line if their cells share a common edge (it
is a standard fact that this graph is a.s. a triangulation). We will denote by
$d_{\mathbb{T}}$ the graph distance in $\mathbb{T}$ and the graph distance
ball of radius $r$ around $x$ in $\mathbb{T}$ is denoted by
$B_{\mathbb{T}}(x,r)$ (for a point $x\in\mathbb{R}^{2}$, $B(x,r)$ denotes the
ball of radius $r$ around a vertex in $\mathbb{T}$ closest to $x$). We will
usually drop the subscript for notational convenience when the graph in
question is unambiguous.

In this section we will prove the following theorem.

######  Theorem 4.1.

Let $\mathbb{T}$ be the Voronoi triangulation formed by a Poisson process of
intensity 1. There exist constants $c_{\mathsf{RSW}},c,\alpha\in(0,1]$ such
that for all $n\geq 1$,

$\mathbb{P}(\Lambda_{3n,n}\text{ is $c_{\mathsf{RSW}}$-crossable})\geq
1-e^{-cn^{\alpha}}$

We refer to [14] for some results in this direction, but we failed find a
reference to the quantitative nature of the estimates we need, hence we prove
it in details.

Fix $s>0$ (think of $s$ as large but constant). Take the lattice
$s\mathbb{Z}^{2}$. For $x\in s\mathbb{Z}^{2}$, divide the box $\Lambda_{s}(x)$
into 400 equal sized boxes of size $s/10$, and call them the _smaller boxes_.
Call a box $\Lambda_{s}(x)$ $A$-red if each of the smaller boxes contain at
least one and at most $As^{2}$ many points in $\Pi$. Clearly, for every
$\varepsilon>0$, one can choose a large $s$ and $A$ so that $x$ is red with
probability at least $1-\varepsilon$ (since the number of points in the box
$\sim$ Poisson $(4s^{2})$). We call a box simply red if we let $A=\infty$
(i.e., we do not specify any upper bound of the number of vertices). We can
think of the collection of red boxes of the form $\\{\Lambda_{s}(x)\\}_{x\in
s\mathbb{Z}^{2}}$ as a site percolation configuration in
$\\{0,1\\}^{s\mathbb{Z}^{2}}$ with a vertex being 1 if and only if it is red.
Call this percolation configuration $\xi=\\{\xi_{x}\\}_{x\in
s\mathbb{Z}^{2}}\in\\{0,1\\}^{s\mathbb{Z}^{2}}$. Observe that $\xi$ is not
necessarily an i.i.d. Bernoulli as the boxes corresponding to two adjacent
vertices in $s\mathbb{Z}^{2}$ overlap. However, $\xi$ is a $2$-dependant
percolation: as soon as graph distance between $x$ and $y$ is strictly greater
than 2, $\Lambda_{s}(x)\cap\Lambda_{s}(y)=\emptyset$ and consequently
$\xi_{x}$ is independent of $\xi_{y}$.

Recall the notion of stochastic domination: $\xi$ stochastically dominates
$\xi^{\prime}$ if one can couple them in the same probability space with
$\xi_{x}\geq\xi^{\prime}_{x}$ for all $x\in s\mathbb{Z}^{2}$.

######  Lemma 4.2.

Fix $\varepsilon>0$ and let $s,\xi$ be chosen as above. Then $\xi$
stochastically dominates a Bernoulli site percolation in $s\mathbb{Z}^{2}$
with parameter $1-\varepsilon^{\prime}(\varepsilon)$ with
$\varepsilon^{\prime}\to 0$ as $\varepsilon\to 0$.

###### Proof.

As observed above, $\xi$ is a $2$-dependent site percolation. So by a result
of Liggett, Schonmann and Stacey [12, Theorem 0.0], $\xi$ dominates a
Bernoulli $(1-\varepsilon^{\prime})$ site percolation $\xi^{\prime}$ with
$\varepsilon^{\prime}\to 0$ as $\varepsilon\to 0$. ∎

A path in a graph is a sequence of vertices $v_{0},v_{1},\ldots,v_{k}$ such
that $v_{i}$ is adjacent to $v_{i+1}$ for all $0\leq i\leq k$, and the edges
$(v_{i},v_{i+1})$ for all $0\leq i\leq k$.

######  Lemma 4.3.

Let $x,y$ be adjacent vertices in $s\mathbb{Z}^{2}$ and assume
$\Lambda_{s}(x)$ and $\Lambda_{s}(y)$ are both $A$-red. Take any two smaller
boxes of side length $s/10$ in the rectangle
$\mathcal{R}:=\Lambda_{s}(x)\cup\Lambda_{s}(y)$ which are at least Euclidean
distance $s/4$ from the boundary of the rectangle. Then for any two points of
$\Pi$ in these boxes (which one can always find by definition of red), there
exists a path in $\mathbb{T}$ with at most $L:=800As^{2}$ many vertices
joining them, which lies completely inside $\mathcal{R}$.

###### Proof.

Join any two points in the first box and the second box by a straight line
$\mathcal{L}$. We claim that the Voronoi cells $\mathcal{L}$ intersects can
only belong to points of $\Pi\cap\mathcal{R}$. Indeed, if a cell corresponding
to a point outside $\mathcal{R}$ intersects $\mathcal{L}$, then there is a
point on $\mathcal{L}$ which is closer to a point outside $\mathcal{R}$ than
any point inside $\mathcal{R}$. Thus the disk of radius at least $s/4$ from
this point is empty. This means that one of the smaller boxes in $\mathcal{R}$
is empty, which is impossible since both the boxes $\Lambda_{s}(x)$ and
$\Lambda_{s}(y)$ are red. This completes the proof of the claim. It is easy to
construct a path in the Voronoi triangulation using only the vertices of the
cells $\mathcal{L}$ intersects. Also since $\mathcal{R}$ is convex, all the
edges of this path also lie inside $\mathcal{R}$. This path can have at most
$800As^{2}$ many vertices as $\Lambda_{s}(x)$ and $\Lambda_{s}(y)$ are $A$-red
and hence contains at most $800As^{2}$ points in total. ∎

We now state a quick result for Bernoulli site percolation in a graph. An open
vertex cluster is a connected component in the graph induced by the open
vertices. Recall that in a percolation configuration, the _chemical distance_
between two vertices in the same open vertex cluster is the length shortest
path in the cluster connecting those two points. It is well-known (see e.g.
Grimmett [10]) that there exists a unique open infinite cluster in
$\mathbb{Z}^{2}$ for $p>p_{c}\approx 0.59$.

######  Lemma 4.4.

There exist constants $c,c^{\prime},C>0$ such that for all $n,k\geq 1$ the
following holds. Take a Bernoulli $p$-site percolation in $\mathbb{Z}^{2}$
with $p>0.9$ and let $\mathcal{C}_{\infty}$ be the unique infinite open vertex
cluster. Let $\mathcal{C}_{n}=\mathcal{C}_{\infty}\cap\Lambda_{n}$. Let
$D_{n,k}$ be the following event

  * •

The chemical distance diameter of $\mathcal{C}_{n}$ is at least $n/2$ and at
most $Cn$.

  * •

For any vertex in $x\in\Lambda_{n}\cap\mathbb{Z}^{2}$,
$\Lambda_{k}(x)\cap\mathcal{C}_{\infty}\neq\emptyset$.

  * •

$\max\\{|\mathcal{H}(x)|:x\in\Lambda_{n}\cap\mathbb{Z}^{2}\\}\leq k^{2}$ where
$\mathcal{H}(x)$ denote the maximal $*$-connected cluster in containing $x$
containing no vertex from $\mathcal{C}_{n}$ (call $\mathcal{H}(x)$ the hole
containing $x$)111$x,y$ are $*$-connected by closed vertices, if there is a
path of closed vertices with two consecutive vertices at distance either 1 or
2 in $\mathbb{Z}^{2}$ (i.e. diagonally adjacent or regular adjacent)
connecting $x$ and $y$. It is well-known that a regular cluster is blocked by
a $*$-connected circuit..

Then the probability of $D_{n,k}$ is at least
$1-cn^{4}e^{-c^{\prime}\sqrt{n}}-cn^{2}e^{-c^{\prime}k}$.

###### Proof.

This lemma follows from some known results which we first gather. Let
$\mathbb{P}_{p}$ denote the probability measure induced by the percolation and
let $D$ denote the chemical distance. Let $x\leftrightarrow y$ denote the
event that $x$ is connected to $y$, with $y=\infty$ meaning that $x$ is in an
infinite cluster. Let $|x|$ denote the graph distance in $\mathbb{Z}^{2}$. [1,
Theorem 1.1] states that there is a constant $C=C(p)$ and $c$ such that for
all $x\in\mathbb{Z}^{2}$,

$\mathbb{P}_{p}(0\leftrightarrow x,D(0,x)>C|x|)\leq e^{-c|x|}.$ (4.1)

Although the result in [1] is about bond percolation, it can be easily
extended to an analogous result for site percolation since we took $p$ large
enough. (e.g. by using [12, Theorem 0.0] again). It also follows from [9, eq.
(4) and references therein] and translation invariance that for any
$x\in\mathbb{Z}^{2}$,

$\mathbb{P}_{p}(\mathcal{C}_{\infty}\cap\Lambda_{k}(x)=\emptyset)\leq e^{-ck}$
(4.2)

Note again, that the results cited hold for bond percolation, but they can be
easily translated to site percolation as we took $p$ large enough.

Using (4.2), we see that $\mathcal{C}_{\infty}$ intersects $\Lambda_{n/2}$
with a probability which is exponentially high in $n$. This immediately
implies that the chemical distance diameter of $\mathcal{C}_{n}$ is at least
$n/2$ on this event (since $\mathcal{C}_{n}$ must intersect the complement of
$\Lambda_{n}$). Also, (4.2) and a union bound over all $x\in\Lambda_{n}$
ensures the second item is valid with probability at least
$1-4n^{2}e^{-c^{\prime}k}$.

We now show that the third item holds with probability $1-cn^{2}e^{-ck}$.
Indeed by isoperimetry of $\mathbb{Z}^{2}$, if the volume of the $*$-connected
hole $\mathcal{H}(x)$ is bigger than $k^{2}$ then there is a $*$-connected
closed circuit separating $\mathcal{C}_{\infty}$ from $x$ of diameter at least
$ck$. It is known that this event has probability exponentially small in $k$.
An union bound over all the vertices in $\Lambda_{n}\cap\mathbb{Z}^{2}$ upper
bounds the probability of
$\max\\{|\mathcal{H}(x)|:x\in\Lambda_{n}\cap\mathbb{Z}^{2}\\}>k^{2}$ by
$4n^{2}e^{-ck}$.

Furthermore, if the chemical distance diameter of $\mathcal{C}_{n}$ is bigger
than $Cn$ where $C$ is chosen according to (4.1), then there must be vertices
$x,y\in\Lambda_{n}\cap\mathbb{Z}^{2}$ with $D(x,y)>Cn$ and $x\leftrightarrow
y$. For any pair with $\|x-y\|\geq\sqrt{n}/10$ this probability is
exponentially small in $\sqrt{n}$ by eq. 4.1. On the other hand if
$\|x-y\|\leq\sqrt{n}/10$ and the chemical distance is larger than $Cn$, then
the cluster containing $x$ and $y$ must exit $\Lambda_{x}(\sqrt{n})$ but are
not connected within $\Lambda_{x}(\sqrt{n})$. This must mean there is a
$*$-connected closed cluster of diameter at least $c\sqrt{n}$ which separates
these clusters. But this event also has probability exponentially small in
$\sqrt{n}$. An union bound over the pairs $x,y$ shows that the probability of
the diameter of $\mathcal{C}_{n}$ being at least $Cn$ is at most
$Cn^{4}e^{-c\sqrt{n}}$.222This part of the bound is probably not optimal, but
since we will be content with a stretched exponential bound anyway in the end,
we do not pursue to make this optimal.

The result follows by observing that $D_{n,k}$ contains the intersection of
these events. ∎

Recall the notation $B(x,r)$ which denotes the graph distance ball of radius
$r$ in the Voronoi triangulation from a point in $\Pi$ which is closest to
$x$.

######  Lemma 4.5.

There exist constants $C_{\textsf{euc}},c,c^{\prime}>0$ such that for all
$n\geq 1$, $\Lambda_{n}\subseteq B(o,C_{\textsf{euc}}n)$ with probability at
least $1-ce^{-c^{\prime}\sqrt{n}}$

###### Proof.

Choose $A,s$ such that the $2$-dependant percolation $\xi$ as described in
Lemma 4.2 dominates a Bernoulli $(1-\varepsilon^{\prime})$ site percolation
$\xi^{\prime}$ with $\varepsilon^{\prime}<0.01$. Couple $\xi,\xi^{\prime}$ so
that $\xi$ dominates $\xi^{\prime}$. Let $\mathcal{C}_{\infty}$ be the unique
infinite cluster of $\xi^{\prime}$ and let
$\mathcal{C}_{2n}=\Lambda_{2n}\cap\mathcal{C}_{\infty}$. Choose $C$ as in
Lemma 4.4.

We will pick a box of the form $S:=\Lambda_{s}(x)\subset\Lambda_{n}$ with
$x\in s\mathbb{Z}^{2}$ and show that any point in $\Pi\cap S$ can be connected
to $o$ by a path of length $O(n)$ in $\mathbb{T}$ with stretched exponentially
high probability. Also assume that if $S$ is empty, this event is vacuously
satisfied. Since there are at most $n^{2}/s^{2}$ many such boxes, a further
union bound does the job.

Assume $|S\cap\Pi|\neq\emptyset$ and assume
$\mathcal{D}^{\prime}_{n}:=\mathcal{D}_{2n,\sqrt{n}/10}$ occurs for
$\xi^{\prime}$ where the event is as described in Lemma 4.4 and fix a sample
of the Point process in $\mathcal{D}^{\prime}_{n}$. Let $\mathcal{H}_{0}$ and
$\mathcal{H}_{1}$ denote the holes of $\xi$ containing the box
$S^{\prime}:=\Lambda_{s}(0)$ and $S$ respectively, where holes are as defined
in third item of Lemma 4.4. Note that $|\mathcal{H}_{0}|\leq n/100$ and
$|\mathcal{H}_{1}|\leq n/100$ on $\mathcal{D}^{\prime}_{n}$ since $\xi$
dominates $\xi^{\prime}$. These clusters are surrounded by open circuits in
$\xi$ each lying completely in $\mathcal{C}_{2n}$. Now using Lemma 4.3 by
concatenating paths in $\mathbb{T}$ in the boxes corresponding to these
circuits, we can find circuits $C,C^{\prime}$ in $\mathbb{T}$ completely
surrounding $S$ and $S^{\prime}$ respectively. This allows us to find a path
from any point inside $C$ to any point inside $C^{\prime}$ as follows. Find
the shortest path in $\mathbb{T}$ until $C,C^{\prime}$ is hit and suppose they
hit the circuits at vertices $u,v\in\mathbb{T}$, in boxes $B_{u},B_{v}$
respectively. Clearly, the length of these paths can be at most the volume of
the holes, so at most $n/100$ each. Then find the shortest path in
$s\mathbb{Z}^{2}$ using $\mathcal{C}_{2n}$ joining $B_{u}$ and $B_{v}$. This
path has length at most $2Cn$ on $\mathcal{D}^{\prime}_{n}$. Furthermore since
all the boxes corresponding to vertices in this path are $A$-red, using Lemma
4.3 we can find a path in $\mathbb{T}$ joining $u$ and $v$ of length at most
$1600As^{2}Cn$. Thus the length of the path is at most $C^{\prime}n$ with
$C^{\prime}=1600As^{2}C+1/50$ on $\mathcal{D}^{\prime}_{n}$. We finish by
applying Lemma 4.4 to lower bound the probability of
$\mathcal{D}^{\prime}_{n}$ by $1-ce^{-c^{\prime}{\sqrt{n}}}$ for appropriate
choices of $c,c^{\prime}$. ∎

Now recall the following standard fact about Binomial random variables.

######  Lemma 4.6.

Let $X\sim$ Binomial $(n,1-\varepsilon)$ and fix $c\in(0,1)$. Then for all
$n\geq 1$

$\mathbb{P}(X<cn)\leq e^{-C(\varepsilon,c)n}$

where $C(\varepsilon,c)\to\infty$ as $\varepsilon\to 0$.

Now we prove a lemma which states a quantitative bound on the probability that
a path in the Voronoi triangulation has many long edges. For connected
subgraph $S$ in the Voronoi triangulation, its Euclidean diameter is denoted
by $\operatorname{Diam}_{\textsf{euc}}(S):=\sup\\{|x-y|,x,y\in S\\}$.

######  Lemma 4.7.

There exist constants $C_{0},c_{0}>0$ such that for all $n\geq 1$ and for all
$C>C_{0}$, the probability that there exists a connected set intersecting
$\Lambda_{1}$ with at most $n$ vertices and Euclidean diameter 333Euclidean
diameter of a set $A\subset\mathbb{R}^{2}$ is $\sup\\{|x-y|:x,y\in A\\}$.  at
least $Cn$ is at most $2^{-Cc_{0}n}$.

###### Proof.

Fix $\varepsilon>0$ and choose $s$ large enough such that the site percolation
$\xi$ defined in Lemma 4.2 dominates a Bernoulli percolation with high
probability, as asserted there. Take a connected subgraph $D$ with at most $n$
vertices intersecting $\Lambda_{1}$. Let $S(D)$ be the collection of squares
of the form $\Lambda_{s}(x)$ with $x\in s\mathbb{Z}^{2}$ which intersect (some
vertex, edge or triangle of) $D$. Let $k$ be the number of squares in $S(D)$.
Because of the large Euclidean diameter of $D$, $k>\frac{Cn}{2s}$. We say a
square is _good_ if it is red and all the squares intersected by it is red,
otherwise we say it’s bad (recall the definition of a red box from the
beginning of this section). This corresponds to a 4-dependant site percolation
in $s\mathbb{Z}^{2}$. Thus again using [12, Theorem 0.0], and increasing $s$
if necessary, we can ensure that the collection of good sites dominates a
$(1-\varepsilon^{\prime})$-Bernoulli site percolation in $s\mathbb{Z}^{2}$
with $\varepsilon^{\prime}<\varepsilon$.

We claim that if a square $A$ in $S(D)$ is good, the collection of squares
$A^{\prime}$ of the form $\\{\Lambda_{s}(x):x\in s\mathbb{Z}^{2}\\}$ which
intersect $A$ contain at least 1 vertex from $D$. To see this observe that if
no edge intersects $A$ then $A\cap\Pi$ is empty, which is not possible as $A$
is red. On the other hand if an edge $e$ intersects $A$, and one of the
endpoints of this edge does not lie in one of $A^{\prime}$, then $e$ must have
length at least $2s$. We know that one of the semi-discs of the disc with
diameter $e$ is empty in a Voronoi triangulation. This must mean that one of
the squares of side $s/10$ in one of the squares $A^{\prime}$ must be empty,
which is a contradiction to the fact that all squares intersecting $A$ are
red. Thus one of the endpoints of $e$ must be in some $A^{\prime}$. One
consequence of this is that the number of good squares is at most $9n$ (since
we can overcount a vertex at most 9 times).

It is well known that the number of connected sets in $\mathbb{Z}^{2}$ with
$k$ vertices containing the origin is at most $\Delta^{k}$ for some
$\Delta>0$. Choose $\varepsilon$ small enough so that
$e^{-C(\varepsilon,1/2)}<(2\Delta)^{-1}$ where $C(\varepsilon,1/2)$ is as in
Lemma 4.6. Now choose $C>C_{0}:=36s=36s(\varepsilon)$ and $c_{0}=(2s)^{-1}$.
For a fixed connected set in $s\mathbb{Z}^{2}$ containing the origin and
containing $k$ vertices, the number of good vertices $X$ dominates a Binomial
$(k,1-\varepsilon)$. Recall that $k>\frac{Cn}{2s}>18n$. Thus

$\mathbb{P}(X<9n)\leq\mathbb{P}(X<k/2)\leq
e^{-C(\varepsilon,1/2)k}<(2\Delta)^{-k}$

again using Lemma 4.6. Since the number of connected sets is at most
$\Delta^{k}$, an union bound gives that the required probability is at most

$(1/2)^{k}\leq(1/2)^{Cn/2s}=(1/2)^{Cc_{0}n}$

as desired. ∎

An immediate corollary is the following:

######  Corollary 4.8.

There exists a constant $C,c>0$ such that for all $n\geq 1$,
$B(o,n)\subseteq\Lambda_{Cn}$ with probability at least $1-e^{-cn}$.

###### Proof.

Note that the event $o\in\Lambda_{n/10}$ has probability at least
$e^{-cn^{2}}$ since $\Pi$ is a Poisson process. Apply Lemma 4.7 to any path
with $n$ vertices starting from $O(n^{2})$ many translates of $\Lambda_{1}$
inside $\Lambda_{n/10}$. ∎

We now use Lemma 4.7 to establish a quantitative isoperimetric inequality. We
recall some topological notions first. For a finite connected set of vertices
$A\subset\mathbb{T}$, we can consider the subgraph induced by $A$, which we
also call $A$ admitting an abuse of notation. This allows us to consider the
faces which has all its incident edges in $A$. Overall, we can think of $A$ as
a subset of $\mathbb{R}^{2}$, by taking the union of all the vertices, edges
and faces described as such. We define the _complement_ of $A$ to be the
complement of the union of the faces and edges of $A$. We say $A$ is _simply
connected_ if the complement has a unique component (which necessarily is the
unbounded component a.s.). If $A$ is not simply connected, it’s complement may
contain a certain number of finite components and one unique infinite
component. Let $\partial_{V}(A)$ denote the vertex boundary of $A$, which is
the collection of vertices of $A$ which has some neighbour outside $A$.

######  Lemma 4.9.

There exist constants $\varepsilon_{0},c,c^{\prime},C>0$ such that for all
$n\geq 1,\alpha\in(0,2)$ the following holds. The probability that there
exists a connected set $A\subset B(o,n)$ with
$k\in[n^{\alpha},\frac{1}{2}n^{2}]$ vertices but

$\mathcal{B}(A):=\\{|\partial_{V}A|\leq\varepsilon_{o}\sqrt{k}\\}\cup\\{\operatorname{Diam}(A)\leq
C\varepsilon_{0}\sqrt{k}\\}$

holds is at most $ce^{-c^{\prime}\sqrt{k}}$. Here $\operatorname{Diam}$
denotes the graph distance diameter.

###### Proof.

Roughly, the idea is as follows: if $|\partial_{V}A|$ is small, then the
Euclidean diameter must also be small up to a constant factor by Lemma 4.7,
and consequently a square of small diameter containing at least as many points
of $A$ is unlikely. We now make this idea rigorous by carefully tracking the
quantifiers.

First observe that it is enough to prove the bound for sets $A$ which are
simply connected, for otherwise we can simply fill in the finite holes, and
this operation decreases boundary size but increases the size of $A$ and also
decreases $\operatorname{Diam}(A)$. Thus $\partial_{V}A$ has a single
connected component. It is a standard fact that the Euclidean diameter of $A$
is the same as the diameter of its boundary. Thus for any point $x$ in $A$,
$\Lambda_{2m}(x)\supseteq A$ where
$m=\operatorname{Diam}_{\textsf{euc}}(\partial_{V}A)$.

Fix $k\in[n^{\alpha},\frac{1}{2}n^{2}]$. First using Corollary 4.8 find a
$C_{1}$ such that $B(o,n)\subset\Lambda_{C_{1}n}$ with probability at least
$1-e^{-c_{1}n}$. Suppose $\partial_{V}A$ intersects $\Lambda_{1}$ for some $A$
with $|A|=k$ and $|\partial_{V}(A)|\leq\varepsilon_{0}\sqrt{k}$ where
$\varepsilon_{0}$ is to be fine tuned later. Now pick $c_{0},C_{0}$ as in
Lemma 4.7 and $C>C_{0}$. The probability that any connected set of size at
most $\varepsilon_{0}\sqrt{k}$ intersecting $\Lambda_{1}$ has Euclidean
diameter at most $C\varepsilon_{0}\sqrt{k}$ is at least
$1-e^{-Cc_{0}\varepsilon_{0}\sqrt{k}}.$ Thus on this event
$A\subset\Lambda_{m^{\prime}}$ with $m^{\prime}=2C\varepsilon_{0}\sqrt{k}$;
and in particular, on this event, $\Lambda_{2m}$ contains at least $k$
vertices. Now pick an $\varepsilon_{0}=\varepsilon_{0}(C)$ small enough so
that the the probability that the number of vertices in $\Lambda_{2m}$ is at
least $k$ is at most $e^{-c^{\prime}k}$ for some $c^{\prime}$. Thus overall
for this choice of $\varepsilon_{0}$, the probability that there exists a set
$A$ intersecting $\Lambda_{1}$ such that $\mathcal{B}(A)$ holds but $|A|\geq
k$ is at most $e^{-Cc_{0}\varepsilon_{0}\sqrt{k}}+e^{-c^{\prime}k}$.

Finally, on the event that $B(o,n)\subset\Lambda_{C_{1}n}$, we can take a
union bound of the above replacing $\Lambda_{1}$ by at most $4C_{1}^{2}n^{2}$
many translates of $\Lambda_{1}$. This yields that the probability of the
event in the lemma is at most

$4C_{1}^{2}n^{2}(e^{-Cc_{0}\varepsilon_{0}\sqrt{k}}+e^{-c^{\prime}k})+e^{-c_{1}n}.$

Since $k\geq n^{\alpha}$ with $\alpha\in(0,1)$, we can find $c,c^{\prime}>0$
such that the above quantity is bounded above by $ce^{-c^{\prime}\sqrt{k}}$.
Taking a further union bound over all integers
$k\in[n^{\alpha},\frac{1}{2}n^{2}]$, we conclude by modifying the choice of
$c,c^{\prime}$ appropriately. ∎

Notice that the boundary in Lemma 4.9 considers the vertex boundary in the
whole Voronoi triangulation. However, the bound in (2.3) only counts the
boundary edges of $A\subset B(y,r)$ inside $B(y,r)$. In the next lemma, we
strengthen Lemma 4.9 to show that even discarding the edges going out of
$B(y,r)$, there are many edges left over in the boundary with high
probability. To do this, we require the following elementary geometric lemma.

######  Lemma 4.10.

Let $A\subset B(o,n)$ and suppose $\partial_{V}(A)$ has a single connected
component. Assume that $\partial_{V}(A)\cap\partial_{V}(B(o,n))\neq\emptyset$.
Let $\partial_{\mathsf{int}}(A)$ denote the set of vertices in
$\partial_{V}(A)$ with at least one neighbour in $B(o,n)\setminus A$ and
assume $|\partial_{\mathsf{int}}(A)|=k$. Then for any
$v\in\partial_{\mathsf{int}}(A)$, $A\subset B(v,2k)$.

###### Proof.

Recall $d$ denotes the graph distance in $\mathbb{T}$. Notice that for any
$v\in\partial_{\mathsf{int}}$, $d(v,\partial_{V}(B(o,n)))\leq k$ since
$\partial_{V}(A)\cap\partial_{V}(B(o,n))\neq\emptyset$ and hence
$\partial_{\mathsf{int}}$ and $\partial_{V}(B(o,n))$ must be at distance $1$.
Thus triangle inequality yields $d(o,v)\geq n-k$. Observe that for any vertex
$w\in A$, a geodesic from $o$ to $w$ must intersect
$\partial_{\mathsf{int}}(A)$ since $\mathbb{T}$ is planar (since this geodesic
must enter $A$ through some vertex, and this vertex is necessarily in
$\partial_{\mathsf{int}}(A)$). Let $w^{\prime}$ be such a vertex which is
closest to $o$. By triangle inequality, and since $d(o,w^{\prime})\geq n-k$,
$d(w^{\prime},w)=d(o,w)-d(o,w^{\prime})\leq n-(n-k)=k$. Then $d(v,w)\leq
d(v,w^{\prime})+d(w^{\prime},w)\leq 2k$. This completes the proof. ∎

######  Lemma 4.11.

There exist constants $\varepsilon_{1},c,c^{\prime}>0$ such that for all
$n\geq 1,\alpha\in(0,2)$ and $k\in[n^{\alpha},\frac{1}{2}n^{2}]$ the following
holds. The probability that there exists a connected set $A\subset B(o,n)$
with $k$ vertices but with
$|\partial_{\mathsf{int}}(A)|\leq\varepsilon_{1}\sqrt{k}$ is at most
$ce^{-c^{\prime}\sqrt{k}}$ where $\partial_{\mathsf{int}}(A)$ is defined as in
Lemma 4.10.

###### Proof.

If all the vertices of $A$ are in $B(o,n-1)$, then
$\partial_{V}(A)=\partial_{\mathsf{int}}(A)$, and we simply choose
$\varepsilon_{1}=\varepsilon_{0}$ where $\varepsilon_{0}$ is as in Lemma 4.9.
On the other hand, if $A$ intersects $\partial B(o,n)$, then by Lemma 4.10,
the graph distance diameter of $A$ is at most $4|\partial_{\mathsf{int}}(A)|$.
Thus again by Lemma 4.9, we can choose
$\varepsilon_{1}=\min\\{\varepsilon_{0},C\varepsilon_{0}/4\\}$. ∎

######  Lemma 4.12.

For any $A\subseteq B(o,n)$ ,

$i_{B(o,n)}(A)=\frac{|\partial_{E}(A,B(o,n)\setminus
A)|}{|A|_{E}}\geq\frac{|\partial_{\mathsf{int}}(A)|}{7|A|}$

where $|A|_{E}$ is the sum of the degrees of vertices in $A$ counting only
edges in $B(o,n)$ and $\partial_{\mathsf{int}}(A)$ is as in Lemma 4.10.

###### Proof.

Let $E$ be the edge set of the subgraph induced by $A$. Notice that this
subgraph is a subgraph of a triangulation, hence the faces form a collection
of triangles and (potentially non-simple) polygons, call the latter outer
faces. Without loss of generality, we can assume that there is only one outer
face, as otherwise we can fill in the bounded faces, thereby decreasing
$i_{B(o,n)}(A)$. Let $|P|$ denote the perimeter of the outer face which counts
the number of edges in it, with the edges having both sides adjacent to $P$
counted twice. Let $F$ denote the set of triangles in this graph. By Euler’s
formula, $|A|-|E|+|F|+1=2$. Also note, $2|E|=3|F|+|P|$. Combining, we get
$|E|=3|A|-|P|-3\leq 3|A|$. Also note
$|A|_{E}=2|E|+|\partial_{E}(A,B(o,n)\setminus A))|$. Thus

$i_{B(o,n)}(A)\geq\frac{|\partial_{E}(A,B(o,n)\setminus
A))|}{6|A|+|\partial_{E}(A,B(o,n)\setminus
A))|}\geq\frac{|\partial_{\mathsf{int}}(A)|}{7|A|}$

The last inequality follows from $|\partial_{E}(A,B(o,n)\setminus
A))|\geq|\partial_{\mathsf{int}}(A)|$, the fact that $x\mapsto x/(6+x)$ is
increasing in $x$ and $x/(6+x)\geq x/7$ for all $x\in(0,1)$. ∎

###### Proof of Theorem 4.1.

We will simply prove that the items in Lemma 2.5 holds with stretched
exponentially high probability for appropriate choice of constants (we use the
notations there). Firstly, $(iv)$ holds with exponentially high probability in
$n^{2}$ for a small enough choice of $d$ using standard estimate of a Poisson
variable. It follows from Lemmas 4.5 and 4.8 that $(i)$ holds with stretched
exponentially high probability in $n\log n$ for an appropriately large choice
of $C_{\textsf{euc}}$. Now fix $r\in[n^{1/9},C_{\textsf{euc}}n\log n]$. It is
easy to see that the volume of $B(o,r)$ is upper and lower bounded by some
constant in $r^{2}$ with stretched exponentially high probability in $r$,
again using Lemmas 4.5 and 4.8 and standard properties of a Poisson process.
Applying Corollary 4.8 to $O(n^{2})$ many translates of $\Lambda_{1}$, we can
also ensure $(ii),(v)$ holds with exponentially high probability in $r$.
Finally, choosing $\varepsilon_{1}$ as in Lemma 4.11, we can ensure that
$(iii)$ holds with $C_{I}=\varepsilon_{1}/7$ and with probability at least
stretched exponentially high in $r$ (and consequently stretched exponentially
high in $n$.). Now we take an union bound over integers
$r\in[n^{1/9},C_{\textsf{euc}}n\log n]$ to complete the proof. ∎

##  5 General criterion for macroscopic decorrelation in Uniform spanning
trees in random environment

Let $\mu$ be a probability measure supported on infinite, locally finite, one
ended, random, planar graphs embedded in a proper way in the plane. Recall
that an embedding is proper if no two edges cross each other. In this section,
we present a result which is an adaptation of [4, Theorem 4.21], but for
random graphs with law $\mu$. Recall that the examples which concern us are
Poisson Voronoi triangulation, and the infinite cluster of a supercritical
Bernoulli percolation. We now state the two main assumptions on $\mu$. Let
$G=(V(G),E(G))$ be a sample from $\mu$. Recall the definition of $C$-crossable
from Definition 2.1.

  1. (i)

The law of $\mu$ is invariant under translations and $\pi/2$-rotations of the
plane.

  2. (ii)

(RSW). There exist constants $c_{\mu},d,d^{\prime},\alpha>0$ such that for all
$n\geq 1$, $\Lambda_{4n,n}$ is $c_{\mu}$-crossable with $\mu$-probability at
least $1-de^{-d^{\prime}n^{\alpha}}$.

  3. (iii)

(Vol) There exist constants $C_{\mu},\beta>0$ such that $\mu(|\Lambda_{n}\cap
V(G)|\geq C_{\mu}n^{2})\leq e^{-\beta n^{2}}$.

We now state our result for decoupling of uniform spanning trees from the
point of view of scaling limits. Let $\delta G$ be a rescaling of the embedded
graph $G$ by $\delta$. Let $D\subset\mathbb{R}^{2}$ be a domain which will
always be an open, simply connected set in this section. Let $D^{\delta}$
denote the graph induced by the vertices of $G^{\delta}$ in $D$ where
$\partial_{V}D^{\delta}$ is identified into a single vertex (i.e. we consider
a wired boundary condition). A spanning tree of a finite graph $H$ is a
subgraph which contains all the vertices of $H$ and does not contain any
cycle. Recall that a uniform spanning tree on a finite graph is simply a
uniformly picked spanning tree of the graph.

Random walks and uniform spanning trees are intimately related to each other
via the celebrated Wilson’s algorithm which we quickly describe here. Order
the vertices of $D^{\delta}$ in any order. Now perform a loop erased random
walk, i.e. a simple random walk where one chronologically erases the loop. We
continue this until the walk hits the boundary vertex (the wired boundary).
This samples a simple path $\gamma$ starting at $v_{1}$ and ending at the
boundary vertex. Then we sample the next vertex in the ordering which is not
in $\gamma$, and repeat the same procedure with the new boundary being the
boundary vertex union $\gamma$. We iterate, until all the vertex belong to
some path. The final object thus obtained is a sample from a uniform spanning
tree. See [15], or [13, Section 4.1] for a proof of this fact.

######  Theorem 5.1.

Suppose $G$ sampled from $\mu$ satisfies the above conditions for some
constants $c_{\mu},\alpha,C_{\mu},\beta$ and let $z_{1},\ldots,z_{k}$ be $k$
points in a domain $D$ where $\Lambda_{1}\subset D\subset\Lambda_{10}$ and let
$r=\min_{i\neq j}|z_{i}-z_{j}|\wedge d(z_{i},\partial D)$ where $d$ is the
Euclidean distance. There exists a constant
$c=c(c_{\mu},\alpha,C_{\mu},\beta)>0$ such that for all
$\varepsilon,\varepsilon^{\prime}>0$, there exists a
$\delta_{0}=\delta_{0}(\varepsilon^{\prime})$ such that for all
$\delta\leq\varepsilon\wedge\delta_{0}(\varepsilon^{\prime})$ the following
holds. There exists a collection of graphs $\mathcal{G}$ with
$\mu(\mathcal{G})>1-\varepsilon$ such that for any $G$ in $\mathcal{G}$ the
following holds.

Let $\mathcal{T}^{\delta}$ be a sample of a wired Uniform spanning tree in
$D^{\delta}$. Then there exists a coupling $\mathbf{P}^{G}$ between
$\mathcal{T}^{\delta}$ and a collection $\\{\mathcal{T}_{i}^{\delta}\\}_{1\leq
i\leq k}$ such that

  * •

$\\{\mathcal{T}_{i}^{\delta}\\}_{1\leq i\leq k}$ are i.i.d. copies of
$\mathcal{T}^{\delta}$.

  * •

$\mathcal{T}_{i}^{\delta}\cap\Lambda_{R}(z_{i})=\mathcal{T}^{\delta}\cap\Lambda_{R}(z_{i})$
for all $1\leq i\leq k$ where $R$ is a random variable satisfying

$\mathbf{P}^{G}(R\leq\varepsilon^{\prime}r)\leq(\varepsilon^{\prime})^{c}.$

######  Remark 5.2.

If we fix $\varepsilon^{\prime}>0$ and apply Theorem 5.1 for a sequence
$\delta_{k}=\varepsilon_{k}=2^{-k}$ with
$2^{-k}<\delta_{0}(\varepsilon^{\prime})$, then by Borel–Cantelli, there
exists a collection $\mathcal{G}$ with $\mu(\mathcal{G})=1$ such that for any
$G\in\mathcal{G}$, the coupling $\mathbf{P}^{G}$ as in Theorem 5.1 holds for
all $k$ large enough depending on $G$.

In [4, Theorem 4.21] an analogous version was proved but for a _fixed_ graph,
where the condition (RSW) was valid above a certain fixed scale (called
$\delta_{0}$ in that article). The main new input in Theorem 5.1 is that an
analogous result holds with high probability with the more general condition
(RSW) above. One can also get an almost sure statement if we allow ourselves
to choose a subsequence of $\delta$ (notice the dependance
$\varepsilon\geq\delta$ in the statement of the theorem above), see Remark 5.2
below

Let $A(z,m,n)$ be the annulus $\Lambda_{n}\setminus\Lambda_{m}$ for $n>m$. Let
$R_{1},\ldots,R_{4}$ be the translations and 90 degree rotations of
$\Lambda_{2n,(n-m)/2}$ whose union is $A(z,m,n)$. We say $A(z,m,n)$ is
$c^{4}$-crossable if all the rectangles $R_{1},\ldots,R_{4}$ are $c$-crossable
(by Markov property of random walk, the probability for a random walk to make
a full turn in $A(z,m,n)$ is at least $c^{4}$). Let

$R^{\delta}(z)=\max\\{2^{i}\delta:A(z,2^{i}\delta,2^{i+1}\delta)\text{ is
{not} $c_{\mu}$-crossable in $\delta$G}\\}.$

Define

$R_{\max}^{\delta}=\max\\{R^{\delta}(z):z\in\Lambda_{10}\cap\delta\mathbb{Z}^{2}\\}.$

######  Lemma 5.3.

There exists a constant $C>0$ such that for all $\varepsilon,\delta>0$,

$\mu(R_{\max}^{\delta}>R_{0}^{\delta})\leq\varepsilon.$

where

$R_{0}^{\delta}=R_{0}^{\delta}(\varepsilon)=\delta\left[\ln\left(\frac{C}{\varepsilon\delta^{2}}\right)\right]^{1/\alpha}$
(5.1)

and $\alpha$ is as in (RSW).

Note that for any $\varepsilon$ which is at least $\delta^{m}$ for some $m$,
$R^{\delta}\to 0$ as $\delta\to 0$.

###### Proof.

Let

$\mathcal{B}_{1}=\cup_{j\geq m}\\{A(0,2^{j}\delta,2^{j+1}\delta)\text{ is not
$c_{\mu}$-crossable in $\delta G$}\\}.$

Notice that by (RSW), the invariance of $\mu$ under translation and
$\pi/2$-rotations, and a union bound,

$\mu(\mathcal{B}_{1})\leq\sum_{j\geq m}4e^{-2^{\alpha j}}=4\sum_{j\geq
0}(e^{-2^{\alpha m}})^{2^{\alpha j}}\leq C^{\prime}e^{-2^{\alpha m}}.$

for some constant $C^{\prime}>0$ independent of everything else. By
translation invariance, the same bound is true if we replace $0$ by any other
$z\in\delta\mathbb{Z}^{2}$. Since there are at most $400/\delta^{2}$ many
points in $\Lambda_{10}\cap\delta\mathbb{Z}^{2}$, by an union bound:

$\mu(R_{\max}^{\delta}>R_{0}^{\delta})\leq
C^{\prime}\frac{400}{\delta^{2}}e^{-2^{\alpha m}}$

where we choose $2^{m}\delta=R_{0}^{\delta}$. The right hand side above is at
most $\varepsilon$ if we choose $C=400C^{\prime}$. This completes the proof. ∎

######  Remark 5.4.

Note that for a choice of the sequence $\delta_{k}=\varepsilon_{k}=2^{-k}$ by
Borel–Cantelli, $\mu$-a.s. $R_{\max}^{\delta_{k}}\leq R_{0}^{\delta_{k}}$ for
all $k$ large enough. Also for this choice, $R_{0}^{\delta_{k}}\to 0$ as
$k\to\infty$.

An application of Lemma 5.3 is that for a large enough rectangle depending on
$R_{\max}^{\delta}$, RSW holds.

######  Lemma 5.5.

Fix a graph $G$ such that $R_{\max}^{\delta}\leq R_{0}^{\delta}$ where
$R_{0}^{\delta}$ is as in (5.1). Then for any $m\geq R_{0}$ and any rectangle
lying completely inside $D$ which is a translate of $\Lambda_{20m,5m}$ is
$c_{\mu}^{10}$-crossable. The same holds true for any rectangle which is a
translation and a $\pi/2$-rotation of $\Lambda_{20m,5m}$ and lies completely
inside $D$.

###### Proof.

This is a standard consequence of RSW theory. Indeed, any rectangle of the
form specified by the lemma can be covered by at most 10 many $2m\times 4m$
rectangles which is one of the rectangles of some $A(z,2m,4m)$ with
$z\in\delta\mathbb{Z}^{2}\cap\Lambda_{10}$ (recall that
$D\subset\Lambda_{1}$). The rest follows by applying the Markov property of
the random walk and using the fact that $m\geq R_{0}\geq R^{\delta}_{\max}$. ∎

One standard application of Lemma 5.5 is a Beurling type hitting estimate for
a random walk:

######  Lemma 5.6.

There exists $c,c^{\prime}$ such that for all $\varepsilon>0$ and for all
$\delta\leq\varepsilon$, the following holds. Let $K\subset D$ be a connected
set. Fix a $G\sim\mu$ such that $R^{\delta}_{\max}\leq
R_{0}^{\delta}(\varepsilon)$ and let $\mathbf{P}^{G}_{v}$ be the law of a
simple random walk $X$ in $G$ started from $v$. Let $d(v,\partial D)$ (resp.
$d(v,K)$) be the Euclidean distance between $v$ and $\partial D$ (resp. $K$).
Then

$\mathbf{P}^{G}_{v}(X\text{ exits $\Lambda_{d(v,\partial D)}(v)$ before
hitting $K$})\leq c\left(\frac{d(v,K)\vee
R_{0}^{\delta}(\varepsilon)}{d(v,\partial D)}\right)^{c^{\prime}}$

###### Proof.

This is standard once we have Lemma 5.5, so we skip the proof. We point out
that the term $R_{0}^{\delta}(\varepsilon)$ in the numerator appears because
we can apply RSW once the scale is larger than $cR_{0}^{\delta}$ since
$R_{\max}^{\delta}\leq R_{0}^{\delta}$ by the choice of $G$. ∎

Armed with this estimate, the rest of the proof of Theorem 5.1 follows the
same line of argument as in [4]. We provide a sketch of the argument pointing
out the crucial differences. We now describe the _good algorithm_ from [4,
Lemma 4.18]. Let $z\in D$ and suppose $r>0$ is small enough so that
$\Lambda_{2r}(z)\subset D$. Fix a $G\sim\mu$ and we now describe a way of
sampling the branches of $\mathcal{T}^{\delta}$ from the vertices of
$\Lambda_{r}^{\delta}(z)$. Let $\mathcal{Q}_{j}$ be the collection of vertices
of $G$ which are furthest from $z$ in each cell of
$\Lambda^{\delta}_{(1+2^{-j})r}(z)\cap r6^{-j}\mathbb{Z}^{2}$, from which a
branch is not sampled before (if there is no such vertex, we ignore that
cell). At each step $j$, we sample from $\mathcal{Q}_{j}$ in any order. This
results in a tree $\mathcal{T}^{\delta}_{j}$ which is the union of all the
branches sampled in steps 1 up to $j$. We continue until we exhaust all the
vertices in $\Lambda^{\delta}_{r}$.

######  Lemma 5.7.

Fix $D,z,r$ as above. For all $\varepsilon,\varepsilon^{\prime}>0$, there
exists a $j_{0}=j_{0}(\varepsilon^{\prime})$ such that for all
$\delta\leq\delta_{0}(r,\varepsilon^{\prime})\wedge\varepsilon$ the following
holds. Fix a $G$ such that $R^{\delta}_{\max}\leq R_{0}^{\delta}(\varepsilon)$
where $R_{0}^{\delta}(\varepsilon)$ is as in (5.1) and
$|\Lambda_{10}\cap\delta G|\leq C_{\mu}100/\delta^{2}$ (i.e., (Vol) is
satisfied). Then with probability at least $1-\varepsilon^{\prime}$

  1. (i)

The random walks emanating from all branches in $\mathcal{Q}_{j}$ for $j\geq
j_{0}$ stay in the square $\Lambda_{2r}(z)$.

  2. (ii)

All the branches sampled from vertices in $\mathcal{Q}_{j}$ for $j>j_{0}$
until they hit $\mathcal{T}_{j_{0}}\cup\partial D^{\delta}$ have Euclidean
diameter at most $\varepsilon^{\prime}r$.

###### Proof.

The proof follows an argument similar to [4, Lemma 4.18], so we provide a
sketch. Fix $j_{0}=j_{0}(\varepsilon^{\prime})$ which will be fine tuned
later. Let

$j_{\max}=\log_{6}\left(4r/R_{0}^{\delta}\right).$

where $R_{0}^{\delta}$ is as in (5.1). First, notice that the distance between
a vertex in $\mathcal{Q}_{j-1}$ and another in $\mathcal{Q}_{j}$ is at most
$4\cdot 6^{-j}r$. For small $j<j_{\max}$, notice that $4\cdot 6^{-j}r\geq
R_{0}^{\delta}$. Thus using the Beurling type estimate of Lemma 5.6, the
probability that the random walk started from a vertex in $\mathcal{Q}_{j}$
reaches distance $C_{0}6^{-j}r$ without hitting a sampled branch is at most
$1/2$ for a large enough choice of $C_{0}$. Applying this bound $j^{2}$ times,
and using Markovian property of the walk, the probability that the walker
reaches distance $j^{2}6^{-j}r$ from a point $w\in\mathcal{Q}_{j}$ without
hitting any sampled branch is at most $(1/2)^{j^{2}/C_{0}}$. Let
$\mathcal{D}(w,j)$ be the event described above. Applying this bound over all
branches for $j_{0}\leq j\leq j_{\max}$, we see that

$\mathbb{P}(\cup_{w\in\mathcal{Q}_{j}}\cup_{j_{0}\leq j\leq
j_{\max}}\mathcal{D}(w,j))\leq\sum_{j\geq
j_{0}}6^{2j}(1/2)^{j^{2}}\leq\varepsilon^{\prime}/2,$ (5.2)

for a large enough choice of $r$.

On the other hand, for $j\geq j_{\max}$, the Beurling bound kicks in only at
distance $4\cdot 6^{-j_{\max}}$. Thus applying this crude bound, the
probability that any $w\in\mathcal{Q}_{j}$ reaches distance larger than
$j^{2}6^{-j}r$ without hitting any branch in $\mathcal{T}_{j}$ is at most
$(1/2)^{j_{\max}^{2}/C_{0}}$. Call this event $\tilde{\mathcal{D}}(w,j)$.
Applying the crude bound that the total number of vertices in $\Lambda_{10}$
is at most $100C_{\mu}/\delta^{2}$, we see that

$\mathbb{P}(\cup_{j\geq j_{\max}}\cup_{w\in\mathcal{D}_{j}}\tilde{D}(w,j))\leq
100C_{\mu}\delta^{-2}(1/2)^{j_{\max}^{2}/C_{0}}\leq\varepsilon^{\prime}/2$
(5.3)

for a small enough choice of
$\delta=\delta(\varepsilon^{\prime},r)\wedge\varepsilon$ (this is the part
where the proof differs from that in [4]). Indeed, we can write $j_{\max}$ as

$j_{\max}=\log_{6}\left(\frac{4r}{\delta}\right)-\log_{6}\Big{(}\log^{1/\alpha}\Big{(}\frac{C}{\varepsilon\delta^{2}}\Big{)}\Big{)}\geq\log_{6}\left(\frac{4r}{\delta}\right)-\log_{6}\Big{(}\log^{1/\alpha}\Big{(}\frac{C}{\delta^{3}}\Big{)}\Big{)}.$

since $\varepsilon\geq\delta$. In the above expression, $j_{\max}$ is much
larger than $-C\log(\delta)$ for some constant $C$ and $\delta$ small enough
(depending only on $r$), and thus $(1/2)^{j_{\max}^{2}}$ is much smaller than
any polynomial in $\delta^{-1}$.

Now it is easy to see that on the complement of (5.2) and (5.3), the diameter
of the branches sampled after step $j_{0}$ is at most

$\sum_{j\geq j_{0}}j^{2}6^{-j}r.$

For the same choice of $j_{0}$, the above quantity is less than
$\varepsilon^{\prime}r$. Thus both items (i) and (ii) are satisfied on the
complement of the event, thereby completing the proof. ∎

###  5.1 The coupling.

The coupling of Theorem 5.1 is as described in Section 4.4 of [4] and proceeds
in two stages. First we couple around a single point. Then if it fails, we
iterate until we succeed. The important difference from [4] is that we have to
pick a ‘good’ sample from $\mu$ first. Fix $\varepsilon>0$ and pick a graph
$G\in\mathcal{G}$ where $\mathcal{G}$ is the collection of graphs satisfying
satisfying $R_{\max}^{\delta}\leq R_{0}$ where $R_{0}$ is as in (5.1) and
$|\Lambda_{10}\cap\delta G|\leq C_{\mu}100/\delta^{2}$. Applying Lemma 5.3 and
assumption (Vol), we obtain

$\mu(\mathcal{G})\geq
1-\varepsilon-\exp\left(-\frac{\beta}{\delta^{2}}\right)$ (5.4)

We assume thoughout that we have picked a graph $G\in\mathcal{G}$ in the rest
of the description of the coupling.

#### Base coupling.

Pick $z\in D$. We will now describe a coupling between a wired UST
$\mathcal{T}$ in $D$ and another wired UST $\tilde{\mathcal{T}}$ of
$\Lambda_{10}^{\delta}$ using the following steps, which we call the base
coupling. It will be described with respect to a scale $r$ satisfying
$\Lambda_{2r}(z)\subset D$. Given a vertex $w$, let $\gamma(w)$ (resp.
$\tilde{\gamma}(w)$) denote the wired UST branch of $\mathcal{T}$ (resp.
$\tilde{\mathcal{T}}$) sampled via Wilson’s algorithm

  * •

Take $w_{1}\in A(z,0.8r,0.9r)$ and sample $\gamma(w_{1})$ and
$\tilde{\gamma}(w_{1})$ independently until they both hit the boundary of
their respective domains. Let $E_{1}$ be the event that both $\gamma(w_{1})$
and $\tilde{\gamma}(w_{1})$ stay outside $\Lambda_{0.7r}(v)$.

  * •

Conditional on the event $E_{1}$ holding, we couple the loop-erased random
walk emanating from a vertex $w_{2}\in A(v,0.3r,0.4r)$ as follows. We sample a
loop-erased random walk until hitting either $\gamma(w_{1})\cup\partial
D^{\delta}$ or $\tilde{\gamma}(w_{1})\cup\partial\Lambda_{10}^{\delta}$.
Without loss of generality, we assume that the walk intersects
$\gamma(w_{1})\cup\partial D^{\delta}$ at time $t_{1}$. Then we continue the
random walk from that point until it intersects
$\tilde{\gamma}(w_{1})\cup\partial\Lambda_{10}^{\delta}$ at time $t_{2}$ and
its path is denoted by $\tilde{\gamma}(w_{2})$. Let $E_{2}$ be the event that
$\gamma(w_{2})$ and $\tilde{\gamma}(w_{2})$ agree in $\Lambda_{0.6r}(v)$.

  * •

Suppose that events $E_{1}$ and $E_{2}$ hold. Fix a $j_{0}=j_{0}(1/2)$ as
defined in Lemma 5.7. As the description of good algorithm above, let
$\mathcal{Q}_{j}$ be a set of vertices in
$\\{0.1r6^{-j}\mathbb{Z}^{2}\\}_{j\geq 0}\cap\Lambda_{0.1r}(v)$ which are
chosen that each one is furthest away from $v$ within the small square. Define
the event $E_{3}$ to be the branches emanating from all the vertices in
$\cup_{j\leq j_{0}}\mathcal{Q}_{j}$ of $\mathcal{T}^{\delta}$ and
$\widetilde{\mathcal{T}}^{\delta}$ agree in $\Lambda_{0.5r}(v)$.

  * •

Assume that events $E_{1}$, $E_{2}$ and $E_{3}$ hold. Let $E_{4}$ be the event
that the remaining branches starting from vertices in
$\cup_{j>j_{0}}\mathcal{Q}_{j}$ of $\mathcal{T}^{\delta}$ and
$\widetilde{\mathcal{T}}^{\delta}$ agree in $\Lambda_{0.1r}(v)$.

We will show below that the base coupling succeeds with a uniformly positive
probability.

#### Iteration of the base coupling.

We now want to iterate the above base coupling, decreasing the scale at every
step and in the end want to conclude that the coupling succeeds after
geometric many tries. Also, we want to conclude that after geometric many
tries, there is enough space around $z$ on which the spanning trees are
coupled.

We say a $z$ has _isolation radius_ $6^{-k}$ at scale $r$ at any step in the
above base coupling if $\Lambda_{6^{-k}r}(z)$ does not intersect any sampled
branches and $k$ is the minimal such integer. Fix a large constant $C_{0}$. We
start the iteration with an attempt at the base coupling with scale $r$. If it
is successful, we say the iteration is complete and the coupling is
successful. If not, let $I_{1}$ be the isolation radius at scale $r$. If
$6^{-I_{1}}r<C_{0}R_{0}^{\delta}$, we abort the coupling and say that the
coupling failed. Otherwise, if the base coupling was not successful and
$6^{-I_{1}}r\geq C_{0}R_{0}^{\delta}$ we attempt another base coupling at
scale $6^{-I_{1}}r/2$ in the domain
$\mathcal{T}\setminus\mathcal{T}_{0}^{\\#\delta}$ where
$\mathcal{T}_{0}^{\\#\delta}$ is the tree sampled in $D^{\delta}$ in the first
step (and ignore the tree sampled for $\Lambda_{10}^{\delta}$). Iterating this
process, we obtain the isolation radii at any step $j$ (if we have not
aborted) is $\sum_{1\leq k\leq j}I_{k}$ at scale $r$.

Let $N$ be the smallest $j$ such that we either abort the coupling or the
coupling succeeds. Let $I_{z}=I_{1}+\ldots+I_{N}$.

#### Full coupling.

Pick distinct points $z_{1},\ldots,z_{k}$ in $D$. Let $r>0$ be such that
$\Lambda_{2r}(z_{i})\subset D$ for all $i$ and $|z_{i}-z_{j}|>2r$ for all
$i\neq j$. Assume that $\delta$ is small enough so that $0.01r>R_{0}$ where
$R_{0}$ is as in $\eqref{eq:R0}$. Since we picked a $G$ with $R_{\max}\leq
R_{0}$, uniform crossing is possible in $A(z_{i},r,1.1r)$ for all $1\leq i\leq
k$. Consequently, there must exist a circuit lying completely in
$A(z_{i},r,1.1r)$. We first perform Wilson’s algorithm from all the vertices
from these circuits in $A(z_{i},r,1.1r)$. Let $J_{z_{i}}$ be the isolation
radius at scale $r$ seen from $z_{i}$ for each $1\leq i\leq k$. Now perform
iteration of base coupling around each vertex independently, starting from
scale $6^{-J_{z_{i}}}r/2$. Let $I_{z_{i}}$ be the isolation radius as defined
in the iteration of the base coupling part of the description. Let

$I=\max\\{J_{z_{i}}+I_{z_{i}}:1\leq i\leq k\\}.$

Let $\mathbf{P}^{G}$ be this coupling, and this will be the coupling used to
prove Theorem 5.1.

######  Proposition 5.8.

Let $G\in\mathcal{G}$ as in (5.4), and let $I,\mathbf{P}^{G}$ be as above.
Then there exist constants $c,c^{\prime}>0$ such that for all $i>0$, and
$\delta$ small enough,

$\mathbf{P}^{G}(I>i)\leq ce^{-c^{\prime}i}+\delta^{c^{\prime}}.$

###### Proof.

The proof of this statement follows the exact same lines as [4, Lemmas 4.19,
4.20 and Theorem 4.21], replacing the scale $\delta_{0}$ which was order $1$
there by $R_{0}/\delta$ which is of order $\log(\delta^{-1})$. This allows us
to upper bound $\mathbf{P}^{G}(I>i)$ by
$ce^{-c^{\prime}i}+(\delta\log(\delta^{-1}))^{c^{\prime\prime}}$ which can be
easily bounded by $ce^{-c^{\prime}i}+\delta^{c^{\prime}}$ for a smaller choice
of $c^{\prime}$. ∎

###### Proof of Theorem 5.1.

Choose $\delta_{0}(\varepsilon^{\prime})$ small enough so that for all
$\delta<\delta_{0}$,
$(\delta\log(\delta^{-1}))^{c^{\prime\prime}}\leq\varepsilon^{\prime}$ where
the expression is as in Proposition 5.8. Pick an even smaller
$\delta\leq\varepsilon$ if needed. Thus by (5.4), we can pick a $\mathcal{G}$
with $\mu(\mathcal{G})\geq 1-\varepsilon-\exp(-\beta/\varepsilon^{2})\geq
1-2\varepsilon$. For such a $G\in\mathcal{G}$, the choice of $\delta$, we
perform the full coupling described above. By Proposition 5.8, if we rename
$R=6^{-I}r$, then

$\mathbf{P}^{G}(R\leq\varepsilon^{\prime}r)\leq\varepsilon^{\prime}+(\varepsilon^{\prime})^{c}\leq(\varepsilon^{\prime})^{c^{\prime\prime}}.$

for some small enough $c^{\prime\prime}$. This completes the proof. ∎

##  6 Dimer model in random graph

In this section we outline a scaling limit result for the height function of
the dimer model on a class of random graphs with law $\mu$. Apart from the
three properties outlined in Section 5, we add the additional fourth
assumption of quenched Invariance principle:

  1. (iv)

For $\mu$-almost sure $\Gamma$, the following holds. As $\delta\to 0$, the
continuous time random walk $\\{X_{t}\\}_{t\geq 0}$ on $G$ started from a
nearest vertex to $0$ converges to Brownian motion in the following sense:

${\delta(\tilde{X}_{t/\delta^{2}})_{t\geq 0}}\xrightarrow[\delta\to
0]{(d)}(B_{\phi(t)})_{0\leq t}$

where $(B_{t},t\geq 0)$ is a two dimensional standard Brownian motion started
from $0$. The convergence above is in law and using the uniform topology on
curves up to parametrisation.

######  Remark 6.1.

By [6, Theorem 1.1] and by [14, Theorem 1.1], Quenched invariance principle
holds for random walk on the infinite cluster for supercritical percolation on
$\mathbb{Z}^{2}$ and for Poisson Voronoi triangulation in $\mathbb{R}^{2}$.

Recall that in a bipartite graph, a _dimer configuration_ is perfect matching
of the black and the white vertices (every black vertex is matched to exactly
one white vertex). The dimer model is a uniform probability measure on all
possible perfect matchings on it. Take $D\subset\mathbb{C}$ be a simply
connected domain with a smooth boundary $\partial D$. Let
$\Gamma^{\delta}=\delta G\cap D$ and assume that the boundary vertices form a
simple cycle which converges in the Hausdorff sense to $\partial D$ almost
surely (crossing estimate ensures that such a cycle exists a.s. at least for
all small enough $\delta$ along a subsequence which is at a Hausdorff distance
$O(\delta^{1/2})$ from $\partial D$). Take $(\Gamma^{\dagger})^{\delta}$ to be
the dual graph. Now introduce white vertices at the points where the primal
and the dual edges cross, and let $H^{\delta}$ be the final graph obtained.
Let $\mu_{\dim}$ denote the uniform probabilty measure on $H^{\delta}$. We
refer to [11] or [5] for more details of this construction.

It is well-known that a dimer configuration is uniquely associated to a height
function $h^{\delta}:F(H^{\delta})\to\mathbb{R}$ where $F(H^{\delta})$ is the
collection of faces of $H^{\delta}$. Furthermore, the height function can be
associated to the winding of the wired Uniform spanning tree on $G^{\delta}$
as follows (here the boundary cycle is wired). Fix a point $x$ on $D$ and let
$x^{\delta}$ be the point closest to it. Take $z\in D$ and a point
$z^{\delta}$ closest to $z$ in $D$. Let $\gamma^{\delta}(z)$ denote the path
formed by UST branch started from $x$, hitting the boundary cycle and then
moving along the boundary cycle to $x^{\delta}$. Then it is known (see [11,
Section 5] or [3] for a more detailed treatment) that one can set things up so
that the height function $h^{\delta}(z)$ is the amount of winding done by
$\gamma^{\delta}(z)$. We refer to [4, Section 2] for a precise definition of
this winding (called ‘intrinsic winding’ there). We now extend $h^{\delta}(z)$
in a natural way to all of $D$ (e.g. by considering Voronoi cells around the
center of the faces of $H^{\delta}$), so that we can integrate $h^{\delta}$
with a smooth compactly supported test function in $D$.

With this setup, the arguments in [4, Section 5] can be readily applied in a
quenched sense. Indeed by Remarks 5.2 and 5.4, if we choose
$\varepsilon=\delta_{k}=2^{-k}$ then $\mu$-a.s. $R_{\max}^{\delta_{k}}\leq
R_{0}^{\delta_{k}}$ and Theorem 5.1 holds for any $\varepsilon^{\prime}$ if we
choose $k$ large enough. Thus we can use the Invariance principle and the
convergence of loop erased random walk to SLE2 to control the macroscopic part
of the winding ([16]) and Theorem 5.1 to control the microscopic part
(basically the independence cancels out the cross terms in a joint moment
calculation). We obtain the following theorem whose proof we omit in order to
keep the exposition succinct and to avoid repitition.

######  Theorem 6.2.

Suppose $\mu$ satisfies the conditions of Section 5 and the Quenched
invariance principle (item (iv)) as above. Then there exists a collection
$\mathcal{G}_{0}$ with $\mu(\mathcal{G}_{0})=1$ such that for any
$G\in\mathcal{G}_{0}$ the following holds. For any compactly supported test
function $\varphi$ in $D$,

$\int_{D}\bar{h}^{{\\#\delta}_{k}}(z)\varphi(z)dz\xrightarrow[]{k\to\infty}\int_{D}\sqrt{2}h_{D}^{\mathsf{GFF}}(z)\varphi(z)dz.$

along the subsequence $\delta_{k}=2^{-k}$ in law, where
$\bar{h}^{{\\#\delta}}=h^{{\\#\delta}}-\mathbf{E}^{G}(h^{{\\#\delta}})$ and
$h_{D}^{\mathsf{GFF}}$ is a Gaussian free field with Dirichlet boundary
condition in $D$.

The above result can also be refined in various directions, we refer to [4]
for more details.

We finish the article by stating a corollary of Theorem 6.2 for the special
cases of random graphs we focussed on in this article, namely: Poisson Voronoi
triangulation $\mathbb{T}$ in $\mathbb{R}^{2}$ and the infinite supercritical
percolation cluster $\mathcal{C}_{\infty}$ in $\mathbb{Z}^{2}$. We proved in
this article that both $\mathbb{T},\mathcal{C}_{\infty}$ satisfies items $(i)$
and $(iii)$ from Section 5 and we proved $(ii)$ in Theorems 3.1 and 4.1.
Finally, Quenched invariance principle is also known for both these cases, see
Remark 6.1. Thus we obtain

######  Corollary 6.3.

The conclusions of Theorem 6.2 hold if $\mu$ is either the unique infinite
cluster of supercritical percolation, or the Poisson Voronoi triangulation.

## References

  * [1] P. Antal and A. Pisztora.  On the chemical distance for supercritical Bernoulli percolation.  The Annals of Probability, 24(2):1036 – 1048, 1996.
  * [2] M. T. Barlow.  Random walks on supercritical percolation clusters.  The Annals of Probability, 32(4):3024 – 3084, 2004.
  * [3] N. Berestycki, B. Laslier, and G. Ray.  The dimer model on Riemann surfaces II: convergence of height function.  2019\.  Preprint.
  * [4] N. Berestycki, B. Laslier, and G. Ray.  Dimers and imaginary geometry.  The Annals of Probability, 48(1):1 – 52, 2020.
  * [5] N. Berestycki, B. Laslier, and G. Ray.  The dimer model on Riemann surfaces, I: convergence of Temperleyan forests.  Preprint, 2021.
  * [6] N. Berger and M. Biskup.  Quenched invariance principle for simple random walk on percolation clusters.  Probability theory and related fields, 137(1-2):83–120, 2007.
  * [7] H. Duminil-Copin.  Lectures on the ising and potts models on the hypercubic lattice.  In PIMS-CRM Summer School in Probability, pages 35–161. Springer, 2017.
  * [8] H. Duminil-Copin.  Sixty years of percolation.  In Proceeding of the International Congress. World Scientific, 2018\.
  * [9] O. Garet and R. Marchand.  Large deviations for the chemical distance in supercritical Bernoulli percolation.  The Annals of Probability, 35(3):833 – 866, 2007.
  * [10] G. Grimmett.  What is percolation?  In Percolation, pages 1–31. Springer, 1999.
  * [11] R. W. Kenyon, J. G. Propp, and D. B. Wilson.  Trees and matchings.  Electron. J. Combin., 7, 2000.
  * [12] T. M. Liggett, R. H. Schonmann, and A. M. Stacey.  Domination by product measures.  The Annals of Probability, 25(1):71–95, 1997.
  * [13] R. Lyons and Y. Peres.  Probability on trees and networks, volume 42.  Cambridge University Press, 2017.
  * [14] A. Rousselle.  Quenched invariance principle for random walks on Delaunay triangulations.  Electronic Journal of Probability, 20(none):1 – 32, 2015.
  * [15] D. B. Wilson.  Generating random spanning trees more quickly than the cover time.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296–303, 1996.
  * [16] A. Yadin and A. Yehudayoff.  Loop-erased random walk and Poisson kernel on planar graphs.  Ann. Probab., 39(4):1243–1285, 2011.