Invariant Percolation and Harmonic Dirichlet Functions

Damien Gaboriau^{∗}

Abstract

The main goal of this paper is to answer question 1.10 and settle conjecture 1.11 of Benjamini-Lyons-Schramm [BLS99] relating harmonic Dirichlet functions on a graph to those on the infinite clusters in the uniqueness phase of Bernoulli percolation. We extend the result to more general invariant percolations, including the Random-Cluster model. We prove the existence of the nonuniqueness phase for the Bernoulli percolation (and make some progress for Random-Cluster model) on unimodular transitive locally finite graphs admitting nonconstant harmonic Dirichlet functions. This is done by using the device of ℓ^{2} Betti numbers.

Mathematical Subject Classification: 60K35, 82B43, 31C05, 37A20, 05C25, 05C80, 37R30 Key words and phrases: percolation; transitive graph; harmonic Dirichlet function; measured equivalence relation; L^{2} Betti number.

0 Introduction

Traditionally, percolation on graphs lives on ℤ^{d} or lattices in ℝ^{d}. Following earlier work of G. Grimmett and C. Newman [GN90] on the direct product of a regular tree and ℤ, a general study of invariant percolation was initiated in I. Benjamini and O. Schramm [BS96] and further developed by several authors.

Let G = (V, E) be a (non-oriented) countable infinite locally finite graph. A bond percolation on G is simply a probability measure P on Ω = {0, 1}^{E}, the subsets of its edge set E. It is an invariant percolation when this measure is invariant under a certain group H of automorphisms of G.

An element ω in Ω defines the graph whose vertices are V and whose edges are the retained (or open) edges, i.e. those e ∈ E with value ω(e) = 1. It is the subgraph of G where edges with value 0 are removed (or closed). One is interested in the shape of the “typical” random subgraph ω^{1} and of its clusters, i.e. its connected components.

One of the most striking instances is Bernoulli bond percolation, and particularly on a Cayley graph^{2} of a finitely generated group: each edge of G is removed with probability 1 − p independently (where p ∈ [0, 1] is a parameter). The resulting probability measure μ_{p} on Ω is the product Bernoulli measure (1 − p, p) on {0, 1}. It is invariant under every automorphism group of G. How does the behavior evolve as p varies? For small p, the clusters are a.s. all finite, while for p = 1 the measure concentrates on the infinite subgraph G itself. Depending on the value of the parameter, μ_{p}-almost every subgraph ω ∈ Ω has no infinite cluster, infinitely many infinite clusters (nonuniqueness phase) or only one infinite cluster (uniqueness phase). According to a somewhat surprising result of O. Häggström and Y. Peres [HP99], the phases are organized around two phase transitions for two critical values of p depending on the graph 0 < p_{c}(G) ≤ p_{u}(G) ≤ 1, as summarized^{3} in the following picture:

∗C.N.R.S.

1In more probabilistic terms, ω is a random variable with values in Ω and distribution P.

2A Cayley graph will always be assumed to be for a finitely generated group and with respect to a finite generating system.

all finite  infinitely many infinite clusters  a unique infinite cluster
|  |  |  |
0  p_{c}(G)  p_{u}(G)  1

The picture at the critical values themselves is far from complete (to which interval belong the transitions? which inequalities are strict: p_{c} ≠ p_{u} ≠ 1 ?) and seems to depend heavily (for Cayley graphs) on the algebraic properties of the group. However, a certain amount of results has been obtained. For instance, in the Cayley graphs setting^{4}:

• p_{u} = p_{c} for amenable groups (Burton-Keane [BK89])

• p_{c} < 1 for groups of polynomial or exponential growth, except for groups with two ends [Lyo95, LP05]

• For any nonamenable group, there is almost surely no infinite cluster at p = p_{c} [BLPS99a, Th. 1.3]^{5} • p_{u} < 1 for finitely presented groups with one end (Babson-Benjamini [BB99]) and for (restricted) wreath products^{6} K ≀ Λ := Λ ⋉ ⊕_{W} K with finite non-trivial K (Lyons-Schramm [LS99])

• p_{u} = 1 for groups with infinitely many ends, thus the percolation at p = p_{u} belongs to the uniqueness phase^{7}

• The percolation at the threshold p = p_{u} belongs to the nonuniqueness phase, and thus p_{u} < 1, for infinite groups with Kazhdan’s property (T) (Lyons-Schramm [LS99])

• in the nonuniqueness phase, infinite clusters have uncountably many ends almost surely [HP99]^{8}

For (much !) more information and references, the reader is referred to the excellent survey of R. Lyons [Lyo00], book (in preparation) by R. Lyons and Y. Peres [LP05] and papers [BLPS99a, BLPS99b, BLS99, BS96, HP99, LS99].

0.1 On Harmonic Dirichlet functions

The space HD(G) of Harmonic Dirichlet functions on a locally finite graph G = (V, E) is the space of functions on the vertex set V whose value at each vertex equals the average of the values at its neighbors

( ∑_{v′∼v}1) f(v) = ∑_{v′∼v}f(v′)

3For Cayley graphs, say. More generally this picture appears for Bernoulli percolation of unimodular quasi-transitive (see below for the definitions) graphs [HP99]. R. Schonmann has even removed the unimodularity assumption.

4i.e. for any Cayley graph G of a given finitely generated group Γ

5This is true more generally for nonamenable unimodular transitive graphs [BLPS99b].

6The finitely generated group Λ acts transitively on the discrete set W of indices and thus on the W -indexed direct product ⊕_{W} K.

7This is a very general result, see [LP05].

8This is true more generally for quasi-transitive unimodular graphs [HP99]. This has also been proved in the nonunimodular case by O. Häggström, Y. Peres, R. Schonmann [HPS99].

and whose coboundary is ℓ^{2}-bounded

∥df∥^{2} = ∑_{v∼v′} |f(v) − f(v′)|^{2} < ∞.

The constant functions on the vertex set V always belong to HD(G). Denote by O_{HD} the class of connected graphs for which these are the only harmonic Dirichlet functions. Belonging or not to O_{HD} plays a role in electrical networks theory: when assigning resistance 1 ohm to each edge, the coboundary of a harmonic Dirichlet function gives a finite energy current satisfying both Kirchhoff’s laws.

As an example, a Cayley graph of a group Γ is in O_{HD} if and only if the first ℓ^{2} Betti number β_{1}(Γ) of the group vanishes (see Theorem 6.1). Thus, the Cayley graphs of the following groups (when finitely generated) all belong to O_{HD}: abelian groups, amenable groups, groups with Kazhdan property (T), lattices in SO(n, 1) (n ≥ 3) or in SU(n, 1). On the other hand, the class of groups whose Cayley graphs don’t belong to O_{HD} contains the non-cyclic free groups, the fundamental groups of surfaces of genus g ≥ 2, the free products of infinite groups, and the amalgamated free products over an amenable group of groups in that class. Look at the very informative paper by Bekka-Valette [BV97] and F. Martin’s thesis [Mar03] for further interpretations in cohomological terms.

P. Soardi [Soa93] has proved that belonging to O_{HD} is invariant under a certain kind of “perturbation” of G, namely quasi-isometry or rough isometry. Bernoulli bond percolation clusters may also be considered as perturbations of G. I. Benjamini, R. Lyons and O. Schramm addressed the analogous invariance problem^{9} in [BLS99], by taking a stand only in one case:

Question [BLS99, Quest. 1.10] Let G be a Cayley graph, and suppose that G ∈ O_{HD}. Let ω be Bernoulli percolation on G in the uniqueness phase. Does it follow that a.s. the infinite cluster of ω is in O_{HD}?

Conjecture [BLS99, Conj. 1.11] Let G be a Cayley graph, G ∉ O_{HD}. Then a.s. all infinite clusters of p-Bernoulli percolation are not in O_{HD}.

They proved this for p sufficiently large:

Theorem[BLS99, Th. 1.12] If a Cayley graph G is not in O_{HD}, then there exists a p_{0} < 1, such that every infinite cluster of μ_{p}-a.e. subgraph is not in O_{HD}, for every p ≥ p_{0}.

On the other hand,

Theorem[BLS99, Th. 1.9] If G is a Cayley graph of an amenable^{10} group, then every cluster of μ_{p}-a.e. subgraph is in O_{HD}.

The main goal of this paper is to complete these results and prove the following:

Theorem 0.1 (Theorem 1.5) Let G be a Cayley graph of a finitely generated group. Consider Bernoulli percolation in the uniqueness phase. Then μ_{p} a.s. the infinite cluster ω_{∞} of ω satisfies: ω_{∞} has no harmonic Dirichlet functions besides the constants if and only if G has no harmonic Dirichlet functions besides the constants: μ_{p} a.s.

ω_{∞} ∈ O_{HD} ⟺ G ∈ O_{HD}

9Observe that for p_{u} < p < 1, the infinite clusters are μ_{p} a.s. not quasi-isometric to G. They contain for instance arbitrarily long arcs without branch points (by deletion tolerance !).

10thus G is in O_{HD}

This answers question 1.10 and settles conjecture 1.11 of [BLS99]. Together with their Corollary 4.7 about the nonuniqueness phase, this theorem allows to complete the picture for Cayley graphs:

Corollary 0.2 Let G a Cayley graph of a finitely generated group.

• If G is not in O_{HD} (i.e. β_{1}(Γ) ≠ 0), then a.s.^{11} the infinite clusters of Bernoulli bond percolation (for both nonuniqueness and uniqueness phases) are not in O_{HD}.

• If G is in O_{HD} (i.e. β_{1}(Γ) = 0), then a.s.^{11} the infinite clusters of Bernoulli bond percolation are

– not in O_{HD} in the nonuniqueness phase

– in O_{HD} in the uniqueness phase.

Since percolation at p_{c} belongs to the finite phase for nonamenable Cayley graphs, it turns out that every p_{0} > p_{c} suits in Th. 1.12 of [BLS99] recalled above, while p_{0} = p_{c} doesn’t.

In the course of the proof, a crucial use is made of the notion of (first) L^{2} Betti numbers for measured equivalence relations, introduced in [Gab02]. We consider two standard equivalence relations with countable classes associated with our situation: the full equivalence relation R^{fu} and the cluster equivalence relation R^{cl}. They are defined concretely or also more geometrically (see Section 1.1 and 1.2) in terms of two laminated spaces L^{fu} and L^{cl}, constructed from Ω × G after taking the quotient under the diagonal Γ-action and removing certain edges. Their laminated structure comes from the fact that these spaces are equipped with a measurable partition into leaves, corresponding to the decomposition of Ω × G into the graphs {ω} × G ≃ G.

One shows (Section 7) that the first L^{2} Betti number of such an equivalence relation, generated by such a 1-dimensional lamination (in fact generated by a graphing in the sense of [Lev95, Gab00] or Section 8 or example 7.1 below), vanishes if and only if the leaf of almost every point in the transversal is a graph without harmonic Dirichlet functions, besides the constants:

Theorem 0.3 (Corollary 7.6) Let R be a measure-preserving equivalence relation on the standard Borel probability measure space (X, μ). Let Φ be a graphing generating R. If the graph Φ[x] associated with x ∈ X has μ a.s. bounded degree^{12}, then β_{1}(R, μ) = 0 if and only if μ a.s. HD(Φ[x]) = ℂ.

Now the triviality of the first L^{2} Betti number of an equivalence relation is invariant when taking a restriction to a Borel subset that meets almost every equivalence class [Gab02, Cor. 5.5]. Denote by U the subset of ω’s with a unique infinite cluster and such that the base point ρ belongs to that cluster. In the uniqueness phase, U meets almost every R^{fu}-equivalence class and the restrictions of R^{fu} and R^{cl} to U define the same equivalence relation. And Theorem 0.1 follows.

Invariant bond percolation on a locally finite graph G, for a group H of automorphisms of G, is also considered in a more general setting than just Cayley graphs. For the invariance property of the measure to be of any use, the group has to be big enough. The standard hypothesis is that H is transitive or at least quasi-transitive (there is only one, resp. only finitely many orbits of vertices).

When closed in all automorphisms of G, the group H is locally compact and equipped with a unique (up to multiplication by a constant) left invariant Haar measure. If that measure is also right invariant, then H is called unimodular. A graph with a unimodular quasi-transitive group H, is called itself unimodular. The unimodularity assumption is a quite common hypothesis in invariant percolation theory, where it is used in order to apply a simple form of the mass-transport principle (see for example [BLPS99a, sect. 3] and Section 2.3).

11every infinite cluster for μ_{p}-almost every subgraph ω ∈ {0, 1}^{E}

12a bound on the number of neighbors of each vertex

The same unimodularity assumption appears here, for a related reason: in order to ensure that a certain equivalence relation preserves the measure (see Section 2.3). We obtain the following generalization^{13} of Theorem 0.1:

Theorem 0.4 Let G be a locally finite graph, H a closed transitive unimodular group of automorphisms of G and P any H-invariant percolation. On the Borel subset of subgraphs with finitely many infinite clusters, P-almost surely the infinite clusters belong (resp. do not belong) to O_{HD} if and only if G belongs (resp. doesn’t belong) to O_{HD}.

The clusters of this theorem satisfy the more general property (to be introduced in Section 3.2) of being (virtually) selectable and the proof is given in that context (Section 3, Theorem 3.9).

The most studied invariant percolation, beyond Bernoulli, is probably the Random-Cluster Model. It was introduced by C. Fortuin and P. Kasteleyn [FK72] in relation with Ising and Potts models as explained for instance in [HJL02a, Prop. 2.3 and 2.4].

It is a (non-independent) percolation process, governed by two parameters^{14} p ∈ [0, 1] and q ∈ [1, ∞]. It is defined through a limit procedure by considering an exhaustion G_{m} of G by finite subgraphs, and on the set of subgraphs of G_{m}, this measure only differs from the Bernoulli(p) product measure by the introduction of a weight (q to the power the number of clusters). However, the count of this number of clusters is influenced by the boundary conditions. This leads to two particular incarnations of the Random-Cluster model: WRC_{p,q} and FRC_{p,q} according to the Wired (the boundary points are all connected from the exterior) or Free (there is no outside connection between the boundary points) boundary conditions . These invariant bond percolations both exhibit phase transitions, for each q, similar to that of Bernoulli percolation, leading to critical values p_{c}(q) and p_{u}(q) (denoted more precisely by p_{c}^{W}(q), p_{u}^{W}(q) and p_{c}^{F}(q), p_{u}^{F}(q) in case the boundary conditions have to be emphasized). They “degenerate” to Bernoulli percolation when q = 1.

The reader is invited to consult the papers [HJL02a, HJL02b] of O. Häggström, J. Jonasson and R. Lyons, for most of the results relevant for this paper and for details and further references.

The above Theorem 0.4 obviously specializes to:

Corollary 0.5 Let G be a locally finite graph admitting a transitive unimodular group of automorphisms. Consider the Random-Cluster model RC_{p,q} = WRC_{p,q} or FRC_{p,q} in the uniqueness phase. Then RC_{p,q} a.s. the infinite cluster admits non- (resp. only) constant harmonic Dirichlet functions if and only if G admits non- (resp. only) constant harmonic Dirichlet functions.

13Compare with [BLS99] where Theorem 5.7 extends Theorem 1.12 (recalled above) to the more general setting of a unimodular transitive graph, and for much more general percolations than Bernoulli percolation.

14The temperature, T in Ising or Potts models is linked with the parameter p of the Random-Cluster model by p = 1 − e^{− \frac{2}{T}} . The parameter q, taken to be q = 2 in the Ising Model, resp. q ∈ ℕ in the Potts Model, may assume any value in [1, ∞) for the Random-Cluster model. For example, the (free) Gibbs distribution FPt_{\frac{1}{T} ,q} of the Potts model on {0, 1}^{V} is obtained from FRC_{p,q} by choosing a subgraph ω ∈ {0, 1}^{E} according to FRC_{p,q} and then choosing a color in {1, 2, ⋯, q} uniformly and independently on the vertices of each cluster.

0.2 On the nonuniqueness Phase

One of the most famous conjectures in the subject is probably Conjecture 6 of Benjamini and Schramm [BS96]:

The nonuniqueness phase always exists^{15} for Cayley graphs G of nonamenable groups.

and more generally

If the quasi-transitive graph G has positive Cheeger constant, then p_{c}(G) < p_{u}(G).

I. Pak and T. Smirnova-Nagnibeda [PSN00] proved that each finitely generated nonamenable group admits a Cayley graph for which p_{c} < p_{u}. On the other hand, the groups with cost strictly bigger than 1 (see [Gab00] or Section 8 below, item “cost”) are the only ones for which it is known that p_{c} ≠ p_{u} for every Cayley graph (R. Lyons [Lyo00]). This class of Cayley graphs contains all those outside O_{HD} (see Th. 6.1 and [Gab02, Cor. 3.23]), but it is unknown whether the reverse inclusion holds.

