arXiv:1803.09686v1 [math.PR] 26 Mar 2018

Strict monotonicity of pc under covering maps
Sébastien Martineau∗ and Franco Severo†
March 28, 2018

Abstract
We answer a question of Benjamini and Schramm by proving that under
reasonable conditions, quotienting a graph with pc < 1 strictly increases the
value of pc . More precisely, let G = (V, E) be a quasi-transitive graph with
pc (G) < 1, and let G be a nontrivial group that acts freely on V by graph
automorphisms. Assume that H := G/G is quasi-transitive. Then, one has
pc (G) < pc (H).
We also investigate the same question beyond this setting: we explain why
no condition in the above result can be removed, which more general result
can though be obtained, and ask a question on quotients by non-free group
actions. The proof makes use of a coupling built by lifting the exploration of
the cluster, and an essential (exploratory) enhancement.

1

Introduction

Bernoulli percolation is a simple model for problems of propagation in random
media that was introduced in 1957 by Broadbent and Hammersely [HB57]: take
a graph G, a parameter p ∈ [0, 1], and erase every edge independently with probability 1 − p. Studying the connected components of this graph (which are referred to as clusters) has been since then an active field of research: see the
books [Gri99, LP16]. A prominent quantity in this theory is the so-called critical
parameter pc (G), which is characterised by the following dichotomy: for every
p < pc (G), there is almost surely no infinite cluster, while for every p > pc (G),
there is almost surely at least one infinite cluster.
Initially, the main focus was on the Euclidean lattice Zd . In 1996, Benjamini
and Schramm initiated the systematic study of Bernoulli percolation on more general graphs, namely quasi-transitive graphs [BS96]. A graph is quasi-transitive
(resp. transitive) if the action of its automorphism group on its vertices yields
finitely many orbits (resp. a single orbit). Intuitively, a graph is quasi-transitive
∗
†

Université Paris-Sud, sebastien.martineau@u-psud.fr
Institut des Hautes Études Scientifiques, severo@ihes.fr

1

if it has finitely many types of vertices, and transitive if all the vertices look the
same. The paper [BS96] contains, as its title suggests, many questions and a few
answers: in their Theorem 1 and Question 1, they investigate the monotonicity of
pc under quotients. Their Question 1 is precisely the topic of the present paper. It
goes as follows.
Setting of [BS96] Let G = (V, E) be a locally finite connected graph. Let G be
a group acting on V by graph automorphisms. A vertex of the quotient graph
G/G is an orbit of G y V , and two distinct orbits are connected by an edge if and
only if there is an edge of G intersecting both orbits.
Theorem 1 of [BS96] asserts that pc (G) ≤ pc (G/G). It is proved by lifting the
exploration of a spanning tree of the cluster of the origin from G/G to G. They
then ask the following natural question. Recall that a group action G y X is free
if the only element of G that has a fixed point is the identity element:
∀g ∈ G\{1}, ∀x ∈ X, gx 6= x.
Question 1.1 (Benjamini-Schramm). Consider the quotient graph H := G/G.
Assume that pc (G) < 1, G 6= {1} acts freely on V (G), and both G and H are
quasi-transitive. Is it necessarily the case that pc (G) < pc (H)?
The main result of the present paper is a positive answer to this question: see
Corollary 2.2. We use an exploratory version of Aizenman-Grimmett’s essential
enhancements [AG91], and build a coupling between p-percolation on G and enhanced percolation on H by lifting the exploration of the cluster of the origin.
The part of our work devoted to essential enhancements (Section 6) follows the
Aizenman-Grimmett strategy, thus making crucial use of differential inequalities
[Men87]. Our coupling (Section 5) improves on that used in [BS96].

2

Definitions and results

To avoid any ambiguity, let us review the relevant vocabulary.
Convention Graphs are taken to be non-empty, locally finite (every vertex has
finitely many neighbours) and connected. Subgraphs (e.g. percolation configurations) may not be connected. Our graphs are also taken to be simple (no multiple
edges, no self-loops, edges are unoriented), though we will also use multigraphs
in some proofs: hence, both graphs and multigraphs appear in this paper. A
graph may be written in the form (V, E), where V = V (G) denotes its set of vertices and E = E(G) its set of edges. An edge is a subset of V with precisely
two elements. Graphs are endowed with their respective graph distance, denoted
by d. The ball of centre x and radius r is Br (x) := {y ∈ V : d(x, y) ≤ r}.
It is considered as a set of vertices, but it may also be considered as a graph
2

