Strict monotonicity of percolation thresholds under covering maps
Sébastien Martineau Franco Severo


 
 

 
 
 
 
 
 
 
 

 


 
 








arrows





.
theoremTheorem[section]
thm[theorem]Theorem
*thmnonum[theorem]Theorem
*propnonum[theorem]Proposition
fact[theorem]Fact
coro[theorem]Corollary
lemma[theorem]Lemma
quest[theorem]Question
problem[theorem]Problem
*fuzzquest[theorem]Fuzzy question
*family[theorem]Family of questions
*conj[theorem]Conjecture
prop[theorem]Proposition
*propun[theorem]Proposition <ref>
*propdeux[theorem]Proposition <ref>
definition
question[theorem]Question


rem[1][Remark.]

  #1

application[1][Application.]

  #1

appli[1][Application.]

  Application.

notation[1][Notation.]

  Notation.

exam[1][Example.]

  #1

cex[1][Counter-example.]

  #1


.3ex⊓⊔
5ptwidth4pt height6pt depth1.5pt
1pt






































↷


































[itemize]noitemsep, nolistsep
[enumerate]noitemsep, nolistsep








Strict monotonicity of percolation thresholds under covering maps
    Sébastien Martineau[Université Paris-Sud, mailto:sebastien.martineau@u-psud.frsebastien.martineau@u-psud.fr]  and Franco Severo[Institut des Hautes Études Scientifiques, mailto:severo@ihes.frsevero@ihes.fr]
    
==================================================================================================================================================================================================================





 We answer a question of Benjamini and Schramm by proving that under reasonable conditions, quotienting a graph strictly increases the value of its percolation critical parameter p_c. More precisely, let 𝒢=(V,E) be a quasi-transitive graph with p_c(𝒢)<1, and let G be a nontrivial group that acts freely on V by graph automorphisms. Assume that ℋ:=𝒢/G is quasi-transitive. Then one has p_c(𝒢)<p_c(ℋ).

We provide results beyond this setting: we treat the case of general covering maps and provide a similar result for the uniqueness parameter p_u, under an additional assumption of boundedness of the fibres. The proof makes use of a coupling built by lifting the exploration of the cluster, and an exploratory counterpart of Aizenman-Grimmett's essential enhancements.







§ INTRODUCTION


Bernoulli percolation is a simple model for problems of propagation in porous media that was introduced in 1957 by Broadbent and Hammersely <cit.>: given a graph 𝒢 and a parameter p∈ [0,1], erase each edge independently with probability 1-p. Studying the connected components of this random graph (which are referred to as clusters) has been since then an active field of research: see the books <cit.>. A prominent quantity in this theory is the so-called critical parameter p_c(𝒢), which is characterised by the following dichotomy: for every p<p_c(𝒢), there is almost surely no infinite cluster, while for every p>p_c(𝒢), there is almost surely at least one infinite cluster.