We are able, using our ℓ^{2} methods, to extend Lyons’ result to the unimodular setting and to make some progress for Random-Cluster model. Our treatment doesn’t make use of the continuity of the probability that ρ belongs to an infinite cluster, but only of the expected degree. We show:

Theorem 0.6 (Cor. 4.5) Let G be a unimodular transitive locally finite graph. If G doesn’t belong to O_{HD}, then the nonuniqueness phase interval of Bernoulli percolation has non-empty interior:

p_{c}(G) < p_{u}(G)

In fact, to each unimodular transitive locally finite graph G, we associate (see def. 2.10) a numerical invariant β_{1}(G), which can be interpreted as the first ℓ^{2} Betti number of any closed transitive group of automorphisms of G. It vanishes if and only if G belongs to O_{HD}. In case G is a Cayley graph of a group Γ, then β_{1}(G) = β_{1}(Γ). A transitive tree of degree d has β_{1}(G) = \frac{d}{2} − 1.

For Bernoulli percolation, we get the more precise estimate, where deg(G) denotes the degree of a (any) vertex of G:

0 < β_{1}(G) ≤ \frac{1}{2}deg(G)(p_{u}(G) − p_{c}(G)).

Observe that deg(G) p is the expected degree μ_{p}[deg(ρ)] of a base point ρ with respect to the Bernoulli measure of parameter p. These inequalities appear as Corollary 4.5 of a quite general result (Th. 4.2) which applies to more general percolations, like the free or the wired Random-Cluster model, RC_{p,q} = WRC_{p,q} or FRC_{p,q}:

Theorem 0.7 (Cor. 4.7) Let G be a unimodular transitive locally finite graph, not in O_{HD}. Fix the parameter q ∈ [1, ∞). The gap between the left limit (when p ↗ p_{c}(q)) and the right limit (when p ↘ p_{u}(q)) of the expected degree of a base point ρ with respect to the measure RC_{p,q} satisfies:

0 < β_{1}(G) ≤ \frac{1}{2}(RC_{p_{u}+,q}[deg(ρ)] − RC_{p_{c}−,q}[deg(ρ)]).

15i.e. p_{c}(G) < p_{u}(G) for Bernoulli percolation

Indeed the function p ↦ FRC_{p,q}[deg(ρ)] := ∫_{{0,1}^{E}} deg(ρ)(ω)dFRC_{p,q}(ω) is left continuous while p ↦ WRC_{p,q}[deg(ρ)] is right continuous in p, but the possible remaining discontinuity doesn’t allow to conclude in general that p_{c}(q) < p_{u}(q). Of course, RC_{p_{u}+,q}[deg(ρ)] denotes lim_{p↘p_{u}(q)} RC_{p,q}[deg(ρ)] and RC_{p_{c}−,q}[deg(ρ)] := lim_{p↗p_{c}(q)} RC_{p,q}[deg(ρ)].

There is no fundamental qualitative difference when shifting from transitive to quasi-transitive graphs. The slight modifications are presented in section 5.

0.3 About Higher Dimensional Invariants and Treeablility

Higher dimensional ℓ^{2} Betti numbers are also relevant in percolation theory. Y. Peres and R. Pemantle [PP00] introduced the percolation theoretic notion of countable treeable groups. They are groups Γ for which the space of trees with vertex set Γ admits a Γ-invariant probability measure. They proved that nonamenable direct products are not treeable. It is not hard to show that being treeable is equivalent to being not anti-treeable in the sense of [Gab00, Déf. VI.1] or to having ergodic dimension 1 in the sense of [Gab02, Déf. 6.4].

Similarly, R. Lyons introduced the notion of almost treeable groups: They are groups for which the space of forests with vertex set Γ admits a sequence (P_{n})_{n∈ℕ} of Γ-invariant probability measures with the property that for each pair of vertices, the probability that they belong to the same connected component of the forest tends to 1 as n tends to infinity: ∀γ_{1}, γ_{2} ∈ Γ, lim_{n→∞} P_{n}(γ_{1} ↔ γ_{2}) = 1. Clearly treeable implies almost treeable.

It is not hard to show that Γ is almost treeable if and only if it has approximate ergodic dimension 1; where the approximate ergodic dimension of Γ is the minimum of the approximate dimensions of the equivalence relations produced by a free p.m.p. action of Γ on a standard Borel space (see [Gab02, Déf. 5.15]).

The next theorem follows from [Gab02, Cor. 5.13, Prop. 5.16, Prop. 6.10] and imposes serious restrictions for a group to be treeable or almost treeable. In particular, lattices in SO(n, 1) are treeable if and only if n ≤ 2. Also direct products Γ_{1} × Γ_{2} are not almost treeable as soon as Γ_{1} and Γ_{2} contain a copy of the free group F_{2}. This answer questions of R. Lyons and Y. Peres (personal communication).

Theorem 0.8 If Γ is treeable in the sense of [PP00], then β_{1}(Γ) = 0 if and only if Γ is amenable. If Γ is almost treeable, then its higher ℓ^{2} Betti numbers all vanish: β_{n}(Λ) = 0 for every n ≥ 2.

Warning for the reader Theorem 0.1 is clearly a specialization of Theorem 0.4. However, for the convenience of the reader mainly interested in Cayley graphs and also to serve as a warm-up for the more technical general case, we present first a separate proof of Theorem 0.1 (Section 1, Subsection 1.3.b and Th. 1.5), while Theorem 0.4 is proved in Section 3.3. A necessary consequence is a certain number of repetitions. Section 4 is devoted to the proof of Theorems 0.7 and 0.6. Some notions related to equivalence relations are recalled in Section 8. Theorem 0.3 is used at several places. It is proved as Corollary 7.6 (see also Remark 7.7). But the sections 6 and 7 are quite technical, and I put it back until the end of the paper. It may be a good advice to skip them and to keep Theorem 7.5 and Corollary 7.6 as “black boxes” for a first reading.

Acknowledgment I wish to thank Thierry Barbot, Étienne Ghys, Alekos Kechris, Yuval Peres and Bruno Sévennec for many valuable discussions, and especially Vincent Beffara who helped me to understand several references. I am particularly grateful to Russell Lyons who explained to me many entertaining and impressive results in graph percolation theory, as well as some connections with my previous work on cost of equivalence relations, and who suggested that the notion of ℓ^{2} Betti numbers of equivalence relations could be relevant for question 1.10 and conjecture 1.11 of [BLS99]. Thanks also for his careful proofreading.

My acknowledgments are due to the anonymous referee who recommended the addition of a section about the quasi-transitive case (Section 5 of the current version) and for his accurate and pertinent comments.

To Carole, Valentine, Alice, Lola and Célestin.

Contents

0 Introduction 1 0.1 On Harmonic Dirichlet functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2 On the nonuniqueness Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 0.3 About Higher Dimensional Invariants and Treeablility . . . . . . . . . . . . . . . . . . 7

1 Percolation on Cayley Graphs 9 1.1 The Full Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 The Cluster Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.a Trivial Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.b Bernoulli Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.c Actions Made Free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.d Standard Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.e Site Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.f Graphings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Harmonic Dirichlet Functions and Clusters for Cayley Graphs . . . . . . . . . . . . . . 13

2 Percolation on Transitive Graphs 14 2.1 The Full Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 The Cluster Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Measure Invariance, Unimodularity and the Mass-Transport Principle . . . . . . . . . 16 2.4 Some computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Harmonic Dirichlet Functions and Clusters for Transitive Graphs 20 3.1 The action made free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Selectability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Selected Clusters and Harmonic Dirichlet Functions . . . . . . . . . . . . . . . . . . . 23

4 Nonuniqueness Phase and Harmonic Dirichlet Functions 23 4.1 Application to Bernoulli Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Application to Random-Cluster Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5 Quasi-transitive graphs 27 6 Harmonic Dirichlet Functions and ℓ^{2} Cohomology 30

6.1 Harmonic Dirichlet Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6.2 … and ℓ^{2} cohomology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7 Fields of Graphs, Harmonic Dirichlet Functions and L^{2} Betti Numbers for Equivalence Relations 33

8 Some Background about Measured Equivalence Relations 35

1 Percolation on Cayley Graphs

Let G = (V, E) be a Cayley graph of a finitely generated group Γ. Let ρ be a base vertex, for example the vertex representing the identity element of Γ. The group Γ acts freely on the set E of edges and freely transitively on the set V of vertices.

The space Ω := {0, 1}^{E} is the space of colorings (assignment of a number) of the edges of G with two colors (0 and 1) of G. A point ω ∈ Ω is also the characteristic function of a subset of E. When viewed as a subgraph of G it is denoted by ω(G). It then has the same set of vertices V as G and for edges the set of retained or open edges: those edges e ∈ E with color ω(e) = 1. It has the same base vertex ρ as G. The cluster ω(v) of a vertex v is its connected component in ω(G). The action of Γ on E induces an action^{16} on the space Ω of colorings.

Let (X, μ) be a standard Borel probability space together with

• a probability measure-preserving (p.m.p.) action of Γ, which is (essentially) free^{17}, and

• a Γ-equivariant Borel map π : X → {0, 1}^{E}.

The push-forward measure π_{∗}μ is a Γ-invariant bond percolation on G.

1.1 The Full Equivalence Relation

Consider now the space X × G with the diagonal action of Γ. It is a “laminated space”, with leaves {x} × G.

Dividing out by the diagonal action of Γ, one gets the laminated space L^{fu} = Γ\(X × G): the full lamination. It is a (huge, highly disconnected) graph with vertex set Γ\(X × V) and edge set Γ\(X × E). A leaf is a connected component of this graph.

– Because of the freeness of the Γ-action on V, the image X^{•} in L^{fu} of the space X × {ρ} is an embedding, leading to a natural identification of X with X^{•}.

– Because of the transitivity on V of the Γ-action, X^{•} equals Γ\(X × V).

\begin{matrix}X & ⟶^{∼} & X^{•} = Γ\(X × V) \\ x & ⟼ & (x, ρ) ∼ (γx, γρ) \end{matrix}

Let’s denote by μ^{•} the push-forward of the measure μ to X^{•}.

With the (any) choice of ρ, the Γ-set V identifies with Γ equipped with the action by left multiplication and the left action of Γ on itself, by multiplication by the inverse on the right, induces on X^{•} = Γ\(X × V) ≃ Γ\(X × Γ) a μ^{•}-preserving Γ-action, isomorphic to the original one on X. With ρ ↔ 1 and γρ ↔ γ one gets γ_{1}(x, 1) := (x, 1γ_{1}^{−1}) = (x, γ_{1}^{−1}1) ∼ (γ_{1}(x), 1).

16For γ ∈ Γ: ω′ = γ · ω if and only if ω′(e) = ω(γ^{−1}e) for every edge e ∈ E.

17the Borel set of points x ∈ X with non-trivial stabilizer have μ-measure 0

– Because of the freeness of the Γ-action on X, the leaf of μ^{•}-almost every x^{•} ∈ X^{•} is isomorphic to G.

Definition 1.1 Define the full equivalence relation R^{fu} on X^{•} by x^{•}R^{fu}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{fu}-leaf.

It is isomorphic with that given by the Γ-action on X and preserves the measure.

R^{fu}: Two points x, y are R^{fu}-equivalent if and only if there is γ ∈ Γ such that γx = y.

Example 1.2 Let G = L be the standard Cayley graph of ℤ: the simplicial line. Take ρ as the point 0 of the line. The product space X × L is a kind of cylinder laminated by lines. A fundamental domain for the diagonal ℤ-action on X ×L is given by X ×[0, 1). Denote by t the automorphism of X given by the generator 1 of ℤ. The quotient space ℤ\(X × L) identifies with the usual suspension or mapping torus construction (ω, 0) ∼ (tω, 1)\(X × [0, 1]) obtained from X × [0, 1] (laminated by {ω} × [0, 1]) by gluing together the top and bottom levels X × {0} and X × {1} after twisting by t. The gluing scar is the transversal X^{•}.

1.2 The Cluster Equivalence Relation

Now, thanks to the map π : X → {0, 1}^{E}, the field of graphs x ↦ {x} × G becomes a Γ-equivariant field of colored graphs x ↦ π(x). Each leaf of L^{fu} becomes a colored graph.

By removing all the 0-colored edges, one defines a subspace L^{cl} of L^{fu}: the cluster lamination. A leaf of L^{cl} is a connected component of 1-colored (or retained) edges.

Definition 1.3 Define the cluster equivalence relation R^{cl} on X^{•} by x^{•}R^{cl}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{cl}-leaf. It is a subrelation of R^{fu}.

For μ-almost every x ∈ X, the leaf of x^{•} is isomorphic to the cluster G_{x} := π(x)(ρ) of the vertex ρ in the subgraph π(x) of G. Thus the R^{cl}-class of x^{•} is infinite if and only if the corresponding cluster π(x)(ρ) is infinite. For each x^{•} ∈ X^{•}, the family of R^{cl}-classes into which its R^{fu}-class decomposes is in natural bijection with the clusters of π(x). The R^{fu}-class of x^{•} contains n infinite R^{cl}-classes iff π(x) has n infinite clusters.

Let e = [ρ, γ^{−1}ρ] be an edge with end point ρ. Once descended in L^{fu}, the edge {x} × e = [(x, ρ), \underbrace{(x, γ^{−1}ρ)}_{∼(γx,ρ)}] is retained in L^{cl} iff π(x)(e) = 1. In this case, the vertices ρ, γ^{−1}ρ are in the same

cluster of π(x), while x, γx are R^{cl}-equivalent. More generally:

R^{cl}: Two points x, y are R^{cl}-equivalent if and only if there is γ ∈ Γ such that γx = y and the vertices ρ, γ^{−1}ρ are in the same cluster of π(x).

It may be relevant to emphasize the role of π and include it in the notation: R_{π}^{cl}.

Example 1.2 (continued) The edges are divided into the positive ones and the negative one according to their position with respect to ρ = 0. The R^{cl}-equivalence class of x ∈ X consists of the iterates t^{k}(x) for k ∈ {−i, −i + 1, ⋯, 0, 1, 2, ⋯, j − 1, j}, where j and i are the number of negative and positive edges colored 1 in π(x), starting from ρ:

π(x) = (\overbrace{⋯, 0, \underbrace{1, 1, 1, ⋯, 1}_{j times}}^{negative edges}, \overbrace{\underbrace{1, 1, 1, ⋯, 1}_{i times}, 0, ⋯}^{positive edges}).

From now on, and until the end of Section 1 we won’t distinguish between (X, μ) and (X^{•}, μ^{•}). The uniqueness set U is the Borel subset of points ω of Ω such that ω has a unique infinite

cluster and such that ρ belongs to it. The uniqueness set U^{π} of π is the Borel subset of points of X such that π(x) belongs to U.

Proposition 1.4 When restricted to the uniqueness set U^{π} the two equivalence relations R^{fu} and R^{cl} do coincide.

The point here is the selectability of the infinite cluster (see Subsection 3.2 devoted to that subject).

Proof: Let x, y be two R^{fu}-equivalent points of U^{π}. Since π(x) contains only one infinite cluster, the R^{fu}-class of x contains only one infinite R^{cl}-class. The R^{cl}-equivalence classes of x and y being both infinite, they coincide. ■

1.3 Examples

1.3.a Trivial Example

Apply the above construction to the particular constant map x ↦^{π_{1}} G, sending every point x to the full graph G (ω ≡ 1, i.e. π(x)(e) = 1 for every x ∈ X and e ∈ E, which is fixed by the whole of Γ). In this case, almost every G_{x} is just G, the uniqueness set U^{π} equals X and R^{cl} = R^{fu}.

1.3.b Bernoulli Percolation

The main example is given by X = {0, 1}^{E} itself, π = id and μ = μ_{p} the Bernoulli measure with survival parameter p, i.e. μ_{p} is the product of the measures giving weights 1 − p, p to 0, 1. The Γ-action is essentially free for p ≠ 0 or 1.

Stricto sensu, this example is just what is needed for the statement of Theorem 0.1. However, it is useful to introduce more objects in order to better distinguish between the various roles played by the space Ω.

The parameter p belongs to the uniqueness phase if and only if μ_{p}-almost every graph in Ω has a unique infinite cluster. In this phase, the uniqueness set U has non-zero μ_{p}-measure and is μ_{p}-a.s. the union of the infinite R^{cl}-classes. The restrictions of R^{fu} and R^{cl} to U coincide (Proposition 1.4). Theorem 0.1 of the introduction will thus be a corollary of Theorem 1.5 for p < 1 and is trivial for p = 1.