— with the structure the ambient graph induces on it. For r ∈ N, the sphere
of centre x and radius r is Sr (x) := {y ∈ V : d(x, y) = r}. We also set
Sr+ 1 (x) := {e ∈ E : e ∩ Sr (x) 6= ∅ and e ∩ Sr+1 (x) 6= ∅}. Finally, percola2
tion is taken to mean Bernoulli bond percolation, but our proofs can be adapted
to Bernoulli site percolation.
In Question 1.1, the graphs G and H are related via the quotient map π : x 7→
Gx. This map is a weak covering map, meaning that it is 1-Lipschitz for the
graph distance and that it has the weak lifting property: for every x ∈ V (G)
and every neighbour u of π(x), there is a neighbour of x that maps to u. This fact
does not use the freeness of the action of G or quasi-transitivity. Weak covering
maps are by definition able to lift edges, but it turns out they can also lift trees,
meaning that for every subtree of the target space and every vertex in the preimage
of the tree, there is a lift of the tree that contains this vertex. Recall that given
a subtree1 T of H, a lift of T is a subtree T ′ of G such that π induces a graph
isomorphism from T ′ to T , i.e. it induces well-defined bijections from V (T ′ ) to
V (T ) and from E(T ′ ) to E(T ).
The map π satisfies a second property, namely disjoint tree-lifting: if T is a
subtree of H and if x and y are distinct vertices of G such that π(x) = π(y) belongs
to the tree, then one can find two vertex-disjoint lifts of T such that one of them
contains x and the other y. This fact uses the freeness of G, and is established in
Lemma 7.1.
Finally, the map π has tame fibres: there is some R such that for every
x ∈ V (G), there is some y ∈ π −1 ({x}) satisfying 0 < d(x, y) ≤ R. See Lemma 7.2.
It turns out that these three properties of π suffice to prove strict inequality,
so that there is no need in general for group actions and quasi-transitivity.
Theorem 2.1. Let G and H be graphs of bounded degree. Assume that there is a
weak covering map π : V (G) → V (H) with tame fibres and the disjoint-tree lifting
property. If pc (G) < 1, then one has pc (G) < pc (H).
Corollary 2.2. Let G be a graph. Let G 6= {1} be a group acting on V (G) by
graph automorphisms, and let H denote the quotient graph G/G. Assume that the
following conditions hold:
1. the action G y V (G) is free,
2. G is quasi-transitive,
3. H is quasi-transitive,
4. pc (G) < 1.
Then, one has pc (G) < pc (H).
Theorem 2.1 yields a second corollary. Say that a map π : V (G) → V (H) is
a strong covering map if it is 1-Lipschitz for the graph distance and has the
1

i.e. a tree with V (T ) ⊂ V (H) and E(T ) ⊂ E(H).

3

strong lifting property: for every x ∈ V (G), for every neighbour u of π(x),
there is a unique neighbour of x that maps to u. Recall that for many authors, the
definition of a “covering map” is taken to be even stricter: a classical covering
map is a graph homomorphism with the strong lifting property.
By Theorem 2.1 and Lemma 7.3, the following result holds.
Corollary 2.3. Let G and H be graphs of bounded degree. Assume that there is a
strong covering map π : V (G) → V (H) with tame fibres.
If pc (G) < 1, then one has pc (G) < pc (H).
Our proofs are explicit in that they actually yield explicit (poor) lower bounds
on pc (H) − pc (G).
Structure of the paper The remaining of the paper is organised as follows.
Section 3 discusses the hypotheses of Corollaries 2.2 and 2.3. Section 4 exposes the
strategy of proof of Theorem 2.1, reducing it to the proof of Propositions 4.1 and
4.2. They are respectively established in Sections 5 and 6. Section 7 explains why
Corollaries 2.2 and 2.3 follow from Theorem 2.1. All these sections can be read in
any order, except that Sections 5 and 6 should be read after Section 4.

3

On the hypotheses of our results

None of the four assumptions of Corollary 2.2 can be removed. This is clear for
Hypothesis 4. For Hypothesis 1, take G0 to be a quasi-transitive graph with pc < 1
— e.g. the square lattice or the 3-regular tree — and define G by setting:
V (G) := V (G0 ) × {0, 1, 2}, E(G) := (E(G0 ) × {0}) ∪ (V (G) × {{0, 1}, {0, 2}}) ,
where one identifies E(G0 )× {0} with {{(x, 0), (y, 0)} : {x, y} ∈ E(G0 )} and V (G)×
{{0, 1}, {0, 2}} with {{(x, 0), (x, i)}} : x ∈ V (G0 ), i ∈ {1, 2}}. It suffices then to
take G := Z/2Z with the non-trivial element acting via (x, i) 7→ (x, σ(i)), where σ
is the (12)-transposition.
For Hypothesis 2, take once again G0 to be a quasi-transitive graph with pc < 1,
and pick some vertex o in G0 . The graph G is defined by taking two disjoint copies
of G0 and putting an additional edge between the two copies of o. The group
G := Z/2Z acts by swapping copies.
As for Hypothesis 3, take G to be the square lattice Z2 , and G to be Z/2Z
acting via the reflection (x, y) 7→ (x, 1 − y).
Still, we do not know what happens if freeness is relaxed to the absence of
trivial G-orbit.
Question 3.1. Let G be a graph. Let G be a group acting on V (G), and let H
denote the quotient graph G/G. Assume that the following conditions hold:
4