Originally, the main focus was on the Euclidean lattice ^d.
In 1996, Benjamini and Schramm initiated the systematic study of Bernoulli percolation on more general graphs, namely quasi-transitive graphs <cit.>. 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 if it has finitely many types of vertices, and transitive if all the vertices look the same.
The paper <cit.> contains, as its title suggests, many questions and a few answers: in their Theorem 1 and Question 1, they investigate the monotonicity of p_c under quotients. Their Question 1 is precisely the topic of the present paper. It goes as follows.




  
Setting of <cit.> Let 𝒢=(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 is an orbit of G V, and two distinct orbits are connected by an edge if and only if there is an edge of 𝒢 intersecting both orbits.

Theorem 1 of <cit.> asserts that p_c(𝒢)≤ p_c(𝒢/G). It is proved by lifting the exploration of a spanning tree of the cluster of the origin from 𝒢/G to 𝒢. They then ask the following natural question.
Recall that a group action G X is free if the only element of G that has a fixed point is the identity element: 
    ∀ g∈ G\{1}, ∀ x∈ X, g x ≠ x.



[Benjamini-Schramm]

Consider the quotient graph ℋ:= 𝒢/G. Assume that p_c(𝒢)<1, G≠{1} acts freely on V(𝒢), and both 𝒢 and ℋ are quasi-transitive. Is it necessarily the case that p_c(𝒢)<p_c(ℋ)?


The main result of the present paper is a positive answer to this question: see Corollary <ref>. We use an exploratory version of Aizenman-Grimmett's essential enhancements <cit.>, and build a coupling between p-percolation on 𝒢 and enhanced percolation on ℋ by lifting the exploration of the cluster of the origin. The part of our work devoted to essential enhancements (Section <ref>) follows the Aizenman-Grimmett strategy, thus making crucial use of certain differential inequalities, see also <cit.>. Our coupling (Section <ref>) improves on that used in <cit.>.

We also address in Theorem <ref> a similar question for the uniqueness parameter p_u. Recall that given a quasi-transitive graph 𝒢, the number of infinite connected components for Bernoulli percolation of parameter p takes an almost sure value N_𝒢(p)∈{0,1,∞}, and that the following monotonicity property holds: ∀  p<q, N_𝒢(p)=1 N_𝒢(q)=1, see <cit.>. One thus defines p_u(𝒢):= inf{p∈ [0,1]:N_𝒢(p)=1}.





(100,10)
(0,0)
   (1,0)100


(33,6)p_c
(33,-1.5)
   (0,1)3


(67,6)p_u
(67,-1.5)
   (0,1)3


(0,6)0
(0,-1.5)
   (0,1)3


(100,6)1
(100,-1.5)
   (0,1)3


(12,3)N_𝒢 = 0

(45,3)N_𝒢 = ∞

(79,3)N_𝒢 = 1




Let us mention that a theorem quite similar to our Corollary <ref> has already been obtained for the connective constant instead of p_c. See Theorem 3.8 in <cit.>.



§ 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. Unless otherwise stated, our graphs are taken to be simple (no multiple edges, no self-loops, edges are unoriented). A graph 𝒢 may be written in the form (V,E), where V=V(𝒢) denotes its set of vertices and E=E(𝒢) its set of edges. An edge is a subset of V with precisely two elements. The degree of a vertex is its number of neighbours. Graphs are endowed with their respective graph distance, denoted by d. Finally, percolation is taken to mean Bernoulli bond percolation, but our proofs can be adapted to Bernoulli site percolation. 




In Question <ref>, the graphs 𝒢 and ℋ are related via the quotient map π : x ↦ 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(𝒢) and every neighbour u of π(x), there is a neighbour of x that is mapped 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 subtree[i.e. a tree with V(𝒯)⊂ V(ℋ) and E(𝒯)⊂ E(ℋ).] 𝒯 of ℋ, a lift of 𝒯 is a subtree 𝒯' of 𝒢 such that π induces a graph isomorphism from 𝒯' to 𝒯, i.e. it induces well-defined bijections from V(𝒯') to V(𝒯) and from E(𝒯') to E(𝒯).

The map π satisfies a second property, namely disjoint tree-lifting: if 𝒯 is a subtree of ℋ and if x and y are distinct vertices of 𝒢 such that π(x)=π(y) belongs to V(𝒯), then one can find two vertex-disjoint lifts of 𝒯 such that one of them contains x and the other y. This fact uses the freeness of G, and is established in Lemma <ref>.

Finally, the map π has tame fibres: there is some R such that for every x∈ V(𝒢), there is some y∈ V(𝒢) satisfying π(x)=π(y) and 0<d(x,y)≤ R. See Lemma <ref>.




It turns out that these three properties of π suffice to prove strict inequality, so that there is actually no need for group actions and quasi-transitivity.



Let 𝒢 and ℋ be graphs of bounded degree. Assume that there is a weak covering map π : V(𝒢)→ V(ℋ) with tame fibres and the disjoint tree-lifting property.
If p_c(𝒢)<1, then one has p_c(𝒢)<p_c(ℋ).




Let 𝒢 be a graph. Let G≠{1} be a group acting on V(𝒢) by graph automorphisms, and let ℋ denote the quotient graph 𝒢/G.
Assume that the following conditions hold:


  * the action G V(𝒢) is free,

  * 𝒢 is quasi-transitive,

  * ℋ is quasi-transitive,

  * p_c(𝒢)<1.

Then one has p_c(𝒢)<p_c(ℋ).




By using the techniques of <cit.>, one can deduce from Corollary <ref> and  <cit.> that when 𝒢 ranges over Cayley graphs of 3-solvable groups, p_c(𝒢) takes uncountably many values. Actually, one gets at least a Cantor set of such values. This is optimal in the following sense: there are only countably many 2-solvable finitely generated groups (see Corollary 3 in <cit.>), hence only countably many Cayley graphs of such groups. The same result without the solvability condition has been obtained previous to <cit.> by Kozma <cit.>, by working with graphs of the form 𝒢⋆𝒢. 



Theorem <ref> yields a second corollary. Say that a map π:V(𝒢)→ V(ℋ) is a strong covering map if it is 1-Lipschitz for the graph distance and has the strong lifting property: for every x∈ V(𝒢), 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 <ref> and Lemma <ref>, the following result holds.



Let 𝒢 and ℋ be graphs of bounded degree. Assume that there is a strong covering map π : V(𝒢)→ V(ℋ) with tame fibres.

If p_c(𝒢)<1, then one has p_c(𝒢)<p_c(ℋ).




We also have the following results regarding the value of p_u. 
Say that a weak covering map π : V(𝒢)→ V(ℋ) has bounded fibres if there is some K such that

    ∀ x,y∈ V(𝒢), π(x)=π(y) d(x,y)≤ K.

The following two theorems are, respectively, the p_u counterparts of Theorem 1 from <cit.> and Theorem <ref> above.

	
	Let 𝒢 and ℋ be quasi-transitive graphs. Assume that there is a weak covering map π : V(𝒢)→ V(ℋ) with bounded fibres. 
	
	Then one has p_u(𝒢)≤ p_u(ℋ).




Let 𝒢 and ℋ be quasi-transitive graphs. Assume that there is a non-injective weak covering map π : V(𝒢)→ V(ℋ) with bounded fibres and the disjoint tree-lifting property.

If p_u(𝒢)<1, then one has p_u(𝒢)<p_u(ℋ).


The next corollary follows from Theorem <ref> and Lemma <ref>.



Let 𝒢 be a graph. Let G≠{1} be a finite group acting on V(𝒢) by graph automorphisms, and let ℋ denote the quotient graph 𝒢/G.
Assume that the following conditions hold:


  * the action G V(𝒢) is free,

  * 𝒢 is quasi-transitive,

  * ℋ is quasi-transitive,

  * p_u(𝒢)<1.

Then one has p_u(𝒢)<p_u(ℋ).




Let 𝒢 and ℋ be quasi-transitive graphs. Assume that there is a non-injective strong covering map π : V(𝒢)→ V(ℋ) with bounded fibres. 

If p_u(𝒢)<1, then one has p_u(𝒢)<p_u(ℋ).


Our proofs can be made explicit in that they actually yield quantitative (but poor) lower bounds on the differences p_c(ℋ)-p_c(𝒢) and p_u(ℋ)-p_u(𝒢).



  
Structure of the paper The remaining of the paper is organised as follows.
Section <ref> discusses the hypotheses of our results. Section <ref> exposes the strategy of proof of Theorem <ref>, reducing it to the proof of Propositions <ref> and <ref>. They are respectively established in Sections <ref> and <ref>. Section <ref> explains why the corollaries follow from the theorems. Finally, Section <ref> is devoted to the proof of Theorems <ref> and <ref>.



§ ON THE HYPOTHESES OF OUR RESULTS



None of the four assumptions of Corollary <ref> can be removed.
This is clear for Hypothesis <ref>. For Hypothesis <ref>, take 𝒢_0 to be a quasi-transitive graph with p_c<1 — e.g. the square lattice or the 3-regular tree — and define 𝒢 by setting: 
    V(𝒢):=V(𝒢_0)×{0,1,2},  E(𝒢):=(E(𝒢_0)×{0})∪(V(𝒢)×{{0,1},{0,2}}),

where one identifies E(𝒢_0)×{0} with {{(x,0),(y,0)}:{x,y}∈ E(𝒢_0)} and V(𝒢)×{{0,1},{0,2}} with {{(x,0),(x,i)}:x∈ V(𝒢_0), i∈{1,2}}. It suffices then to take G:= /2 with the non-trivial element acting via (x,i)↦ (x,σ(i)), where σ is the (12)-transposition. Notice that if 𝒢_0 is taken to be amenable (e.g. the square lattice), then p_u(𝒢)=p_c(𝒢) and p_u(ℋ)=p_c(ℋ), so that Hypothesis <ref> is also necessary in Corollary <ref>. See <cit.>.

For Hypothesis <ref>, take once again 𝒢_0 to be a quasi-transitive graph with p_c<1, and pick some vertex o in 𝒢_0. The graph 𝒢 is defined by taking two disjoint copies of 𝒢_0 and putting an additional edge between the two copies of o. The group G:=/2 acts by swapping copies.

As for Hypothesis <ref>, take 𝒢 to be the square lattice ^2, and G to be /2 acting via the reflection (x,y) ↦ (x,1-y).



Still, we do not know what happens if freeness is relaxed to the absence of trivial G-orbit.



Let 𝒢 be a graph. Let G be a group acting on V(𝒢), and let ℋ denote the quotient graph 𝒢/G.
Assume that the following conditions hold:


  * ∀ x∈ V(𝒢), ∃ g∈ G, gx≠x,

  * 𝒢 is quasi-transitive,

  * ℋ is quasi-transitive,

Is it necessarily the case that p_c(𝒢)<1 implies p_c(𝒢)<p_c(ℋ)? If we assume further that G is finite, is it necessarily the case that p_u(𝒢)<1 implies p_u(𝒢)<p_u(ℋ)?


An interesting particular case (which we also do not know how to solve) is when G is normal in a quasi-transitive subgroup of 𝖠𝗎𝗍(𝒢). In that  setting, ℋ is automatically quasi-transitive, and the map π always has tame fibres.


As for Theorem <ref> and Corollary <ref>, notice that the assumption that fibres are tame cannot be replaced by non-triviality of the fibres (namely ∀ u∈ V(ℋ), |π^-1({u})|≠1), even if π is taken to be a classical covering map. Indeed, take ℋ to be a graph with bounded degree and p_c<1, and pick some edge e in ℋ. To define 𝒢, start with two copies of ℋ, and denote by {x,y} and {x',y'} the two copies of e. Then replace these two edges by {x',y} and {x,y'}, thus yielding a connected graph. Take π to be the natural projection from 𝒢 to ℋ.



We do not know how to answer the following question, which investigates a generalisation of Theorem <ref>/Corollary <ref>.



Let 𝒢 and ℋ be graphs of bounded degree. Assume that there is a weak covering map π : V(𝒢)→ V(ℋ) with tame fibres.

If p_c(𝒢)<1, is it necessarily the case that p_c(𝒢)<p_c(ℋ)?




Let 𝒢 and ℋ be quasi-transitive graphs. Assume that there is a weak covering map π : V(𝒢)→ V(ℋ) with tame and bounded fibres.

If p_u(𝒢)<1, is it necessarily the case that p_u(𝒢)<p_u(ℋ)?




Finally, notice that one cannot remove the finiteness assumption from Theorem <ref> and its corollaries. Indeed, without this assumption, it is even possible to have the strict inequality in the reverse direction. The following example shows that this is easy to obtain if one further relaxes the assumption that p_u(𝒢)<1: if one takes 𝒢 to be the 2d-regular tree and ℋ to be the d-dimensional hypercubic lattice, for some d≥ 2, then we have 
    p_u(ℋ)=p_c(ℋ)<1=p_u(𝒢).

If one does not want to relax the assumption that p_u(𝒢)<1, one can take d to be large enough, 𝒢_d to be the product of the 2d-regular tree and the bi-infinite line, and ℋ_d to be the (d+1)-dimensional hypercubic lattice. Indeed, p_u(𝒢_d)∼1/√(d) but p_u(ℋ_d)=p_c(ℋ_d)∼1/2d, see respectively <cit.> and <cit.>. 




§ PROOF OF THEOREM <REF>



Let 𝒢, ℋ and π be as in Theorem <ref>.
Let r be a positive integer. Pick a root o in ℋ, and some o'∈π^-1({o}).



  
Notation Given a graph (V,E), the ball of centre x and radius r is B_r(x):={y∈ V:d(x,y)≤ r}. It is considered as a set of vertices, but it may also be considered as a graph — with the structure the ambient graph induces on it. For r∈, the sphere of centre x and radius r is S_r(x):={y∈ V:d(x,y)=r}. We also set S_r+1/2(x):={e∈ E: e∩ S_r(x)≠∅ and e∩ S_r+1(x)≠∅}.





We are going to construct a random subset 𝒞_0 of V(ℋ) which will be a “strict enhancement” of the cluster of o in a p-percolation model on ℋ. Given a configuration (ω,α)∈{0,1}^E(ℋ)×{0,1}^V(ℋ), we define inductively a sequence (C_n)_n≥ 0 of subsets of V(ℋ) as follows. We sometimes identify ω with the subset of edges {e: ω_e=1} or the subgraph of ℋ associated with it. Set C_0 :={o}. For n≥ 0, let C_2n+1 be the union of the ω-clusters of the vertices of C_2n. Then let C_2n+2 be the union of C_2n+1 and the vertices v such that there is some u∈ C_2n+1 satisfying the following conditions:

	
  * d(u,v)=r+1,
	
  * ω_e=1 for all edges e in B_r(u),
	
  * α_u=1.

The sequence of sets (C_n) is non-decreasing, and we define 𝒞_o=𝒞_o(ω,α):= ⋃_n C_n. Given p,s∈ [0,1], the distribution of the random variable 𝒞_o(ω,α) under the probability measure ℙ_p,s:=𝖡𝖾𝗋(p)^⊗ E(ℋ)⊗𝖡𝖾𝗋(s)^⊗ V(ℋ) is denoted by 𝒞_ℋ^p,s(o). In a similar way, we can define 𝒞_A=𝒞_A(ω,α) — and its distribution under ℙ_p,s, denoted by 𝒞_ℋ^p,s(A) — by considering the same process but initialising it with C_0=A.
We also set 𝒞_𝒢^p(A) to be the distribution of the cluster of A in bond percolation of parameter p on 𝒢.

Note that 𝒞_o(ω,α) does not coincide with the cluster of o for the following model: declare an edge e to be open if “e is ω-open or there is a vertex u such that e∈ S_r+1/2(u), all the edges in B_r(u) are ω-open and α_u=1”. This would be an instance of the classical enhancement introduced by Aizenman and Grimmett — see <cit.>. Indeed, the model we consider here is an exploratory version of their model, and the former is stochastically dominated by the latter. For example, in our model the assertion v∈𝒞_u(ω,α) does not necessarily imply u∈𝒞_v(ω,α).


We will prove the following two propositions. The proof of Proposition <ref> proceeds by lifting some exploration process from ℋ to 𝒢: in that, it is similar to the proof of Theorem 1 of <cit.>. The proof of Proposition <ref> uses an exploratory variation of the techniques of Aizenman and Grimmett <cit.>. Even though essential enhancements are delicate in general <cit.>, it turns out that our particular enhancement can be handled for general graphs, even for site percolation.


There is a choice of r≥ 1 such that the following holds: for every ε >0, there is some s∈ (0,1) such that for every p∈ [ε, 1], 𝒞_ℋ^p,s(o) is stochastically dominated[There is a coupling such that the (ℋ,p,s)-cluster is a subset of the π-image of the (𝒢,p)-cluster.] by π(𝒞_𝒢^p(o')).




Assume further that p_c(ℋ)<1.
Then, for any choice of r≥ 1, the following holds: for every s∈ (0,1], there exists p_s<p_c(ℋ) such that for every p∈ [p_s,1], the cluster 𝒞_ℋ^p,s(o) is infinite with positive probability.


Assuming these propositions, let us establish Theorem <ref>.



Proof of Theorem <ref>. First, notice that if p_c(ℋ)=1, then the conclusion holds trivially. We thus assume that p_c(ℋ)<1. We pick r so that the conclusion of Proposition <ref> holds.
Since boundedness of the degree of ℋ implies that p_c(ℋ)>0, we can pick some ε in (0,p_c(ℋ)).
By Proposition <ref>, we can pick s∈ (0,1) such that for every p∈ [ε, 1], 𝒞_ℋ^p,s(o) is stochastically dominated by π(𝒞_𝒢^p(o')). By Proposition <ref>, there is some p_s<p_c(ℋ) such that for every p∈ [p_s,1], the cluster 𝒞_ℋ^p,s(o) is infinite with positive probability. Fix such a p_s, and set p:=max(p_s,ε)<p_c(ℋ). By definition of p_s, the cluster 𝒞_ℋ^p,s(o) is infinite with positive probability. As p≥ε, the definition of s implies that 𝒞_ℋ^p,s(o) is stochastically dominated by π(𝒞_𝒢^p(o')). As a result, π(𝒞_𝒢^p(o')) is infinite with positive probability. In particular, 𝒞_𝒢^p(o') is infinite with positive probability, so that p_c(𝒢)≤ p < p_c(ℋ). 

□





§ PROOF OF PROPOSITION <REF>









The choice of a suitable value of r is given by the following lemma.


There is a choice of r≥ 1 such that for every x∈ V(𝒢), the set Z=Z(x,r) defined as the connected component[Here π^-1(B_r(π(x)))∩ B_3r(x) is seen as endowed with the graph structure induced by 𝒢.] of x in π^-1(B_r(π(x)))∩ B_3r(x) satisfies that for any u∈ S_r+1(π(x)), the fibre π^-1({u}) contains at least two vertices adjacent to Z.



Let R be given by the fact that π has tame fibres and set r:=⌈R/2⌉. Let x be any vertex of 𝒢. Take some y∈ V(𝒢) such that π(x)=π(y) and 0<d(x,y)≤ R. Let 𝒯 be a spanning tree of B_r+1(π(x)) obtained by adding first the vertices at distance 1, then at distance 2, etc. As π has the disjoint tree-lifting property, one can pick two vertex-disjoint lifts 𝒯_x and 𝒯_y of 𝒯 such that x∈ V(𝒯_x) and y ∈ V(𝒯_y).

Let γ be a geodesic path from x to y, thus staying inside π^-1(B_r(π(x))) as R≤ 2r. The set Z' consisting in the union of the span of γ and (V(𝒯_x)∪ V(𝒯_y))∩π^-1(B_r(π(x))) is a connected subset of Z(x,r): its connectedness results from the choice of the spanning tree 𝒯. It thus suffices to prove that for any u∈ S_r+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 𝒯_x and another one in 𝒯_y.


Take r to satisfy the conclusion of Lemma <ref>.
Let ε >0.
Set M and s to be so that the following two conditions hold:

    ∀ e={x,y}∈ E(ℋ), M≥ |B_r(x)∪ B_r(y)|,


    ∀ x ∈ V(𝒢), s≤(1-(1-ε)^1/M)^|E(B_3r+1(x))|.

For instance, one may take M:=D^r+2 and s:=(1-(1-ε)^1/M)^D^3r+2, where D stands for the maximal degree of a vertex of 𝒢.
Let p∈ [ε, 1].



We define the multigraph  as follows: the vertex-set is V(𝒢), the edge-set is E(𝒢)×{1,…,M}, and ({x,y},k) is interpreted as an edge connecting x and y. The multigraph  is defined in the same way, with ℋ instead of 𝒢. The purpose of this multigraph is to allow multiple use of each edge for a bounded number of “s-bonus”. 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 :=1-(1-p)^1/M on , so that -percolation on  corresponds to p-percolation on . Let ω' be a Bernoulli percolation of parameter  on  that is independent of ω.  Choose an injection from E() to , so that E() is now endowed with a well-ordering. Do the same with E(), V() and V().

We now define algorithmically an exploration process. This dynamical process will construct edge after edge a Bernoulli percolation η of parameter  on  and an α with distribution (s)^⊗ V(ℋ). The random variables η, α, and ω will be coupled in a suitable way, and α will be independent of ω. 



  
Structure of the processIn the exploration, edges in  may get explored in two different ways, called p-explored and s-explored. Edges in  may get p-explored, and vertices in  may get s-explored. No vertex or edge will get explored more than once. In particular, no edge of  will get p- and s-explored.













For every ℓ>0, during Step ℓ, we will define inductively a sequence (C_ℓ,n)_n of subsets of V(ℋ) and a sequence (C'_ℓ,n)_n of subsets of V(𝒢).
At the end of each iteration of the process, it will be the case that the following conditions hold:


   If an edge e in  is p-explored, then there is a lift e' of e in 𝒢 such that the set of the p-explored lifts of e is precisely {e'}×{1,…,M}.


   If an edge e in E() is p-unexplored, then all of its lifts are unexplored.


   Every element of C_ℓ,n' is connected to o' by an η-open path.


   For every edge e in  and each lift e' of e in 𝒢, the number of s-explored edges of the form (e',k) is at most the number of s-explored vertices u in  at distance at most r from some endpoint of e.


   The map π induces a well-defined surjection from C'_ℓ,n to C_ℓ,n.





  
Step 0 Set C_0={o} and C'_0={o'}. Initially, nothing is considered to be p- or s-explored.




  
Step 2K+1 Set C_2K+1,0:=C_2K and C'_2K+1,0:=C'_2K.


While there is an unexplored edge that intersects C_2K+1,n in , do the following (otherwise finish this step):






  * take e to be the smallest such edge, 


  * pick u an endpoint of e in C_2K+1,n and call v its other endpoint,


  * pick e' some lift of e intersecting π^-1({u})∩ C'_2K+1,n≠∅,


  * declare e and all (e',k)'s to be p-explored (they were unexplored before because of Conditions and ),


  * for every k≤ M, define η_(e',k):=ω_(e,k),


  * set (C_2K+1,n+1,C'_2K+1,n+1):=(C_2K+1,n,C'_2K+1,n) if all the (e,k)'s are ω-closed; otherwise, set (C_2K+1,n+1,C'_2K+1,n+1):=(C_2K+1,n∪{v},C'_2K+1,n∪ e').





When this step is finished, which occurs after finitely or countably many iterations, set C_2K+1:=⋃_n C_2K+1,n and C'_2K+1:=⋃_n C_2K+1,n'.



  
Step 2K+2 Set C_2K+2,0:=C_2K+1 and C'_2K+2,0:=C'_2K+1.


While there is at least one s-unexplored vertex in C_2K+1 whose r-ball is “fully open”[In the sense that for each ℋ-edge inside, at least one of its copies in  is open.] in ω, do the following (otherwise finish this step):






  * take u to be the smallest such vertex,


  * pick some x ∈ C'_2K+1∩π^-1({u})≠∅,


  * This paragraph is not an algorithmic substep, but gathers a few relevant observations. Call an edge in 𝒢 p-explored if one (hence every by ) of its copies in  is p-explored. Call a p-explored edge of 𝒢 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 the p-explored edges of 𝒢 that lie inside π^-1(B_r(u)) are open. Also note that for each edge lying in Z(x,r), Condition and the value of M guarantee that at least one of its copies in  has not been s-explored. As a result, for every edge in Z(x,r), 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 <ref> possible.


  * For each p-unexplored edge e' in Z(x,r), take its s-unexplored copy (e',k) in  of smallest label k, set η_(e',k):=ω'_(e',k), and switch its status to s-explored.


  * If all these newly s-explored edges are open (so that Z is “fully η-open”), then perform this substep. By and the definition of r, for every ℋ-edge e∈ S_r+1/2(u), there is at least one lift e' of e that is adjacent to Z(x,r) and p-unexplored: pick the smallest one. By and the value of M, one of its copies (e',k) is s-unexplored: pick that with minimal k=:k_e. Declare all these edges to be s-explored and set η_(e',k_e):=ω'_(e',k_e). If all these (e',k_e)'s are ω'-open, then say that this substep is successful.


  * Notice that conditionally on everything that happened strictly before the current Substep <ref>, the event “Substep <ref> is performed and successful” has some (random) probability q≥^|E(Z(x,r))|≥^|E(B_3r(x))|≥ s. If the corresponding 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.


  * If α_u=1, then set C_2K+2,n+1:=C_2K+2,n∪ S_r+1(u) and C'_2K+2,n+1 to be the union of C_2K+2,n, Z(x,r), and the e''s of Substep <ref>. Notice that Condition  continues to hold as in this case Z is “fully η-open” and η-connected to C_2K+2,n. Otherwise, set C_2K+2,n+1:=C_2K+2,n and C'_2K+2,n+1:=C'_2K+2,n.



When this step is finished, set C_2K+2:=⋃_n C_2K+2,n and C'_2K+2:=⋃_n C_2K+2,n'.




  
Step ∞ Set C_∞:=⋃_K C_K and C'_∞:=⋃_K C'_K. Take η' independent of everything done so far, with distribution 𝖡𝖾𝗋()^⊗ E(). 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.




By construction, C_∞ has the distribution of the cluster of the origin for the (p,s)-process on : it is the cluster of the origin of ((∨_k ω_e,k)_e,α) which has distribution 𝖡𝖾𝗋(p)^⊗ E()⊗𝖡𝖾𝗋(s)^⊗ V(). Recall that ∨ stands for the maximum operator.
Besides, C'_∞ is included in the cluster of o' for (∨_k η_e,k)_e, which is a p-bond-percolation on 𝒢. Finally, the coupling guarantees that π surjects C'_∞ onto C_∞. Proposition <ref> follows.


This construction adapts to site percolation. The lift is the same as in <cit.> while the “multiple edges” trick now consists in defining  as follows: each vertex has M possible states, and it is p-open if one of its -states says so.




§ PROOF OF PROPOSITION <REF>



In this proof, we follow the strategy of Aizenman and Grimmett <cit.>.

By monotonicity, we can assume without loss of generality that s<1. Let θ_L(p,s) be the ℙ_p,s-probability of the event ℰ_L := {𝒞_o(ω,α) ∩ S_L(o) ≠∅}, and θ(p,s)=lim_L→∞θ_L(p,s) be the probability that 𝒞_o(ω,α)=𝒞_ℋ^p,s(o) is infinite.
We claim that in order to prove Proposition <ref>, we only need to show that for any ε>0, there exist c=c(ε)>0 and L_0(ε)≥1 such that for any p,s ∈ [ε,1-ε] and L≥ L_0, we have

    ∂/∂ sθ_L(p,s) ≥ c∂/∂ pθ_L(p,s).

Indeed, assume that (<ref>) is true. It is easy to see that, since p_c(ℋ)∈(0,1), for any s∈(0,1), there is some ε>0 such that we can find a curve  — actually a line segment — (𝐩(t),𝐬(t))_t∈[0,s] inside [ε,1-ε]^2 satisfying 𝐩'(t)/𝐬'(t)=-c for all t∈[0,s] and p_0:=𝐩(0)>p_c(ℋ), p_s:=𝐩(s)<p_c(ℋ), 𝐬(s)=s. But now note that (<ref>) implies that t↦θ_L(𝐩(t),𝐬(t)) is a non-decreasing function for all L≥ L_0. In particular we have θ(p_s,s)=θ(𝐩(s),𝐬(s)) = lim_Lθ_L(𝐩(s),𝐬(s)) ≥lim_Lθ_L(𝐩(0),𝐬(0)) = θ(𝐩(0),𝐬(0))≥θ(p_0,0)>0,
where in the last inequality we use p_0>p_c(ℋ). By monotonicity, we conclude that for every p∈[p_s,1], we have θ(p,s)>0 as desired.

Now note that since the event ℰ_L, which depends only on finitely many coordinates, is increasing in both ω and α, the Margulis-Russo formula gives us

    ∂/∂ pθ_L(p,s) = ∑_eℙ_p,s(e  is p-pivotal for ℰ_L),


    ∂/∂ sθ_L(p,s) = ∑_xℙ_p,s(x  is s-pivotal for ℰ_L).

Recall that an edge e is said to be p-pivotal for an increasing event ℰ in a configuration (ω,α) if (ω∪{e},α)∈ℰ but (ω∖{e},α)∉ℰ. 
Similarly, a vertex x is said to be s-pivotal for an increasing event ℰ in a configuration (ω,α) if (ω,α∪{x})∈ℰ but (ω,α∖{x})∉ℰ. 

It follows from the above formulas that in order to derive (<ref>), it is enough to prove that for some R, L_0>0, for every ε>0, there is some c'>0 such that for any edge e, any p,s∈[ε,1-ε], and any L≥ L_0, one has

    ∑_x∈ B_R(e)ℙ_p,s(x  is s-pivotal for ℰ_L) ≥ c' ℙ_p,s(e  is p-pivotal for ℰ_L),

where for e={x,y}, we set B_R(e):=B_R(x)∪ B_R(y).
Indeed, since each vertex can be in B_R(e) for at most C:=max_x |E(B_R+1(x))| different e's, summing (<ref>) over e gives:

    ∑_x C ℙ_p,s(x  is s-pivotal for ℰ_L) ≥ c' ∑_eℙ_p,s(e  is p-pivotal for ℰ_L)

which implies (<ref>) for c:=c'/C.

The following deterministic lemma directly implies (<ref>).
 




	There are constants R and L_0 such that the following holds. If L≥ L_0 and an edge e is p-pivotal for ℰ_L in a configuration (ω,α), then there exist a configuration (ω',α') differing from (ω,α) only inside B_R(e) and a vertex z in B_R(e) such that z is s-pivotal for ℰ_L in (ω',α').



 Take R:=3r+1 and L_0:=2r+2. Let (ω,α) and e be as in Lemma <ref> and assume without loss of generality that (ω,α)∈ℰ_L. Now, remove from α all the vertices in B_R(e) one by one. If at some point we get, for the first time, a configuration (ω,α') that is not in ℰ_L 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 (ω,α')∈ℰ_L where α':=α∖ B_R(e). In particular, e is still p-pivotal in (ω,α'). We now have two cases.
 


  
Case a. The edge e={x,y} is far from the origin o, namely d(o,e) > r.




 Since e is p-pivotal for ℰ_L, we have e⊂ B_L(o) and e⊄S_L(o). So we can assume without loss of generality that x∈ B_L-1(o). Take z to be a vertex such that x∈ B_r(z)⊂ B_L-1(o) and o∉ B_r(z).[Just take a suitable vertex in some geodesic from x to o. In the case where d(x,S_L-1(o))≥ r one can simply take z=x. Here we are using that L≥ L_0=2r+2.] 
 Now, take some vertex u∈ S_r+1(z) such that u∈𝒞_o(ω̃,α'), where ω̃ is given by closing in ω all the edges inside B_r+1(z), i.e. ω̃:=ω∖ E(B_r+1(z)). Such a vertex can be obtained as follows. Let n be the first step of the exploration that contains some vertex of S_r+1(z), i.e. such that C_n(ω,α')∩ S_r+1(z)≠∅. The previous step n-1 does not depend on the state of the edges inside B_r+1(z). In particular, one has C_n-1:=C_n-1(ω,α')=C_n-1(ω̃,α'). Notice that as α'∩ B_2r+1(z)=∅, the step n is actually an odd one (in which we only explore things in ω). Therefore C_n-1 is ω-connected to S_r+1(z). In particular, there is some u∈ S_r+1(z) such that C_n-1 is ω-connected to u outside B_r+1(z), thus also ω̃-connected. All of this implies that u∈ C_n(ω̃,α') ⊂𝒞_o(ω̃,α'). 
 Let v be any neighbour of u in B_r(z). Finally, define ω' by opening in ω̃ the edge {u,v} together with all the edges inside B_r(z). Formally, one has 
    ω':=[ω∖ E(B_r+1(z))] ∪ [E(B_r(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 B_r+1(x) and then opening all the edges inside B_r(x), i.e. ω':=[ω∖ E(B_r+1(x))]∪ E(B_r(x)).
 



 We claim that, in both cases above, z is s-pivotal for the event ℰ_L in the configuration (ω',α'). We are only going to treat Case a. We leave the slightly simpler Case b to the reader.

Remind that by definition of u, we have u∈𝒞_o(ω̃,α'). Since α'∩ B_2r+1(z)=∅, one can see that after opening at ω̃ all the edges inside B_r(z) together with {u,v} (thus yielding ω'), we do not add any extra vertex in even steps but we add B_r(z) at a certain odd step, so that 𝒞_o(ω',α')=𝒞_o(ω̃,α')∪ B_r(z). In particular, one has 𝒞_o(ω',α')∩ S_L(o)=∅, so that (ω',α')∉ℰ_L.


Recall that z∈𝒞_o(ω',α')⊂𝒞_o(ω',α'∪{z}) and that B_r(z) is p-open. This implies that B_r+1(z) is contained in 𝒞_o(ω',α'∪{z}). Together with ω⊂ω'∪ B_r+1(z) and B_2r+1(z) ∩α'=∅, this implies that 𝒞_o(ω,α')⊂𝒞_B_r+1(z)∪{o}(ω,α')⊂𝒞_B_r+1(z)∪{o}(ω',α'∪{z})= 𝒞_o(ω',α'∪{z}). As a result, 𝒞_o(ω',α'
 ∪{z})∩ S_L(o)≠∅, so that (ω',α'∪{z})∈ℰ_L.




As in the previous section, the proof above can be adapted to site percolation in a straightforward way.	





§ DERIVING COROLLARIES FROM THEOREMS <REF> AND <REF>



Corollary <ref> results from and Lemmas <ref> and <ref>, and Theorem <ref>, while Corollary <ref> results from and Lemmas <ref>, <ref> and <ref>, and Theorem <ref>.
Likewise, Corollaries <ref> and <ref> follow by combining Lemma <ref> with Theorems <ref> and <ref>, respectively.




Let 𝒢 be a graph, and let G be a group acting on V(𝒢) by graph automorphisms. Let ℋ be the quotient graph 𝒢/G and π:V(𝒢)→ V(ℋ) denote the quotient map x↦ Gx.

If G V(𝒢) is free, then π has the disjoint tree-lifting property.



With the notation of Lemma <ref>, let x and y be two distinct vertices of 𝒢 such that π(x)=π(y). Let 𝒯 be a subtree of ℋ, and let 𝒯_x be a lift of 𝒯 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 𝒯_y:=g𝒯_x is a lift of 𝒯 that is vertex-disjoint from 𝒯_x. It is indeed a lift, as ∀ z∈ V(𝒢), π(z)=π(gz). To prove vertex-disjunction, let z∈ V(𝒯_x)∩ gV(𝒯_x). Thus, one can pick z_⋆ in V(𝒯_x) 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.




Let 𝒢 and ℋ be quasi-transitive graphs. Let π : V(𝒢)→ V(ℋ) be a non-injective weak covering map with the disjoint tree-lifting property.

Then π has tame fibres.



Let (𝒢,ℋ,π) satisfy the assumptions of Lemma <ref>.
First, assume additionally that there is some r such that for every x∈ V(𝒢), one has |B_r(x)|>|B_r(π(x))|. Fix such an r. Let x be any vertex of 𝒢. As π(B_r(x))= B_r(π(x)), by the pigeonhole principle, one can pick two vertices y and z in B_r(x) such that π(y)=π(z). Pick a self-avoiding path of length at most r from π(y) to π(x) in B_r(π(x)). As π has the disjoint tree-lifting property, 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)})∩ B_2r(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 𝖠𝗎𝗍(𝒢)-orbit, thus yielding a finite set {x_1,…,x_m}⊂ V(𝒢). Define {u_1,…,u_n}⊂ V(ℋ) by doing the same in ℋ. Proceeding by contradiction and as π is a weak covering map, we may assume that for every r, there is some x∈ V(𝒢) such that B_r(x) and B_r(π(x)) are isomorphic as rooted graphs. As a result, for every r, there are some i and j such that B_r(x_i) and B_r(u_j) are isomorphic as rooted graphs. As i and j can take only finitely many values, there is some (i_0,j_0) such that for infinitely many values of r — hence all values of r —, the rooted graphs B_r(x_i_0) and B_r(u_j_0) are isomorphic. It results from local finiteness and diagonal extraction (or equivalently from the fact that the local topology on locally finite connected rooted graphs is Hausdorff) that 𝒢 and ℋ are isomorphic.

This is a contradiction for the following reason. There are two vertices x and y in 𝒢 such that π(x)=π(y): fix such a pair (x,y).  For r_0 large enough, for all i≤ m, the r_0-ball centred at x_i contains x and y. Pick such an r_0 and pick i such that the cardinality of B_r_0(x_i) is minimal: as π(x)=π(y), the cardinality of B_r_0(π(x_i)) is strictly less than that of B_r_0(x_i). Therefore, the minimal cardinality of an r_0-ball is not the same for ℋ and 𝒢.




Notice that in the above proof we only needed to use that we can lift paths disjointly.




Any strong covering map has the disjoint tree-lifting property.



Let π:𝒢→ℋ denote a strong covering map. Let x and y be two vertices of 𝒢 such that π(x)=π(y). Let 𝒯 be a subtree of ℋ, and let 𝒯_x and 𝒯_y be lifts of 𝒯 such that x belongs to V(𝒯_x) and y to V(𝒯_y). Assume that V(𝒯_x)∩ V(𝒯_y)≠∅. Let us prove that x=y.

As 𝒯_x is connected, it suffices to prove that if z_0 belongs to V(𝒯_x)∩ V(𝒯_y), then all its 𝒯_x-neighbours belong to V(𝒯_x)∩ V(𝒯_y). But this is the case: indeed, any 𝒯_x-neighbour z_1 of z_0 is, by the strong lifting property, the unique neighbour z_⋆ of z_0 such that π({z_0,z_⋆})=π({z_0,z_1}), so that π^-1({π(z_1)})∩ V(𝒯_y)={z_1}.





In the following lemma, we show that the assumption of bounded fibres in Theorems <ref> and Corollary <ref> can actually be relaxed to that of fibres of bounded cardinality, i.e. the condition that sup_u∈ V(ℋ)|π^-1({u})|<∞.


	
	Let 𝒢 and ℋ be quasi-transitive graphs. Assume that there is a non-injective weak covering map π:V(𝒢)→ V(ℋ) with the disjoint tree-lifting property and fibres of bounded cardinality.

	Then there is a map π_⋆:V(𝒢)→ V(ℋ) satisfying all these conditions and that furthermore has bounded and tame fibres.




Concerning Corollary <ref>, the boundedness assumption can be relaxed further to the condition that π^-1({o}) is finite. Indeed, for a strong covering map, the cardinality of π^-1({u}) does not depend on u. 



	First, let us prove that there is a weak covering map π_⋆:V(𝒢)→ V(ℋ) with the disjoint tree-lifting property and bounded fibres. If π has bounded fibres, then we are done. Thus, assume that this is not the case. Let K denote the maximal cardinality of a fibre, i.e. K=max_u∈ V(ℋ) |π^-1({u})|. Since π does not have bounded fibres and since u↦𝖽𝗂𝖺𝗆(π^-1({u}) is 2-Lipschitz, for every n, there is some x_n∈ V(𝒢) such that
	
    ∀ u ∈ V(ℋ), |π^-1({u})∩ B_n(x_n)|≤ K-1.

As 𝒢 is quasi-transitive, one can pick F some finite set of vertices of 𝒢 that intersects every 𝖠𝗎𝗍(𝒢)-orbit. For every n, pick some graph automorphism φ_n of 𝒢 such that φ^-1(x_n)∈ F, and define the equivalence relation ℛ_n on V(𝒢) by:

    x ℛ_n y π(φ_n(x)) = π(φ_n(y)).

By taking a pointwise limit of these relations along a converging subsequence, one can endow V(𝒢) with an equivalence relation ℛ such that:
	
		
  * 𝒢/ℛ is isomorphic to ℋ,
		
  * the projection π_1 : V(𝒢)→ V(𝒢)/ℛ is a weak covering map with the disjoint tree-lifting property,
		
  * every ℛ-class has cardinality at most K-1.
	If π_1 has bounded fibres, then we are done. Otherwise, iterate the process, applying the same construction to π_1 instead of π. Since the maximal cardinality of a fibre cannot decrease forever, this process stops at some suitable π_⋆.
	
	Now, we need to show that π_⋆ has tame fibres. Notice that the weak covering map π_⋆ cannot be injective, as 𝒢 and ℋ are not isomorphic: see the last paragraph of the proof of Lemma <ref>. As π_⋆ has the disjoint tree-lifting property, every π_⋆-fibre π_⋆^-1({u}) has cardinality at least 2. As π_⋆ has bounded fibres, this implies that π_⋆ has tame fibres.





§ PROOF OF THEOREMS <REF> AND <REF>



As a warm-up, let us first prove Theorem <ref>.



 §.§ Proof of Theorem <ref>



In what follows, we will denote by _p the percolation measure of parameter p on both graphs 𝒢 and ℋ, but this will not cause any confusion. For A and B two subsets of the vertices of a graph, we write “A ↔ B” for the event that there is an open path intersecting both A and B. Similarly, “A↔∞” will denote the event that there is an infinite (self-avoiding) open path intersecting A.

Let 𝒢, ℋ and π be as in Theorem <ref>. The coupling used in <cit.> to prove the monotonicity of p_c under covering maps yields straightforwardly the following fact: for any two finite subsets A,B⊂ V(ℋ) one has

    _p[π^-1(A)↔π^-1(B) ]≥_p[A ↔ B].


Assume that p>p_u(ℋ). By uniqueness of the infinite cluster at p and the Harris-FKG inequality, one has 

    _p[ B_ℓ(u) ↔ B_ℓ (v)]   ≥_p[ B_ℓ(u) ↔∞,  B_ℓ (v)↔∞]
       ≥_p[ B_ℓ(u) ↔∞]_p[ B_ℓ(v) ↔∞]
 
for any two vertices u,v∈ V(ℋ). This implies, by quasi-transitivity, that

    lim_ℓ→∞ inf_u,v ∈ V(ℋ)_p[ B_ℓ(u) ↔ B_ℓ (v)]=1.

Let K be given by the boundedness of the fibres. As for any vertex x∈ V(𝒢), one has π^-1(B_ℓ(π(x)))⊂ B_ℓ+K(x), inequality (<ref>) and the previous equation imply that 

    lim_ℓ→∞ inf_x,y ∈ V(𝒢)_p[ B_ℓ(x) ↔ B_ℓ (y)]=1.
 
Now simply remind that the above equation guarantees that p≥ p_u(𝒢), see <cit.>.




 §.§ Proof of Theorem <ref>


The proof of Theorem <ref> follows quite closely that of Theorem <ref>.



Let 𝒢, ℋ and π be as in Theorem <ref>.
Let r be a positive integer.
We use the (p,s)-model of Section <ref>, except that we now initialise it at any finite set A, instead of just at a single point o. When using the (p,s)-model initialised at some finite set A⊂ V(ℋ), if B is a subset of V(ℋ), we write “A  B” for the event “𝒞_A∩ B≠∅”.



Here are two propositions, which are reminiscent of Propositions <ref> and <ref>. 


There is some choice of r≥ 1 such that the following holds: for every ε >0, there is some s∈ (0,1) such that for every p∈ [ε, 1], for every non-empty finite subset A' of V(𝒢), the random set 𝒞_ℋ^p,s(π(A')) is stochastically dominated by π(𝒞_𝒢^p(A')). In particular, for any two finite subsets A,B⊂ V(ℋ), one has

    _p[π^-1(A)↔π^-1(B) ]≥_p,s[A  B ].



Given a positive integer r, we say that a subset B of V(ℋ) is 𝐫-nice if it is finite, non-empty, and if for every u ∈ V(ℋ)\ B, there is some vertex v of ℋ such that B_r(v) contains u and does not intersect B.



For every r≥ 1 and s,ϵ>0, there exists δ>0 such that the following holds: for every p∈ [ϵ,1-ϵ] and any two non-empty finite subsets A, B⊂ V(ℋ) such that B is r-nice and  d(A,B)>3r, [recall that d(A,B):=min{d(u,v):u∈ A, v∈ B}]  one has

    _p,s[A  B ]≥_p+δ[A ↔ B].





Proposition <ref> is proved exactly as Proposition <ref>, except that the process is initialised at (A',π(A')) instead of ({o'},{o}). Recall that the assumptions of Theorem <ref> imply that π has tame fibres. 

In Section <ref>, we explain  how to adjust the proof of Proposition <ref> in order to get Proposition <ref>.





If p_u(ℋ)=1, then the conclusion holds trivially, so we can assume that p_u(ℋ)<1.
Since in addition p_u(ℋ)≥ p_c(ℋ)>0, we can find some ε>0 such that p_u(ℋ)∈ (ϵ,1-ϵ).
By Proposition <ref>, we can pick r∈ and s∈ (0,1) such that for every p∈ [ε, 1], for any two non-empty finite subsets A,B of V(ℋ), one has 

    _p[π^-1(A)↔π^-1(B) ]≥_p,s[A  B ].


By applying Proposition <ref> to some parameter p∈ (ϵ,1-ϵ) that satisfies p<p_u(ℋ)<p+δ=:q, we get that for any two non-empty finite subsets A, B⊂ V(ℋ) such that B is r-nice and d(A,B)>3r, one has

    _p,s[A  B ]≥_q[A↔ B ].


Let K be given by the fact that π has bounded fibres. 
Notice that for every x,y∈ V(𝒢), one has d(x,y)-K≤ d(π(x),π(y))≤ d(x,y). 
Let ℓ be a positive integer and x, y be vertices of 𝒢 such that d(x,y)>L(ℓ):=2ℓ+4r+K. Define u:=π(x), v:=π(y), A:= B_ℓ(u) and B:=V(ℋ)\⋃_w:  d(w,v)>r+ℓ B_r(w). Since B is r-nice and d(A,B)>3r, we have 

    _p[π^-1(A)↔π^-1(B) ]≥_p,s[A  B ]≥_q[A↔ B ].

Also notice that B_ℓ(v)⊂ B ⊂ B_ℓ+r(v), π^-1(A)⊂ B_ℓ+K(x)⊂ B_L(x) and π^-1(B)⊂ B_ℓ+r+K(y)⊂ B_L(y). These inclusions combined with the previous inequality give

    _p[B_L(ℓ)(x)↔ B_L(ℓ)(y) ]≥_q[B_ℓ(π(x))↔ B_ℓ(π(y)) ]

for any two vertices x,y∈ V(𝒢) such that d(x,y)>L(ℓ). Notice that this inequality is still true when d(x,y)≤ L(ℓ), as the left hand side is then equal to 1.
Taking the infimum over x,y ∈ V(𝒢) and then sending ℓ to infinity gives

    lim_L→∞inf_x,y∈ V(𝒢)_p[B_L(x)↔ B_L(y) ]≥lim_ℓ→∞inf_u,v∈ V(ℋ)_q[B_ℓ(u)↔ B_ℓ(v) ]=
    1

where the last equality follows, as in Section <ref>, from the fact that q>p_u(ℋ). It follows from the above equation (see <cit.>) that p_u(𝒢)≤ p< p_u(ℋ).



A recent paper of Tang <cit.> proves that on any quasi-transitive graph, there is a unique infinite cluster at parameter p if and only if inf_u,v∈ V_p[u ↔ v]>0. By using this theorem instead of <cit.>, one can simplify the above proof: one does not need to connect large balls anymore, but only vertices.





 §.§ Proof of Proposition <ref>



The proof follows the same lines as that of Proposition <ref>, so we will only highlight the necessary adaptations here. 

For any two finite subsets A,B⊂ V(ℋ), we consider the following finite dimensional approximation of the event A B: for each L, define ℰ^A,B_L:={(ω,α): 𝒞_A(ω_L,α_L)∩ B≠∅}, where ω_L (resp. α_L) is the configuration equal to ω (resp. α) in B_L(o) and equal to 0 elsewhere. 
By the argument presented at the beginning of Section <ref>, one can easily reduce the proof to the following deterministic lemma.


	
	There is a constant R such that the following holds. For any two non-empty finite subsets A, B⊂ V(ℋ) such that B is r-nice and d(A,B)>3r, there is some L_0=L_0(A,B) such that for all L≥ L_0, if an edge e is p-pivotal for ℰ^A,B_L in a configuration (ω,α), then there exist a configuration (ω',α') differing from (ω,α) only inside B_R(e) and a vertex z in B_R(e) such that z is s-pivotal for ℰ^A,B_L in (ω',α').



	As in Lemma <ref>, it is enough to take R=3r+1. Given A and B as above, take L_0 such that A∪ B ⊂ B_L(o) and d(A∪ B,S_L(o))>3r for all L≥ L_0.
	Let (ω,α) and e be as in Lemma <ref>. As before, we can assume that e is p-pivotal for ℰ^A,B_L in (ω,α'), where α':=α∖ B_R(e). Again, we have two cases.
	 
	 

  
Case a. The edge e={x,y} is far from A, namely d(e,A) > r.
	 
	 

	 
	 Notice that, since e is p-pivotal, we can assume without loss of generality that x∉ B. In this case, one can always find a vertex z such that B_r(z)⊂ B_L∖(A∪ B) and x∈ B_r(z). Indeed, if d(x,B)>r and d(x,S_L(o))≥ r, it suffices to take z=x; if d(x,B)≤ r, we use the fact that B is r-nice to find z such that B_r(z)∩ B=∅ and x∈ B_r(z), which directly implies B_r(z)⊂ B_L(o)∖ A since d(B,S_L(o))>3r and d(A,B)>3r; and if d(x,S_L(o))< r, we can take an appropriate z in the geodesic path from o to x in such a way that x∈ B_r(z)⊂ B_L, which directly implies B_r(z)∩ (A∪ B)=∅ since d(A∪ B,S_L(o))> 3r. As in the proof of Lemma <ref>, we can find u∈ S_r+1(z) such that u∈𝒞_o(ω̃,α'), where ω̃:=ω∖ E(B_r+1(z)). Pick v∈ B_r(z) some neighbour of u and define ω':=[ω∖ E(B_r+1(z))] ∪ [E(B_r(z))∪{{u,v}}].
	 
	 

  
Case b. The edge e={x,y} is close to A, namely d(e,A)≤ r.
	 
	 

	 
	 Without loss of generality, assume  d(x,A)≤ r. Then simply take z=x and ω' given by closing in ω all the edges inside B_r+1(x) and then opening all the edges inside B_r(x), i.e. ω':=[ω∖ E(B_r+1(x))]∪ E(B_r(x)).
	 
	 

	
	 One can check in the same way as in the proof of Lemma <ref> that in both cases above, z is s-pivotal for the event ℰ^A,B_L in the configuration (ω',α').






  
Acknowledgements
We are indebted to Hugo Duminil-Copin, Vincent Tassion, and Augusto Teixeira for many valuable discussions. We also wish to thank Itai Benjamini for suggesting us to investigate the strict monotonicity question for p_u. 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.






Men87
	
	[AG91]aizenmangrimmett
	Michael Aizenman and Geoffrey Grimmett.
	Strict monotonicity for critical points in percolation and
	ferromagnetic models.
	Journal of Statistical Physics, 63(5-6):817–835, 1991.
	
	[BBR]essrev
	Paul Balister, Béla Bollobás, and Oliver Riordan.
	Essential enhancements revisited.
	ArXiv 1402.0834.
	
	[BK89]burtonkeane
	Robert Burton and Michael Keane.
	Density and uniqueness in percolation.
	Comm. Math. Phys., 121(3):501–505, 1989.
	
	[BS96]bspercobeyond
	Itai Benjamini and Oded Schramm.
	Percolation beyond Z^d, many questions and a few answers.
	Electron. Comm. Probab., 1:71–82, 1996.
	
	[GL14]glstrict
	Geoffrey Grimmett and Zhongyang Li.
	Strict inequalities for connective constants of transitive graphs.
	SIAM Journal on Discrete Mathematics, 28(3):1306–1333, 2014.
	
	[GN90]GN90
	Geoffrey Grimmett and Charles Newman.
	Percolation in ∞ + 1 dimensions.
	In Disorder in Physical Systems, pages 167–190. Oxford
	University Press, 1990.
	
	[Gri99]grimmettbook
	Geoffrey Grimmett.
	Percolation, volume 321 of Grundlehren der Mathematischen
		Wissenschaften.
	Springer-Verlag, Berlin, second edition, 1999.
	
	[Hal54]hall1954
	Philip Hall.
	Finiteness conditions for soluble groups.
	Proceedings of the London Mathematical Society, 3(1):419–436,
	1954.
	
	[HB57]broadbenthammersley
	John Hammersley and Simon Broadbent.
	Percolation processes: I. Crystals and mazes.
	In Proc. Cambridge Philos. Soc, volume 53, pages 629–641,
	1957.
	
	[Hut]hutchcroftlocality
	Tom Hutchcroft.
	Locality of the critical probability for transitive graphs of
	exponential growth.
	ArXiv 1808.08940.
	
	[Kes90]Kes90
	Harry Kesten.
	Asymptotics in high dimensions for percolation.
	In Disorder in Physical Systems, pages 219–240. Oxford
	University Press, 1990.
	
	[Koz]kozmapersonal
	Gady Kozma.
	Personal communication.
	
	[LP16]lyonsperesbook
	Russell Lyons and Yuval Peres.
	Probability on trees and networks, volume 42.
	Cambridge University Press, 2016.
	
	[Mar17]cantor
	Sébastien Martineau.
	The set of connective constants of Cayley graphs contains a
	Cantor space.
	Electronic Communications in Probability, 22, 2017.
	
	[Men87]menshikovstrict
	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.
	
	[Sch99]Sch99
	Roberto Schonmann.
	Stability of infinite clusters in supercritical percolation.
	Probability Theory and Related Fields, 113(2):287–300, Feb
	1999.
	
	[Tan]tang
	Pengfei Tang.
	Heavy Bernoulli-percolation clusters are indistinguishable.
	ArXiv 1809.01284.
	