1.3.c Actions Made Free

If one is considering a percolation for which the Γ-action is not free, one can switch to a free action by taking any probability measure-preserving free Γ-action on a space (Y, ν), and replacing Ω by its product with Y, equipped with the product measure and the measure-preserving diagonal action of Γ, together with the natural Γ-equivariant projection π : X = Ω × Y → Ω. General (non-free) percolations are thus treated together in the same framework.

1.3.d Standard Coupling

The standard coupling is a very useful way to put all the Bernoulli measures μ_{p} together and to vary the map π instead of changing the measure on Ω with the parameter p.

Let X = [0, 1]^{E} be the product space with the product measure μ of Lebesgue measures on the intervals [0, 1]. An element of X gives a colored graph: a coloring of the graph G, with [0, 1] as set of colors. For each p ∈ [0, 1], let π_{p} be the Γ-equivariant map sending [0, 1]-colored graphs to {0, 1}-colored ones by retaining only the edges colored in [0, p]:

π_{p} : ( \begin{matrix}[0, 1]^{E} & ⟶ & \{0, 1\}^{E} \\ x & ⟼ & π_{p}(x) : \begin{cases}π_{p}(x)(e) = 1 & if x(e) ∈ [0, p] \\ π_{p}(x)(e) = 0 & if x(e) ∈ (p, 1] \end{cases} \end{matrix} )

Clearly, π_{p} pushes the measure μ to μ_{p}. For each value of p, one gets the cluster equivalence relation R_{p}^{cl}, also defined as follows:

R_{p}^{cl}: Two [0, 1]-colored graphs x, y are R_{p}^{cl}-equivalent if and only if there is γ ∈ Γ such that γx = y and the vertices ρ, γ^{−1}ρ are connected in the colored graph x by a path of edges with colors ≤ p.

This gives an intuitive picture of the clusters evolution as p varies: The family (R_{p}^{cl})_{p∈[0,1]} is strictly increasing. Moreover for every p, R_{p}^{cl} = ∪_{t<p}R_{t}^{cl} and R_{1}^{cl} = R^{fu}. The critical value p_{c} is characterized as the supremum of those p for which the R_{p}^{cl}-classes are finite (μ-a.s.), as well as the infimum of p such that R_{p}^{cl} admits a μ-non-null set of points with infinite classes. Much less obvious is the similar characterization of p_{u}, obtained by O. Häggström and Y. Peres, who showed that after p_{c}, there is no spontaneous generation of infinite clusters; all infinite clusters are born simultaneously: If p_{c} < p ≤ q, then μ-a.s. every infinite R_{q}^{cl}-class contains an infinite R_{p}^{cl}-class [HP99]. This explains that the uniqueness phase is an interval.

p_{c} := inf{p : there is a unique infinite cluster for μ_{p}}
= sup{p : there is not a unique infinite cluster for μ_{p}}

1.3.e Site Percolation

An invariant site percolation on G is a probability measure P on the space {0, 1}^{V} that is invariant under a certain group of automorphisms of G. To a site percolation corresponds a bond percolation by the equivariant map π : {0, 1}^{V} → {0, 1}^{E} sending a coloring of the vertices V to the coloring of the edges E where an edge gets color 1 if and only if both its endpoints are colored 1.

1.3.f Graphings

Let (γ_{1}, γ_{2}, ⋯, γ_{n}) be the generating system defining the Cayley graph G and e_{i} be the edge [ρ, γ_{i}ρ].

If π(x)(e_{i}) = 1, the vertices ρ, γ_{i}ρ are in the same cluster of π(x), and x, γ_{i}^{−1}x are R^{cl}-equivalent. Define the Borel set A_{i} := {x ∈ X : π(x)(e_{i}) = 1} and the partial Borel isomorphism φ_{i} = γ_{i|A_{i}}^{−1}, the restriction of γ_{i}^{−1} to A_{i}. The family Φ = (φ_{1}, φ_{2}, ⋯, φ_{n}) is a graphing (in the sense of [Lev95, Gab00]

– see also Section 8) that generates R^{cl}: the latter is the smallest equivalence relation such that x ∼ φ_{i}(x), for every x ∈ A_{i}. For instance, in the above standard coupling (ex. 1.3.d), the cluster equivalence relation R_{p}^{cl} is generated by the graphing Φ_{p} = (φ_{1}^{p}, φ_{2}^{p}, ⋯, φ_{n}^{p}), where φ_{i}^{p} is the restriction of γ_{i}^{−1} to A_{i}^{p} := {x ∈ [0, 1]^{E} : x(e_{i}) ≤ p}.

Conversely, given a free p.m.p. Γ-action on (X, μ), consider n Borel subsets A_{i}, partial isomorphisms φ_{i} = γ_{i|A_{i}}^{−1}, the graphing Φ = (φ_{1}, φ_{2}, ⋯, φ_{n}) and the generated equivalence relation R_{Φ}. The coloring π(x)(e_{i}) = 1 iff x belongs to A_{i} extends by Γ-equivariance to a map π : X → {0, 1}^{E} whose cluster equivalence relation R^{cl} coincides with R_{Φ}.

1.4 Harmonic Dirichlet Functions and Clusters for Cayley Graphs

We are now able to state the main result of this section. Recall that we have at hand: (1) A locally finite graph G = (V, E) with a free action of a countable group Γ, transitive on V; (2) A standard probability measure space (X, μ) with a free measure-preserving Γ-action, and with a Γ-equivariant map π : X → {0, 1}^{E}; (3) The two associated cluster (R^{cl}) and full (R^{fu}) equivalence relations.

Theorem 1.5 For μ-a.e. x in the uniqueness set U^{π}, the cluster G_{x} of the vertex ρ in the colored graph π(x) belongs to O_{HD} if and only if G belongs to O_{HD}.

For the purpose of proving this result, very little has to be known about the L^{2} Betti numbers of equivalence relations. Just assume the following “black box”, which will be further developed in Section 7. The reader feeling more comfortable with the notion of cost may think at first glance that β_{1}(R) = cost(R) − 1 (see Section 8, item “cost”).

Fact 1. For each measurably defined subrelation R of R^{fu} on a non-null Borel subset Y of X, there is a well-defined notion of first L^{2} Betti number β_{1}(R, μ_{Y}), where μ_{Y} denotes the normalized restricted measure \frac{μ_{|Y}}{μ(Y)} ([Gab02]). In particular, β_{1}(R^{fu}, μ), β_{1}(R_{|Y}^{fu} , μ_{Y}) and β_{1}(R_{|Y}^{cl} , μ_{Y}) are well defined.

Fact 2. If Y meets almost all R^{fu}-classes, then β_{1}(R^{fu}, μ) = μ(Y)β_{1}(R_{|Y}^{fu} , μ_{Y}) [Gab02, Cor. 5.5].

Fact 3. The first L^{2} Betti number β_{1}(R_{|Y}^{cl} , μ_{Y}) of R_{|Y}^{cl} vanishes if and only if for μ-almost every y ∈ Y, the graph G_{y} belongs to O_{HD} (Theorem 0.3).

Remark. However, when Y is R^{cl}-saturated (the R^{cl}-class of every y ∈ Y is entirely contained in Y), these numbers are “easily explicitly defined”: consider the space HD(G_{x}) of harmonic Dirichlet functions on G_{x} := π(x)(ρ). Its image dHD(G_{x}) by the coboundary operator d in the ℓ^{2} cochains C_{(2)}^{1}(G_{x}) is a closed subspace of C_{(2)}^{1}(G) (every edge outside G_{x} is orthogonal to it), isomorphic to HD(G_{x})/ℂ. Denote by p_{x} : C_{(2)}^{1}(G) → dHD(G_{x}) the orthogonal projection and, for each edge e ∈ E, denote by 1_{e} the characteristic function of the edge e. Let e_{1}, e_{2}, ⋯, e_{n} be a set of orbit representatives for the Γ-action on E.

Proposition 1.6 Let Y be a non-null R^{cl}-saturated Borel subset of X. The first L^{2} Betti number of the restricted equivalence relation R_{|Y}^{cl} on (Y, μ_{Y}) equals

β_{1}(R_{|Y}^{cl} , μ_{Y}) = \frac{1}{μ(Y)} ∑_{i=1}^{n} ∫_{Y} ⟨p_{y}(1_{e_{i}})|1_{e_{i}}⟩dμ(y).

To prove this, we essentially use Theorem 7.5 stating that β_{1}(R_{|Y}^{cl} , μ_{Y}) = dim_{R_{|Y}^{cl}} ∫_{Y} d(HD(G_{y})) dμ_{Y} (y) and then the definition of the dimension (see [Gab02, Prop. 3.2 (2)]). See also Proposition 2.7.

Proof: (of Theorem 1.5) If U^{π} is a μ-null set, the theorem is empty. Up to replacing X by the union of the Γ-orbits meeting U^{π}, one may assume that U^{π} meets every R^{fu}-class of X. The following are then equivalent:

1. G is in O_{HD}

2. β_{1}(R^{fu}, μ) = 0

3. β_{1}(R_{|U^{π}}^{fu}, μ_{U^{π}}) = 0

4. β_{1}(R_{|U^{π}}^{cl}, μ_{U^{π}}) = 0

5. for μ-almost every x ∈ U^{π}, the graph G_{x} is in O_{HD}

The equivalence 1 ⟺ 2 follows from fact 3 (i.e. Theorem 0.3) applied to the map π_{1} of the example 1.3.a, since in this case X = Y, R^{cl} = R^{fu} and almost every G_{x} equals G.

The equivalence 2 ⟺ 3 follows from fact 2.

By Proposition 1.4, R_{|U^{π}}^{cl} = R_{|U^{π}}^{fu}. The key point of the proof is that from [Gab02] these numbers depend only on the equivalence relation: one gets 3 ⟺ 4. Again, fact 3 shows the equivalence 4 ⟺ 5, after noticing that μ and the normalized measure μ_{U^{π}} are equivalent on U^{π}.

It remains to move the quantifier (μ-almost every x ∈ U^{π}) outside the equivalence 1 ⟺ 5. Let Y ⊂ U^{π} be the Borel subset of points such that the graph G_{y} is in O_{HD}. If Y is non-null, then the argument applied to Y shows that G belongs to O_{HD} and thus Y = U^{π} a.s. This implies that in case G does not belong to O_{HD}, then for μ-almost every x ∈ U^{π}, the graph G_{x} is not in O_{HD}. ■

Remark 1.7 Observe that the freeness of the Γ-action on X is a hypothesis made to simplify some arguments (γ is the unique element of the group sending x to γx) and to apply more directly results from [Gab02]. However, thanks to the example 1.3.c, the above Theorem 1.5 admits a natural generalization without it.

2 Percolation on Transitive Graphs

Let G = (V, E) be a locally finite transitive^{18} graph. Let Aut(G) be the automorphism group of G with the topology of pointwise convergence. Let H be a closed subgroup of Aut(G). We assume that H acts transitively on the set V of vertices. It is locally compact and the stabilizer of each vertex is compact. Let ρ be a base vertex and denote by K_{ρ} its stabilizer.

The action of H on E induces an action on the space Ω = {0, 1}^{E} of colorings: for each h ∈ H, ω′ = h · ω if and only if ω′(e) = ω(h^{−1}e) for every edge e ∈ E.

Let (X, μ) be a standard Borel probability space together with

• a probability measure-preserving (p.m.p.) action of H, which is essentially free^{19}, and

• an H-equivariant Borel map π : X → {0, 1}^{E}.

The push-forward measure π_{∗}μ is an H-invariant bond percolation on G.

18The quasi-transitive case is very similar and we restrict our attention to the transitive one only to avoid an excess of technicality. The modifications for quasi-transitivity are presented in section 5

19the Borel set of points x ∈ X with non-trivial stabilizer have μ-measure 0

2.1 The Full Equivalence Relation

Consider now the space X × G with the diagonal action of H. It is an H-equivariant field of graphs above X, all isomorphic to G: x ↦ {x} × G. It is also a “laminated space”, with leaves {x} × G.

Dividing out by the diagonal action of H, one gets the laminated space L^{fu} = H\(X × G): the full lamination. It is a (huge, highly disconnected) graph with vertex set H\(X × V) and edge set H\(X × E). A leaf is a connected component of this graph.

Denote by X^{•} the image in L^{fu} of the space X × {ρ}. Because of the transitivity on V of the H-action, X × {ρ} meets every H-orbit of X × V, so that X^{•} equals H\(X × V):

( \begin{matrix}X ≃ X × \{ρ\} & ⟶ & X^{•} = H\(X × V) \\ x & ⟼ & (x, ρ) ∼ (hx, hρ) \end{matrix} )  (1)

In particular, two points of X × {ρ} happen to be identified in X^{•}, i.e. (x, ρ) ∼ (hx, ρ), if and only if h belongs to K_{ρ}. Thanks to the compactness of the stabilizer K_{ρ} of ρ, the space X^{•} gets naturally the structure of a standard Borel space (see Proposition 2.4, Section 2.3).

( \begin{matrix}X^{•} = H\(X × V) & ≃ & K_{ρ}\X \\ (hx, hγρ) & ↦ & K_{ρ}γ^{−1}x \end{matrix} )

Denote by μ^{•} the push-forward of the measure μ to X^{•}. Because of the freeness of the H-action on X, the leaf of μ^{•}-almost every x^{•} ∈ X^{•} is isomorphic to G.

Define the full equivalence relation R^{fu} on X^{•} by x^{•}R^{fu}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{fu}-leaf.

R^{fu}: Two points x^{•}, y^{•} are R^{fu}-equivalent if and only if they admit two representatives in X × V with the same first coordinate, iff they admit two representatives x, y in X for which there exists h ∈ H such that hx = y, iff any of their representatives are in the same H-orbit.

It inherits naturally an unoriented graphing and a smooth field of graphs (see Section 8, and examples 7.1, 7.3 of Section 7) from the edge set H\(X × E), where the graph associated with each point admits an isomorphism with G, canonical up to “rotation around ρ”, i.e. up to the action of the stabilizer K_{ρ} of ρ.

Theorem 2.1 The equivalence relation R^{fu} preserves the measure μ^{•} if and only if the group H is unimodular.

This result is just an application of Theorem 2.5 below. It sheds another light on the unimodularity assumption and on the Mass Transport Principle (see the proof of Theorem 2.5).

Example 2.2 The simplest example of the graph G made of a single infinite line is quite eloquent, with H = Aut(G) ≃ ℤ/2ℤ⋉ℤ. The compact subgroup K_{ρ} = ℤ/2ℤ is finite and X^{•} = (ℤ/2ℤ)\X. If the H-action on X is ergodic, then the lamination L^{fu} is not orientable, so that the associated unoriented graphing cannot be made (measurably) oriented.

2.2 The Cluster Equivalence Relation

Now, thanks to the map π : X → {0, 1}^{E}, the field of graphs x ↦ {x} × G becomes an H-equivariant field of colored graphs x ↦ π(x) so that each leaf of L^{fu} becomes a colored graph.

By removing all the 0-colored edges, one defines a subspace L^{cl} of L^{fu}: the cluster lamination. A leaf of L^{cl} is a connected component of 1-colored (or retained) edges.

Define the cluster equivalence relation R^{cl} on X^{•} by x^{•}R^{cl}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{cl}-leaf. It is a subrelation of R^{fu}.

The leaf of μ^{•}-almost every x^{•} is a graph L_{x^{•}}^{fu} which admits an isomorphism with the cluster G_{x} := π(x)(ρ) of the vertex ρ in the subgraph π(x) of G for any representative x of x^{•} (just observe that since kρ = ρ, for any k ∈ K_{ρ}, the clusters of ρ for x on the one hand and for kx on the other hand are isomorphic: π(kx)(ρ) = kπ(x)(ρ)). Thus the R^{cl}-class of x^{•} is infinite if and only if the corresponding clusters π(x)(ρ) are infinite. For each x^{•} ∈ X^{•}, the family of R^{cl}-classes into which its R^{fu}-class decomposes is in bijection with the clusters of π(x). The R^{fu}-class of x^{•} contains n infinite R^{cl}-classes iff π(x) has n infinite clusters.

R^{cl}: Two points x^{•}, y^{•} are R^{cl}-equivalent if and only if they admit two representatives in X ×V with the same first coordinate x and second coordinates in the same connected component of π(x), iff they admit two representatives x, y in X for which there exists h ∈ H such that hx = y and the vertices ρ, h^{−1}ρ are in the same cluster of π(x).