– ∀x ∈ V (G), ∃g ∈ G, gx 6= x,
– G is quasi-transitive,
– H is quasi-transitive,
– pc (G) < 1.
Is it necessarily the case that pc (G) < pc (H)?
Remark. An interesting particular case (which we also do not know how to solve)
is when G is normal in a quasi-transitive subgroup of Aut(G). In that setting, H
is automatically quasi-transitive, and the map π always has tame fibres.
As for Theorem 2.1 and Corollary 2.3, notice that the assumption that fibres are tame cannot be replaced by non-triviality of the fibres (namely ∀u ∈
V (H), |π −1 ({u})| =
6 1), even if π is taken to be a classical covering map. Indeed,
one can take H to be a graph with bounded degree and pc < 1, and pick some edge
e in H. To define G, start with two copies of H, and denote by {x, y} and {x′ , y ′ }
the two copies of e. Then, replace these edges by {x′ , y} and {x, y ′ }, thus yielding
a connected graph. Take π to be the natural projection from G to H.
We do not know how to answer the following question, which investigates a
generalisation of Theorem 2.1/Corollary 2.3.
Question 3.2. Let G and H be graphs of bounded degree. Assume that there is a
weak covering map π : V (G) → V (H) with tame fibres and that pc (G) < 1.
Is it necessarily the case that pc (G) < pc (H)?

4

Proof of Theorem 2.1

Let G, H and π be as in Theorem 2.1. Let r be a positive integer. Pick a root o in
H, and some o′ ∈ π −1 ({o}).
For p, s ∈ [0, 1], define the following random process on H. Independently,
each edge is open with probability p and each vertex is activated with probability
s. To insist on the difference between these two states, we will often speak of
p-open edges and s-activated vertices. Formally, take (ω, α) a random variable
of distribution Pp,s := Ber(p)⊗E(H) ⊗ Ber(s)⊗V (H) . Set C0 := {o}. We define
inductively a sequence (Cn )n≥0 as follows. For n ≥ 0, let C2n+1 be the union of
the p-clusters of the vertices of C2n (let us call it the p-closure of C2n ). Then, let
C2n+2 be the union of C2n+1 and the vertices v such that there is some u ∈ C2n+1
satisfying the following conditions:
1. d(u, v) = r + 1,
2. all the edges in Br (u) are p-open,
3. u is s-activated.

5

The random sequence of sets (Cn ) is non-decreasing, and we define Co :=
S
p,s
(o) := n Cn to be the cluster of the origin in the (p, s)Co (ω, α) := CH
model. In a similar way, one could define Cu (ω, α) by the same procedure but
starting the process at the vertex u.
Say that an edge e is s-open if there is some u ∈ Co (ω, α) satisfying the
following conditions:
1. e ∈ Sr+ 1 (u),
2
2. all the edges in Br (u) are p-open,
3. u is s-activated.
Remark. Note that Co (ω, α) does not coincide with the cluster of o for the following
model: declare an edge to be open if “it is p-open or there is some s-activated vertex
u such that the edge belongs to Sr+ 1 (u) and all the edges in Br (u) are p-open”.
2
This would be an instance of the classical essential enhancement introduced by
Aizenman and Grimmett — see [AG91]. Indeed, the model we consider here is
an exploratory version of their model (in particular, the former is stochastically
dominated by the latter). For example, in our model the assertion v ∈ Cu (ω, α)
does not necessarily imply u ∈ Cv (ω, α).
We can also set CGp (o′ ) to be the cluster of o′ in bond percolation of parameter
p on G. We will prove the following two propositions. The proof of Proposition 4.1
proceeds by lifting some exploration process from H to G: in that, it is similar to
the proof of Theorem 1 of [BS96]. The proof of Proposition 4.2 uses an exploratory
variation of the techniques of Aizenman and Grimmett [AG91]. Even though essential enhancements are delicate in general [BBR], it turns out that our particular
enhancement can be handled for general graphs, even for site percolation.
Proposition 4.1. There is some choice of r ≥ 1 such that the following holds:
p,s
(o) is
for every ε > 0, there is somes ∈ (0,1) such that for every p ∈ [ε, 1], CH
p ′
2
stochastically dominated by π CG (o ) .
Proposition 4.2. Assume further that pc (H) < 1. Then, for any choice of r ≥ 1,
the following holds: for every s ∈ (0, 1], there exists ps < pc (H) such that for every
p,s
(o) is infinite with positive probability.
p ∈ [ps , 1], the cluster CH
Assuming these propositions, let us establish Theorem 2.1.
First, notice that if pc (H) = 1, then the conclusion holds trivially. We thus
assume that pc (H) < 1, so that we can use both propositions. We pick r so that
the conclusion of Proposition 4.1 holds. Since boundedness of the degree of H
implies that pc (H) > 0, we can pick some ε in (0, pc (H)). By Proposition 4.1, we
There is a coupling such that the (H, p, s)-cluster is a subset of the π-image of the (G, p)cluster.
2

6

p,s
can pick
 s ∈ (0, 1) such that for every p ∈ [ε, 1], CH (o) is stochastically dominated
by π CGp (o′ ) . By Proposition 4.2, there is some ps < pc (H) such that for every
p,s
p ∈ [ps , 1], the cluster CH
(o) is infinite with positive probability. Fix such a ps ,
p,s
(o) is infinite
and set p := max(ps , ε) < pc (H). By definition of ps , the cluster CH
p,s
with positive probability. As 
p ≥ ε, the definition of s implies
 that CH (o) is