Let’s check by hand that the above characterization doesn’t depend on the choice of representatives. This h defines an isomorphism between the cluster π(x)(ρ) = π(x)(h^{−1}ρ) and π(hx)(hh^{−1}ρ) = π(y)(ρ). If k_{1}x and k_{2}y are two other representatives, k_{1}, k_{2} ∈ K_{ρ}, then k_{2}hk_{1}^{−1}(k_{1}x) = k_{2}y (i.e. h has to be replaced by k_{2}hk_{1}^{−1}), then k_{1}ρ = ρ and k_{1}h^{−1}ρ = k_{1}h^{−1}k_{2}^{−1}ρ = (k_{2}hk_{1}^{−1})^{−1}ρ are in the same cluster of π(k_{1}(x)).

The equivalence relation R^{cl} inherits naturally an unoriented graphing and a smooth field of graphs (see Section 8, and examples 7.1, 7.3 of Section 7).

Remark 2.3 Let Y^{•} ⊂ X^{•} be the union of the infinite R^{cl}-classes. Assume the action of H on X is ergodic. Then the invariant percolation π_{∗}μ has indistinguishable infinite clusters in the sense of [LS99, Sect. 3] if and only if the restriction R_{|Y}^{cl} is ergodic.

2.3 Measure Invariance, Unimodularity and the Mass-Transport Principle

Recall that a locally compact second countable group G admits a left-invariant Radon measure, its Haar measure m, unique up to a multiplicative constant. Pushed forward by right-multiplication, the measure is again left-invariant, and thus proportional to m. One gets a homomorphism mod : G → ℝ_{+}^{∗}, the modular map, which encodes the defect for m to be also right-invariant. In case the modular map is trivial (mod(G) = {1}), i.e. m is also right-invariant, then the group G is called unimodular.

Let (X, μ) be a standard Borel space with a probability measure and an essentially free measurepreserving action of a locally compact second countable group G. Let K be a compact open subgroup of G. Restricted to K, the modular function is trivial.

Proposition 2.4 The space \overline{X} = K\X is a standard Borel space. The quotient map X → K\X admits a Borel section.

Proof: The following argument has been explained to me by A. Kechris. Pushing forward the normalized Haar measure m on K by the Borel map (for any fixed x) K → X, k ↦ kx defines a measure m_{x} and thus a Borel map from X to the standard Borel space of probability measures on X ([Kec95, Th. 17.25]). But the right invariance of m on K shows^{20} that x and y are in the same K-orbit iff m_{x} = m_{y}. The K-action is then smooth. It follows from [Kec95, Ex. 18.20] that the action has a Borel selector. ■

Let \overline{R} be the reduced equivalence relation defined on \overline{X} by \overline{x}\overline{R}\overline{y} iff \overline{x} and \overline{y} admit G-equivalent preimages. Let’s denote by \overline{μ} the push-forward probability measure on \overline{X} = K\X, or by \overline{μ}_{K} if one wants to emphasize the choice of K. Section 8 recalls the terminology for the next Theorem.

Theorem 2.5 The equivalence relation \overline{R} on \overline{X} is standard countable. It preserves the measure \overline{μ}_{K} if and only if G is unimodular.

Proof: It is obviously a Borel subset of \overline{X} × \overline{X}. The countability of the classes comes from that of the set K\G.

The statement about unimodularity is quite natural once one realizes that the decomposition of μ relatively to \overline{μ} makes use of the right invariant Haar measure on G. However, we will follow elementary but enlightening facts leading by two ways to the result.

Recall (see Section 8) that \overline{R} preserves \overline{μ}_{K} if and only if the measures ν_{1} and ν_{2} on the set \overline{R} ⊂ X × X coincide, defined with respect to the projections on the first (resp. second) coordinate pr_{1} (resp. pr_{2}) by ν_{1}(C) = ∫_{X} #(C ∩ pr_{1}^{−1}(x))d\overline{μ}_{K}(x) and ν_{2}(C) = ∫_{X} #(C ∩ pr_{2}^{−1}(y))d\overline{μ}_{K}(y).

Proof by hand: If K, K′ are compact open subgroups of G, then K is made of unimodular elements of G. The intersection K ∩ K′ is a compact open subgroup of G. By a covering argument, its index in K is finite: [K : K ∩ K′] := #K/(K ∩ K′) = \frac{m(K)}{m(K∩K′)}. For γ ∈ G, m(γ^{−1}Kγ) = mod(γ)m(K). In particular, G is unimodular iff all the conjugates of K have the same Haar measure. Observe that [K : γKγ^{−1} ∩ K] = mod(γ)[K : K ∩ γ^{−1}Kγ] and that K and K′ as well as their Haar measures are commensurable, so that the modular function on G is rational. The reduction map (K ∩ K′)\X → K\X is a.s. [K : K ∩ K′]-to-one, and yields a disintegration of the push-forward measure \overline{μ}_{K∩K′} with respect to \overline{μ}_{K}, with normalized counting measure in the fibers. For γ ∈ G, consider the graph C_{γ} := \{(x, γx) : x ∈ X\} and its image in \overline{R}:

\overline{C}_{γ} := \{(\overline{x}, \overline{γx}) : x ∈ X\} = \{([K.x], [K.γx]) : x ∈ X\}.

For every k ∈ K, \overline{C}_{γ} = \overline{C}_{kγ}. Two points (x_{1}, y_{1}) and (x_{2}, y_{2}) of the “curve” C_{γ} define the same point in \overline{C}_{γ} iff there exist k, k′ ∈ K such that x_{1} = kx_{2} and γx_{1} = y_{1} = k′y_{2} = k′γx_{2}, iff (since by freeness of the action k = γ^{−1}k′γ) there exists k ∈ K ∩ (γ^{−1}Kγ) such that x_{1} = kx_{2}, γx_{1} = y_{1} and γx_{2} = y_{2} iff there exists k′ ∈ (γKγ^{−1}) ∩ K such that x_{1} = γ^{−1}y_{1}, x_{2} = γ^{−1}y_{2} and y_{1} = k′y_{2}. Thus, the preimage in C_{γ} (not in X × X !) of a point in \overline{C}_{γ} is of the form (for certain x and y): {(kx, γkx) : k ∈ (K ∩ γ^{−1}Kγ)} = {γ^{−1}k′y, k′y) : k′ ∈ (γKγ^{−1} ∩ K)}, so that

\overline{C}_{γ} ≃ (K ∩ γ^{−1}Kγ)\X  or  \overline{C}_{γ} ≃ (γKγ^{−1} ∩ K)\X,

according to whether \overline{C}_{γ} is parameterized by its first coordinate or its second coordinate. We have thus proved the following:

20m_{hx}(A) = m({k : khx ∈ A}) = m({k′h^{−1} : k′x ∈ A}) = m({k : kx ∈ A}) = m_{x}(A)

Proposition 2.6 The projection of \overline{C}_{γ} ⊂ \overline{R} to the first coordinate is [K : K ∩ γ^{−1}Kγ]-to-one. To the second coordinate, it is [K : γKγ^{−1} ∩ K]-to-one.

It follows that the measures ν_{1} and ν_{2} restricted to \overline{C}_{γ} satisfy ν_{2} = \frac{[K:γKγ^{−1}∩K]}{[K:K∩γ^{−1}Kγ]} ν_{1} = mod(γ) ν_{1}.

Proof by Mass-Transport Principle: Denote by W the countable discrete set G/K and observe that \overline{X} is isomorphic with the quotient G\(X × W) (where the G-action is diagonal).

( \begin{matrix}G\(X × W) & ≃ & K\X = \overline{X} \\ (gx, gγK) & ↦ & Kγ^{−1}x \end{matrix} )

Denote by ρ the class K ∈ G/K and by K_{v} the stabilizer of v ∈ W in the left multiplication G-action. In particular, K_{ρ} = K.

Two points x̄_{1} and x̄_{2} of \overline{X} are \overline{R}-equivalent iff they admit representatives in X ×W with the same first coordinate. One thus gets an identification of \overline{R} with G\(X × W × W) (where the G-action is diagonal on the three coordinates), thanks to the two coordinate-forgetting projections (where W_{1}, W_{2} are two copies of W):

G\(X × W_{1}) = \overline{X}
pr_{1}↗
G\(X × W_{1} × W_{2})
pr_{2}↘
G\(X × W_{2}) = \overline{X}

It becomes equivalent to consider a function F on \overline{R} or a G-invariant function f on X × W × W. Thus, for non-negative functions

\begin{aligned}ν_{1}(F) & = & ∫\overline{R} F (x̄_{1}, x̄_{2})dν_{1} = ∫\overline{X} ∑_{x̄_{2}∼x̄_{1}} F (x̄_{1}, x̄_{2})dμ̄(x̄_{1}) \\ & = & ∫_{X} ∑_{v_{2}∈W} f(x, ρ, v_{2})dμ(x) \end{aligned}

while

ν_{2}(F) = ∫_{X} ∑_{v_{1}∈W} f(x, v_{1}, ρ)dμ(x)

On the other hand, the mass-transport principle below essentially gives the correcting terms for ν_{1} and ν_{2} to coincide. In particular, unimodularity, equivalent to the coincidence of the Haar measures m(K_{v_{1}}) = m(K_{ρ}) for every v_{1}, is equivalent to the preservation for \overline{R} of the measure μ̄.

The mass-transport principle:

∫_{X} ∑_{v_{2}∈W}f(x, ρ, v_{2}) m(K_{ρ}) dμ(x) = ∫_{X} ∑_{v_{1}∈W} f(x, v_{1}, ρ) m(K_{v_{1}}) dμ(x),

where m is the Haar measure on G, is a useful device in invariant percolation theory. For details, see [BLPS99a] where I took the following two-line proof, credited to W. Woess. Let f̄(v, v′) := ∫_{X} f(x, v, v′) dμ(x) denote the mean value.

\begin{aligned}∑_{v_{2}∈W} f̄(ρ, v_{2}) m(K_{ρ}) & = ∑_{v_{2}∈W} f̄(ρ, v_{2}) m(\{g : gρ = v_{2}\}) & = ∫_{G} f̄(ρ, gρ) dm(g) \\ ∑_{v_{1}∈W} f̄(v_{1}, ρ)m(K_{v_{1}}) & = ∑_{v_{1}∈W} f̄(v_{1}, ρ)m(\{\underbrace{g : gv_{1} = ρ}_{\{g:g^{−1}ρ=v_{1}\}}\}) & = ∫_{G} f̄(g^{−1}ρ, ρ)dm(g) \end{aligned}

And, the last terms are equal, thanks to the G-invariance of f and μ. ■

2.4 Some computation

Assume that H is transitive and unimodular. Recall that G_{x} denotes, for x ∈ X, the cluster of the vertex ρ in the subgraph π(x). Let p_{x} : C_{(2)}^{1}(G) → dHD(G_{x}) be the orthogonal projection from the space of ℓ^{2} cochains of G to the image, under the coboundary d, of HD(G_{x}) in C_{(2)}^{1}(G). Denote by 1_{e_{1}}, 1_{e_{2}}, ⋯, 1_{e_{n}} ∈ C_{(2)}^{1}(G) the characteristic functions of the edges e_{1}, e_{2}, ⋯, e_{n} adjacent to the base point ρ.

Proposition 2.7 Let Y^{•} be a non-null R^{cl}-saturated Borel subset of X^{•}, and Y its preimage in X. The first L^{2} Betti number of the restricted measure equivalence relation R_{|Y^{•}}^{cl} on (Y^{•}, μ_{Y^{•}}^{•}) equals

β_{1}(R_{|Y^{•}}^{cl}, μ_{Y^{•}}^{•}) = \frac{1}{2μ(Y)} ∑_{i=1}^{n} ∫_{Y} ⟨p_{y}(1_{e_{i}})|1_{e_{i}}⟩dμ(y).

Here, μ_{Y^{•}}^{•} is of course the normalized restriction of μ^{•} to Y^{•}. The \frac{1}{2} terms just reflects that, the graph being transitive, each edge is counted twice: once per endpoint, while \frac{1}{μ(Y)} is just designed to normalize.

Proof: We use first Theorem 7.5 stating that β_{1}(R_{|Y^{•}}^{cl}, μ_{Y^{•}}) = dim_{R_{|Y^{•}}^{cl}} ∫_{Y^{•}} d(HD(G_{y^{•}})) dμ_{Y^{•}}^{•}(y^{•}); second the definition of the dimension (see [Gab02, Prop. 3.2 (2)]): A measurable labeling (see Proposition 2.4) e_{1}^{•}, e_{2}^{•}, ⋯, e_{n}^{•} of the edges adjacent to y^{•} leads to measurable vector fields y^{•} ↦ 1_{e_{i}^{•}} ∈ C_{(2)}^{1}(G_{y^{•}}) that define a family of fields of representative (in the sense of [Gab02]), except that each edge is represented twice (the additionnal difficulty of a possible loop in G is dismissed by the fact that it would give a vector orthogonal to d(HD(G_{y^{•}})). Third, we use the relation between the objects with and without a • sign. ■

Remark 2.8 In case Y^{•} is not R^{cl}-saturated, the families of fields of representative are more delicate to describe. However, Corollary 5.5 of [Gab02], for induction on Borel subsets (see fact 2, Subsection 1.4), applied to Y^{•} and its R^{cl}-saturation leads to the same formula except that the domain of integration is now the H-saturation HY of Y:

β_{1}(R_{|Y^{•}}^{cl}, μ_{Y^{•}}^{•}) = \frac{1}{2μ(Y)} ∑_{i=1}^{n} ∫_{HY} ⟨p_{y}(1_{e_{i}})|1_{e_{i}}⟩dμ(y).

Observe that the quantity on the right in the above Proposition 2.7 in fact only depends on the image Ω_{Y} := π(Y) in Ω = {0, 1}^{E}

β_{1}(R_{|Y^{•}}^{cl}, μ_{Y^{•}}^{•}) = \frac{1}{2π_{∗}μ(Ω_{Y})} ∑_{i=1}^{n} ∫_{Ω_{Y}} ⟨p_{ω}(1_{e_{i}})|1_{e_{i}}⟩dπ_{∗}μ(ω).

Concerning the full equivalence relation, one gets,

β_{1}(R^{fu}, μ^{•}) = \frac{1}{2} ∑_{i=1}^{n} ∫_{X} ⟨p_{x}(1_{e_{i}})|1_{e_{i}}⟩dμ(x).

But in the case of R^{fu}, the projection p_{x} doesn’t depend on x: it is just the projection

p : C_{(2)}^{1}(G) → dHD(G) ≃ HD(G)/ℂ.

It follows that Proposition 2.9 For the full equivalence relation on X^{•}:

β_{1}(R^{fu}, μ^{•}) = \frac{1}{2} ∑_{i=1}^{n} ⟨p(1_{e_{i}})|1_{e_{i}}⟩.  (2)

Observe that this quantity doesn’t even depend on what happens on X nor on the choice of H, once H is unimodular and transitive on the vertices: It is an invariant of the graph.

Definition 2.10 Call it the first ℓ^{2} Betti number of G and denote it

β_{1}(G) := \frac{1}{2} ∑_{i=1}^{n} ⟨p(1_{e_{i}})|1_{e_{i}}⟩.  (3)

It is clear^{21} that β_{1}(G) = 0 if and only if G belongs to O_{HD}.

3 Harmonic Dirichlet Functions and Clusters for Transitive Graphs

In this section, we give the proof of Theorem 0.4 of the introduction by putting/proving it in the more general context of selectability.

Recall that we have at hand: (1) A locally finite graph G = (V, E) with a transitive (on V) action of a closed group H of automorphisms; (2) An H-invariant probability measure P on the set Ω = {0, 1}^{E} of colorings of G.

3.1 The action made free

The H-action on Ω being not necessarily free, let’s consider a diagonal H-action on X = Ω × Z, where Z is a standard Borel space with an essentially free probability measure-preserving action of H. An example of such a Z is furnished by the Lemma 3.2 below.

The diagonal action preserves the product measure μ and is (essentially) free. The obvious projection π : X = Ω × Z → Ω sends μ to P and is H-equivariant, so that we are in the context of Section 2.

Remark 3.1 We could probably avoid the detour by the freeness of the action by defining L^{2} Betti numbers for groupoids instead of just for equivalence relations, as suggested in [Gab02, p.103]. Notice that such a study of L^{2} Betti numbers for measured groupoids has been carried out by R. Sauer (see [Sau03]), using Lück’s approach of ℓ^{2} theory.

Lemma 3.2 If H acts continuously^{22} faithfully on a discrete countable set V, then the diagonal action of H on Ω̌ = ({0, 1}^{V} )^{ℕ} is continuous, preserves the Bernoulli measure (product of equiprobabilities on {0, 1}), and is essentially free.

Proof: Enumerate the elements of V: v_{1}, v_{2}, …, v_{n}, … and denote by Ω̌_{i,j} the subset of points of Ω̌ that are fixed by an element of H which sends v_{i} to v_{j}. This subset satisfying infinitely many equations: ω(v_{i}, l) = ω(v_{j}, l) for each coordinate l ∈ ℕ, has thus measure 0. The set of points ω with a non-trivial stabilizer is contained in the countable union of the Ω̌_{i,j}; it has measure zero. ■

21⟨p(1_{e_{i}})|1_{e_{i}}⟩ = ⟨p^{2}(1_{e_{i}})|1_{e_{i}}⟩ = ⟨p(1_{e_{i}})|p(1_{e_{i}})⟩ = 0 iff h.p(1_{e_{i}}) = p(h.1_{e_{i}}) = 0 for all h ∈ H and i = 1, ⋯, n.

22The stabilizer of a point of V is a closed open subgroup of H.

3.2 Selectability

Let G be a locally finite transitive graph and H a closed transitive subgroup of Aut(G). Equip {0, 1}^{V} with the natural action of H induced by its action on V.

Definition 3.3 Let P be an H-invariant percolation on G. Let Δ be a closed subgroup of H.

A Δ-equivariant selected cluster on a Δ-invariant P-non-null Borel subset D ⊂ {0, 1}^{E} is a Δequivariant measurable map c : D → {0, 1}^{V}, such that c(ω) is the (characteristic function of the) vertex set of one cluster C(ω) of ω.

A Δ-equivariant virtually selected cluster on a Δ-invariant P-non-null Borel subset D ⊂ {0, 1}^{E} is a Δ-equivariant measurable map c : D → {0, 1}^{V} such that c(ω) is the (characteristic function of the) vertex set of (the union of) finitely many clusters C_{1}(ω), C_{2}(ω), ⋯, C_{n(ω)}(ω) of ω.

Example 3.4 If almost every subgraph ω has a unique infinite cluster, assigning to ω this infinite cluster defines an H-equivariant selected cluster. And similarly, if almost every subgraph ω has finitely many infinite clusters, assigning to ω these infinite clusters defines an H-equivariant virtually selected cluster.

Let (X, μ) be a standard Borel probability space together with

• a probability measure-preserving (p.m.p.) action of H, which is free, and

• an H-equivariant Borel map (field of graphs) π : X → {0, 1}^{E}

so that our situation fits in the general context of Section 2.

Proposition 3.5 The following are equivalent:

(1) The invariant percolation π_{∗}(μ) admits a H-equivariant selected cluster,

(2) There is a non-null Borel subset T^{•} of X^{•} to which the restrictions of R^{fu} and R^{cl} coincide: R_{|T^{•}}^{fu} = R_{|T^{•}}^{cl}.

Moreover, T^{•} can be taken to be the image in X^{•} of the set of those x ∈ X whose selected cluster contains the base point ρ.

Proof: The selected cluster c : {0, 1}^{E} → {0, 1}^{V} selects by composition by π one connected component of the splitting of each L^{fu}-leaf into its L^{cl}-components. The union of these selected leaves intersects the transversal X^{•} along a Borel subset T^{•} which is characterized as the image in X^{•} of the set of x ∈ X such that the selected cluster c(π(x)) contains the base point ρ. Two R^{fu}-equivalent points in T^{•} belong to the same L^{fu}-leaf and both belong to THE selected L^{cl}-leaf; they are thus R^{cl}-equivalent.

Conversely, if T^{•} is a Borel subset of X^{•} to which the restrictions of R^{fu} and R^{cl} coincide, then it selects an L^{cl}-leaf in each L^{fu}-leaf meeting T^{•}. One can assume that T^{•} is R^{cl}-saturated (two points that are R^{fu}-equivalent and R^{cl}-equivalent to some point in T^{•} have to be R^{cl}-equivalent). Let Ť be the preimage of T^{•} in X × V. It is an H-invariant subset, whose projection T in X is non-null and H-invariant, and whose intersection with each fiber ({x}×V)∩Ť is a cluster č(x) of π(x). This defines an H-equivariant map č: T → {0, 1}^{V}. Now the set (X × {ρ}) ∩ Ť once projected in X corresponds to those x ∈ T for which č(x) is the cluster of the base point ρ. This shows that the cluster č(x) only depends on π(x). Moreover, π(T) is non-null for the measure π_{∗}μ, so that the map č induces an H-equivariant selected cluster on π(T) ⊂ {0, 1}^{E}. ■

Recall that a subrelation S has finite index in R if each R-class splits into finitely many S-classes. The same kind of argument as above shows:

Proposition 3.6 The following are equivalent:

(1) The invariant percolation π_{∗}(μ) admits a H-equivariant virtually selected cluster,

(2) There is a non-null Borel subset T^{•} of X^{•} to which the restriction of R^{cl} has finite index in the restriction of R^{fu}: [R_{|T^{•}}^{fu} : R_{|T^{•}}^{cl}] < ∞.

Moreover, T^{•} can be taken to be the image in X^{•} of the set of those x ∈ X for which one of the selected clusters contains the base point ρ.

Observe that if G is not a finite graph, then R^{fu} has infinite classes and the H-equivariant virtually selected clusters are (almost) all infinite.

Remark 3.7 The main result of [LS99] (indistinguishability of the infinite clusters) implies that Bernoulli percolation in the nonuniqueness phase admits no H-equivariant virtually selected clusters.

Remark 3.8 Let Δ be a closed subgroup of H that contains the stabilizer K_{ρ} of ρ. One can define a notion of full Δ-equivalence relation R_{Δ}^{fu} ⊂ R^{fu} and cluster Δ-equivalence relation: the intersection R_{Δ}^{cl} = R^{cl} ∩ R_{Δ}^{fu}.

R_{Δ}^{fu}: Two points x^{•}, y^{•} are R_{Δ}^{fu}-equivalent if and only if they admit two representatives x, y

in X for which there exists δ ∈ Δ such that δx = y, iff any of their representatives are in the same Δ-orbit.

Similarly, for the cluster Δ-equivalence relation:

R_{Δ}^{cl}: Two points x^{•}, y^{•} are R_{Δ}^{cl}-equivalent if and only if they admit two representatives x, y in X for which there exists δ ∈ Δ such that δx = y and the vertices ρ, δ^{−1}ρ are in the same cluster of π(x).

In case G is the Cayley graph of a discrete group Γ (i.e. K_{ρ} = {1} and X^{•} = X) then R_{Δ}^{fu} is just the equivalence relation defined by the Δ-action on X, while R_{Δ}^{cl} = R^{cl} ∩ R_{Δ}^{fu} is just defined by: (x, y) ∈ R_{Δ}^{cl} iff there exists δ ∈ Δ such that δx = y and the vertices ρ, δ^{−1}ρ are in the same cluster of π(x).

Exactly along the same arguments as above, one can show that the following are equivalent:

(1) The invariant percolation π_{∗}(μ) admits a Δ-equivariant selected cluster,

(2) There is a non-null Borel subset T^{•} of X^{•} to which the restrictions of R_{Δ} and R_{Δ}^{cl} coincide: R_{Δ|T}^{fu} = R_{Δ|T}^{cl} . And similarly, with finite index, for the virtual notion.

The lamination interpretation of these equivalence relations goes as follows: Consider first the space X × G and divide out by Δ to get the laminated space L_{Δ}^{fu}. Consider now the transversal Δ\(X × Δρ) ⊂ Δ\(X × V), which is naturally isomorphic with X^{•} = K_{ρ}\X since Δ contains K_{ρ}, and the equivalence relation defined on it by “belonging to the same L_{Δ}^{fu}-leaf”. This is the full Δ-equivalence relation R_{Δ}^{fu} ⊂ R^{fu} and it appears as the image in X^{•} = H\(X × V) of the equivalence relation defined by the Δ-action on X. Just like in Section 1, use now π to get a coloring on the leaves. Define L_{Δ}^{cl} as the sub-laminated space where the 0-colored edges are removed and R_{Δ}^{cl} as the subrelation of R_{Δ}^{fu} induced on Δ\(X × Δρ) by “belonging to the same L_{Δ}^{cl}-leaf”.

3.3 Selected Clusters and Harmonic Dirichlet Functions

The connections between selected clusters and harmonic Dirichlet functions is very simple:

Theorem 3.9 Assume π_{∗}μ admits an H-equivariant virtually selected cluster. Assume that the closed subgroup H is unimodular. If G belongs to O_{HD}, then μ-a.e. virtually selected cluster belongs to O_{HD}. If G doesn’t belong to O_{HD}, then μ-a.e. virtually selected cluster doesn’t belong to O_{HD}.

Proof: Thanks to unimodularity, the associated equivalence relations R^{fu} and R^{cl} are measurepreserving (Th. 2.5).

Start with the case of a selected cluster. Denote by c the H-equivariant selected cluster c : {0, 1}^{E} → {0, 1}^{V} and C = c ∘ π : X → {0, 1}^{V}. Let T be the Borel subset of x ∈ X where the selected cluster C(x) contains ρ and let T^{•} be its image in X^{•}.

The following are equivalent:

1. G is in O_{HD}

2. β_{1}(R^{fu}, μ^{•}) = 0

3. β_{1}(R_{|T^{•}}^{fu}, μ_{T^{•}}^{•}) = 0

4. β_{1}(R_{|T^{•}}^{cl}, μ_{T^{•}}^{•}) = 0

5. for μ^{•}-almost every x^{•} ∈ T^{•}, the graph L_{x^{•}}^{cl} is in O_{HD}

6. for μ-almost every x ∈ T, the selected cluster C(x) is in O_{HD}

Theorem 0.3 applied to the field of graphs x^{•} ↦ L_{x^{•}}^{fu} ≃ G (example 7.3) gives the equivalence 1 ⟺ 2. When applied to the restriction of that field to T^{•} (example 7.4), it gives 1 ⟺ 3. Observe that the equivalence 2 ⟺ 3 is also an application of [Gab02, Cor. 5.5]. Since β_{1} is an invariant of the equivalence relation, 3 ⟺ 4 is deduced from the coincidence R_{|T^{•}}^{cl} = R_{|T^{•}}^{fu} (prop. 3.5). Theorem 0.3, applied to the field of graphs x^{•} ↦ L_{x^{•}}^{cl} (example 7.3) restricted to T^{•}, shows the equivalence 4 ⟺ 5. Each L_{x^{•}}^{cl} being isomorphic to the cluster π(x)(ρ) = C(x) of any of its representatives, and μ^{•} being the push-forward of μ, one deduces the last equivalence.

Let T′ ⊂ T be the Borel subset of points such that the selected cluster is in O_{HD}. If T′ is non-null, then the above arguments applied to T′ shows that G belongs to O_{HD} and thus T′ = T a.s. This implies that in case G does not belong to O_{HD}, then for μ-almost every x ∈ T, the selected cluster C(x) is not in O_{HD}.

For the case of a virtually selected cluster, partition first T as ∐ T_{n} according to how many clusters are selected. On T_{n}^{•} the R_{|T^{•}}^{fu}-classes decompose into n R_{|T^{•}}^{cl}-classes (prop. 3.6). Then just replace the argument in the proof of the equivalence 3 ⟺ 4 above by Proposition 5.11 of [Gab02], asserting that β_{1}(R_{|T^{•}}^{cl}) = nβ_{1}(R_{|T^{•}}^{fu}). ■

4 Nonuniqueness Phase and Harmonic Dirichlet Functions

This section is concerned with a comparison between two invariant percolations. Its main goal is to prove Theorem 4.2, which implies both Theorem 0.6 (Corollary 4.5) and Theorem 0.7 (Corollary 4.7) of the introduction.

Consider a unimodular transitive group H of automorphisms of G and two H-invariant percolations μ_{1} and μ_{2} on G. Recall that given two H-invariant percolations on G, an H-equivariant coupling is a p.m.p. H-action on a standard probability measure space (X, μ) with two H-equivariant maps

(X, μ)
π_{1} ↙  ↘^{π_{2}}
({0, 1}^{E}, μ_{1})  ({0, 1}^{E}, μ_{2})

pushing μ to μ_{i} respectively, i.e. π_{1∗}μ = μ_{1} and π_{2∗}μ = μ_{2}.

To π_{1} and π_{2} correspond two laminations L_{1}^{cl} and L_{2}^{cl} (both sub-laminations of L^{fu}) with transversal X^{•} = K_{ρ}\X and two cluster equivalence relations R_{1}^{cl} and R_{2}^{cl} (both subrelations of R^{fu}).

Remark 4.1 An invariant coupling always exists since the product space with the product measure and the diagonal action will do. In case the coupling witnesses a stochastic domination^{23} (see for instance [HJL02a, sect. 2.2]), then R_{1}^{cl} fits into R_{2}^{cl}: R_{1}^{cl} ⊂ R_{2}^{cl}.

Theorem 4.2 Let G be a unimodular transitive locally finite graph. Let H be a unimodular transitive group of automorphisms of G, let (X, μ) be an H-equivariant coupling between two H-invariant percolations μ_{1}, μ_{2}. Assume that

1. μ_{1}-a.e. cluster belongs to O_{HD},

2. π_{2} has an H-equivariant selected cluster defined on a non-null set^{24}, then

β_{1}(G) ≤ \frac{1}{2} ∑ ; edges e ; adjacent to ρ μ(π_{2}(e) = 1 and π_{1}(e) = 0).

Here, β_{1}(G) is the invariant of the graph introduced in Definition 2.10. It is strictly positive if and only if G doesn’t belong to O_{HD}.

The main ingredient in the proof of the theorem will be the following useful result. Here, graphing may be understood as oriented or unoriented (see Section 8).

Theorem 4.3 Let R_{1} be a p.m.p. equivalence relation on the standard Borel space (X, μ). Let Ψ_{2} be a p.m.p. graphing and let R_{2} = R_{1} ∨ Ψ_{2} be the equivalence relation generated by R_{1} and Ψ_{2}. Then

β_{1}(R_{2}) − β_{0}(R_{2}) ≤ β_{1}(R_{1}) − β_{0}(R_{1}) + cost(Ψ_{2}).

Remark 4.4 There is no continuity in the other direction: Think in R_{i} given by a free action of Γ_{1} = F_{2} and Γ_{2} = F_{2} × ℤ. Then R_{2} can be generated from R_{1} by adding a graphing Ψ_{2} of arbitrarily small cost. However, β_{1}(R_{2}) − β_{0}(R_{2}) = 0 while β_{1}(R_{1}) − β_{0}(R_{1}) = 1.

Proof: The proof is just an adaptation of the proof of the Morse inequalities (see [Gab02, sect. 4.4, p.137]). Let Σ̄_{1} be a simply connected smooth simplicial R_{1}-complex, with a big enough 0-skeleton: R_{1} ⊂ Σ̄_{1}. Then (β_{1} − β_{0})(R_{1}) = (β_{1} − β_{0})(Σ̄_{1}). Let (Σ̄_{1}^{n})_{n} be an increasing sequence of ULB smooth simplicial R_{1}-complexes that exhausts Σ̄_{1}, with say R_{1} ⊂ Σ̄_{1}^{0}.

23i.e. μ{x : π_{1}(x) ≤ π_{2}(x)} = 1, i.e. for μ a.e. x ∈ X and for every edge e ∈ E, if π_{1}(x)(e) = 1, then π_{2}(x)(e) = 1.

24For instance, if μ_{2} has a non-null set of subgraphs with exactly one infinite cluster.

Let ¯ Σ̄_{1} and ¯ Σ̄_{1}^{n} be the corresponding smooth R_{2}-complexes ([Gab02, sect. 5.2, p.140]): R_{2} ⊂ ¯ Σ̄_{1}^{0} and moreover, the reciprocity formula gives

(β_{1} − β_{0})(R_{1}) = lim_{n}(β_{1} − β_{0})(Σ̄_{1}^{n}, R_{1}) = lim_{n}(β_{1} − β_{0})(¯Σ̄_{1}^{n}, R_{2}).

Define ¯ Σ̄_{2} and ¯ Σ̄_{2}^{n} by just adding to ¯ Σ̄_{1} and ¯ Σ̄_{1}^{n} the R_{2}-field of graphs associated to Ψ_{2} on R_{2}. Claim: (β_{1} − β_{0})(¯Σ̄_{2}^{n}) ≤ (β_{1} − β_{0})(¯Σ̄_{1}^{n}) + cost(Ψ_{2}), ∀n. This is an immediate computation by mimicking the first 4 lines of [Gab02, sect. 4.4, p.137] (read b_{0} = 0 instead of b_{−1} = 0, there). Now, by letting n tend to ∞, (β_{1} − β_{0})(¯Σ̄_{2}) ≤ (β_{1} − β_{0})(¯Σ̄_{1}) + cost(Ψ_{2}) = (β_{1} − β_{0})(R_{1}) + cost(Ψ_{2}). By definition, ¯ Σ̄_{2} is connected, so that β_{0}(¯Σ̄_{2}) = β_{0}(R_{2}) [Gab02, 3.14]. On the other hand, β_{1}(R_{2}) ≤ β_{1}(¯Σ̄_{2}) [Gab02, 3.13 and 3.14]. This proves Th. 4.3. ■

Proof (of Theorem 4.2): Denote by Ř = R_{1}^{cl} ∨ R_{2}^{cl} the equivalence relation generated by R_{1}^{cl} and R_{2}^{cl}. It is also the relation defined on X^{•} by the union lamination L_{1}^{cl} ∪ L_{2}^{cl}. Let Y ⊂ X^{•} be a μ^{•}-non-null Ř-saturated Borel subset. It is clear from the lamination description that the restriction Ř_{|Y} is generated by the restriction R_{1|Y}^{cl} together with the graphing Ψ_{2} consisting of edges of L_{2}^{cl} \ L_{1}^{cl} with both endpoints in Y (one endpoint in Y implies the other one in Y, by saturation):

Ř_{|Y} = R_{1|Y}^{cl} ∨ Ψ_{2}.

The cost of Ψ_{2} (again, \frac{1}{2} just reflects that each edge is counted twice, while \frac{1}{μ^{•}(Y)} is just designed to normalize) is bounded above by

cost(Ψ_{2}) ≤ \frac{1}{2μ^{•}(Y)} ∑ ; edges e ; adjacent to ρ μ(π_{2}(e) = 1 and π_{1}(e) = 0).

The above Theorem 4.3 gives:

β_{1}(Ř_{|Y}) − β_{0}(Ř_{|Y}) ≤ β_{1}(R_{1|Y}^{cl} ) − β_{0}(R_{1|Y}^{cl} ) + \frac{1}{2μ^{•}(Y)} ∑ ; edges e ; adjacent to ρ μ(π_{2}(e) = 1 and π_{1}(e) = 0).

If Z is a measurable non-null subset where ρ belongs to the H-equivariant selected cluster (for instance, the unique infinite cluster), then R_{2|Z}^{cl} = R_{|Z}^{fu}. So that its Ř-saturation Y satisfies Ř_{Y} = R_{Y}^{fu} and thus (see fact 2, Subsection 1.4)

μ^{•}(Y)β_{1}(Ř_{|Y}) = μ^{•}(Y)β_{1}(R_{|Y}^{fu} ) = β_{1}(R^{fu}),

which coincides by definition with the quantity β_{1}(G) introduced in Section 2.4, Definition 2.10. Recall that β_{1}(G) = 0 iff G ∈ O_{HD}. The graph G being infinite, β_{0}(Ř_{|Y}) = β_{0}(R_{|Y}^{fu} ) = 0, so that

0 < β_{1}(G) ≤ μ^{•}(Y)(β_{1}(R_{1|Y}^{cl} ) − β_{0}(R_{1|Y}^{cl} )) + \frac{1}{2} ∑ ; edges e ; adjacent to ρ μ(π_{2}(e) = 1 and π_{1}(e) = 0).

Now, the assumption (1) of Theorem 4.2 is designed (since β_{1}(R_{1|Y}^{cl} ) = 0 by Th. 0.3) to ensure that

β_{1}(R_{1|Y}^{cl} ) − β_{0}(R_{1|Y}^{cl} ) ≤ 0

and this finishes its proof. ■

4.1 Application to Bernoulli Percolation

Corollary 4.5 (Th. 0.6) Let G be a unimodular transitive locally finite graph. If G doesn’t belong to O_{HD}, then the nonuniqueness phase interval of Bernoulli percolation has non-empty interior:

p_{c}(G) < p_{u}(G)

More precisely,

0 < β_{1}(G) ≤ \frac{1}{2}(degree of G)(p_{u}(G) − p_{c}(G)).

Proof: The standard coupling ([0, 1]^{E}, ⊗Lebesgue) →^{π_{p}} ({0, 1}^{E}, P_{p}) (see for example Section 1.3.d) provides a family of countable equivalence relations R_{p}^{cl} (on the quotient space K_{ρ}\[0, 1]^{E}, once given a closed unimodular transitive group of automorphisms of G). For s < p_{c}, the equivalence classes of the cluster equivalence relation are a.s. finite, thus μ_{s}-a.e. cluster belongs to O_{HD}. The right-hand quantity of Theorem 4.2 with μ_{1} = μ_{s} and μ_{2} = μ_{t}, for t in the uniqueness phase, is

\frac{1}{2} ∑ ; edges e ; adjacent to ρ μ(π_{2}(e) = 1 and π_{1}(e) = 0) = \frac{1}{2}(degree of G)(t − s).

One concludes by continuity, by letting s tend to p_{c}(G) and t tend to p_{u}(G).

Observe that one could have applied Theorem 4.2 directly with s = p_{c}(G): there is almost surely no infinite cluster at p_{c}(G) [BLPS99a, Th. 1.3]. ■

Remark 4.6 While the above corollary extends to unimodular quasi-transitive locally finite graphs, it is unknown whether the unimodularity assumption may be removed. On the other hand, the removal of any transitivity assumption makes it false since R. Lyons and Y. Peres showed (personal communication: I want to thank them allowing me to reproduce their description here) that the following graph G doesn’t belong to O_{HD} but on the other hand, the set of parameters p in Bernoulli percolation doesn’t admit any interval of nonuniqueness.

Denote by G_{m} the graph obtained from the lattice ℤ^{2} by replacing each edge of ℤ^{2} by m paths of length 2. We fix m large enough so that p_{c}(G_{m}) < p_{c}(ℤ^{3}). Denote by G_{m}(k) a k-by-k square in ℤ^{2}, with each edge replaced by m paths of length 2. Now consider two copies of ℤ^{3} (call them G′ and G′′) that we will join in countably many corresponding places (x_{i}, y_{i}) ∈ G′ × G′′, with density 0 in both G′ and G′′, using graphs G_{m}(k_{i}) as follows: position G_{m}(k_{i}) with one corner at x_{i} and another corner at y_{i}. We make k_{i} grow fast enough so that the effective conductance between G′ and G′′ is finite; explicitly, we make ∑_{i} 1/(log k_{i}) < ∞. This constructs the graph G.

4.2 Application to Random-Cluster Model

Corollary 4.7 (Th. 0.7) Let G be a unimodular transitive locally finite graph, not in O_{HD}. Fix the parameter q ∈ [1, ∞). The gap between the left limit (when p ↗ p_{c}(q)) and the right limit (when p ↘ p_{u}(q)) of the expected degree of a base point ρ with respect to the measure RC_{p,q} satisfies:

0 < β_{1}(G) ≤ \frac{1}{2}(RC_{p_{u}+,q}[deg(ρ)] − RC_{p_{c}−,q}[deg(ρ)]).

Here, RC denotes either WRC or FRC.

Proof: Consider the invariant coupling introduced by O. Häggström, J. Jonasson and R. Lyons in [HJL02a] of (all) the measures FRC_{p,q} and WRC_{p,q} (together) for p ∈ [0, 1] and q ∈ [1, ∞)

(X, μ) →^{π_{p,q}^{RC}} ({0, 1}^{E}, RC_{p,q})

It provides two families of countable equivalence relations R_{p,q}^{cl} (on the quotient space K_{ρ}\X, once given a closed unimodular transitive group of automorphisms of G), one for FRC and one for WRC. The usefulness of that coupling is that it reflects the stochastic domination (see [HJL02a, sect. 3]); in particular, for a fixed parameter q and s < t (and denoting π_{s,q}^{RC} by π_{s}):

μ(π_{t}(e) = 1 and π_{s}(e) = 0) = μ(π_{t}(e) = 1) − μ(π_{s}(e) = 1)

Take s, t such that s < p_{c}(q) ≤ p_{u}(q) < t, then Theorem 4.2 says that:

β_{1}(G) ≤ \frac{1}{2} ∑ ; edges e ; adjacent to ρ μ(π_{t}(e) = 1) − μ(π_{s}(e) = 1)

Now, the right member is precisely: \frac{1}{2}(RC_{t,q}[deg(ρ)] − RC_{s,q}[deg(ρ)]). The monotonicity properties of the measures RC lead to the required inequality. Indeed, monotonicity as well as left continuity of p ↦ FRC_{p,q}[deg(ρ)] and right continuity of p ↦ WRC_{p,q}[deg(ρ)] follow, like in [HJL02b], from the fact that FRC is an increasing (and WRC is a decreasing) limit of increasing (in p) continuous functions. ■

5 Quasi-transitive graphs

This section indicates how to extend the above results to the context of quasi-transitive graphs, instead of just transitive ones. There is no qualitative reversal, and just some quantitative adjustments. The proofs are straightforward adaptions of those of the transitive case with just slight changes of notation. We first describe how to modify section 2.

Let G = (V, E) be a locally finite quasi-transitive graph, H a closed subgroup of Aut(G) whose action on V has finitely many orbits. Choose one vertex ρ_{1}, ρ_{2}, ⋯, ρ_{q} in each orbit and denote by K_{1} = K_{ρ_{1}}, K_{2} = K_{ρ_{2}}, ⋯, K_{q} = K_{ρ_{q}} its stabilizer. Let (X, μ) be a standard Borel probability space together with

• a probability measure-preserving (p.m.p.) action of H, which is essentially free, and

• an H-equivariant Borel map π : X → {0, 1}^{E}. Divide out X × G by the diagonal action of H to get the laminated space L^{fu} = H\(X × G): the full lamination. Corresponding to the partition of V into H-orbits V_{1}, V_{2}, ⋯, V_{q}, the transversal X^{•} := H\(X × V) identifies with the disjoint union of standard Borel spaces K_{1}\X ∐ K_{2}\X ∐ ⋯ ∐ K_{q}\X via X × V_{i} ∋ (hx, hγρ_{i}) ↦ K_{i}γ^{−1}x ∈ K_{i}\X. The leaf of μ^{•}-almost every x^{•} ∈ X^{•} is isomorphic to G.

Define the full equivalence relation R^{fu} on X^{•} by x^{•}R^{fu}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{fu}-leaf.

It inherits naturally an unoriented graphing and a smooth field of graphs (see Section 8, and examples 7.1, 7.3 of Section 7) from the edge set H\(X × E), where the graph associated with each point admits an isomorphism with G.

Consider, on X^{•}, the probability measure μ^{•} := \frac{1}{T} (\frac{Π_{1∗}μ}{m(K_{1})} + \frac{Π_{2∗}μ}{m(K_{2})} + ⋯ + \frac{Π_{p∗}μ}{m(K_{q})}), where T = \frac{1}{m(K_{1})} + \frac{1}{m(K_{2})} + ⋯ + \frac{1}{m(K_{q})} and Π_{i∗}μ is the pushed-forward measure by Π_{i} : X → K_{i}\X. It is preserved by the equivalence relation R^{fu} if and only if the group H is unimodular (Th. 2.1). Observe that with this choice (under the unimodularity asumption), the description depends neither on the choice of scaling of the Haar measure, nor on the choice of a particular orbit of vertices. The first L^{2} Betti number of the equivalence relation R^{fu} is given by the formula:

β_{1}(R^{fu}, μ^{•}) := \frac{1}{2T} ∑_{i=1}^{q} \frac{1}{m(K_{i})} ∑_{j=1}^{n_{i}} ⟨p(1_{e_{i,j}})|1_{e_{i,j}}⟩,

where p is the projection p : C_{(2)}^{1}(G) → dHD(G) ≃ HD(G)/ℂ, and for each i = 1, 2, ⋯, q, the vectors 1_{e_{i,1}}, 1_{e_{i,2}}, ⋯, 1_{e_{i,n_{i}}} ∈ C_{(2)}^{1}(G) are the characteristic functions of (all) the edges e_{i,1}, e_{i,2}, ⋯, e_{i,n_{i}} adjacent to the orbit representative ρ_{i} (see sect. 2.4). It is not hard to check that this quantity doesn’t depend on the particular unimodular quasi-transitive group of automorphisms H^{25} ^{26}. One defines the first ℓ^{2} Betti number of G by the same formula (see def. 2.10):

β_{1}(G) := \frac{1}{2T} ∑_{i=1}^{q} \frac{1}{m(K_{i})} ∑_{j=1}^{n_{i}} ⟨p(1_{e_{i,j}})|1_{e_{i,j}}⟩.

Clearly, β_{1}(G) = 0 if and only if G belongs to O_{HD} (see footnote 21).

Example 5.1 The leading example is the group H = ℤ/rℤ ∗ ℤ/sℤ acting on its Bass-Serre tree G: the bipartite tree with valencies r and s. The stabilizers are K_{1} = ℤ/rℤ and K_{2} = ℤ/sℤ and the components of X^{•} ≃ (ℤ/rℤ)\X ∐(ℤ/sℤ)\X identifie with pieces of X of measure \frac{1}{r} and \frac{1}{s}. By considering the cost of the graphing inherited by R^{fu} (see example 7.3 of Section 7 and Section 8), one computes: β_{1}(G) = β_{1}(R^{fu}, μ^{•}) = (\frac{1}{r} + \frac{1}{s})^{−1}[1 − (\frac{1}{r} + \frac{1}{s})]. In the particular case of the regular tree of even valency r = s = 2t, β_{1}(R^{fu}, μ^{•}) = t − 1 = β_{1}(F_{t}) coincide for H = ℤ/2tℤ ∗ ℤ/2tℤ or H = F_{t}.

Thanks to the map π : X → {0, 1}^{E}, each leaf of L^{fu} becomes a colored graph. The cluster lamination is obtained by removing all the 0-colored edges. Define the cluster equivalence relation R^{cl} on X^{•} by x^{•}R^{cl}y^{•} if and only if x^{•} and y^{•} are vertices of the same L^{cl}-leaf. It is a subrelation of R^{fu}.

The proof of Theorem 3.9 extends to quasi-transitive graphs with no modification.

25this is in fact true for the convex combination \frac{1}{T} ∑_{i=1}^{q} \frac{1}{m(K_{i})} ∑_{j=1}^{n_{i}} η(e_{i,j}) associated with any Aut(G)-invariant function η defined on the edges of G.

26It is most probably the case that the higher dimensional L^{2} Betti numbers β_{n}(R^{fu}, μ^{•}) are also invariants of the graph (in fact, of the automorphism group of the unimodular graph, with a normalization given by an appropriate combination of the Haar measures of the stabilizers of the vertices), but this would move us apart from the purpose of this paper.

Theorem 3.9* Assume that the closed subgroup H is unimodular and π_{∗}μ admits an H-equivariant virtually selected cluster. If G belongs to O_{HD}, then μ-a.e. virtually selected cluster belongs to O_{HD}. If G doesn’t belong to O_{HD}, then μ-a.e. virtually selected cluster doesn’t belong to O_{HD}. In particular, on the Borel set of subgraphs with one infinite cluster, the infinite cluster belongs (resp. doesn’t belong) to O_{HD} a.s. iff G belongs (resp. doesn’t belong) to O_{HD}.

We now turn to give the modifications in the statements of the quantitative estimates of section 4.

Theorem 4.2* Consider a unimodular quasi-transitive group H of automorphisms of G, two Hinvariant percolations μ_{1} and μ_{2} on G and an H-equivariant coupling

(X, μ)
π_{1} ↙  ↘^{π_{2}}
({0, 1}^{E}, μ_{1})  ({0, 1}^{E}, μ_{2})

Assume that

1. μ_{1}-a.e. cluster belongs to O_{HD},

2. π_{2} has an H-equivariant selected cluster defined on a non-null set^{27}, then

β_{1}(G) ≤ \frac{1}{2T} [∑_{i=1}^{q} \frac{1}{m(K_{i})} ∑ ; edges e adjacent to ρ_{i} μ(π_{2}(e) = 1 and π_{1}(e) = 0)].

The only modifications in the proof of Theorem 4.2 are the bound on cost(Ψ_{2}):

cost(Ψ_{2}) ≤ \frac{1}{2μ^{•}(Y)} \frac{1}{T} ∑_{i=1}^{q} \frac{1}{m(K_{i})} ∑ ; edges e_{i,j} adjacent to ρ_{i} μ(π_{2}(e) = 1 and π_{1}(e) = 0),

and the definition of the measurable subset Z ⊂ X^{•}: For at least one of the ρ_{i}, the set of those x ∈ X whose selected cluster contains ρ_{i} is non-null. Take for Z its image in X^{•}. ■

Application to Bernoulli Percolation (subsection 4.1*).

Corollary 4.5* Let G be a unimodular quasi-transitive locally finite graph. If G doesn’t belong to O_{HD}, then the nonuniqueness phase interval of Bernoulli percolation has non-empty interior:

p_{c}(G) < p_{u}(G)

More precisely,

0 < β_{1}(G) ≤ \frac{1}{2T} ∑_{i=1}^{q} \frac{deg(ρ_{i})}{m(K_{i})}(p_{u}(G) − p_{c}(G)).

where deg(ρ_{i}) is the number of edges in G that are adjacent to ρ_{i}. ■

27For instance, if μ_{2} has a non-null set of subgraphs with exactly one infinite cluster.

Application to Random-Cluster Model (subsection 4.2*).

Corollary 4.7* Let G be a unimodular quasi-transitive locally finite graph, not in O_{HD}. Fix the parameter q ∈ [1, ∞). The gap between the left limit (when p ↗ p_{c}(q)) and the right limit (when p ↘ p_{u}(q)) of the expected degree of a base point ρ with respect to the measure RC_{p,q} satisfies:

0 < β_{1}(G) ≤ \frac{1}{2T} ∑_{i=1}^{q} \frac{1}{m(K_{i})}(RC_{p_{u}+,q}[deg(ρ_{i})] − RC_{p_{c}−,q}[deg(ρ_{i})]).

Here, RC either denotes WRC or FRC, and RC_{p,q}[deg(ρ_{i})] is the mean degree of the vertex ρ_{i} in the random subgraph for the random-cluster measure RC with parameters p and q. Also RC_{p_{u}+,q}[deg(ρ_{i})] := lim_{p↘p_{u}(q)} RC_{p,q}[deg(ρ_{i})] and RC_{p_{c}−,q}[deg(ρ_{i})] := lim_{p↗p_{c}(q)} RC_{p,q}[deg(ρ_{i})]. ■

6 Harmonic Dirichlet Functions and ℓ^{2} Cohomology

The main result of the section is the technical Proposition 6.6 that will allow to make the connection between harmonic Dirichlet functions and the definitions of L^{2} Betti numbers for equivalence relations in [Gab02] (see the proof of Theorem 7.5). However, as a leading and motivating example, we will consider the following well-known result relating harmonic Dirichlet functions with the first ℓ^{2} Betti number.

Theorem 6.1 Let Γ be a finitely generated group. Its first ℓ^{2} Betti number β_{1}(Γ) is not zero if and only if any of its Cayley graphs admits nonconstant harmonic Dirichlet functions.

6.1 Harmonic Dirichlet Functions…

Let G = (V, E) be a connected graph^{28} with bounded degree. The tail and head of an oriented edge ê are denoted by ê^{−} and ê^{+}.

Denote by F(V) or C^{0}(G) the space of all complex-valued functions (0-cochains) on V and by C^{1}(G) the space of 1-cochains^{29}. Define the coboundary, “boundary” and Laplace maps:

d : C^{0}(G) ⟶ C^{1}(G)  df(ê) = f(ê^{+}) − f(ê^{−})
d^{∗} : C^{1}(G) ⟶ C^{0}(G)  d^{∗}g(v) = ∑_{{ê: ê^{+}=v}} g(ê)
Δ : C^{0}(G) ⟶ C^{0}(G) Δf(v) = d^{∗}df(v) = ∑_{{ê: ê^{+}=v}}(f(ê^{+}) − f(ê^{−}))
= deg(v)f(v) − ∑_{{ê: ê^{+}=v}} f(ê^{−})

The spaces of ℓ^{2}-cochains will be denoted by C_{(2)}^{0}(G) and C_{(2)}^{1}(G). By definition, the space of harmonic Dirichlet functions on G is the space of functions whose value at each v equals the mean of the values at its neighbors (Δ(f) = 0, i.e. f is harmonic) and with coboundary in ℓ^{2} (f has finite energy or finite Dirichlet sum):

HD(G) := {f ∈ F(V) : df ∈ C_{(2)}^{1}(G) and Δf = 0}.

28In the whole Section 6, except in the examples, G is not assumed to have any kind of symmetries or automorphisms.

29i.e. the space of anti-symmetric functions on the set of oriented edges: f(ě) = −f(ê) where ě is the edge ê with the reverse orientation

The kernel of d clearly consists of the constant functions (since G is connected), so that naturally

HD(G)/ℂ ≃ d(HD(G)) = Imd ∩ C_{(2)}^{1}(G) ∩ Kerd^{∗}.  (4)

As for the ℓ^{2} cohomology, it is not really that of the graph G that is of interest, since, for example, for Cayley graphs it is too sensitive to changes of generators (think of Cayley graphs of ℤ, where H̄_{(2)}^{1} = 0 or ≠ 0 according to whether the generating system is (1) or (2, 3)). One has first to “fill in the holes” of the graph: Consider a simply-connected 2-dimensional complex Σ, with G as 1-skeleton.

Example 6.2 For instance, let Γ be a group given by a presentation with g generators and r relators. Recall that the Cayley complex of the presentation is a 2-dimensional complex built from a bouquet of g oriented circles labeled by the generators, together with r oriented disks labeled by the relators glued along their boundary to this 1-dimensional skeleton by following successively the circles associated with the labeling relator. Its fundamental group is (isomorphic to) Γ. The universal cover Σ of the Cayley complex is a (simply connected) 2-dimensional complex (with a free action of Γ and) with the Cayley graph of Γ as 1-skeleton.

More generally, Σ can be obtained from G by gluing one oriented disk (thought of as a polygon) along its boundary to each circuit (and the opposite orientation for the reverse circuit).

Denote by C^{2}(Σ) the space of 2-cochains, i.e. anti-symmetric functions on the oriented 2-cells –disks–), by C_{(2)}^{2}(Σ) the space of those that are ℓ^{2} (i.e. ∑_{σ} h(σ)^{2} < ∞, where the sum is over all the 2-cells σ). The boundary of a 2-cell σ in Σ being a 1-cycle D^{∗}σ, one defines the coboundary D by Dg(σ) = g(D^{∗}σ).