stochastically dominated by π CGp (o′ ) . As a result, π CGp (o′ ) is infinite with
positive probability. In particular, CGp (o′ ) is infinite with positive probability, so
that pc (G) ≤ p < pc (H).

5

Proof of Proposition 4.1

The choice of a suitable value of r is given by the following lemma.
Lemma 5.1. There are some finite r ≥ 1 and d ≥ 1 such that for every x ∈ V (G),
the set Z = Z(x, r, d) defined as the connected component3 of x in π −1 (Br (π(x))) ∩
Bd (x) satisfies that for any u ∈ Sr+1 (π(x)), the fibre π −1 ({u}) contains at least
two vertices adjacent to Z.
Proof. Let R be given by the fact that π has tame fibres. Set r := ⌈ R2 ⌉ and
d := R + r. Let x be any vertex of G. Take some y ∈ V (G) such that π(x) = π(y)
and 0 < d(x, y) ≤ R. Let T be a spanning tree of Br+1 (π(x)) obtained by adding
first the vertices at distance 1, then at distance 2, etc. As π has the disjoint treelifting property, one can pick two vertex-disjoint lifts Tx and Ty of T such that
x ∈ V (Tx ) and y ∈ V (Ty ).
Let γ be a geodesic path from x to y, thus staying inside π −1 (Br (π(x))). The
set Z ′ consisting in the union of the span of γ and (V (Tx ) ∪ V (Ty )) ∩ π −1 (Br (π(x)))
is a connected subset of Z(x, r, d): its connectedness results from the choice of the
spanning tree T . It thus suffices to prove that for any u ∈ Sr+1 (π(x)), the fibre
π −1 ({u}) contains at least two vertices adjacent to Z ′ . But this is the case as every
⊓
such u admits a lift in Tx and another one in Ty .
⊔
Take (r, d) to satisfy the conclusion of Lemma 5.1. Let ε > 0. Set M and s to
be so that the following two conditions hold:
∀e = {x, y} ∈ E(H), M ≥ |Br (x) ∪ Br (y)|,


∀x ∈ V (G), s ≤ 1 − (1 − ε)1/M

|E(Bd+1 (x))|

.

For instance, one may take M := Dr+2 and s := (1 − (1 − ε)1/M )D
the maximal degree of a vertex of G. Let p ∈ [ε, 1].
3

d+2

, where D be

Here π −1 (Br (π(x))) ∩ Bd (x) is seen as endowed with the graph structure induced by G.

7

We define the multigraph Ĝ as follows: the vertex-set is V (G), the edge-set is
E(G) × {1, . . . , M }, and ({x, y}, k) is interpreted as an edge connecting x and y.
The multigraph Ĥ is defined in the same way, with H instead of G. The purpose of
this multigraph is to allow multiple use of each edge for a bounded number of “sbonus”. They will play no role as far as p-exploration is concerned: concretely, for
“p-exploration”, each edge will be considered together with all its parallel copies.
Let ω be a Bernoulli percolation of parameter p̂ := 1 − (1 − p)1/M on Ĥ, so
that p̂-percolation on Ĥ corresponds to p-percolation on H. Let ω ′ be a Bernoulli
percolation of parameter p̂ on Ĝ that is independent of ω. Choose an injection
from E(H) to N, so that E(H) is now endowed with a well-ordering. Do the same
with E(G), V (G) and V (H).
We now define algorithmically an exploration process. This dynamical process
will construct edge after edge a Bernoulli percolation η of parameter p̂ on Ĝ and an
α with distribution Ber(s)⊗V (H) . The random variables η, α, and ω will be coupled
in a suitable way and η will be independent of α.
Structure of the process In the exploration, edges in Ĝ may get explored in two
different ways, called p-explored and s-explored. Edges in H may get p-explored,
and vertices in H may get s-explored. No vertex or edge will get explored more
than once; in particular, no edge of Ĝ will get p- and s-explored.
For every ℓ > 0, during Step ℓ, we will define inductively a sequence (Cℓ,n )n
′ ) of subsets of V (G). At the end of each
of subsets of V (H) and a sequence (Cℓ,n
n
iteration of the process, it will be the case that the following conditions hold:
(A) if an edge e in H is unexplored, then none of its lifts in Ĝ is p-explored,
otherwise there is a lift e′ of e in G such that the set of the p-explored lifts
of e is precisely {e′ } × {1, . . . , M }.
(B) if an unexplored edge e ∈ E(H) has at most one endpoint in the current Cℓ,n ,
then none of its lifts is s-explored.
′ is connected to o′ by an η-open path.
(C) every element of Cℓ,n
(D) for every edge e in H and each lift e′ of e in G, the number of s-explored
edges of the form (e′ , k) is at most the number of s-explored vertices u in H
at distance at most r from some endpoint of e.
′ to C .
(E) the map π induces a well-defined surjection from Cℓ,n
ℓ,n
Step 0 Set C0 = o and C0′ = o′ . Initially, nothing is considered to be p- or
s-explored.
′
′ .
Step 2K + 1 Set C2K+1,0 := C2K and C2K+1,0
:= C2K
While there is an unexplored edge in the edge-boundary of C2K+1,n in H, do
the following (otherwise finish this step):

8

1.
2.
3.
4.

take e to be the smallest such edge,
call u its unique endpoint in C2K+1,n and v its other endpoint,
pick e′ some lift of e intersecting πn−1 ({u}) 6= ∅,
declare e and all (e′ , k)’s to be p-explored (they were unexplored before because of Conditions (A) and (B)),
5. for every k ≤ M , define η(e′ ,k) := ω(e,k) ,
′
′
6. set (C2K+1,n+1 , C2K+1,n+1
) to be (C2K+1,n , C2K+1,n
) if all the (e, k)’s are ω′
′
closed; otherwise, set (C2K+1,n+1 , C2K+1,n+1 ) to be (C2K+1,n ∪{v}, C2K+1,n
∪
′
e ) — note that (E) continues to hold.
When this step is finished, which occurs after finitely or countably many iterS
S ′
′
ations, set C2K+1 := C2K+1,n and C2K+1
:= C2K+1,n
.
′
′
Step 2K + 2 Set C2K+2,0 := C2K+1 and C2K+2,0
:= C2K+1
.
While there is at least one s-unexplored vertex in C2K+1 whose r-ball is “fully
open”4 in ω, do the following (otherwise finish this step):

1. take u to be the smallest such vertex,
′
2. pick some x ∈ C2K+1
∩ π −1 ({u}) 6= ∅,
3. This is paragraph is not an algorithmic substep, but gathers a few relevant
observations. Call an edge in G p-explored if one (hence every by (A)) of its
copies in Ĝ is p-explored; call a p-explored edge of G open if at least one of its
copies is η-open. Notice that by construction and as the r-ball of u is “fully
open” in ω, all p-explored edges in π −1 (Br (u)) are open. Also note that for
each edge lying in Z(x, r, d), Condition (D) and the value of M guarantee that
at least one of its copies in Ĝ has not been s-explored. As a result, for every
edge in Z(x, r, d), either all its copies have a well-defined η-status and one
of them is open, or at least one of these copies has a still-undefined η-status.
This is what makes Substep 4 possible.
4. For each p-unexplored edge e′ in Z(x, r, d), take its s-unexplored copy (e′ , k) in
′
Ĝ of smallest label k, set η(e′ ,k) := ω(e
′ ,k) , and switch its status to s-explored.
5. If all these newly s-explored edges are open (so that Z is “fully η-open”), then
perform this substep. By (A) and Lemma 5.1, for every H-edge e ∈ Sr+ 1 (u),
2
there is at least one lift e′ of e that is adjacent to Z(x, r, d) and p-unexplored:
pick the smallest one. By (D) and the value of M , one of its copies (e′ , k) is
s-unexplored: pick that with minimal k =: ke . Declare all these edges to be
′
′
′
s-explored and set η(e′ ,ke ) := ω(e
′ ,k ) . If all these (e , ke )’s are ω -open, then
e
say that this substep is successful.
6. Notice that conditionally on everything that happened strictly before the
current Substep 4, the event “Substep 5 is performed and successful” has some
(random) probability q ≥ p̂|E(Z(x,r,d))| ≥ p̂|E(Bd (x))| ≥ s. If the corresponding
4

In the sense that for each H-edge inside, at least one of its copies in Ĥ is open.

9

event does no occur, set αu := 0. If this event occurs, then, independently
on (ω, ω ′ ) and everything that happened so far, set αu := 1 with probability
s/q ≤ 1 and αu := 0 otherwise. Declare u to be s-explored.
′
7. If αu = 1, then set C2K+2,n+1 := C2K+2,n ∪ Sr+1 (u) and C2K+2,n+1
to be
′
the union of C2K+2,n , Z(x, r, d), and the e ’s of Substep 5. Notice that Condition (C) continues to hold as in this case Z is “fully η-open” and η-connected
′
′
to C2K+2,n . Otherwise, set C2K+2,n+1 := C2K+2,n and C2K+2,n+1
:= C2K+2,n
.
When this step is finished, set C2K+2 :=

S

′
C2K+2,n and C2K+2
:=

S

′
C2K+2,n
.

′ :=
′
′
Step ∞ Set C∞ := K CK and C∞
K CK . Take η independent of everything done so far, with distribution Ber(p̂)⊗E(Ĝ) . Wherever η is undefined, define
it to be equal to η ′ . In the same way, wherever α is undefined, toss independent
Bernoulli random variables of parameter s, independent of everything done so far.

S

S

By construction, C∞ has the distribution of the cluster of the origin for the
(p, s)-process on H: it is the cluster of the origin of ((∨k ωe,k )e , α) which has distribution Ber(p)⊗E(H) ⊗Ber(s)⊗V (H) . Recall that ∨ stands for the maximum operator,
′ is included
thus corresponding to the union of the corresponding sets. Besides, C∞
in the cluster of o′ for (∨k ηe,k )e , which is a p-bond-percolation on G. Finally, the
′ onto C . Proposition 4.1 follows.
coupling guarantees that π surjects C∞
∞
Remark. This construction adapts to site percolation. The lift is the same as in
[BS96] while the “multiple edges” trick now consists of defining Ĝ as follows: each
vertex has M possible states, and it is p-open if one of its p̂-states says so.

6

Proof of Proposition 4.2

In this proof, we follow the strategy of Aizenman and Grimmett [AG91, BBR].
There is essentially no difficulty in adapting their ideas to our specific context, but
we provide the details for the sake of completeness.
Let θL (p, s) be the Pp,s-probability of the event EL := {Co (ω, α) ∩ SL (o) 6= ∅},
p,s
and θ(p, s) = limL→∞ θL (p, s) be the probability that Co (ω, α) = CH
(o) is infinite.
We claim that in order to prove Proposition 4.2, we only need to show that for any
ε > 0, there exist c = c(ε) > 0 and L0 (ε) ≥ 1 such that for any p, s ∈ [ε, 1 − ε] and
L ≥ L0 , we have
∂
∂
θL (p, s) ≥ c θL (p, s).
(1)
∂s
∂p
Indeed, assume that (1) is true. It is easy to see that, since pc (H) ∈ (0, 1), for any
s > 0, there is some ε > 0 such that we can find a curve — actually a line seg′ (t)
ment — (p(t), s(t))t∈[0,s] inside [ε, 1 − ε]2 satisfying ps′ (t)
= −c for all t ∈ [0, s] and
p0 := p(0) > pc (H), ps := p(s) < pc (H), s(s) = s. But now note that (1) implies
10

that t 7→ θL (p(t), s(t)) is a non-decreasing function for all L ≥ L0 . In particular we have θ(ps , s) = θ(p(s), s(s)) = limL θL (p(s), s(s)) ≥ limL θL (p(0), s(0)) =
θ(p(0), s(0)) ≥ θ(p0 , 0) > 0, where in the last inequality we use p0 > pc (H). By
monotonicity, we conclude that for every p ∈ [ps , 1], we have θ(p, s) > 0 as desired.
Now, note that, since the event EL , which depends only on finitely many coordinates, is increasing in both ω and α, the Margulis-Russo formula gives us
X
∂
θL (p, s) =
Pp,s(e is p-pivotal for EL ),
∂p
e
X
∂
Pp,s (x is s-pivotal for EL ).
θL (p, s) =
∂s
x

Recall that an edge e is said to be p-pivotal for an increasing event E in a configuration (ω, α) if (ω ∪ {e}, α) ∈ E but (ω \ {e}, α) ∈
/ E. Similarly, a vertex x is said to
be s-pivotal for an increasing event E in a configuration (ω, α) if (ω, α ∪ {x}) ∈ E
but (ω, α \ {x}) ∈
/ E.
It follows from the above formulas that in order to derive (1), it is enough to
prove that for some R, L0 > 0, for every ε > 0, there is some c′ > 0 such that for
any edge e and any p, s ∈ [ε, 1 − ε], one has
X

Pp,s(x is s-pivotal for EL ) ≥ c′ Pp,s(e is p-pivotal for EL ),

(2)

x∈BR (e)

where for e = {x, y}, we set BR (e) := BR (x) ∪ BR (y). Indeed, since each vertex
can be in BR (e) for at most C := maxx |BR (x)| × maxx degree(x) different e’s,
summing (2) over e gives:
X

CPp,s(x is s-pivotal for EL ) ≥ c′

X

Pp,s(e is p-pivotal for EL )

e

x

which implies (1) for c := c′ /C.
The following deterministic lemma directly implies (2).
Lemma 6.1. There are constants L0 and R such that the following holds. If
L ≥ L0 and an edge e is p-pivotal for EL in a configuration (ω, α), then there exist
a configuration (ω ′ , α′ ) differing from (ω, α) only inside BR (e) and a vertex z in
BR (e) such that z is s-pivotal for EL in (ω ′ , α′ ).
Proof. Take R := 3r + 1 and L0 := 2r + 2. Let (ω, α) and e be as in Lemma 6.1
and assume without loss of generality that (ω, α) ∈ EL . Now, remove from α
all the vertices in BR (e) one by one. If at some point we get, for the first time,
a configuration (ω, α′ ) which is not in EL anymore, then it means that the last
vertex z that was removed is s-pivotal for that configuration (ω, α′ ), thus yielding
the conclusion of the lemma. Therefore we can assume that (ω, α′ ) ∈ EL where
α′ := α \ BR (e). In particular, e is still p-pivotal for (ω, α′ ). We now have two
cases.
11

Case a) The edge e = {x, y} is far from the origin o, namely d(o, e) > r.
Since e is pivotal for EL , we have e ⊂ BL (o) and e 6⊂ SL (o). So we can assume
without loss of generality that x ∈ BL−1 (o). Take z to be a vertex such that
x ∈ Br (z) ⊂ BL−1 (o) and o ∈
/ Br (z).5 Now, take some vertex u ∈ Sr+1 (z) such
′
that u ∈ Co (ω̃, α ), where ω̃ is given by closing in ω all the edges inside Br+1 (z),
i.e. ω̃ := ω \ {f ∈ E(H) ; f ⊂ Br+1 (z)}. Such a vertex can be obtained as follows.
Let n be the first step of the exploration that contains some vertex of Sr+1 (z), i.e.
such that Cn (ω, α′ ) ∩ Sr+1 (z) 6= ∅. The previous step n − 1 does not depend on the
state of the edges inside Br+1 (z). In particular, one has Cn−1 := Cn−1 (ω, α′ ) =
Cn−1 (ω̃, α′ ). Notice that as α′ ∩ B2r+1 (z) = ∅, the step n is actually an odd one
(in which we only explore things in ω). Therefore Cn−1 is ω-connected to Sn+1 (z).
In particular, there is some u ∈ Sr+1 such that Cn−1 is ω-connected to u outside
Br+1 (z), thus also ω̃-connected. All of this implies that u ∈ Cn (ω̃, α′ ) ⊂ Co (ω̃, α′ ).
Let v be any neighbour of u in Br (z). Finally, define ω ′ by closing in ω all the
edges inside Br+1 (z) and then opening {u, v} together with all the edges inside
Br (z). Formally, one has
ω ′ := (ω \ {f ∈ E(H) ; f ⊂ Br+1 (z)}) ∪ ({f ∈ E(H) ; f ⊂ Br (z)} ∪ {{u, v}}.
Case b) The edge e is close to the origin, namely d(o, e) ≤ r.
Without loss of generality, assume d(o, x) ≤ r. Then simply take z = x and ω ′
given by closing in ω all the edges inside Br+1 (x) and then opening all the edges
inside Br (x), i.e. ω ′ := (ω \ {f ∈ E(H) ; f ⊂ Br+1 (x)}) ∪ {f ∈ E(H) ; f ⊂ Br (x)}.
We claim that, in both cases above, z is s-pivotal for the event EL in the
configuration (ω ′ , α′ ). We are only going to treat Case a). We leave the slightly
simpler Case b) to the reader.
Remind that by the definition of u, we have u ∈ Co (ω̃, α′ ). Since α′ ∩B2r+1 (z) =
∅, we see that after opening in ω̃ all the edges inside Br (z) together with {u, v}
(therefore yielding ω ′ ), we do not create new s-open edges, so that Co (ω ′ , α′ ) =
Co (ω̃, α′ )∪Br (z). In particular, one has Co (ω ′ , α′ )∩SL (o) = ∅, so that (ω ′ , α′ ) ∈
/ EL .
Recall that z ∈ Co (ω ′ , α′ ) ⊂ Co (ω ′ , α′ ∪ {z}) and that Br (z) is p-open. It
implies that Br+1 (z) is contained in Co (ω ′ , α′ ∪ {z}). Together with ω ⊂ ω ′ ∪
Br+1 (z) and B2r+1 (z) ∩ α′ = ∅, it implies that Co (ω, α′ ) ⊂ CBr+1 (z)∪{o} (ω, α′ ) ⊂
CBr+1 (z)∪{o} (ω ′ , α′ ∪ {z}) = Co (ω ′ , α′ ∪ {z}), where CBr+1 (z)∪{o} (ω, α) is defined as
Co (ω, α) but with C0 = Br+1 (z) ∪ {o}. As a result, Co (ω ′ , α′ ∪ {z}) ∩ SL (o) 6= ∅,
⊓
so that (ω ′ , α′ ∪ {z}) ∈ EL .
⊔
Remark. As in the previous section, the proof above can be adapted to site percolation in a straightforward way.
Just take a suitable vertex in some geodesic from x to o. In the case where d(x, SL−1 (o)) ≥ r
one can simply take z = x. Here we are using that L ≥ L0 = 2r + 2.
5