C^{0}(Σ) ⟶^{d} C^{1}(Σ) ⟶^{D} C^{2}(Σ)

By taking the adjoint, C_{(2)}^{1}(Σ) ∩ Kerd^{∗} = [dC_{(2)}^{0}(Σ)]^{⊥C_{(2)}^{1}}, the orthogonal of Imd_{(2)} = dC_{(2)}^{0}(Σ) in C_{(2)}^{1}(Σ). Since Σ is simply connected, Imd = KerD. From formula (4) we get the natural isomorphisms

HD(G)/ℂ ≃ KerD ∩ C_{(2)}^{1}(Σ) ∩ [dC_{(2)}^{0}(Σ)]^{⊥} ≃ \frac{KerD ∩ C_{(2)}^{1}(Σ)}{\overline{Im}d_{(2)}},  (5)

where \overline{Im}d_{(2)} is the closure of the space Imd_{(2)}.

6.2 … and ℓ^{2} cohomology

To define ℓ^{2} cohomology of Σ, one is led to consider ℓ^{2} cochains and restrictions of the coboundary maps:

C_{(2)}^{0}(Σ) ⟶^{d_{(2)}} C_{(2)}^{1}(Σ) ⟶^{D_{(2)}} C_{(2)}(Σ)

Say that Σ is uniformly locally bounded (ULB) if it admits a uniform bound M s.t. each vertex (resp. edge) belongs to at most M edges (resp. 2-cells), and the boundary of each 2-cell has length at most M. In this situation, D_{(2)} is a bounded operator, and the standard first reduced ℓ^{2} cohomology space of Σ is defined as the Hilbert space

H̄_{(2)}^{1}(Σ) := \frac{KerD_{(2)}}{\overline{Im}d_{(2)}} = \frac{KerD ∩ C_{(2)}^{1}(Σ)}{\overline{Im}d_{(2)}}.

It follows from (5) that for a ULB Σ

HD(G)/ℂ ≃ H̄_{(2)}^{1}(Σ).  (6)

Example 6.3 Σ is ULB if it comes from the Cayley complex of a finitely presented group. One can show that any other simply connected, cocompact free Γ-complex Σ′ leads to a (Γ-equivariantly) isomorphic H̄_{(2)}^{1}(Σ′), so that the non-triviality of H̄_{(2)}^{1}(Σ) is an invariant of the group Γ, and not only of the complex Σ. The first ℓ^{2} Betti number β_{1}(Γ) is the von Neumann Γ-dimension dim_{Γ}H̄_{(2)}^{1}(Σ) and we retain from this dimension theory that it vanishes iff H̄_{(2)}^{1}(Σ) = {0}.

Observe that some finiteness condition on Σ is however necessary since the free group F_{2}, for example, acts on its Cayley tree as well as on the product of the tree with a line, whose 1-skeleton admits (resp. doesn’t admit) nonconstant harmonic Dirichlet functions. In case the presentation of Γ is not finite (r = ∞), Σ is no longer Γ-cocompact, and D_{(2)} is no longer a continuous (=bounded) map.

The general way to proceed to define ℓ^{2} cohomology for a complex that is not ULB, in the spirit of J. Cheeger and M. Gromov [CG86], consists in approximating Σ by its ULB subcomplexes. Consider the directed set of ULB subcomplexes Σ_{t} of Σ, directed by inclusion and the inverse system of reduced ℓ^{2} cohomology spaces H_{(2)}^{n}(Σ_{t}) of Σ_{t} with the maps H_{(2)}^{n}(Σ_{s}) → H_{(2)}^{n}(Σ_{t}) induced by inclusion Σ_{s} ⊃ Σ_{t} (denoted by s ≥ t). Then define the reduced ℓ^{2} cohomology as the inverse limit H_{(2)}^{n}(Σ) := lim_{←}H_{(2)}^{n}(Σ_{t}).

In our context, all the ULB complexes Σ_{t}, as well as Σ itself, share the same ULB 1-skeleton G. Thus, the first reduced ℓ^{2} cohomology spaces H̄_{(2)}^{1}(Σ_{t}) are each the quotient of the subspace

Ker(C_{(2)}^{1}(G) ⟶^{D} C_{(2)}^{2}(Σ_{t})) of C_{(2)}^{1}(G) (organized into an inverse system by inclusion), by the common

subspace \overline{Im}d_{(2)}. It follows that:

H̄_{(2)}^{1}(Σ) = lim_{←}H̄_{(2)}^{1}(Σ_{t}) = \frac{⋂_{t} Ker(C_{(2)}^{1}(G) ⟶^{D} C_{(2)}^{2}(Σ_{t}))}{\overline{Im}d_{(2)}} = \frac{KerD ∩ C_{(2)}^{1}(G)}{\overline{Im}d_{(2)}}  (7)

and by formula (5), valid for any Σ:

H̄_{(2)}^{1}(Σ) ≃ HD(G)/ℂ.  (8)

Example 6.4 Let Γ be finitely generated, but not necessarily finitely presented. For a Γ-complex Σ, the Σ_{t} are moreover required to be Γ-invariant (and cocompact) and the ℓ^{2} Betti numbers of the Γ-action on Σ are defined by keeping track of the Γ-dimensions:

β_{n}(Σ, Γ) := sup_{t} dim_{Γ}\overline{Im}(H̄_{(2)}^{n}(Σ) → H̄_{(2)}^{n}(Σ_{t}))
= sup_{t} dim_{Γ} ∩_{s≥t} \overline{Im}(H̄_{(2)}^{n}(Σ_{s}) → H̄_{(2)}^{n}(Σ_{t}))

For simply connected Γ-complexes Σ, the value β_{1}(Σ, Γ) doesn’t depend on a particular choice of Σ, so that for Σ constructed from a Cayley complex of Γ,

β_{1}(Γ) = β_{1}(Σ, Γ) = dim_{Γ}HD(G)/ℂ

vanishes if and only if HD(G)/ℂ = {0}. This proves Theorem 6.1.

Let’s quote for further use the observation that the space of formula (7) may be obtained by considering a exhausting sequence instead of the whole inverse system:

Proposition 6.5 Let G be a graph with finite degree, Σ a simply-connected 2-dimensional complex with 1-skeleton G. If (Σ_{t})_{t∈ℕ} is an increasing and exhausting sequence of ULB subcomplexes of Σ, then for any fixed t

∩_{s≥t}Im(H̄_{(2)}^{1}(Σ_{s}) → H̄_{(2)}^{1}(Σ_{t})) = \frac{KerD ∩ C_{(2)}^{1}(G)}{\overline{Im}d_{(2)}}

doesn’t depend on t and is NATURALLY isomorphic with HD(G)/ℂ.

The connection with the simplicial framework of [Gab02] is made by considering a double barycentric subdivision Σ^{∗} of Σ, with the exhaustion Σ_{t}^{∗} corresponding to the subdivision of Σ_{t}. Since for each t, H̄_{(2)}^{1}(Σ_{t}) and H̄_{(2)}^{1}(Σ^{∗}) are naturally isomorphic, it follows that

Proposition 6.6 For any fixed t, ∩_{s≥t}Im(H̄_{(2)}^{1}(Σ_{s}^{∗}) → H̄_{(2)}^{1}(Σ_{t}^{∗})) doesn’t depend on t and is NATU-RALLY isomorphic with d(HD(G)) and HD(G)/ℂ.

7 Fields of Graphs, Harmonic Dirichlet Functions and L^{2} Betti Numbers for Equivalence Relations

Let (X, μ) be a standard Borel space with a probability measure μ and R a measure-preserving Borel equivalence relation with countable classes.

Recall from [Gab02] that an R-equivariant field x ↦ Σ_{x} of simplicial complexes is a measurable assignment to each x ∈ X of a simplicial complex Σ_{x}, together with an “action” of R, i.e. with the measurable data of a simplicial isomorphism, for every (x, y) ∈ R, ψ_{x,y} : Σ_{y} → Σ_{x} such that ψ_{x,y}ψ_{y,z} = ψ_{x,z} and ψ_{z,z} = id_{Σ_{z}}. It is smooth if the action on the vertices admits a Borel fundamental domain. It is smooth uniformly locally bounded if there is a uniform bound N on the degree of the 1-skeleton of the Σ_{x}, and there is a Borel fundamental domain that meets each Σ_{x} in at most N vertices.

Example 7.1 Let R be a p.m.p. countable Borel equivalence relation on the probability standard Borel space (X, μ). An unoriented graphing Ψ over R (see Section 8) defines an R-equivariant field of graphs x ↦ Ψ_{x} with vertex set R itself, which is smooth.

- The vertex set of Ψ_{x} is the set {(x, y) ∈ R}, i.e. the set of elements of R with first coordinate x.

- Two vertices (x, y) and (x, z) of Ψ_{x} are neighbors if and only if (y, z) belongs to Ψ, i.e. iff the second coordinates are neighbor for Ψ

- The left action of R on itself (w, x).(x, y) = (w, y) and thus on the set of vertices induces a natural

action on the field: (w, x) : ( \begin{matrix}Ψ_{x} & ⟶ & Ψ_{w} \\ [(x, y), (x, z)] & ↦ & [(w, y), (w, z)] \end{matrix} ).

- The “diagonal” set {(x, x) : x ∈ X} of vertices forms a Borel fundamental domain.

This example contains as main applications the various equivariant fields of graphs (described below) relevant for percolation theory.

Example 7.2 In the context of Section 1 for a Cayley graph G, (R^{fu}, x ↦ G) The full lamination L^{fu} (Section 1.1) defines an unoriented graphing over R^{fu} (see

Section 8). In the corresponding smooth R^{fu}-equivariant field x ↦ L_{x}^{fu}, each L_{x}^{fu} admits a canonical isomorphism with G.

(R^{cl}, x ↦ π(x)(ρ)) The cluster lamination L^{cl} defines an unoriented graphing over R^{cl}. In the corresponding smooth R^{cl}-equivariant field x ↦ L_{x}^{cl}, each L_{x}^{fu} is isomorphic to the cluster π(x)(ρ) of ρ in π(x).

(R^{fu}, x ↦ π(x)) The cluster lamination L^{cl} defines also an unoriented graphing over R^{fu} and in the corresponding field x ↦ Ψ_{x}, each Ψ_{x} is isomorphic to the subgraph π(x), which is non-connected in general.

Example 7.3 In the context of Section 2 for a transitive, locally finite graph G,