12

7

Deriving corollaries from Theorem 2.1

Corollary 2.2 follows from Theorem 2.1 and Lemmas 7.1 and 7.2.
Lemma 7.1. Let G be a graph, and let G be a group acting on V (G) by graph
automorphisms. Let H be the quotient graph G/G and π : V (G) → V (H) denote
the quotient map x 7→ Gx.
If G y V (G) is free, then π has the disjoint tree-lifting property.
Proof. With the notation of Lemma 7.1, let x and y be two distinct vertices of
G such that π(x) = π(y). Let T be a subtree of H, and let Tx be a lift of T that
contains x: recall that such a lift exists, as π is a weak covering map. As Gx = Gy,
let us take some g ∈ G such that gx = y. Since x and y are distinct, g is not the
identity element. Therefore, by freeness of the action, g has no fixed point.
We claim that Ty := gTx is a lift of T that is vertex-disjoint from Tx . It
is indeed a lift, as ∀z ∈ V (G), π(z) = π(gz). To prove vertex-disjunction, let
z ∈ V (Tx ) ∩ gV (Tx ). Thus, one can pick z⋆ in V (Tx ) such that z = gz⋆ . As
π(z) = π(gz⋆ ) = π(z⋆ ), one has z = z⋆ . Therefore, one has z = gz, which
⊓
contradicts the fact that g has no fixed point.
⊔
Lemma 7.2. Let G be a graph, and let G be a group acting on V (G) by graph
automorphisms. Let H be the quotient graph G/G and π : V (G) → V (H) denote
the quotient map x 7→ Gx. Assume that G y V (G) is free, that G is not equal to
{1}, and that both G and H are quasi-transitive. Then, π has tame fibres.
Proof. Let (G, G, H, π) satisfy the assumptions of Lemma 7.2. First, assume
additionally that there is some r such that for every x ∈ V (G), one has |Br (x)| >
|Br (π(x))|. Fix such an r. Let x be any vertex of G. As π(Br (x)) = Br (π(x)),
by the pigeonhole principle, one can pick two vertices y and z in Br (x) such that
π(y) = π(z). Pick a path of length at most r from π(y) to π(x) in Br (π(x)).
As paths are trees, by Lemma 7.1, one can obtain two vertex-disjoint lifts of this
path with one starting at y and the other at z. Each of these paths ends inside
π −1 ({π(x)}) ∩ B2r (x): therefore, this set contains at least one vertex distinct from
x, thus establishing the tameness of fibres with R := 2r.
Let us now prove that the assumptions of the lemma imply the existence
of such an r. Pick one vertex in each Aut(G)-orbit, thus yielding a finite set
{x1 , . . . , xm } ⊂ V (G). Define {u1 , . . . , un } ⊂ V (H) by doing the same in H. Proceeding by contradiction and as π is a weak covering map, we may assume that for
every r, there is some x ∈ V (G) such that Br (x) and Br (π(x)) are isomorphic as
rooted graphs. As a result, for every r, there are some i and j such that Br (xi ) and
Br (uj ) are isomorphic as rooted graphs. As i and j can take only finitely many
values, there is some (i0 , j0 ) such that for arbitrarily large values of r — hence all
values of r —, the rooted graphs Br (xi0 ) and Br (uj0 ) are isomorphic. It results
from local finiteness and diagonal extraction (or equivalently from the fact that
13

the local topology on locally finite connected rooted graphs is Hausdorff) that G
and H are isomorphic.
This is a contradiction for the following reason. Let g ∈ G\{1} =
6 ∅, and let
γ be a path from x1 to gx1 6= x1 . For r0 large enough, for all i ≤ m, the r0 -ball
centred at xi contains the support of γ. Pick such an r0 and pick i such that the
cardinality of Br0 (xi ) is minimal: as π(x1 ) = π(gx1 ), the cardinality of Br0 (π(xi ))
is strictly less than that of Br0 (xi ). Therefore, the minimal cardinality of an r0 -ball
⊓
is not the same for H and G.
⊔
Corollary 2.3 results from Theorem 2.1 and the following lemma.
Lemma 7.3. Any strong covering map has the disjoint tree-lifting property.
Proof. Let π : G → H denote a strong covering map. Let x and y be two vertices
of G such that π(x) = π(y). Let T be a subtree of H, and let Tx and Ty be lifts of
T such that x belongs to V (Tx ) and y to V (Ty ). Assume that V (Tx ) ∩ V (Ty ) 6= ∅.
Let us prove that x = y.
As Tx is connected, it suffices to prove that if z0 belongs to V (Tx ) ∩ V (Ty ), then
all its Tx -neighbours belong to V (Tx ) ∩ V (Ty ). But this is the case: indeed, any
Tx -neighbour z1 of z0 is, by the strong lifting property, the unique neighbour z⋆ of
z0 such that π({z0 , z⋆ }) = π({z0 , z1 }), so that π −1 ({π(z1 )}) ∩ V (Ty ) = {z1 }.
⊓
⊔
Acknowledgements We are indebted to Hugo Duminil-Copin, Vincent Tassion,
and Augusto Teixeira for many valuable discussions. We are grateful to Vincent
Beffara, Hugo Duminil-Copin, and Aran Raoufi for comments on an earlier version
of this paper. SM is funded by the ERC grant GeoBrown: he is thankful to his
postdoctoral hosts Nicolas Curien and Jean-François Le Gall, the Laboratoire de
Mathématiques d’Orsay, and GeoBrown for excellent working conditions. FS is
thankful to his PhD advisor Hugo Duminil-Copin and IHES for excellent working
conditions as well.

14

References
[AG91] Michael Aizenman and Geoffrey Grimmett. Strict monotonicity for critical points
in percolation and ferromagnetic models. Journal of Statistical Physics, 63(56):817–835, 1991.
[BBR]

Paul Balister, Béla Bollobás, and Oliver Riordan. Essential enhancements revisited. ArXiv 1402.0834.

[BS96]

Itai Benjamini and Oded Schramm. Percolation beyond Zd , many questions and
a few answers. Electron. Comm. Probab., 1:71–82, 1996.

[Gri99] Geoffrey Grimmett. Percolation, volume 321 of Grundlehren der Mathematischen
Wissenschaften. Springer-Verlag, Berlin, second edition, 1999.
[HB57] John Hammersley and Simon Broadbent. Percolation processes: I. Crystals and
mazes. In Proc. Cambridge Philos. Soc, volume 53, pages 629–641, 1957.
[LP16]

Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42.
Cambridge University Press, 2016.

[Men87] Mikhail Men’shikov. Quantitative estimates and strong inequalities for critical
points of a graph and its subgraph. Teoriya Veroyatnostei i ee Primeneniya,
32(3):599–602, 1987.

15