(R^{fu}, x^{•} ↦ G) The full lamination L^{fu} (Section 2.1) defines an unoriented graphing over R^{fu}. In the corresponding smooth R^{fu}-equivariant field x^{•} ↦ L_{x^{•}}^{fu} each L_{x^{•}}^{fu} admits a (non-canonical) isomorphism with G. However, each representative x ∈ X of x^{•} defines an isomorphism j_{x} : L_{x^{•}}^{fu} ≃ G and for another one y = kx, j_{y} = kj_{x}, where k ∈ K_{ρ} so that this isomorphism is canonical up to an element of K_{ρ}.

(R^{cl}, x^{•} ↦ π(x)(ρ)) The cluster lamination L^{cl} defines an unoriented graphing over R^{cl}. The corresponding field x^{•} ↦ L_{x^{•}}^{cl} assigning to x^{•} its leaf (graph) in the lamination L^{cl} is a smooth uniformly locally bounded R^{cl}-equivariant field of connected graphs. Each L_{x^{•}}^{fu} is isomorphic to the cluster π(x)(ρ) of ρ for a (any) representative x ∈ X of x^{•}. Two representatives give subgraphs of G that are isomorphic under an element of K_{ρ}. The graph L_{x^{•}}^{cl} belongs to O_{HD} iff π(x)(ρ) belongs to O_{HD} for any representative x of x^{•}.

Example 7.4 (Restrictions) If x ↦ Ψ_{x} is a smooth R-equivariant field of graphs and Y is a Borel subset then restricted to Y, the fields Y ∋ x ↦ Ψ_{x} is a smooth R_{|Y} -equivariant field of graphs, where R_{|Y} is the restriction of R to Y.

Also recall from [Gab02] that there is a well-defined notion of L^{2} Betti numbers β_{n}(R, μ) for a measure-preserving Borel equivalence relation R with countable classes, which uses the notion of equivariant fields of simplicial complexes and the von Neumann dimension dim_{R} associated with the von Neumann algebra of the equivalence relation and the measure μ.

Theorem 7.5 Let R be a measure-preserving equivalence relation with countable classes on the standard Borel probability measure space (X, μ). Consider a smooth uniformly locally bounded R-equiva-riant field x ↦ G_{x} of connected graphs. Then

β_{1}(R, μ) = dim_{R} ∫_{X}^{⊕} d(HD(G_{x})) dμ(x) = dim_{R} ∫_{X}^{⊕} HD(G_{x})/ℂ dμ(x).

Since dim_{R}H = 0 if and only if H = {0}, one gets:

Corollary 7.6 For a smooth uniformly locally bounded R-equivariant field x ↦ G_{x} of connected graphs, β_{1}(R, μ) = 0 if and only if μ a.s. G_{x} ∈ O_{HD}.

Remark 7.7 Since a generating (oriented) graphing in the sense of [Lev95, Gab00] (see also Section 8) defines an unoriented graphing and thus a smooth R-equivariant field of connected graphs, the above Corollary 7.6 reduces to Theorem 0.3 of the introduction.

Proof: By Theorem/Definition [Gab02, Th. 3.13, Déf. 3.14], β_{1}(R, μ) is the first L^{2} Betti number β_{1}(Σ, R, μ) of ANY smooth R-equivariant field of simply connected (2-dimensional, say) simplicial complexes Σ. It can be computed [Gab02, prop. 3.9] by using any exhausting increasing sequence (Σ_{s})_{s∈ℕ} of R-invariant uniformly locally bounded (ULB) sub-complexes by the following formula (9):

β_{1}(Σ, R, μ) = lim_{s→∞}↗ lim_{s≥t s→∞} ↘ dim_{R} \overline{Im}[H̄_{1}^{(2)}(Σ_{t}, R, μ) → H̄_{1}^{(2)}(Σ_{s}, R, μ)]  (9)
= lim_{t→∞}↗ lim_{s≥t s→∞} ↘ dim_{R} \overline{Im}[H̄_{(2)}^{1}(Σ_{s}, R, μ) → H̄_{(2)}^{1}(Σ_{t}, R, μ)]  (10)
= lim_{t→∞}↗ dim_{R} ⋂_{s≥t s→∞}\overline{Im}[H̄_{(2)}^{1}(Σ_{s}, R, μ) → H̄_{(2)}^{1}(Σ_{t}, R, μ)]  (11)

The equality (10) holds by duality between homology and cohomology because, just as in usual linear algebra, taking dual does not alter the dimension of the image. Equality (11) is due to the continuity of dimension, since \overline{Im}[H̄_{(2)}^{1}(Σ_{s}, R, μ) → H̄_{(2)}^{1}(Σ_{t}, R, μ)] ⊂ H̄_{(2)}^{1}(Σ_{t}, R, μ) decreases with s. Now, for a fixed t, one has the Hilbert integral decomposition:

⋂_{s≥t s→∞}\overline{Im}[H̄_{(2)}^{1}(Σ_{s}, R, μ) → H̄_{(2)}^{1}(Σ_{t}, R, μ)] = ∫_{X}^{⊕} ⋂_{s≥t s→∞}\overline{Im}[H̄_{(2)}^{1}(Σ_{s,x}) → H̄_{(2)}^{1}(Σ_{t,x})]dμ(x) (12)

It remains to make the choice of a Σ and of the sequence (Σ_{t})_{t∈ℕ} and to relate this with harmonic Dirichlet functions via Section 6. The simplicial complex Σ_{t,x} is obtained from G_{x} by first gluing a disk along each circuit of length t and then taking the second barycentric subdivision. The simplicial complex Σ_{x} is their union. For each s, it follows from naturality in Proposition 6.6, applied for each x, that there is an isomorphism of Hilbert R-modules:

∫_{X}^{⊕} ⋂_{s≥t s→∞}\overline{Im}[H̄_{(2)}^{1}(Σ_{s,x}) → H̄_{(2)}^{1}(Σ_{t,x})]dμ(x) ≃ ∫_{X}^{⊕} HD(G_{x})/ℂ dμ(x)  (13)

so that its R-dimension does not depend on t, and Theorem 7.5 is proved by putting the equalities (11), (12) and (13) together. ■

8 Some Background about Measured Equivalence Relations

In this section, we just recall briefly the definition of some notions appearing in the paper. The reader may consult [FM77] and [Gab00, Gab02] for more details and more references.

Countable standard equivalence relation. A countable standard equivalence relation on the standard Borel space (X, μ) is an equivalence relation R with countable classes that is a Borel subset of X × X for the product σ-algebra.

Preservation of the measure. The (countable standard) equivalence relation R is said to preserve the measure if for every partially defined isomorphism φ : A → B whose graph is contained in R ({(x, φ(x)) : x ∈ A} ⊂ R), one has μ(A) = μ(B), or equivalently iff the measures ν_{1} and ν_{2} on the set R ⊂ X × X coincide, defined with respect to the projections on the first (resp. second) coordinate pr_{1} (resp. pr_{2}) by ν_{1}(C) = ∫_{X} #(C ∩ pr_{1}^{−1}(x))dμ(x) and ν_{2}(C) = ∫_{X} #(C ∩ pr_{2}^{−1}(y))dμ(y). One denotes by ν = ν_{1} = ν_{2} this common (usually infinite) measure on R.

Essentially Free Action. A Borel action of H on a standard probability measure space (X, μ) is essentially free if the Borel subset of points x ∈ X with non-trivial stabilizer (Stab_{H}(x) = {h ∈ H : hx = x} ≠ {id}) has μ-measure 0. The term “essentially” is frequently omitted.

Restrictions. Let (X, μ) be a standard Borel space with a probability measure μ and R a measurepreserving Borel equivalence relation. If Y is a Borel subset of X of non-zero measure, denote by μ_{Y} := \frac{μ_{|Y}}{μ(Y)} the normalized probability measure on Y. The restriction R_{Y} of R to Y is the μ_{Y} - measure-preserving Borel equivalence relation on Y defined by for every x, y ∈ Y, xR_{Y} y ⇔ xRy.

Saturation. A Borel subset U ⊂ X is called R-saturated if it is a union of R-classes. The Rsaturation of a Borel set U is the smallest R-saturated set containing it. It is the union of the R-classes meeting U.

Finite index. A sub-equivalence relation S ⊂ R has finite index in R if each R-class decomposes into finitely many S-classes. If this number is constant, it is called the index of S in R and is denoted by [R : S].

Graphings. A probability measure-preserving oriented graphing on (X, μ) is an at most countable family Φ = (φ_{i})_{i∈I} of partial measure-preserving isomorphisms φ_{i} : A_{i} → B_{i} between Borel subsets A_{i}, B_{i} ⊂ X.

A probability measure-preserving unoriented graphing Ψ on (X, μ) is a Borel subset of X × X \ {(x, x) : x ∈ X} that is symmetric under the flip (x, y) ↔ (y, x) such that the smallest equivalence relation R_{Ψ} containing it has coutable classes and is measure-preserving. It provides a Borel choice of pairs of R_{Ψ}-equivalent points (“neighbors”), and thus a graph structure on each equivalence class of R_{Ψ}. When these graphs are (almost) all trees, the graphing is called a treeing.

R_{Ψ} is generated by Ψ.

Ψ is a graphing over R if it is contained in R.

An oriented graphing defines clearly an unoriented one, by considering the graphs of the φ_{i}, φ_{i}^{−1}’s. The terms probability measure-preserving, oriented and unoriented are frequently omited.

The notion of unoriented graphing has been introduced by S. Adams in [Ada90] and oriented graphing by G. Levitt, together with the notion of cost, in [Lev95].

Cost. The cost of an unoriented graphing Ψ is the number cost(Ψ, μ) := \frac{1}{2}ν(Ψ), where ν is the witness measure on R_{Ψ} for R_{Ψ} to preserve the measure μ of X.

The cost of an oriented graphing Φ = (φ_{i})_{i∈I}, is the sum of the measures of the domains ∑_{i∈I} μ(A_{i}).

Except in the obvious cases (redundancy in Φ), the two notions coincide. In general the cost of an oriented graphing is greater than that of the associated unoriented one.

The cost (cost(R, μ)) of a p.m.p. countable equivalence relation R is the infimum of the costs of the generating graphings. The cost of a group Γ is the infimum of cost(R, μ) over all equivalence relations R defined by a p.m.p. free actions of Γ (see [Gab00]). A comparison has been established between the cost and the first L^{2} Betti number: β_{1}(R, μ) ≤ cost(R, μ) − 1 [Gab02, Cor. 3.23]. Despite that equality is not known to be true in general for an R with only infinite classes, there is no (not yet ?) counterexample. However, when Ψ is a treeing, then β_{1}(R_{Ψ}, μ) = cost(R_{Ψ}, μ) − 1 = cost(Ψ) − 1 ([Gab02, Cor. 3.23] and [Gab00, Th. 1]).

References

[Ada90] S. Adams. Trees and amenable equivalence relations. Ergodic Theory Dynamical Systems, 10(1):1–14, 1990.

[Ati76] M. Atiyah. Elliptic operators, discrete groups and von Neumann algebras. In Colloque “Analyse et Topologie” en l’Honneur de Henri Cartan (Orsay, 1974), pages 43–72. Astérisque, SMF, No. 32–33. Soc. Math. France, Paris, 1976.

[BBCK00] M. Biskup, C. Borgs, J.T. Chayes, R. Kotecký. Gibbs states of graphical representations of the Potts model with external fields. J. Math. Phys., 41(3): 1170–1210, 2000.

[BB99] E. Babson, I. Benjamini. Cut sets and normed cohomology with applications to percolation. Proc. Amer. Math. Soc., 127(2):589–597, 1999.

[BK89] R. Burton, M. Keane. Density and uniqueness in percolation. Comm. Math. Phys., 121(3):501–505, 1989.

[BLPS99a] I. Benjamini, R. Lyons, Y. Peres, O. Schramm. Group-invariant percolation on graphs. Geom. Funct. Anal., 9(1):29–66, 1999.

[BLPS99b] I. Benjamini, R. Lyons, Y. Peres, O. Schramm. Critical percolation on any nonamenable group has no infinite clusters. Ann. Probab., 27(3):1347–1356, 1999.

[BLS99] I. Benjamini, R. Lyons, O. Schramm. Percolation perturbations in potential theory and random walks in Random walks and discrete potential theory (Cortona, 1997), pages 56–84, Sympos. Math., XXXIX, Cambridge Univ. Press, 1999.

[BS96] I. Benjamini, O. Schramm. Percolation beyond ℤ^{d}, many questions and a few answers. Electron. Comm. Probab., 1:no. 8, 71–82 (electronic), 1996.

[BS01] I. Benjamini, O. Schramm. Percolation in the hyperbolic plane. Jour. Amer. Math. Soc., 14: 487–507, 2001.

[BV97] M. Bekka, A. Valette. Group cohomology, harmonic functions and the first L^{2}-Betti number. Potential Anal., 6(4):313–326, 1997.

[CG86] J. Cheeger, M. Gromov. L_{2}-cohomology and group cohomology. Topology, 25(2):189–215, 1986.

[FK72] C.M. Fortuin, P.W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57, 536–564, 1972.

[FM77] J. Feldman, C. Moore. Ergodic equivalence relations, cohomology and von Neumann algebras. I and II. Trans. Amer. Math. Soc., 234(2):289–324, 325–359, 1977.

[Gab00] D. Gaboriau. Coût des relations d’équivalence et des groupes. Invent. Math., 139(1):41–98, 2000.

[Gab02] D. Gaboriau. Invariants L^{2} de relations d’équivalence et de groupes. Publ. math. Inst. Hautes Étud. Sci., 95(1):93–150, 2002.

[GN90] G. R. Grimmett, C. M. Newman. Percolation in ∞+1 dimensions. In Disorder in physical systems, Oxford Sci. Publ., pages 167–190. Oxford Univ. Press, New York, 1990.

[HJL02a] O. Häggström, J. Jonasson, R. Lyons. Coupling and Bernoullicity in random-cluster and Potts models. Bernoulli; 8(3): 275–294, 2002.

[HJL02b] O. Häggström, J. Jonasson, R. Lyons. Explicit isoperimetric constants and phase transitions in the Random-Cluster Model. Ann. of Proba. 30 (1):443–473, 2002.

[HP99] O. Häggström, Y. Peres. Monotonicity of uniqueness for percolation on Cayley graphs: all infinite clusters are born simultaneously. Probab. Theory Related Fields, 113(2):273–285, 1999.

[HPS99] O. Häggström, Y. Peres, R. H. Schonmann. Percolation on transitive graphs as a coalescent process: relentless merging followed by simultaneous uniqueness. In Perplexing problems in probability, volume 44 of Progr. Probab., pages 69–90. Birkhäuser Boston, Boston, MA, 1999.

[Kec95] A. Kechris. Classical descriptive set theory, Graduate Texts in Mathematics, 156, Springer-Verlag, New York, 1995.

[Lev95] G. Levitt. On the cost of generating an equivalence relation. Ergodic Theory Dynam. Systems, 15(6):1173–1181, 1995.

[Lyo95] R. Lyons. Random walks and the growth of groups. C. R. Acad. Sci. Paris Sér. I Math., 320:1361–1366, 1995.

[LP05] R. Lyons, Y. Peres. Probability on Trees and Networks. Book in preparation. To appear. Cambridge University Press. http://mypage.iu.edu/∼rdlyons/prbtree/prbtree.html.

[LS99] R. Lyons, O. Schramm. Indistinguishability of percolation clusters. Ann. Probab., 27(4):1809–1836, 1999.

[Lyo00] R. Lyons. Phase transitions on nonamenable graphs. J. Math. Phys. 41, 1099–1126. Probabilistic techniques in equilibrium and nonequilibrium statistical physics, 2000.

[Mar03] F. Martin. Analyse harmonique et 1-cohomologie réduite des groupes localement compacts. Thèse de l’université de Neuchâtel, 2003.

[Per00] Y. Peres Percolation on nonamenable products at the uniqueness threshold. Ann. Inst. H. Poincaré Probab. Statist.36(5), 395–406, 2000.

[PP00] Y. Peres, R. Pemantle Nonamenable products are not treeable. Israel J. Math.118, 147–155, 2000.

[PSN00] I. Pak, T. Smirnova-Nagnibeda. On non-uniqueness of percolation on nonamenable Cayley graphs. C. R. Acad. Sci. Paris Sér. I Math., 330(6):495–500, 2000.

[Sau03] R. Sauer. L^{2}-Betti Numbers of Discrete Measured Groupoids. Preprint arXiv math.AT/0312411.

[Soa93] P. M. Soardi. Rough isometries and Dirichlet finite harmonic functions on graphs. Proc. Amer. Math. Soc., 119(4):1239–1248, 1993.

D. G.: UMPA, UMR CNRS 5669, ENS-Lyon, 69364 Lyon Cedex 7, FRANCE

gaboriau@umpa.ens-lyon.fr