Universita degli Studi di Roma“Sapienza”

Dipartimento diMatematica Guido Castelnuovo

FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALICorso di Laurea Specialistica in Matematica

Costo per i Gruppoidi Discreti e Misurabili

Tesi di Laurea

Relatore:Prof.Damien Gaboriau

Relatrice interna:Prof.Claudia Pinzari

Laureando:Alessandro CarderiMatricola: 1171193

Anno Accademico 2010/2011

Alessandro Carderi

Cost for Discrete Measured Groupoids

Master Thesis in Mathematics

Contents

1 An introduction to orbit equivalence 41.1 What is orbit equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Actions of a countable group . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Other examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Orbit equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1 Measured discrete equivalence relations . . . . . . . . . . . . . . . . 81.4 Amenable vs Non-amenable . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.1 Amenability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.2 Non-amenability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Cost for equivalence relations . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5.1 Cost in group theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5.2 Treeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Cost for Discrete Measured Groupoids 162.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.1 Groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.2 Cost for groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.3 Cost for free groupoids . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.4 Cost in theory of (countable) groups . . . . . . . . . . . . . . . . . . 18

2.2 Borel and measured discrete groupoids . . . . . . . . . . . . . . . . . . . . 192.2.1 Fibred spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2.2 Discrete measured groupoids . . . . . . . . . . . . . . . . . . . . . . 212.2.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2.4 Path/free groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2.5 Groupoid actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.6 Totally isotropic sub-groupoids . . . . . . . . . . . . . . . . . . . . . 292.2.7 Bernoulli actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2.8 Free products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.2.9 G-fields of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3 Groupoid Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.3.1 Compatibility with other definitions . . . . . . . . . . . . . . . . . . 362.3.2 Case of finite-rank isotropy . . . . . . . . . . . . . . . . . . . . . . . 382.3.3 Cost of free groupoids and free products . . . . . . . . . . . . . . . 41

2.4 Cost of free groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.4.1 Group case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2

2.4.2 Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.4.3 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502.4.4 Main proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512.4.5 Cost of free groupoids . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.5 Groupoid Cost of a group . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532.5.1 Cost for direct products . . . . . . . . . . . . . . . . . . . . . . . . . 552.5.2 Free products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582.5.3 Normal Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Bibliography 69

3

Chapter 1

An introduction to orbit equivalence

What follows is here to introduce the reader who has never heard anything on thesubject of orbit equivalence. Very good surveys have been written about (and readingthese we took our inspiration): depending on the reader interest and time, we reallyrecommend the long paper by Furman [17] and (or) the brief introduction (containing arich bibliography) by Gaboriau [20].

We tried to make the second and main chapter independent of this introduction, sothat any acknowledged reader can skip this first part.

1.1 What is orbit equivalence

The world of countable groups is a wild and unknown world. Even the family offinitely generated groups can not be classified, in a precise set-theoretical meaning, andthe discovered groups are an insignificant part of this world. In order to understand betterthis world, one can study general properties of subclasses of groups, like amenability orproperty (T). Groups in the same class behave similarly in some kind of situations (butmaybe in a complete different way in others) and in this way we can get some informationson these interesting objects. One of the most common way to study groups, is to studyactions on some particular spaces. Orbit equivalence is a way to study countable groupsusing measure-theoretic tools.

Orbit equivalence regards actions of countable discrete groups on standard measurespace. The girth of orbit equivalence is related to von Neumann algebras and the “groupmeasure space” construction, but the first important results were obtained by Dye, [12]and [13]. Starting from these works, many authors get interested in the subject andnow orbit equivalence (and measured group theory) is a living and growing area ofmathematics. It has maintained its original connection with von Neumann algebrasand it is strongly linked with geometric group theory, descriptive set theory, percolationtheory. . . The more these connections become stronger the more we can regard inside thetheory and understand better the theory and its implications in the world of countablegroups.

4

1.2 Actions of a countable group

Let (X, µ) be a diffuse standard probability space, that is a standard Borel space X,equipped with a non-atomic probability measure µ. All such spaces are measurablyisomorphic, see for example [26], so one can suppose that X is the interval [0, 1] and themeasure µ is the Lebesgue measure. Let G be a countable group.

Definition 1.2.1. An action of G on (X, µ) is measurable if for each 1 ∈ G the application1 : X→ X is a measurable map. The action is probability measure preserving (shortly p.m.p.), if for every measurable subset A ⊂ Xwe have

µ(1A) = µ(A).

Before giving other definitions, we give some examples of p.m.p. actions.

Example 1.2.2. 1. For every α ∈ R, we can consider the action of the group of integersG := Z on the circle (X, µ) := (S1,Leb) by rotation of angle α.

2. For every measure-preserving automorphism T of (X, µ), we can define an action ofZ on X as n · x = Tn(x) for every n ∈ Z and x ∈ N.

3. More generally, given any T1, . . . ,Tn measure preserving automorphisms, we candefine in the same way an action of the free group Fn.

4. Given a compact group K and a discrete countable subgroup G < K, we can considerthe action on the left (or right) of G on K. This action preserves the Haar measureon K.

Definition 1.2.3. An action of G on (X, µ) is (essentially) free if for almost every x ∈ X andfor every element in the group 1 ∈ G, we have 1x , x.

Definition 1.2.4. An action of G on (X, µ) is ergodic if every invariant measurable subsetA = GA ⊂ X is trivial, namely µ(A) ∈ {0, 1}.

Example 1.2.5. 1. The action of Z on the circle is ergodic and free if and only if the angleα is irrational.

2. The action of a discrete subgroup G of a compact group K by multiplication on K isergodic if and only if G is dense, (see [27][Example 3.2]).

Definition 1.2.6. To every p.m.p. action a of a countable group G we can associate arepresentation κa, called the Koopman representation, as follows. We consider the Hilbertspace L2(X, µ) and we define(

κa(1)ξ)

(x) = ξ(a(1−1)x), ∀ξ ∈ L2(X, µ), ∀1 ∈ G, ∀x ∈ X.

Often it is useful to use the Koopman representation to study the actions. For examplethe action is ergodic if and only if there are no non-constant invariant vectors in theKoopman representation. This allows us to give a two-line proof of the ergodicity of theaction of Z on S1, by Fourier transform.

5

1.2.1 Other examples

We want to construct some other important example.

Example 1.2.7. Volume-preserving actions of discrete groups on manifolds are of this type.

Example 1.2.8. Let G and G′ be two lattices of a locally compact second countable groupH, for example one can take H to be a Lie group. The action by multiplication on the leftof G on H is smooth, namely there exists a Borel fundamental domain D ⊂ H, such that

H =∐1∈G

1D.

By definition of lattice the measure of D is finite. The group G′ also acts on H bymultiplication on the right and its action clearly commutes with the action of G. So wecan define an action of G′ on D and this action preserves the measure.

Example 1.2.9 (Profinite actions). Let G be a group and let G = G0 > G1 > G2 > . . . bea nested sequence of finite index subgroups. For each i, we define Xi := G/

Giand we

define

Ti : Xi → Xi−1, [1]Gi 7→ [1]Gi−1 .

We observe that |T−1i (1)| = [Gi−1 : Gi]. We define a space

X :={(xi)i∈N; xi ∈

G/Gi, Ti(xi) = xi−1

}.

This space is a Cantor space and it is the profinite limit of the family {Xi, Ti}. Equiv-alently we can define the space as the set of ends of the tree whose vertices are given by{Xi}i and edges are couples (xi, xi−1), where xi ∈ Xi, xi−1 ∈ Xi1 and Ti(xi) = (xi−1).

We equipXwith the uniform measure and the group G acts onX by left multiplication.The action on each level Xi is transitive, so the action on X is ergodic. The stabilizer of theaction is (modulo conjugation), ∩i∈NGi. So the action is free if and only if ∩i∈NGi = {1}.

Example 1.2.10 (Bernoulli actions). Let (Y, ν) be a probability space, possibly with atoms,and let G be a group. The standard Bernoulli shift action of G is the action on the standardmeasurable space X := YG equipped with the product measure µ := ⊗Gν, defined by

h · (y1)1∈G = (yh−11)1∈G.

By definition, this action is Borel and preserves the measure. We will prove that it areergodic. In order to do that, we define a stronger property.

Definition 1.2.11. An action of a countable group G on a probability space (X, µ) is mixingif for every A,B ⊂ X, we have

limn→∞

µ(1nA ∩ B) = µ(A)µ(B),

for every sequence {1n}n∈N ⊂ G such that∣∣∣{1n} ∩ S

∣∣∣→ 0 for every finite subset S ⊂ G.

Proposition 1.2.12. If an action is mixing, then it is ergodic.

6

Proof. Suppose that the action of G on (X, µ) is mixing and let A ⊂ X be an invariant set.By the mixing property

µ(A) = µ(A ∩ A) = µ(1nA ∩ A)→ µ(A)2⇒ µ(A) = µ(A)2,

hence µ(A) ∈ {0, 1}. �

Now we can prove that the Bernoulli actions of any infinite group G is ergodic. Asubset C ⊂ X is cylindrical if it “imposes” finitely many conditions on the coefficients1 ∈ G. Namely, the set

supp(C) :={1 ∈ G; π1(C) , Y

},

π1 : X→ Y, π1((yh)h∈G

)= y1,

of the coefficients where there is some restriction, is finite. Given any two cylindrical setsC and C′ and given 1 < supp(C)± · supp(C′)±, we have

µ(1C ∩ C′) = µ(C)µ(C′),

since 1C and C′ are “independent”. So given any two cylindrical subsets C and C′, andgiven any {1n} as in the definition of mixing,

µ(1nC ∩ C′)→ µ(C)µ(C′).

Given any measurable subset A ⊂ X and any ε > 0, there exists a cylindrical subsetC ⊂ X such that µ(C∆A) ≤ ε. Hence, given A,B ⊂ X and {1n}, we consider two cylindricalsubsets C and C′ such that µ(A∆C) ≤ ε and µ(B∆C′) < ε, so∣∣∣µ(1nA ∩ B) − µ(1nC ∩ C′)

∣∣∣ ≤ Nε⇒ µ(1nA ∩ B)→ µ(A)µ(B).

So for each group G we have constructed an ergodic free action.

1.3 Orbit equivalence relation

In the previous section we have introduced the notion of measurable action. Now wegive two different meaning of isomorphism of actions.

Definition 1.3.1. Let G and G′ be countable groups and consider two p.m.p. action of Gand G′ on (X, µ) and (X′, µ′) respectively. We say that the two actions are conjugate if thereexists a measure-preserving isomorphism T : X → X′ and an isomorphism of groupsϕ : G→ G′ such that

T(1x) = ϕ(1)T(x), ∀1 ∈ G, x ∈ X.

This notion is quite rigid and there are many non-conjugate actions for each group.

7

Example 1.3.2. Let Y = {1, 2, . . . ,n} and let ν be a probability measure on Y, defined byν(i) := pi,

∑i pi = 1. We consider the Bernoulli action of Z onX := YZ. Varying the measure

ν, we obtain an uncountable family of actions. Are all these actions conjugate?Kolmogorov introduced an invariant called the entropy. We will not define it, the

interested reader can look at [37]. The entropy is invariant by conjugacy of actions andin our particular case its value is −

(∑i pi log(pi)

). So there exist uncountably many non-

conjugate Bernoulli shift actions of Z. We remark also that Ornstein proved that theentropy is a complete invariant for these actions, [32], namely two Bernoulli shift actionsare conjugate if and only if they have the same entropy.

Now we introduce a weaker notion of equivalence.

Definition 1.3.3. Consider two p.m.p. actions of G and G′ on (X, µ) and (X′, µ′) respectively.The actions are orbit equivalent if there exists a measure-preserving isomorphism T : X→X′ that sends orbits to orbits

T(Gx) = G′T(x), ∀x ∈ X.

We observe that this definition does not require an isomorphism of the groups. Thedefinition is weaker then the notion of conjugacy.

Theorem 1.3.4 (Die, [12]). All the p.m.p. actions of Z are orbit equivalent.

So we have a completely different phenomenon. To understand better this newconcept we define the orbit equivalence relation.

Definition 1.3.5. Consider a p.m.p. action a of G on (X, µ). We define the orbit equivalencerelation to be the equivalence relation on X,

Ra{(x, y) ∈ X × X; ∃1 ∈ G such that 1x = y

}.

Two actions are orbit equivalent if and only if the associated equivalence relations areisomorphic, as measured discrete equivalence relations.

1.3.1 Measured discrete equivalence relations

The orbit equivalence relation remembers many properties of the action.

Definition 1.3.6. Let (X, µ) be a probability space. An equivalence relation R ⊂ X × X ismeasurable if it is a measurable subspace. It is discrete if each equivalence class is countable.

We denote with πi (for i = 1, 2) the projections of the equivalence relation R to X,

π1(x, y) := x, π2(x, y) = y.

Any subset A ⊂ R, such that π1

∣∣∣A and π2

∣∣∣A are injective, is a graph of a partial

isomorphism φ : π1(A) → π2(A). By Lusin-Novikov theorem, 2.2.1, any equivalencerelation is the disjoint union of such subsets.

8

Definition 1.3.7. A discrete measurable equivalence relation R over a probability space(X, µ) is measure-preserving if each partial isomorphism φ : A → B, whose graph is con-tained in R, preserves the measure. A measure preserving discrete equivalence relationR is ergodic if every saturated subset A ⊂ X, i.e. such that x ∈ A and (x, y) ∈ R imply thaty ∈ A, is trivial µ(A) ∈ {0, 1}.

Now we have a dictionary. Let a be a p.m.p. free action of a group G and let Ra be theorbit equivalence relation.

1. G is countable if and only if Ra is discrete.

2. The action is measurable if and only if Ra is measurable.

3. G preserves the measure if and only if Ra does.

4. The action is ergodic if and only if Ra is ergodic.

5. Two actions are orbit equivalent if and only if the associated equivalence relationsare isomorphic.

So{free actions of

discrete groups

}/{orbit

equivalence

} ↪→{

discrete measuredequivalence relations

}/{isomorphism

}.Is this an equivalence? Does every discrete measured equivalence relation come from

a free action of a group?

Theorem 1.3.8 (Feldmann-Moore, [16]). Every measured discrete equivalence relation is theorbit equivalence relation of the action of a discrete group.

The proof of the theorem is not hard and follows from the Lusin-Novikov’s theorem.We stress here an important fact, thie group provided by the theorem does not act freely.In general given a discrete measured equivalence relation, it is not possible to find a freeaction of a group whose orbit equivalence relation is the given one.

1.4 Amenable vs Non-amenable

In the measurable world there exists a dichotomy between amenable groups and non-amenable ones. The actions of the amenable groups are completely isolated from theactions of other groups and they are reduced to a single action. Conversely each non-amenable group admits uncountably many orbit inequivalent actions. We recall thedefinition of amenability for groups.

Definition 1.4.1. A discrete countable group G is amenable if there exists a translation-invariant and normalized mean m on the group G, that is a function m from the subsets ofG to R+ such that

m(Aq B) = m(A) + m(B), m(G) = 1.

9

Example 1.4.2. A finite group is amenable, since the uniform measure on the group is aninvariant mean.

There are many different characterizations of amenability. We give a useful one.

Definition 1.4.3. Let G be a group. A Følner sequence is a sequence {Fn}n∈N of finite subsetof G, such that

∀1 ∈ G,

∣∣∣1FnδFn∣∣∣

|Fn|→ 0.

Proposition 1.4.4. A discrete group is amenable if and only if it admits a Følner sequence.

Example 1.4.5. The group Zd is amenable, since the sequence {−n, . . . ,n}d is a Følnersequence.

More generally solvable groups are amenable and amenability is stable under quo-tients and subgroups.

Proposition 1.4.6. 1. Subgroups of an amenable group are amenable.

2. Quotients of an amenable group are amenable.

Proposition 1.4.7. The free group F2 is not amenable.

Proof. Let m be a mean. By invariance under translations, for every finite set F, m(F) = 0.Let {a, b} be a free generating set of F2. We denote with Sa the set of words of F2 such thatthe first letter is a. Then

F2 = {id} q Sa q Sa−1 q Sb q Sb−1 ,

Sb = {b} q bSa q bSa−1 q bSb.

By invariance

m(Sb) = m(Sa) + m(Sa−1) + m(Sb)⇒ m(Sa) = m(Sa−1) = 0,

hence m = 0 and F2 is not amenable. �

Every group that contains a free non Abelian group is non-amenable. The questionof whether every non amenable group contains a free non Abelian group, known asvon Neumann’s Problem, was unsolved for many years. The answer is negative andOl′šanskiı found a counterexample, [31]: a non-amenable torsion group such that everysubgroup is cyclic (called the Tarski monster).

1.4.1 Amenability

Example 1.4.8. Consider the groups

G :=⊕

Z

Z/2Z < K :=

∏Z

Z/2Z.

10

The group K is compact and G < K is a dense subgroup, so the action of G on K is ap.m.p. ergodic action. Let define

Gn :=⊕

i=1,...,n

Z/2Z < G.

We denote the orbit equivalence relation associated to Gn with Rn and the one associ-ated to G with R. Since each Gn is finite, the equivalence relation Rn is finite: each classhas finite cardinality. The equivalence relation R has a particular form, it is the union ofan increasing sequence of finite sub-equivalence relation.

Definition 1.4.9. An equivalence relations R is hyperfinite if it is the increasing union of asequence of finite sub-equivalence relations.

The considered action of G :=⊕

ZZ/

2Z has nothing of particular. Every orbitequivalence relation associated to any action of G is hyperfinite. The same result is truefor all the actions of a direct sum of finite groups or for any action of Z. The surprisingfact is that they are all the same.

Theorem 1.4.10 (Dye, [12]). All the ergodic measured hyperfinite equivalence relations arepairwise isomorphic.

Starting from this theorem, different authors tried to determinate the class of groupswhose equivalence relation is hyperfinite. Ornstein and Weiss gave the solution of thisproblem.

Theorem 1.4.11 (Ornstein-Weiss, [33]). All the p.m.p. ergodic actions of amenable groups areorbit equivalent.

More generally one can introduce the concept of amenable equivalence relations and allthe amenable equivalence relations are isomorphic, see [11] for the most general statement.From a measurable point of view, all the amenable groups are the same. Moreover if agroup admits a p.m.p. free hyperfinite ergodic action, then the group is amenable. So theamenable world is completely isolated in the measurable context and it is reduced to apoint.

1.4.2 Non-amenability

The non-amenable world is wilder then the amenable one, each group admits manyorbit inequivalent actions. For this section we refer to the wonderful work of Houdayer,[24], where the reader can find almost every proof of the stated theorems.

The first result in this direction was obtain by Connes and Weiss, [10]. They provedthat each group that is not amenable and that has not Kazhdan property (T) admits two orbitinequivalent actions. They proved this result showing that each group has an ergodicaction that is not strongly ergodic and one that is so. Groups with property (T) admits onlystrongly ergodic actions, so that strategy could not work for that kind of groups. Thesecond important result was obtained by Hjorth, [23]. He proved that every property(T) group admits uncountably many orbit inequivalent actions. Gaboriau and Popa, [22],proved that the same is true for free groups and using their result Ioana was able to provethe following theorem.

11

Theorem 1.4.12 (Ioana, [25]). Every group that contains F2 admits uncountably many orbitinequivalent actions.

For a group that satisfies the von Neumann problem we have found a dichotomy:either it has only one action and it is amenable, or it has uncountably many differentactions and it is non-amenable.

In the measurable world we have more flexibility than in group theory. Working“up to measure 0” many problems can disappear and the freedom given by a diffusespace allows us to prove surprising result. One of these phenomenons is the measurablesolution of the von Neumann problem.

Theorem 1.4.13 (Gaboriau-Lyons, [21]). For any non-amenable countable group G, the or-bit equivalence relation of the Bernoulli shift action on ([0, 1]G,⊗GLeb) contains a subrelationgenerated by a free p.m.p. ergodic action of F2.

We would like to say two words about the proof of this theorem. It is a wonderfulexample of interaction of apparently different areas of mathematics. The proof is basedon the theory of cost, see the next section, and percolation theory in probability.

Using the two above theorems Epstein was able to give a complete solution of theproblem.

Theorem 1.4.14 (Epstein, [14]). Every non amenable group admits uncountably many orbitinequivalent actions.

Both Ioana’s theorem and Epstein’s theorem rely on a separability argument thereforethey only provide an existence theorem. It is still open whether one can define a family ofexplicit actions for every non amenable group. There some partial result on this directionand we invite the interested reader to look at the Bourbaki’s séminaire of Houdayer, [24].

1.5 Cost for equivalence relations

The notion of cost for a p.m.p. action of a countable group was introduced by Levittfifteen years ago, [28].

Definition 1.5.1. Let R be a discrete measured equivalence relation on the standard prob-ability space (X, µ). A graphing is a family of partial isomorphism Φ :=

(ϕi : Ai → Bi

)i∈N

whose graph is contained in R, such that the smallest equivalence relation generated byx ∼ ϕi(x) is R.

Example 1.5.2. Consider the action of a countable group G on the standard probabilityspace (X, µ). Let {1i} be a generating set for G. Then Φ :=

(1i : X→ X

)i∈N is a graphing of

the orbit equivalence relation.

Graphings should be considered as generating sets for the equivalence relations.Given a graphing Φ we can define a measured graph as follows: the set of vertices is X andthere exists an edge between x and y if and only if ϕi(x) = y for some i. Such a graphis not connected, each connected component is an orbit of the equivalence relation. Sographings are measurable ways to put a structure of connected graph on each orbit. Foreach x ∈ Xwe will denote with Φ[x] the graph whose vertices are the elements of the orbitof x.

12

Example 1.5.3. If the equivalence relation and the graphing are given as in the examplebefore, each Φ[x] is naturally identified with the Cayley graph of G with respect to the fixedgenerating set.

Example 1.5.4. We consider a free p.m.p. ergodic action of Z2 on the circle X := S1, given bytwo rationally independent rotation and letR be the associated orbit equivalence relation.Let a and b be the standard generators of Z2. Then

Φ := (a : X→ X, b : X→ X) ,

is a graphing for R. Let A ⊂ X be a measurable subset of positive measure. Let’s provethat

Φ′ := (a : X→ X, b : A→ bA) ,

is a graphing. We have to show that each (x, bx) for x ∈ X is in the equivalence relationgenerated by Φ′. Let x ∈ X, by ergodicity of the action of 〈a〉, there exists an integer n ∈ Zsuch that anx ∈ A. Since a and b commutes a−nban = b so a−nbanx = bx and the left handside is clearly generated by Φ′.

With the theory of cost we try to answer to the following question: which is the sizeof an optimal graphing?

Definition 1.5.5. Let Φ :=(ϕi : Ai → Bi

)i∈N be a graphing of the measured discrete equiv-

alence relation R on the standard probability space (X, µ). The cost of the graphing is

cost(Φ) :=∑i∈N

µ(Ai).

The cost of a measured discrete equivalence relation is

cost(R) := infΦ graphing

cost(Φ).

The cost measures, somehow, the complexity of the smallest graph-structure on theorbits, or in other words, the minimum information that we need in order to describethe whole equivalence relation. Clearly if two equivalence relations are isomorphic, thenthey have the same cost.

1.5.1 Cost in group theory

Definition 1.5.6. Let G be a countable group. The cost of a p.m.p. action of G on thestandard probability space (X, µ) is the cost of the associated orbit equivalence relation.

In the Example 1.5.2, we proved that the cost of a p.m.p. action of a group is less orequal the rank of the group (minimum number of generators).

Proposition 1.5.7 (Levitt, [28]). 1. If G is a finite group of cardinality |G|, then the cost ofeach free p.m.p. action is 1 − 1

|G| .

2. If G is an infinite group, then the cost of each free p.m.p. action is greater than 1.

13

Example 1.5.8. The cost of the action of Z2 by two rationally independent rotation on thecircle has cost 1.

Example 1.5.9. Ornstein-Weiss’ theorem, 1.4.11, says that all the orbit equivalence relationof all the actions of any amenable group are isomorphic. So the cost of any free action ofan amenable group is 1.

Definition 1.5.10. The cost of a group G is the infimum of the costs of its actions,

cost(G) := infa free action of G

cost(a).

A well-known open problem is the fixed price problem: does every free action of acountable group have the same cost?

1.5.2 Treeability

An important class of graphings are treeings.

Definition 1.5.11. A graphing Ψ for R is a treeing if for every x ∈ X the graph Φ[x] is atree.

Example 1.5.12. The hyperfinite equivalence relation is treeable and there exists a graphingsuch that each graphh is a line.

Actually, the notion of treeing was introduced before the notion of graphing by Adamsin [5]. There is a strong relation between treeings and cost. Let Φ be a graphing forR. If Φis not a treeing, then there exists some non-trivial loop (or circuit). If we erase some loops,we obtain smaller graphings of “smaller” cost. So if the cost of an equivalence relationis a minimum, then there exists a treeing for it. Anyway not every equivalence relationadmits a treeing, for example the equivalence relation induced by an action of a Kazhdangroup is not treeable, [4, Theorem 1.8]. More generally if a group admits an action whoseequivalence relation is treeable, then it has Haagerup property, see [36, Propposition 2.5].

Example 1.5.13. The equivalence relation generated by any free action of a free group istreeable. A treeing is given by a free generating set for the group (defined in the wholespace).

Suppose now that R is an equivalence relation and let Ψ be a treeing. Clearly thereexists no-sub graphing of Ψ. But it is not clear a priori that the cost of R is exactly the costof Ψ, since it could exists another “completely different” graphing. Gaboriau showedthat it is not the case.

Theorem 1.5.14 (Gaboriau, [18]). If Ψ is a treeing for R, then cost(R) = cost(Ψ).

This fact has a really strong corollary.

Corollary 1.5.15. The cost of any free p.m.p. action of the free group n is equal to the number offree generators. In particular, p.m.p. free actions of different free groups are not orbit equivalent.

With similar techniques Gaboriau also computed the cost of free and amalgamatedproducts. An equivalence relation is an amalgamated product of equivalence relations ifit admits a normal form as in the group-theoretical sense, see [19] for the precise definition.

14

Theorem 1.5.16 (Gaboriau, [19]). Let R = R1 ∗R3 R2 an amalgamated product of equivalencerelation and suppose that R3 is hyperfinite. Then

cost(R) = cost(R1) + cost(R2) − cost(R3).

Using this theorem Gaboriau showed that for each c ∈ [1,∞] there exists a group withcosts c.

Acknowledgements

I wrote this thesis during my year in Erasmus at the École Normale Supérieure deLyon. I really thank my advisor, Damien Gaboriau for the uncountably many discussionsand for all the help that he gave to me. I am also grateful to François, Pierre-Adelin andSébastien for the nice afternoons spent at the blackboard, they have been the bests Frenchteachers ever!

I would like to warmly thank Claudia Pinzari for her guidance and support thoughtthe last three years.

In addition, a special thanks to Angela and Michele for doing all the administrativethings I should have done.

15

Chapter 2

Cost for Discrete MeasuredGroupoids

2.1 Introduction

2.1.1 Groupoids

In this thesis we extend the theory of cost to measured discrete groupoids. These objectsare quite natural if one is interested in measure preserving non free actions of a groupon a probability space. For non free actions the orbit equivalence relation could not saymuch about the original group, so in order to understand them from a measurable pointof view, we need an object that takes care of all the stabilizer of the action, but, somehow,that forgets the groups. The groupoids do the job. Given a group G and an action overthe standard Borel space X, we define the groupoid action to be the set of all the arrowsfrom X to X, that express the action of the elements of the group. So from each x ∈ X,we will have {G} arrows going in different directions (possibly loops). The product in thegroupoid is the composition of arrows. These groupoids encode perfectly the action andreflect many properties of the group.

Groupoids behave like groups under many point of view. There are many objects inthe world of groups that can still be defined for a groupoid:

• generating set, subsets of the groupoid that are not contained in any smaller sub-groupoid,

• Cayley graph of a groupoid, a field of graphs that represent the geometry induced bya given generating set,

• free groupoids, that will take the role of free groups,

• presentation of a groupoid, given by generators and relations,

• free products of groupoids, defined as for groups via generators and relations,

• actions of a groupoid on a fibred space,

• Bernoulli actions of a groupoid that will give us the existence of an ergodic action foreach groupoid.

16

2.1.2 Cost for groupoids

The groupoid cost of a measured discrete groupoid takes the role of the rank of a group(the minimal number of generators). Measured groupoids carry their own measure, sowe can measure the size of any subset. As for groups, we define the groupoid cost to bethe infimum of the measure of its generating sets.

The definition is compatible with rank for groups and cost for equivalence relations.Namely,

• if the groupoid is a group, then the groupoid cost is the rank of the group,

• if the groupoid is an equivalence relation, then the groupoid cost is the cost of theequivalence relation,

• if the groupoid is the action groupoid of some group, then the groupoid cost is thecost defined by Abért and Nikolov in [3].

In some cases one can compute the groupoid cost knowing the cost of the equivalencerelation and the rank of the isotropy groups.

Proposition. 2.3.9 Let G = (Gx)x∈X be a field of groups, then the groupoid cost gcost(G) =∫Xr(Gx)dµ(x).

2.3.11 If GP is aperiodic and if the rank function is bounded, then gcost(G) = gcost(GP).

2.3.13 If D ⊂ G0 is a fundamental domain for the action of GP on G0, then gcost(G) = µ(G0) −µ(D) +

∫D r(Gx)dµ(x).

In general it is not the case, when the equivalence relation is ergodic and the rank ofthe isotropy groups is infinite the situation is more complicate. This invariant has alreadyappeared in the literature under a slightly different form. Ueda found a von Neumannalgebras’ proof of the result of Gaboriau on free and amalgamated product, 1.5.16, in thegroupoid case.

Theorem (Ueda, [36]). Let G = G1 ∗G3 G2 be an amalgamated product of groupoids. Supposethat G3 is an hyperfinite equivalence relation, then

gcost(G) = gcost(G1) + gcost(G2) − gcost(G3).

Anyway we will not use his work and we will recover the cost of a free product in ourcontext.

2.1.3 Cost for free groupoids

An important result for the groupoid cost is an analogue of Gaboriau’s Theorem fortreeable equivalence relations, 1.5.14. In the context of groupoids we will adopt thegroup-name of treeablility, namely freeness. A free groupoid can be seen in different ways:

• as a solution of a universal property,

• as a path groupoid over a graph,

17

• as the free words over a generating set.

We will prove the following theorem.

Theorem (cr. 2.3.17). Let G be a free groupoid and let Ψ be a free generating set for G. Thengcost(G) = µ(Ψ).

A free groupoid that is an equivalence relation is a treeable equivalence relation, sothe previous theorem is a generalization of Gaboriau’s result. Actually, it will follow asa corollary. The key idea is to consider the free groupoid G as a group. The equivalencerelation associated to a free action of G is treeable and the result of Gaboriau tells us thatthe cost of the free actions of G and is equal to the rank of G. The only problem with thisproof is the existence of a free action of a groupoid. In order to do that, we will define theBernoulli actions, Definition 2.2.68 and the proof will follow as said before.

Using the free groupoids we will define the presentation of a groupoid, as in the PhDthesis of Alvarez, [6]. In particular he was able to prove the Nielsen-Schreier’s Theoremand Grushko’s Theorem for groupoids. Using Grushko’s theorem in this context, we cangive compute the groupoid cost of a free product exactly as in the group case.

Corollary (cr. 2.3.18). For a free product of groupoids G1 ∗ G2, we have

gcost (G1 ∗ G2) = gcost (G1) + gcost (G2) .

So, we recover Ueda’s Theorem in the particular case of free product. We would like toremark that the definition of free product of groupoids is more natural then the definitionfor equivalence relations. In fact one can only say when an equivalence relation is a freeproduct. There is no natural way to construct a free product of equivalence relation.Conversely the free product of groupoids is defined via generators and relations as in thegroup case. So, in some sense, in order to speak of free products we have to stay in thecategory of groupoids and not in the one of equivalence relations.

The case of amalgamated product seems to be harder. It is not possible to give a goodanswer in the group-theoretical case. For example it is possible to construct a family ofgroups {An}n∈N and {Bn}n∈N of rank n such that Gn = An ∗F2 Bn has rank 2, [38]. Evenfor amalgamated product over a finite group the situation is far from being clear, seefor example [39] and cited references. We can say something, only in the case of anamalgamated product over an amenable equivalence relation. In this case one can followthe proof of Gaboriau in [19] for equivalence relations and translate it into the groupoidcontext (as Ueda did).

2.1.4 Cost in theory of (countable) groups

Our main source of examples is given by groups. Given an action of a countable groupG, we can define the cost of the action as the cost of the associated groupoid action. Wecan defineM(G) ⊂ R+ to be the of all possible costs of the probability measure preservingergodic actions of G. The last section of this work is dedicated to this invariant. A firstremark is that

Md(G) ⊂ [cost(G), r(G)],

18

where cost(G) is the usual cost of G, namely the infimum over all the costs of its freeprobability measure preserving actions. In particular Gaboriau proved that cost(Fn) = n,see [18], so that we obtain the following corollary.

Corollary (cr. 2.5.4). Let Fn be the free group of rank n, thenM(Fn) = {n}.

Anyway this set is reduced to a point only in the case of a free group. We defineM

d(G) ⊂ M(G) to be the set of costs of actions on a diffuse space. An action on a finitespace is ergodic if and only if is transitive, so the actions are given by the action on thecosets of a finite index subgroup. Using the results on cost for groupoids we will able tocompute some examples.

Theorem. Let G and G′ be any groups, p, k ∈ N. Then

2.5.8 M(Zk

)= {1} ∪

⋃n∈N

{1 + k−1

n

},

2.5.13 Md(Zk× Fp) = {1} ∪

⋃n∈N

{1 +

p−1n

},

2.5.20 Md(G ∗ G′) is an interval,

2.5.18 one can deduceM f (G ∗ G′) knowing the finite index subgroups of G and G′,

2.5.21 M(Fp ∗ G) = [cost(G) + p, r(G) + p],

2.5.25 for any n > m ∈ N,Md(Zn∗ Zm) = [2,n + 1],

2.5.32 M(SL2(Z)) =[1 + 1

12 , 1 + 18

]q

[1 + 1

6 , 1 + 13

].

We would like to make some remarks.

• The subgroups of direct products are still not well understood, see for example [9].We do not have any idea how to computeM(Z × F2).

• Using 2.5.21 of the previous theorem, we are able to find an uncountable family ofgroups with the same invariantM.

• We will give a general formula for the cost of a free product, see 2.5.24, unfortunatelyit is quite ugly.

The cost of the actions is not an orbit invariant, even for a fixed group, but (at least forfinitely generated groups) is an invariant of the weakly equivalence, as shown by Abértand Weiss in [2, Theorem 9].

2.2 Borel and measured discrete groupoids

The aim of this Section is to collect some generalities of Borel and measured discretegroupoids. We will define:

• generating sets for a groupoid, similar to the group-case;

• free groupoids and presentations of groupoids;

19

• actions of groupoids on fibred spaces and smoothness;

• free products;

• the Cayley graph of a groupoid with respect to a generating set.

All these objects are already defined in the PhD Thesis of Alvarez, [6], for the Borelcase. Thus, in the present chapter, we will focus on the measure and we will show thatall the constructions made in [6] are compatible with the measure.

We will use many times the following theorem.

Theorem 2.2.1 (Lusin-Novikov). Let f : X→ Y be a Borel map between standard Borel spacessuch that f−1(y) is countable for each y ∈ Y. Then the image of f is measurable and there exists apartition X = qi∈NXi such that f

∣∣∣Xi

: Xi → f (Xi) is an isomorphism.

Proof. The proof follows from theorem 18.10 of [26]. �

Throughout this paper all the Borel spaces are standard Borel spaces and every mea-sure is a Borel measure. We do not assume in general that the measure is finite and it canhave atoms.

2.2.1 Fibred spaces

Definition 2.2.2. A Borel fibred space is a triple (F, π,X), where F and X are Borel spaces andπ : F → X is a surjective Borel map. The fibred space is said discrete if π has countablefibres and it is said diffuse otherwise.

Definition 2.2.3. Suppose that (X, µ) is a measured space and let ν be a measure of F.The quadruple (F, π,X, ν) is a measured fibred space if there exists a measurable field ofmeasures {νx

}x∈X such that

ν(A) =

∫X

νx(A ∩ π−1(x))dµ(x).

Definition 2.2.4. Let (F, π,X) be a discrete Borel fibred space and let µ be a measure on X.We define the counting measure of a fibred space to be the measure

µπ(A) :=∫X

|π−1(x) ∩ A|dµ(x) for any A ⊂ F.

The measure µπ is a measure on F and with this measure (F, π,X, µ) is a measureddiscrete fibred space, in the sense of the previous definition.

Definition 2.2.5. Let (F, π,X) and (F′, π′,X′) be Borel fibred spaces. A Borel map of fibredspaces ϕ : (F, π,X)→ (F′, π′,X′) is a commutative diagram of measurable maps

F

π��

ϕ // F′

π′

��X

ϕ // X′

Suppose that (X, µ) and (X′, µ′) are measured. We say that ϕ is a fibration if ϕ issurjective with countable fibres and if µ′ϕ = µ.

20

Definition 2.2.6. Given two fibred spaces (F1, π1,X) and (F2, π2,X), we define the fibredproduct to be the following fibred space:

F = (F1, π1) × (F2, π2) :={(x, y) ∈ F1 × F2 such that π1(x) = π2(y)

},

π(x, y) :=π1(x) = π2(y) ∈ X,

with the Borel structure on F induced by the canonical projections P1 : F→ F1, P2 : F→ F2.

Remark 2.2.7. The fibred product is the categorical product in the category of fibred Borelspaces.

Definition 2.2.8. Given a triple {(Fi, πi,X)}i=1,2,3 of fibred spaces and a Borel map π : F2 →

X, we set

F = (F1, π1) × (F2, π2, π) × (F3, π3) := (((F1, π1) × (F2, π2)) , π ◦ P2) × (F3, π3)π2(x, y, z) := π1(x) = π2(y), π(x, y, z) := π(y) = π3(z).

Clearly (F, π,X) and (F, π2,X) are fibred spaces.

2.2.2 Discrete measured groupoids

General references for measured groupoid are [34] and [7]. For the discrete ones [6]and [35].

Definition 2.2.9. A groupoid is a small category where all the morphisms are invertible.Given a groupoid G, we denote with G0 the set of its objects.

We will always identify the groupoid with the set of its arrows. The set of objects G0is identified with the set of identity maps, also called unities of the groupoid.

Each element 1 ∈ G is an arrow between two objects: 1 : s(1)→ t(1), where we denotewith s : G → G0 the source map and with t : G → G0 the target map.

We define the set of composable elements to be

Gc :=

{(1, h) ∈ G × G such that t(h) = s(1)

}.

We denote with i : G → G the inversion i : 1 7→ 1−1 and with p : Gc→ G the

composition p : (1, h) 7→ 1h.

Definition 2.2.10. A morphism of groupoids between two groupoids G and H is a functorbetween the two small categories. An isomorphism is a functor that admits an inverse.

Definition 2.2.11. A Borel groupoid is a groupoid G equipped with the structure of astandard Borel space, such that i and p are Borel maps.

Since p ◦ (i, id) = s and p ◦ (id, i) = t the source and the target maps are Borel maps.

Gc

p

��G

s //

(i,id)??

G

Gc

p

��G

t //

(id,i)??

G

A Borel groupoid is discrete if the source and the target map have countable fibres.

21

Definition 2.2.12. If G is a discrete Borel groupoid then (G, s) and (G, t) are Borel fibredspaces. If (G0, µ) is a measured space, we can define two counting measure on G, namelyµt and µs, see Definition 2.2.2. The couple (G, µ) is a discrete measured groupoid if µs = µt.

Since i ◦ s = t, the equality above is equivalent to i∗µs = µs.

Notation 2.2.13. If (G, µ) is a measured discrete groupoid we will denote with µ := µs = µtthe measure over G.

Example 2.2.14 (Equivalence relations). Every Borel equivalence relation R on X is natu-rally a Borel groupoid. In fact we can think R ⊂ X × X and define

• s(x, y) := y and t(x, y) := x,

• p((x, y)(y, z)) := (x, z),

• i(x, y) := (y, x).

Given a measure µ on X, the equivalence relation is measure-preserving if µs = µt.

Example 2.2.15 (Groups action). Let G be a discrete countable group acting onX (preservingthe Borel structure). We define the action groupoid G n X to be the following groupoid

• G n X := G × Xwith the product Borel structure,

• s(1, x) := x and t(1, x) := 1x,

• p((1′, x′), (1, x)) := (1′1′, x), if x′ = 1x,

• i(1, x) := (1−1, 1x).

If a measure µ on X is preserved by the action of G, then it is easy to show that µs = µt,whence (G n X, µ) is a measured groupoid.

Definition 2.2.16. Let G be a discrete Borel groupoid and let A ⊂ G0 be a measurablesubset. We define the restriction of G

G

∣∣∣A := G

⋂(s−1(A) ∩ t−1(A)

).

If (G, µ) is a measured groupoid then (G∣∣∣A, µ

∣∣∣A) is a measured groupoid.

Generating sets

Let (G, µ) be a discrete measured groupoid.

Definition 2.2.17. We denote the k-fold product map with

pk : (G, s) × (G, s, t) × . . . × (G, s, t) × (G, t)→ G,pk(1k, . . . , 11) = 1k . . . 11.

For Φ ⊂ G, we define

(Φ, s)k := (Φ, s) × (Φ, t, s) × . . . × (Φ, t, s) × (Φ, t),

Φk := pk

((Φ, s)k

),

Φ± := Φ ∪ i(Φ).

22

Definition 2.2.18. A measurable subset Φ ⊂ G is a generating set (for G) if the smallestsub-groupoid containing Φ is G. Equivalently, Φ is a generating set if G = ∪k (Φ±)k.

Example 2.2.19. Let G = G n X be an action groupoid as in Example 2.2.15 and let S ⊂ G agenerating set. Then X × S is a generating set for G.

The groupoid G is a generating set for itself, so the family of generating sets is notempty.

Remark 2.2.20. Let f : G → H be a measurable surjective map of groupoids, if Φ is agenerating set for G, then f (Φ) is a generating set forH .

Definition 2.2.21. Given a generating set Φ ⊂ G, we can define the length function asfollows:

` = `Φ : G → N, `(1) := min{k∣∣∣1 ∈ (Φ±)k

}.

The map is Borel since `−1(n) = (Φ±)n\ (Φ±)n−1 .

2.2.3 Graphs

In this section we recall the definition of graph, paths, measured graphs and fields ofgraphs. Generality on graphs can be found in many books, for Borel graphs and fields ofgraphs, see Alvarez [6].

Definition 2.2.22. An oriented graph Γ is a couple of sets (V(Γ),E(Γ)), called set of verticesand set of edges, and a couple of maps o, r : E(Γ)→ V(Γ), called origin map and range map.

Given an oriented graph Γ we define c(Γ) to be the graph with the same couple of setsbut with o(c(γ)) = r(γ) and r(c(γ)) = o(γ). We call it the opposite graph.

Given two graphs Γ1 and Γ2 with the same set of vertices, we define Γ := Γ1 ∪ Γ2 to bethe following graph:

V(Γ) := V(Γ1) = V(Γ2), E(Γ) := E(Γ1)q E(Γ2),

(o, r)∣∣∣E(Γ1) = (o1, r1), (o, r)

∣∣∣E(Γ)2

= (o2, r2).

Notation 2.2.23. We set Γ = Γ ∪ c(Γ).

Assumption: Every graph is oriented.

Paths

Let Γ be a graph.

Definition 2.2.24. A path in Γ is an ordered finite subset (γk, . . . , γ1) ⊂ E(Γ) such thato(γi) = r(γi−1). We define the origin and range of a path to be

o(γk, . . . , γ1) := o(γ1) r(γk, . . . , γ1) := r(γk).

Notation 2.2.25. We will say that x ∈ V(Γ) is an empty path.

23

Definition 2.2.26. A path (γk, . . . , γ1) ⊂ E(Γ) is reduced if γi < {c(γi−1), c(γi+1)} for i ∈{2, . . . , k − 1}.

Convention: an empty path is reduced.

Definition 2.2.27. A graph is a tree if for every reduced path (γk, . . . , γ1), one has r(γk) ,o(γ1). A graph is a forest if it is the disjoint union of trees.

Definition 2.2.28. Given a path (γk, . . . , γ1) we define a path R(γk, . . . , γ1) to be

• if (γk, . . . , γ1) is reduced, then R(γk, . . . , γ1) := (γk, . . . , γ1),

• if (γk, . . . , γ1) is not reduced,

– if k = 2 then R(γ2, γ1) := o(γ1),– let i the first integer such that γi = c(γi+1), we define

R(γk, . . . , γ1) := (γk, . . . , γi+2, γi−1, . . . , γ1).

The reduction of a path (γk, . . . , γ1) is the reduced path (possibly empty) such thatRk(γk, . . . , γ1) = Rk−1(γk, . . . , γ1).

It is easy to check that this operation is well defined (the check is similar to the proofof associativity for free groups).

Definition 2.2.29. Given two paths (γk, . . . , γ1) and (γ′h, . . . , γ′

1) such that o(γ1) = r(γ′h), wedefine the concatenation to be the path (γk, . . . , γ1, γ′h, . . . , γ

′

1).

Measured graphs

Definition 2.2.30. An oriented graph Γ is locally countable if o and r have countable fibres.

Definition 2.2.31. A Borel graph Γ is a graph such that V(Γ) and E(Γ) are equipped witha Borel structure and o, r are Borel maps. Let Γ be a locally countable Borel graph, then(E(Γ), o,V(Γ)) and (E(Γ), r,V(Γ)) are Borel fibred spaces. So given any measure µ on X we,can define the counting measures µo and µr on E(Γ). A Borel graph is measured if µo = µr.

Notation 2.2.32. If (Γ, µ) is a measured graph we will denote µ := µo = µr the measure onE(Γ).

Definition 2.2.33. Let Γ1 and Γ2 be Borel graphs, a measurable map of graphs ϕ : Γ1 → Γ2 isa couple of measurable maps ϕ = (ϕ1, ϕ0) such that the following diagrams commute:

Γ11

ϕ1//

o��

Γ12

o��

Γ11

ϕ1//

r��

Γ12

r��

Γ01

ϕ0// Γ0

2 Γ01

ϕ0// Γ0

2

Example 2.2.34. Let (G, µ) be a discrete measured groupoid and let Φ ⊂ G a measurablesubset. We set o = s

∣∣∣Φ

and r = t∣∣∣Φ

and we observe that (Φ, o, r,G0, µ) is a measured graph.With a little abuse of notation we will say that every measurable subset ofG is a measuredgraph.

From now on, every graph is an oriented locally countable Borel graph.

24

Fields of graphs

Definition 2.2.35. Let F be a Borel graph and let π : V(F ) → X be a Borel map withcountable fibres. The triple (F , π,X) is a field of graphs if π(o(e)) = π(r(e)) for all e ∈ E.

Let µ a measure on X and let µπ the counting measure on V(F ). Then µπ◦o = µπ◦r onE(F ), so any measure µ over Xmakes F a measured graph.

Definition 2.2.36. A measurable map ϕ : (F1, π1,X1) → (F2, π2,X2) is a map of fields ofgraph if it is a map of graphs and ϕ0 : (V(F1), π1,X1)→ (V(F2), π2,X2) is a map of fibredspaces.

2.2.4 Path/free groupoids

Now we will define (and prove the existence) of one of the main object of the paper:the free groupoids. We will define first the geometrical version, the path groupoids, andat the end the algebraic characterization. See, again, [6].

Definition 2.2.37. Let (Γ, µ) be a measured graph. We define the path groupoid

• G(Γ) :={reduced paths (possibly empty) in Γ

},

• s := o, t := r,

• the product of two paths is the reduction of the concatenation of the two paths andthe inverse of a path is the opposite path.

We remark that V(Γ) = G (Γ)0 and E(Γ) ⊂ G(Γ) is a generating set for G(Γ).

Proposition 2.2.38. There exists a unique Borel structure (up to isomorphisms) on G(Γ) suchthat (G(Γ), µ) is a discrete measured groupoid and the induced Borel structure on Γ is the originalone.

Proof. If Γ is a graph, we denote with c(Γ) the opposite graph. The set E(Γ) ⊂ G(Γ) hasits Borel structure and we give to c(E(Γ)) the Borel structure induced by the bijectionc : E(Γ) → c(E(Γ)). We set Φ := E(Γ) ∪ c(E(Γ)) ∪ V(Γ). Using the notation of Definition2.2.17, we observe that

pk : (Φ, s)k\ p−1

k

(Φk−1

)↪→ G(Γ),

is injective, since there are no relations between paths. Moreover

G(Γ) = Φ ∪⋃k>1

pk

((Φ, s)k

\ p−1k

(Φk−1

)).

We define the Borel structure on G(Γ) to be the Borel structure induced by pk. Clearlywe can extend i to a Borel map. Using Lusin-Novikov Theorem we can show that µt = µsin every (Φ, s)k, hence the equation is true in the whole groupoid. �

We recall that every measurable subset of a discrete Borel groupoid is a Borel locallycountable graph, see Example 2.2.34.

25

Definition 2.2.39. Let G be a discrete Borel groupoid and let Ψ ⊂ G be a measurablesubset. The groupoid G is free over Ψ, if for every discrete Borel groupoid H and forevery map of graphs f : Ψ→H , there exists a unique map of groupoids f : G → H , suchthat f

∣∣∣Ψ

= f .

Free groupoids are also called treable groupoids in analogy with equivalence relations,see [19]. A free generating set is called a treeing for the groupoid.

Proposition 2.2.40. A groupoid G is free over Ψ if and only if G � G(Ψ). In particular givenΨ, G is unique.

Proof. LetG(Ψ) be a path groupoid. LetH be a discrete Borel groupoid and let f : Ψ→Hbe a map of graphs. We define

f : G → H , f (1) = f (ψ±k . . . ψ±

1 ) = f (ψk)± . . . f (ψ1)±.

Conversely let G be a free groupoid over Ψ ⊂ G. Let f : Ψ → G(Ψ) be the injectivemap associated to the inclusion Ψ ⊂ G and let 1 : Ψ→ G be the injective map associatedto the other inclusion. By freeness 1 f = 1 f = id and f1 = f1 = id so G and G(Ψ) areisomorphic. �

Remark 2.2.41. A groupoid is free with respect to a generating set, if and only if none ofthe non empty words in the generating set is an unity.

Let G be a groupoid, let Ψ ⊂ G be a measurable subset and let G(Ψ) be the freegroupoid. The inclusion Ψ ⊂ G extends uniquely to a measurable map G(Ψ) → G. Thismap is injective if and only if Ψ is free inside G. The map is surjective if and only if Ψ isa generating set.

We state the Nielsen-Schreier theorem for free groupoids.

Theorem 2.2.42 (Alvarez). A sub-groupoid of a free groupoid is free.

Proof. See Corollary 3.32 of [6]. �

2.2.5 Groupoid actions

In this section we will define the G-spaces and we will study the smooth actions.

Definition 2.2.43. Let G be a discrete Borel groupoid and let (F, π,G0) be a fibred space.A Borel action of the groupoid G on (F, π,G0) on the left is a Borel map

a : (G, s) × (F, π)→ (F, π),

such that

• π(a(1, x)) = t(1),

• a is associative, a(1, a(1′, x)) = a(11′, x) whenever s(1) = t(1′),

• the unites act trivially, a(π(x), x) = x, for every x ∈ F.

26

Notation 2.2.44. If G acts on (F, π,G0), we say that (F, π) is a G-fibred space. We will alwayswrite (F, π) instead of (F, π,G0) in this context. We will denote 1x := a(1, x) the action. If Gacts on (F, π) and A ⊂ F is a measurable subset, we set

GA := a((G, s) × (A, π)) ⊂ F.

Definition 2.2.45. Let (F1, π1) and (F2, π2) be G-fibred spaces. A G-equivariant map is amap of fibred spaces ϕ : (F1, π1,G0) → (F2, π2,G0), such that ϕ(1x) = 1ϕ(x) and the mapϕ : G0 → G0 is the identity map.

Definition 2.2.46. Let G be a discrete Borel groupoid and let (F, π) be a G-fibred space.We define a groupoid G n F as in Example 2.2.15:

• G n F := (G, s) × (F, π) as a Borel space,

• s(1, x) := x and t(1, x) = 1x,

• (1′, x′) · (1, x) = (1′1, x) if 1x = x′,

• i(1, x) = (1−1, 1x).

Definition 2.2.47. Let (G, µ) be a discrete measured groupoid and let (F, π, ν,G0) be ameasured fibred space. An action of G on (F, π, ν,G0) is said measure preserving if νs = νtas measures on G n F (observe that (G n F)0 = F).

Remark 2.2.48. We set ν =∫G0νxdµ(x). The previous condition is equivalent to the follow-

ings.

1. For every measurable subset θ ⊂ G such that s∣∣∣θ

and t∣∣∣θ

are injective, we have

ν((θ, s) × (A, π)) = ν(A) = ν(θA).

2. For every x,

νx(Ax) = ν1x(1Ax), ∀Ax⊂ π−1(x), 1 ∈ s−1(x).

Smooth actions

Definition 2.2.49. Let (G, µ) be measured discrete groupoid and let (F, π) be a G-fibredspace. A fundamental subset A ⊂ F is a measurable non-empty subset such that 1x < A forevery x ∈ A and 1 ∈ G \ G0. A fundamental domain is a fundamental subset D ⊂ F, suchthat for every x ∈ F there exists 1 ∈ G such that 1x ∈ D. The action of G on (F, π) is smoothif there exists a fundamental domain.

Remark 2.2.50. If D is a fundamental domain, then for every x ∈ F there exists a unique1 ∈ G such that 1x ∈ D. In fact if 1x, 1′x ∈ D, then (1′1−1)1x = 1′x ∈ D, so 1′1−1 = id.

Proposition 2.2.51. If D is a fundamental domain for the action ofG on (F, π), then the action-mapa gives an isomorphism (G, s) × (D, π

∣∣∣D) � F.

27

Proof. Since F and (G, s) × (D, π∣∣∣D) are standard Borel spaces, it is enough to show that it

is injective and surjective. The surjectivity is clear by definition of fundamental domain.If a(11, x1) = a(12, x2), then 11x1 = 12x2, so 1−1

2 11x1 = x2 and x1 = x2. Hence 11 = 12. �

Corollary 2.2.52. Let (F, π) be a smooth G-fibred space.

1. Any fundamental subset is a subset of a fundamental domain.

2. Every subset A ⊂ F has a partition in fundamental subsets.

3. All the fundamental domains are isomorphic via a partial isomorphism whose graph iscontained in G.

Proof. Let D be a fundamental domain. Given A ⊂ F, we consider a−1(A) ⊂ (G, s)×(D, π∣∣∣D).

Using Lusin-Novikov’s Theorem, we can find a partition

a−1(A) = qi(Θi, s) × (Di, π),

such that t∣∣∣Θi

and s∣∣∣Θi

are injective. We define Ai = a ((Θi, s) × (Di, π)) and we observe thatΘi defines an isomorphism θi : Ai → Di.

1. If A is a fundamental subset, then Di are disjoint subsets, hence A � qiDi andA ∪D \ qiDi is a fundamental domain.

2. Each Ai is a fundamental set.

3. If A is a fundamental domain, then it is also a fundamental subset, so Di are disjointand the function f = qiθi : A → D is injective. For every x ∈ D there exist y ∈ Aand 1 ∈ G such that 1y = x. By uniqueness of y and 1, we have f (y) = x.

�

Definition 2.2.53. Let (F, π) be a smooth G-fibred space with fundamental domain D. Wedefine the quotient map to be q = P2 ◦ a−1 : F→ D,

(G, t) × (D, π∣∣∣D) a //

P2

��

F

π

��q

vvDπ|D // G0

Remark 2.2.54. Let ϕ : (F1, π1) → (F2, π2) be a G-equivariant map. If A2 ⊂ F2 is a funda-mental subset, then ϕ−1(A2) is a fundamental subset. In fact for every x ∈ ϕ−1(A2),

ϕ(1x) = 1ϕ(x) < A2 ⇒ 1x < ϕ−1(A2).

Moreover if (F2, π2) is smooth, with fundamental domain D2, then ϕ−1(D2) is a fun-damental domain for (F1, π1). In fact given x ∈ F1 there exists 1 such that 1ϕ(x) ∈ D2, so1x ∈ ϕ−1(D2).

Remark 2.2.55. Let (F1, π1) and (F2, π2) beG-fibred spaces and let D1 ⊂ F1 be a fundamentaldomain. For every map ϕ : (D1, π1) → (F2, π2), there exists a unique G-equivariant mapϕ : (F1, π1)→ (F2, π2), defined by ϕ(1x) := 1ϕ(x).

28

Remark 2.2.56. Let (F1, π1) and (F2, π2) be smooth G-fibred spaces with fundamental do-mains D1 and D2. Let ϕ : (F1, π1) → (F2, π2) be a G-equivariant morphism of fibredspaces, such that ϕ(D1) ⊂ D2. If ϕ

∣∣∣D1

is injective, then ϕ is injective. Let x, y ∈ D1 suchthat ϕ(11x) = ϕ(12y), then

11ϕ(x) = 12ϕ(y)⇒ 1−12 11ϕ(x) = ϕ(y)⇒ 12 = 11,

since D2 is a fundamental domain. Then we obtain ϕ(x) = ϕ(y), hence x = y.

2.2.6 Totally isotropic sub-groupoids

Definition 2.2.57. Let G be a Borel discrete groupoid.

1. The groupoid G is principal if for every 1 ∈ G, s(1) = t(1) implies 1 ∈ G0.

2. The groupoid G is totally isotropic if for every 1 ∈ G, s(1) = t(1).

3. The isotropy group of x in G, is the discrete countable group Gx := s−1(x) ∩ t−1(x).

Remark 2.2.58. Principal groupoids are equivalence relations, in the sense of Example2.2.14.

Definition 2.2.59. A sub-groupoidH < G is a measurable subsetH ⊂ G such that for every(11, 12) ∈ (H , s) × (H , t), 111

−12 ∈ H . The sub-groupoid is principal (or totally isotropic) if

it is so as groupoid.

Definition 2.2.60. A sub-groupoid H < G acts on G by right multiplication. Since theaction of G on itself is smooth with fundamental domain G0, for every H < G theeaction by right multiplication is measurable and smooth. So we can define the quotientq : G → G

/H

.

In general G/H

is a Borel graph and we observe that G0 � V(G/H

). If (G, µ) is

measured, then ( G/H, µ) is a measured graph, since the action is smooth.

Each element 1 ∈ G defines an isomorphism of groups:

c1 : Gs(1) → Gt(1), c1(11) := 1111−1.

Definition 2.2.61. A totally isotropic sub-groupoid H < G is normal, if h ∈ H impliesc1(h) ∈ H , whenever (1, h) ∈ (G, s) × (H , t) is compatible.

IfH < G is a normal totally isotropic sub-groupoid, then the quotient G/H

is a Borelgroupoid with the product q(1)q(1′) = q(11′). As in group theory the consistency of theproduct is equivalent to the normality of the sub-groupoid.

Definition 2.2.62. Let G be a Borel discrete groupoid.

1. The isotropic part GI < G is the maximal totally isotropic sub-groupoid.

2. The principal part of G is the quotient GP := G/G

I .

29

Definition 2.2.63. Let ϕ : G → H be a morphism of Borel groupoids. We define theisotropy kernel ker(ϕ) to be the totally isotropic sub-groupoid of G

ker(ϕ) := ϕ−1(H0) ∩ GI.

The kernel is a Borel normal sub-groupoid, in fact for every h ∈ ker(ϕ)

ϕ(c1(h)) = ϕ(1)ϕ(h)ϕ(1−1) = ϕ(1)ϕ(1−1) = idt(1).

Remark 2.2.64. The kernel is the field of groups defined by ker(ϕ)x = ker(ϕx : Gx →Hϕ(x)

).

Example 2.2.65. Given any generating set Φ for G, we have a canonical surjection φ :G(Φ)→ G, that induces an isomorphism G(Φ)

/ker(φ) � G.

Definition 2.2.66. A presentation of the groupoid G, consist in a couple (G(Φ),H), whereG(Φ) is a free groupoid and H < G(Φ) is a normal totally isotropic subgroupoid, suchthat G � G(Φ)

/H

.

Since the family of generating sets is not empty, the family of presentations is notempty.

2.2.7 Bernoulli actions

Definition 2.2.67. Let (F, π,X) be a discrete fibred space, such that π−1(x) is infinite forevery x ∈ X. A sequence of sections {σn}n∈N, σn : G0 → G, is called a complete set of sectionsif

1. σi(G0) ∩ σ j(G0) = ∅ if i , j,

2. ∪nσn(G0) = G.

The Lusin-Novikov’s Theorem assures us that there always exists such a sequence.

Definition 2.2.68. Let G be a discrete Borel groupoid and let Y be a standard Borel space.We set

YG :=∐x∈G0

Yt−1(x).

Each section σ : G0 → G defines a morphism

σ : YG → Y, σ((yk)k∈t−1(x)) := yσ(x),

we define also a projection

π : YG → G0, π((yk)k∈t−1(x)) := x.

We endow YG with the Borel structure induced by the family σ and π.

30

Proposition 2.2.69. For each complete set of sections {σn}n (with respect to t), we have anisomorphism

YG � X ×YN,

given by

(yk)k∈t−1(x) 7→ (x, (yσn(x))n).

Proof. Given {σn}n we define

Σ :YG → X ×YN,

(yk)k∈t−1(x) 7→ (x, (yσn(x))n).

By definition Σ is Borel. Suppose that Σ(y) = Σ(y′), then x = x′ and yσn(x) = y′σn(x) for

all n, for (2) of Definition 2.2.67, y = y′. The map is surjective by definition. We have toshow that the inverse map is Borel. In order to do that we have only to observe that givenany section σ : G0 → G there exists a partition G0 = qnAn such that σ

∣∣∣An

= σn. So the mapσ : YG → Y is a Borel map respect to the Borel family induced by {σn}. �

In particular YG is a standard Borel space. Given a section σ : G0 → G of s, we cansimilarly define σ and also this map is Borel since we can find a measurable partitionG0 = qnAn such that σ

∣∣∣An

is a t-section.

Definition 2.2.70. We define an action of G on (YG, π,G0) as follows,

1 · (yk)k∈t−1(x) := (yk)1k∈t−1(1x) if t(1) = x.

In the case G = G a group, this action is the standard Bernoulli action.

Proposition 2.2.71. The action is a Borel action.

Proof. We have to show that for every section σ : G0 → G, the map

T := σ ◦ a : (G, s) × (YG, π)→ Y, T(1, y) = y1−1σ(1x),

is a Borel map. Let {σi} be a complete set of section of (G, s,G0) and we define a family oft-Borel sections as

τi : G0 → G, τi(x) := σi(x)−1σ(σi(x)x).

Then

T−1(A) =∐i∈N

(σi(G0), s) × (τ−1i (A), π),

so T is Borel. �

31

Definition 2.2.72. Suppose that (G, µ) is a discrete measured groupoid and that (Y, ν0) isa probability space. We define the measure ν on YG as follows

ν =

∫G0

ν⊗t−1(x)

0 dµ(x).

Let Σ be an isomorphism as in Proposition 2.2.69, then it is easy to see that Σ∗ν =

µ ⊗ ν⊗N

0 , so that ν is a well defined probability measure. In this way (YG, π,G0, ν) is ameasured diffuse fibred space.

Proposition 2.2.73. Suppose that the equivalence relation GP is ergodic. Then the action of G on(YG, π, ν) is free, ergodic and measure preserving.

Proof. Suppose that

1(yk)k∈t−1(x) = (yk)1k∈t−1(1x) = (yk)k∈t−1(x),

then 1x = x and yk = y1−1k for every k. So, up to a set of measure zero, the action is free.The fact that the action preserves the measure is pretty straightforward since

1∗ν⊗

t−1(x)

0 = ν⊗t−1(1x)

0 , ∀1 ∈−1 (x).

We prove now that the equivalence relation is ergodic. We fix a complete sequence ofsections {σk}k. Let A ⊂ YG. We define the support

supp(A) :=∐

k

σk(π

(Y × G0 \ π × σk(A)

)),

more explicitly

1 ∈ supp(A)⇔ π1(π−1(t(1)) , Y, where π1 : (yk)k∈t−1(t(1)) 7→ y1.

Lemma 2.2.74. For each θ ⊂ G such that s∣∣∣θ

and t∣∣∣θ

are isomorphisms, supp(θA) = θsupp(A).

Proof. We observe that {y1; (yk)k∈t−1(t(1)) ∈ θA

}=

={y1; (yθk)k∈t−1(θt(1)) ∈ A

}=

={yθ−11; (yk)k∈t−1(t(θ1)) ∈ A

},

so that 1 ∈ supp(θA) if and only if θ−11 ∈ supp(A). �

Remark 2.2.75. As in the classical case, if supp(A) and supp(B) are disjoint, we have

ν⊗t−1(x)

(A ∩ B ∩ π−1(x)) = ν⊗t−1(x)

(A ∩ π−1(x))ν⊗t−1(x)

(B ∩ π−1(x)),

as the two events are independent.

32

We say that A is bounded if supp(A) has finite measure. We observe that if A isbounded, then π(A) = X and that A = YG if and only if supp(A) = ∅. We can now provethe ergodicity. Let A be an invariant subset of positive measure. By the ergodicity of GP

we know that π(A) = X and that the function

x 7→ ν⊗t−1(x)

(A ∩ π−1(x)),

is constant to λ = µ(A ∩ π−1(x)) ∈ (0, 1]. Up to a small error, we can suppose that A isbounded. We fix

θ ⊂ G \(supp(A)−1

· supp(A)),

such that t∣∣∣θ

and s∣∣∣θ

are isomorphisms. Then the lemma and the remark imply

λ = ν(A) =ν(θA ∩ A) =

∫G0

ν⊗t−1(x)

(A ∩ θA ∩ π−1(x))dµ(x) =

=

∫G0

ν⊗t−1(x)

(A ∩ π−1(x))ν⊗t−1(x)

(θA ∩ π−1(x))dµ(x) =

=

∫G0

λ2dµ(x) = λ2,

so λ = 1. �

In particular the action-groupoid G nYG is an ergodic equivalence relation.

Remark 2.2.76 (Generalized Bernoulli actions). LetG be a discrete Borel groupoid, let (F, π)be a discrete G-fibred space and let Y be a standard Borel space. As in Definition 2.2.68,we can define the standard Borel space YF and the groupoid G acts freely on YF, as in theprevious case.

2.2.8 Free products

Free products are good tools for constructing new examples. A reference for the grouptheoretical case is [29] and for equivalence relations [19].

Definition 2.2.77. Let Gi = G(Ψi) be free groupoids for i = 1, 2 over the same baseX := (G1)0 = (G2)0. We define the free products of free groupoids to be

G(Ψ1) ∗ G(Ψ2) := G(Ψ1 qΨ2),

equipped with the natural Borel structure of free groupoid. We have two injective mea-surable maps

ji : G(Ψi)→ G(Ψ1 qΨ2),

that identify G(Ψi), with the sub-groupoid generated by Ψi, inside the free product.

33

Definition 2.2.78. LetG1 andG2 be Borel groupoids over the same baseX := (G1)0 = (G2)0.We define the free products as

G1 ∗ G2 := G(Ψ1 qΨ2)/⟨j1(H1), j2(H2)

⟩.As in the group case this definition does not depend on the presentations.

Remark 2.2.79. 1. If µ is a measure on X such that (G1, µ) and (G2, µ) are measuredgroupoids, then µ is a measure for the free product.

2. The two measurable maps of groupoids ji : Gi → G1 ∗G2, induced by the immersionat the level of free groupoids, are injective.

3. The free product is commutative G1 ∗ G2 = G2 ∗ G1.

4. We can similarly define the free product of an arbitrary family of groupoids.

We state the Grushko’s theorem, that will be used in the next section. For a proof inthe context of group theory see [29]. The theorem for groupoid was proved by Alvarezin [6].

Theorem 2.2.80 (Alvarez). Let G(Ψ) be a free groupoid, H = ∗i∈IHi a free product and f :G → H a surjective map. There exist measurable subsets Ψi ⊂ G(Ψ) for i ∈ I, such thatG(Ψ) � ∗i∈IG(Ψi) and f (G(Ψi)) = Hi.

Proof. See Theorem 4.23 of [6]. �

By the Nielsen-Schreier’s Theorem, 2.2.42, G(Ψi) are free groupoids.

2.2.9 G-fields of graphs

Definition 2.2.81. Let (F , π,G0) be a field of graphs. An action of the groupoid G on(F , π,G0) is:

• an action of G on (V(F ), π,G0) as fibred space,

• an action of G on E(F ) such that 1o = o1, 1r = r1.

The action ofG on (F , π,G0) is smooth, if there exists a fundamental domain D ⊂ V(F )for the action of G on V(F ).

Notation 2.2.82. We adopt the same notation of 2.2.44: if G acts on (F , π,G0), we say that(F , π) is aG-field of graphs. We will always write (F , π) instead of (F , π,G0) in this context.We will denote 1x := a(1, x) the action.

Definition 2.2.83. Let Φ ⊂ G be a measurable subset. We define the Cayley graph Γ(G,Φ)to be the field of graphs

• th vertices V(Γ(G,Φ)) := G, edges E(Γ(G,Φ)) := (Φ, s) × (G, t) and π := s,

• o, r : E(Γ(G,Φ))→ V(Γ(G,Φ)) are defined by o(ϕ, 1) := 1 and r(ϕ, 1) := ϕ1.

34

The groupoid G acts on Γ(G,Φ) in the following way:

1 · h :=h1−1, ∀1 ∈ G, h ∈ V(Γ(G,Φ)),

1 · (ϕ, h) :=(ϕ, h1−1) ∀1 ∈ G, (ϕ, h) ∈ E(Γ(G,Φ)).

The action is smooth with fundamental domain D = G0 ⊂ E(Γ(G,Φ)).

Example 2.2.84. Let G = X ×G be an action groupoid as in Example 2.2.15 and let S ⊂ G agenerating set. The Cayley graph Γ(G,X × S) is a field of Cayley graphs, that is for eachx ∈ G0 the graph π−1(x) is isomorphic to the Cayley graph of G with respect to S.

The Cayley graphs of X × Z with respect to X × {2, 3} and X × {1}.

-2

0

2

-1

1

34

56

7

X X

-101234567

Remark 2.2.85. The field Γ(G,Φ) is a field of connected graphs if and only if Φ is a generatingset.

Proposition 2.2.86. Let Ψ ⊂ G be a measurable subset and let H < G be the sub-groupoidgenerated by Ψ. The groupoidH is free over Ψ if and only if Γ(G,Ψ) is a field of forests.

Proof. If the groupoid H is free over Ψ, then it is a path groupoid H � G(Ψ), henceΓ(G,Ψ) is a field of forests. Conversely suppose that Γ(G,Ψ) is a field of forests. There isno non-empty word in Ψ, that is an unity, soH is free. �

We obtain an analogy between treeable equivalence relation, see [19], and free groupoids.

Corollary 2.2.87. A treeable equivalence relation is a free principal groupoid.

Remark 2.2.88. Let (F , π) be a smooth G-field of graphs. By definition of action, the mapso and r pass to the quotient o, r : E(F )

/G→

V(F )/G

. So the quotient is a Borel graph. Itis measured if the field of graph is measured.

Example 2.2.89. Let Γ(G,Φ) be a Cayley graph, then Γ(G,Φ)/G� Φ (as graphs).

35

2.3 Groupoid Cost

In this chapter we define a fundamental invariant, the (groupoid-)cost. This invarianttakes the role of the rank (the minimal number of generators) of a group. We will showthat when the groupoid is an equivalence relation, then the cost coincides with the costdefined by Levitt, [28]. The cost for groupoids was defined by Abèrt and Nikolov, [3], forthe special case of group actions.

The first simple case that we will study is the groupoid with “finite rank isotropy”. Wewill show that if the rank of each isotropy group is finite, then one can compute the costof the groupoid knowing the rank of the isotropy groups and the cost of the associatedprincipal groupoid.

Definition 2.3.1. The (groupoid-)cost of a discrete measured groupoid (G, µ) is:

gcost(G) := inf{µ(Φ)

∣∣∣Φ is a generating set}.

Example 2.3.2. Let G = GnX be an action groupoid as in Example 2.2.15. Then gcost(G) ≤r(G)µ(G0) where r(G) is the rank of G. The equality holds for trivial actions.

Definition 2.3.3. Let (G, µ) and (H , ν) be measured discrete groupoids. As in Definition2.2.5, we say that a surjective map of groupoids f : G → H is a fibration if it has countablefibres and the counting measure satisfies ν f = µ (see Definition 2.2.2 for the countingmeasure). We say that G is fibred over G, if there exists a fibration f : G → H .

Proposition 2.3.4. Let (G, µ) and (H , ν) be measured discrete groupoids.

1. If f : G → H is a fibration, then gcost(G) ≥ gcost(H).

2. Let GP be the associated principal groupoid, then gcost(G) ≥ gcost(GP).

Proof. 1. Let Φ ⊂ G be a generating set. Since f is surjective, f (Φ) is a generating setforH . The equality ν f = µ tells us that µ(Φ) ≥ ν( f (Φ)).

2. Let GI < G be the totally isotropic sub-groupoid of G. Then the quotient mapq : G → G

/G

I = GP is a fibration.�

2.3.1 Compatibility with other definitions

The cost for an equivalence relation was defined by Levitt in [28] and mainly developedby Gaboriau, see [19]. The cost of an equivalence relation, denote by cost(R), is definedthrough a graphing of the equivalence relation, see [19] for the definition. We prove thatthe two different definitions of cost for a principal groupoid coincide.

Proposition 2.3.5. If G is principal, then gcost(G) = cost(G).

Proof. In first place we can suppose that G ⊂ G0 ×G0 via the isomorphism 1 7→ (s(1), t(1)).Let Φ = (ϕ j : A j → B j) j∈J be a graphing of G. For every j, the graph of ϕ j is a subset ofG and its measure is exactly the measure of A j (or equivalently of B j). Moreover the set

36

Φ := ∪ j graph(ϕ j) ⊂ G is a generating set, since every element 1 ∈ G can be written asa word in the ϕ±j . Therefore µ(Φ) ≤ cost(Φ) and so gcost(G) ≤ cost(G). Conversely, let Φ

be a generating set. We take a measurable partition Φ = q jΦ j such that s∣∣∣Φ j

and t∣∣∣Φ j

areinjective. The measurable subset Φ j are graphs of partial isomorphism ϕ j : s(Φ j)→ t(Φ j),hence

Φ := (ϕ j : s(Φ j)→ t(Φ j)) j∈J,

is a graphing, cost(Φ) = µ(Φ), so gcost(G) ≥ cost(G). �

The first definition of cost, in a non-free context, was given by Abèrt and Nikolov in [3]for a (possibly non-free) measure-preserving action of a countable group G on a standardBorel space (X, µ). Given an action of G on (X, µ) we denote with pcost(G,X) the cost ofthe action in the sense of Abèrt and Nikolov and let G = G n X be the action groupoid, asin Example 2.2.15.

Proposition 2.3.6. If G = G n X is an action-groupoid, then gcost(G) = pcost(G,X).

Proof. We will recall step by step the notation of [3] and we will translate it in our context.

1. A graphing for G is a Borel subset M ⊂ G. For every 1 ∈ G, we denote

M1 := {x ∈ X such that (1, x) ∈M}.

We set

degM(x) :=∣∣∣{1 ∈ G such that x ∈M1}

∣∣∣ and e(M) :=∫

x∈XdegM(x)dµ(x).

We observe that µ(M) = e(M).

2. We define the graphing Mᵀ as Mᵀ1 := 1−1·M1−1 , where · is the action of 1 on X. We

observe that Mᵀ = M−1, in fact (1, x) ∈M−1 if and only if (1−1, 1x) ∈M, if and only if

1x ∈M1−1 ⇔ x ∈ 1−1·M1−1 = Mᵀ1 ⇔ (1, x) ∈Mᵀ.

3. Given two graphings M and N, we define the graphing M ·N by

(M ·N)1 :=⋃h∈G

(Mh ∩

(h−1·Nh−11

)).

We observe that M ·N = NM, in fact (1, x) ∈ NM if and only if there exists (1h−1, hx) ∈N and (h, x) ∈M, if and only if

hx ∈ N1h−1 , x ∈Mh ⇔ x ∈ h−1·N1h−1 ∩Mh for a h ∈ G.

4. Let I = G0 ⊂ G be the graph consisting only of the set of unities. We set

Mk := Mk−1∪

(Mk−1

· (M ∪Mᵀ ∪ I)).

We observe that it is the k-th power of M±.

37

5. The graphing M is a L-graphing if ⋃k

Mk = G.

We observe that this is equivalent to ask that M is a generating set. Now we canrecall the definition of the cost for the action and we show that is equivalent to thecost in our context:

pcost(G,X) := infM L-graphing

e(M) = infM generating set

µ(M) = gcost(G).

�

2.3.2 Case of finite-rank isotropy

Definition 2.3.7. Let G be a discrete Borel groupoid. We define the rank function of G tobe

r : G0 → N ∪ {∞}, r(x) :={minimum number of generators of the isotropy group Gx

}.

If Gx = {1}, then r(x) = 0.

Let G be a discrete Borel groupoid. We recall that we denote with GP the principalpart of G and GI the totaly isotropic sub-groupoid of G. See Definition 2.2.62.

Proposition 2.3.8. For every groupoid G, there exists a generating set A ⊂ GI of GI, such thatr(x) = |s−1(x) ∩ A|. In particular r : G0 → N ∪ {∞} is measurable.

Proof. We can suppose that G = GI is totally isotropic and that Gx , {id} almost every-where. We take a measurable partition of G =

∐i Ai such that s

∣∣∣Ai

is injective. Let I be theset of finite parts of N. For each α ∈ I, we define

Bα := G0 \ s (G \ 〈∪i∈αAi〉) .

We observe that

r−1(N) = ∪α∈IBα,

and we set B∞ = r−1(∞). We observe that each Bα is measurable, so B∞ is measurable. LetG0 = C∞ qqα∈ICα be a partition that satisfy the following conditions:

1. Cα ⊂ Bα possibly empty, C∞ = B∞,

2. if x ∈ Cα ∩ Bβ, then |α| ≤ |β|.

Then

A := s−1(C∞)q∐α∈I

s−1(Cα) ∩ (∪i∈αAi) ,

is the required set. �

38

Given A ⊂ G0 we denote r(A) =∫

A r(x)dµ(x).

Corollary 2.3.9. If G = GI is a field of groups, then gcost(G) = r(G0).

Proposition 2.3.10. Let A ⊂ G0 be a subset that meet every GP-orbit. The following inequalityholds: gcost(G) ≤ gcost(GP) + r(A).

Proof. Let Φ1 be a generating set for GP and let q : G → GP be the quotient map. Weconsider Φ1 ⊂ G such that q : Φ1 → Φ1 is an isomorphism. Let Φ2 ⊂ G

I be a generatingset for GI

∣∣∣A, we set Φ := Φ1 ∪ Φ2. We claim that Φ is a generating set. Given 1 ∈ G, there

exist h, hk, . . . , h1 ∈ 〈Φ1〉 such that s(h) ∈ A, t(h) = s(1) and q(1) = q(hk . . . h1). Then

h = h−11−1hk . . . h1h ∈ GI

and

1 =(hhh−1h−1

1 . . . h−1k

)−1.

So gcost(G) ≤ µ(Φ) + r(A) and then gcost(G) ≤ gcost(GP) + r(A). �

Corollary 2.3.11. If GP is aperiodic and if the rank function is bounded, then gcost(G) =gcost(GP).

Proof. We know that gcost(G) ≥ gcost(GP). Now we apply the Proposition 2.3.10 to asequence of nested subsets An ⊂ G0 that meets every GP orbit and such that µ(An) → 0(so r(An)→ 0), to obtain the other inequality. �

The cost for smooth equivalence relations was studied by Levitt in [28], see alsoProposition III.3 of [19].

Proposition 2.3.12 (Levitt). If A is a fundamental domain for the principal groupoid G = GP,then G is free over Ψ and µ(Ψ) = cost(G) = µ(G0) − µ(A).

We state an analogue for the groupoid case.

Proposition 2.3.13. If D ⊂ G0 is a fundamental domain for the action of GP on G0, thengcost(G) = µ(G0) − µ(D) + r(D).

As in [19], the proposition is a corollary of the “induction” (see Proposition II.6 of[19]). We recall that if G is a groupoid and A ⊂ G0 a measurable subset we denote withG

∣∣∣A the restriction of G, see Definition 2.2.16.

Proposition 2.3.14 (Gaboriau; Induction). Let A ⊂ G0 be a measurable subset that meets everyorbit, then gcost

(G

∣∣∣A

)= gcost (G) − µ(G0 \ A).

Proof. Given Φ ⊂ G and B1,B2 ⊂ G0 measurable subsets, we set

ΦB1, B2 := Φ ∩ s−1(B1) ∩ t−1(B2).

39

Let Φ be a generating set of G. We define a sequence of disjoint measurable subsetsΨn ⊂ Φ inductively. We define

f1 : ΦA, G0\A

∐ΦG0\A, A → G0 \ A, f1(1) =

{t(1) if s(1) ∈ As(1) if t(1) ∈ A

and let Ψ1 be a subset such that f1∣∣∣Ψ1

is injective and f1(Ψ1) is maximal. Suppose we havedefined Ψi for i ≤ k. We set

Ak := A ∪k⋃

i=1

fi(Ψi),

and we define as before

fk+1 : Φ fk(Ψk), G0\Ak

∐ΦG0\Ak, fk(Ψk) → G0 \ Ak, fk+1(1) =

{t(1) if s(1) ∈ fk(Ψk)s(1) if t(1) ∈ fk(Ψk)

and let Ψk+1 be a subset such that fk+1

∣∣∣Ψk+1

is injective and fk+1 (Ψk+1) is maximal. Wedefine Ψ := qkΨk and f := qk fk. Since Φ is a generating set and since A meets everyorbit, f : Ψ→ G0 \ A is an isomorphism.

We can assume f = t. We remark that H = 〈Ψ〉 is principal and free, since f∣∣∣Ψ

isinjective, so

t : HA,G0\A → G0 \ A,

is an isomorphism. Using the notation of Definition 2.2.8 we observe that

(AqHA, G0\A, t) × (Φ \Ψ, t, s) × (AqHA, G0\A, t)P2 // Φ \Ψ ,

is an isomorphism and we define

ψ := p3 ◦ P−12 : Φ \Ψ→ G, ψ(1) = h−1

2 1h1 if P−12 (1) = (h2, 1, h1).

By definition is clear that ψ(Φ \ Ψ) q Ψ is a generating set for G and ψ(Φ \ Ψ) is agenerating set for G

∣∣∣A. So

gcost(G

∣∣∣A

)≤ µ

(ψ(Φ \Ψ)

)≤ µ(Φ) − µ (G0 \ A) ,

and by arbitrariness of Φ, we have

gcost(G

∣∣∣A

)≤ gcost(G) − µ (G0 \ A) .

Conversely let Φ′ be a generating set for G∣∣∣A. Let Φ be any generating set for G and

we define Ψ as before. For each 1 ∈ G we can find h, h′ ∈ Ψq A such that h−11h′ ∈ G∣∣∣A,

so Φ′ ∪Ψ is a generating set for G. Hence the other inequality. �

We can now prove Proposition 2.3.13.

Proof of Proposition 2.3.13. We apply Proposition 2.3.14 with A = D. Since G∣∣∣D is totally

isotropic gcost(G

∣∣∣D

)= r(D). �

40

2.3.3 Cost of free groupoids and free products

Proposition 2.3.15. Let (G, µ) be a discrete measured groupoid and (F, π, ν) be a diffuse G-fibredspace with ν a probability measure (on F). Then gcost(G n F) ≤ gcost(G).

Proof. Let Φ be a generating set for G. We define Φ ⊂ G n F as

Φ := (Φ, s) × (F, π).

By definition Φ is a generating set for G n F, and ν(Φ)

= µ(Φ). �

We recall a famous theorem of Gaboriau.

Theorem 2.3.16 (Gaboriau, [18]). Let R be an equivalence relation and let Φ be a treeing of R.Then cost(R) = cost(Φ).

Corollary 2.3.17. Let G = G(Ψ) be a free groupoid over Ψ, then gcost(Ψ) = µ(Ψ).

Proof. Let (Y, ν0) be a probability space and consider the Bernoulli action of G on YG.Since the action is free, the generating set Ψ = (Ψ, s) × (YG, π) is a free generating set forthe equivalence relation, also called treeing. By the previous theorem,

gcost(G) ≥ cost(G nYG

)= ν(Ψ) = µ(Ψ).

�

Proof. Let G be a free groupoid over Ψ and let Φ be a generating set. If Φ has not finitemeasure there is nothing to prove. Otherwise we consider Γ(Φ,Ψ) as in Proposition2.4.12. If µ(Ψ) if finite, then we apply the Theorem 2.4.21 to Γ(Φ,Ψ) as a deploymentof Γ(G,Ψ). We obtain Ms(Γ(G,Φ)) ≥ Ms(Γ(G,Ψ)) and so µ(Φ) ≥ µ(Ψ). If µ(Ψ) is notfinite, then up to an arbitrary small error, we can suppose that D′ has finite measure.Since Ms(Γ(Φ,Ψ)) is finite, o−1 (D′) has finite measure. We denote with D a fundamentaldomain of Γ(G,Ψ), then

P : E(Γ(Φ,Ψ))→ E(Γ(G,Ψ))

is a G-equivariant surjective morphism of fibred spaces, hence P−1(o−1(D)) is a funda-mental subset by Remark 2.2.54, and it has infinite measure. This is a contradiction, sinceall the fundamental domains have the same measure. �

Using Grushko’s theorem, we can compute the groupoid cost of a free products as ingroup theory.

Corollary 2.3.18. Given two discrete measured groupoid (G1, µ) and (G2, µ) with the same spaceof unites ((G1)0, µ) = ((G2)0, µ), we have gcost(G1 ∗ G2) = gcost(G1) + gcost(G2).

Proof. Taking the disjoint union of a generating set of G1 and one of G2 inside the freeproduct, we obtain gcost(G1 ∗ G2) ≤ gcost(G1) + gcost(G2). Let Ψ ⊂ G1 ∗ G2 be a generating

41

set, by Grushko’s Theorem, 2.2.80, there exists Ψ1,Ψ2 ⊂ G(Ψ) such that the diagramcommutes

G(Ψ)∼

''

ϕ // G1 ∗ G2

G(Ψ1) ∗ G(Ψ2)

ϕ77

where ϕ is the canonical map and ϕ(G(Ψi)) = Gi. So µ(Ψi) ≥ gcost(Gi), hence

gcost(G(Ψ)) = µ(Ψ) = gcost(G(Ψ1) ∗ G(Ψ2)) = µ(Ψ1) + µ(Ψ2) ≥ gcost(G1) + gcost(G2).

�

2.4 Cost of free groupoids

The aim of this section is to give a complete proof of Corollary 2.3.17 in the groupoidcontext, without using Gaboriau’s result.

Theorem 2.4.1. Let G be a free groupoid over Ψ. Then gcost(G) = µ(Ψ).

• In the case G0 = {∗}, so G is a group, this theorem says that a free groups over ngenerators has rank n.

• In the case G = GP, so G is an equivalence relation, this theorem is equivalent to atheorem of Gaboriau, see [18].

We will adopt the strategy of [18] and the ideas of Stalling’s proof of Grushko’stheorem, see [29, p. 121]. The idea of the proof is to compare the Cayley graph withrespect to a given generating set and the Cayley graph with respect to the free generatingset. A priori, there is not an obvious way to construct a morphism of graphs betweenthem and in order to define a “nice” one, we have to subdivide all the edges of the firstfield of graph. The new graph obtained in this way is too big and we will conclude theproof by “folding” some edges.

2.4.1 Group case

First of all, we prove the theorem when the groupoid is actually a group.

Theorem 2.4.2. Let S be any finite set and let G(S) be the free groups over S, then r(G(S)) = |S|.

We give a one-line proof: G(S) maps onto Z|S|, so r(G(S)) ≥ |S|. Unfortunately thisproof does not generalize to the case of groupoids. So we give an another proof of thetheorem and we will adopt the same strategy and similar notation of the general case.

Proof. Let X ⊂ G(S) be a generating set. We consier the Cayley graphs Γ(G(S),X) andΓ(G(S),S) and we consider a G(S)-equivariant map

ϕ : V(Γ(G(S),X))→ V(Γ(G(S),S)).

42

In order to compare the two graphs, we would like to extend ϕ to a map of graphs.Obviously this is not always possible, since the image of an edge of Γ(G(S),X) should be apath in Γ(G(S),S). So to extend ϕwe need to subdivide each edge of Γ(G(S),X) accordingto the path in Γ(G(S),S).

Locally the two graphs look like these and there is no way toconstruct a morphism of graphs between them.

Let’s do it formally. Clearly we can suppose Γ(G(S),X) to be without loops and doubleedges. First of all, we extend ϕ to a maps

ϕ : G(Γ(G(S),X))→ G(Γ(G(S),S)),

of the associated path groupoids. The groupoid G(Γ(G(S),X)) is free, so it is enough todefine

ϕ : E(Γ(G(S),X))→ G(Γ(G(S),S)).

We define ϕ(e) to be the unique reduced path form ϕ(o(e)) to ϕ(r(e)). The G(S)-actionson the Cayley graphs extend to the path groupoids and with respect to these actions ϕ isG(S)-equivariant.

For each e ∈ E(Γ(G(S),X)), we define the length function

˜(e) = k if ϕ(e) = (ek, . . . , e1), ei ∈ E(Γ(G(S),S)).

The new “intermediary” graph Γ(X,S) is defined in the following way: we startfrom Γ(G(S),X) and we subdivide each edge e ∈ E(Γ(G(S),X)) in ˜(e) edges, adding thecorresponding vertices. That means

V(Γ(X,S)) := V(Γ(G(S),X))q∐

e∈E(Γ(G(S),X))

˜(e)∐i=2

(e, i)v

E(Γ(X,S)) :=∐

e∈E(Γ(G(S),X))

˜(e)∐i=1

(e, i)e ,

o ((e, i)e) := (e, i)v , o(e) = o(e),

r((e, i)e) :={

(e, i + 1)v if i < ˜(e),r(e) otherwise,

r(e) = (e, 2)v.

= The new graph looks like this.

We define an action of G(S) on Γ(X,S) in the following way

1 · (e, i)∗ = (1e, i)∗, with ∗ ∈ {v, e}.

43

If we forget the new vertices, this action is the old action on Γ(G(S),X). The actionis not anymore vertex-transitive, but it has a finite fundamental domain. We recall thatgiven a graph Γ, we denote with Γ the union of the graph and its opposite, see Definition2.2.22. We define a G(S)-equivariant morphism of graphs

P : Γ(X,S)→ Γ(G(S),S),P ((e, i)e) := ei, P(e) = e1, P ((e, i)v) = o(ei), P(v) = v

where ϕ(e) = (ek, . . . , e1), note that ei could not be in E(Γ(F(S),S)). This map is clearlyG(S)-equivariant. Since Γ(G(S),S) is a tree, the extended map

P : Γ(X,S)→ Γ(G(S),S)

is surjective. We define a G(S)-equivariant injective map os the Cayley graph Γ(G(S),X)into the path groupoid of Γ(X,S), in the following way

Q : Γ(G(S),X)→ G(Γ(X,S)),

Q(v) = v, Q(e) =((e, ˜(e)), . . . , (e, 2), e

),

for v ∈ V(Γ(G(S),X) and e ∈ E(Γ(G(S),X).We have constructed what we wanted and now we want to isolate the essential

information of this graph. We list here the properties we really care about:

1. the action of G(S) on Γ(X,S) is smooth,

2. every fundamental domain is finite,

3. the following diagram commutes

G (Γ(X,S))P

''Γ(F(S),X)

ϕ //*

Q77

G(Γ(F(S),S))

The next step is to encode Γ(F(S),X) in the bigger graph. Let D be a fundamentaldomain for Γ(X,S), we define

M(X,S) :=12

∑x∈D

val(x) − 2

,where val is the valency function in the graph Γ(X,S), see Definition 2.4.9. We remark thatall the fundamental domains are isomorphic, see Corollary 2.2.52, so that M(X,S) doesnot depends on D. By construction of the graph, most of the edges have valency 2, inparticular it is the case for all the added vertices, so M(X,S) = |X| − 1. Finally observe that

σ := Q ◦ ϕ−1 : V(Γ(F(S),X))→ V(Γ(X,S)),

is a section of P at the level of vertices.Now we have isolated all the essential properties of Γ(X,S).

44

Definition 2.4.3. A triple (Γ′,P, σ) is a deployment of Γ(G(S),S) if

1. Γ′ is a smooth connected G(S)-graph

2. the fundamental domain is finite,

3. P : Γ′ → Γ(G(S),S) is a surjective map of graphs,

4. σ : V(Γ(G(S),S))→ V(Γ′) is a section of P such that

G(Γ′)∣∣∣σ(Γ(G(S),S))

P−→ G(Γ(G(S),S)),

is surjective. We will denote P := P∣∣∣G(Γ′)

∣∣∣σ(Γ(G(S),S))

the restricted map.

The forth condition holds in our case, since

G(Γ′)∣∣∣σ(Γ(G(S),S)) � Q(G(Γ(G(S),X)).

Given a deployment (Γ′,P, σ), we consider a fundamental set D′ and we define

M(Γ′) :=12

∑x∈D′

val(x) − 2

,as before. We can restate the theorem:

Theorem. If (Γ′,P, σ) is a deployment of Γ(G(S),S), then M(Γ′) ≥ |S| − 1.

Clearly it is enough to prove this theorem, in fact taking Γ′ = Γ(X,S) the previoustheorem says |X| − 1 ≥ |S| − 1.

Definition 2.4.4. Let x ∈ V(Γ(G(S),S). Given a deployment (Γ′,P, σ), we define

d := maxe ∈ o−1(x)

minp ∈ P−1(e)

`′(p)

,where `′ is the length function with respect to Γ′, see Definition 2.2.21. We observe thatd does not depend on x.

The integer d expresses the length of the longest minimal path in the deployment,whose image via P is an edge in Γ(G(S),S).

Lemma 2.4.5. If d = 1, then M(Γ′) ≥ |S| − 1.

Proof. We consider the finite graph Λ := Γ′/G(S). Since Γ′ is connected Λ is connected.

The assumption d = 1 implies that Λ has at least |S| loops. So

M(Γ′) = |E(Λ)| − |V(Λ)| ≥ |S| + |V(Λ)| − 1 − |V(Λ)| ≥ |S| − 1.

�

45

Intuitively the condition d = 1 means that the deployment contains the original graph.In the general situation the deployment contains only the associated groupoid. So eachedge is represented by a path (maybe more). Now we have to reduce the graph Γ(X,S),to make it satisfy the hypothesis of the lemma.

Definition 2.4.6. Let (Γ′,P, σ) be a deployment of Γ(G(S),S). A couple of oriented edges(eε1

1 , eε22 ) ∈ E(Γ′) × E(Γ′), where ε1, ε2 ∈ {+1,−1}, is reducible if

1. e1 , e2 and P(eε11 ) = P(eε2

2 ),

2. r(eε11 ) , r(eε2

2 ) and o(eε11 ) = o(eε2

2 ).

A couple of reducible edges are two consecutive edges representing the “redundancy”of the deployment. Clearly we do not need both of them in the graph. So, given a coupleof reducible edges (eε1

1 , eε22 ), we define an equivalence relation R on V(Γ′) as follows

1 · r(eε11 )R 1 · r(eε2

2 ), 1 ∈ G(S),

and a new deployment Γ′R, “without the redundancy”,

V(Γ′R) := V(Γ′)/R

E(Γ′R) := E(Γ′) \

⋃1∈G(S)

1e1

.We denote with q : V(Γ′) → V(Γ′R) the quotient map and we define oR = q ◦ o and

rR = q ◦ r. The identified vertices have the same P-image, so we can define PR in thequotient and similarly σR. The new graph is still smooth with fundamental domainP−1R (ϕS(id)),

ΓP

��q��

Γ′

P′

66Γ(G(S),S)σ′ooσ

dd

Lemma 2.4.7. In the above notations, we have M(Γ′) = M(Γ′R).

Proof. It is enough to observe that

E(

Γ′R/G(S)

)= E

(Γ′

/G(S)

)− 1,

V(

Γ′R/G(S)

)= V

(Γ′

/G(S)

)− 1.

�

Now, we want to prove that if we are not in the hypothesis of the Lemma 2.4.5, thenwe can erase something. For this purpose we use that Γ(G(S),S) is a tree. Suppose d > 1,

46

then there exists a path p of length greater than 1 whose image via P has length 1 (in thegroupoid). Since Γ(G(S),S) is a tree, there are two reducible edges.

We can conclude the proof of the theorem. We start with Γ(X,S). If d > 1, then wefind a couple of reducible edges and we take the quotient. We keep doing that until weobtain d = 1. This process has to finish, since in each step we decrease the cardinality ofthe fundamental set of the deployment, which is finite. In all the steps M(Γ(X,S)) remainsconstant, so

|X| − 1 = M(Γ(X,S)) ≥ |S| − 1⇒ |X| ≥ |S|.

�

→ → We glue edges until we erase all the new vertices.

2.4.2 Deployment

Definition 2.4.8. Let G be a discrete measured groupoid and let (F , π) be a smoothconnected G-field of graphs with a finite-measure fundamental set. A deployment of F isa triple (F ′,P, σ) where

1. F ′ = (F ′, π′) is a smooth connected G-field of graphs,

2. for each fundamental domain D′ for F ′, the fibers of π′ : D′ → G0 are finite,

3. P : F ′ → F is a G-equivariant morphism of fields of graphs,

4. σ : V(F )→ V(F ′) is an injective section of P such that

P : G (F ′)∣∣∣σ(V(F )) → G(F )P,

is surjective. We will denote with P := P∣∣∣G(F ′)

∣∣∣σ(V(F ))

the restricted map.

Definition 2.4.9. Let Γ be a Borel graph. We define the valency function

val = valΓ : V(Γ)→ N ∪ {∞}, val(x) =∣∣∣o−1(x)

∣∣∣ +∣∣∣r−1(x)

∣∣∣ .Given a measured graph (Γ, µ), we define

M(Γ) =12

∫V(Γ)

(val(x) − 2) dµ(x).

Given a smooth G-field of graphs F , we define

Ms(F ) := M(

Γ/G

).

47

Remark 2.4.10. Let (G, µ) be a measured discrete groupoid and let Φ be a generating set.Then

Γ(G,Φ)/G� Φ ⇒ Ms(Γ(G,Φ)) = M(Φ).

Definition 2.4.11. Let (F ′,P, σ) be a deployment ofF and let D be a fundamental domainof F . We define

d : D→ N ∪∞, d(v) := supe ∈ o−1(v)

minp ∈ P−1(e)

`′(p)

,where `′ is the length function with respect to E(F ′), see 2.2.21. By definition the functiond is measurable.

Proposition 2.4.12. Let (G, µ) be a measured discrete groupoid. Let Ψ and Φ be generating sets,such that µ(Φ) < ∞. Then there exists a deployment Γ(Φ,Ψ) of Γ(G,Ψ) such that Ms(Γ(Φ,Ψ)) =M(Φ).

We proceed exactly as in Theorem 2.4.2. We fix a G-equivariant isomorphism ϕ :V(Γ(G,Φ))→ V(Γ(G,Ψ)). The proposition follows from the following, a bit more general,proposition.

Proposition 2.4.13. Let (F1, π1) and (F2, π2) be smooth and connected G-fields of graphs. Sup-pose that the measure of the fundamental domains of F2 is finite and let ϕ : (V(F1), π1) →(V(F2), π2) be a G-equivariant isomorphism of fibred spaces. Then there exists a deployment(Γ(F1,F2),P, σ) of F2 such that Ms(Γ(F1,F2)) = Ms(F1).

Proof.

Lemma 2.4.14. There exists an extions of ϕ to a map ϕ : F1 → G(F2).

Proof. Let D1 be a fundamental domain of F1. We define

J :o−1(D1)→ V(F2) × V(F2), J(e) := (ϕ(o(e)), ϕ(r(e))),I :G(F2)→ V(F2) × V(F2), I(p) := (o(p), r(p)).

Let τ be a section of I. The morphism

τ ◦ J : o−1(D1)→ G(F2),

is defined on a fundamental domain and we can extend to a G-equivariant morphism ϕof the path groupoids

V(F2) × V(F2)τ

11 G(F2)Ipp

o−1(D1)

J

OO

τ◦J

55

� � // E(F1)

ϕ

OO .

�

48

At this point we can define the deployment exactly as Theorem 2.4.2. For e ∈ E(F1),let ˜(e) be the length of ϕ(e) with respect to E(F2). We set

V(Γ(F1,F2)) := V(F1)q∐

e∈E(F1)

˜(e)∐i=2

(e, i)v ,

E(Γ(F1,F2)) :=∐

e∈E(F1)

˜(e)∐i=1

(e, i)e ,

o ((e, i)e) := (e, i)v , o(e) = o(e),

r((e, i)e) :={

(e, i + 1)v if i < ˜(e),r(e) otherwise,

r(e) = (e, 2)v.

We define a map of graphs P : Γ(F1,F2)→ F2 as follows

P ((e, i)e) := ei, P ((e, i)v) = o(ei),

where ϕ(e) = (ek, . . . , e1). We define

π : V(Γ(F1,F2))→ G0, π((e, i)v) := π(e) = π(ei).

The action ofG defined by 1 ·(e, i)∗ = (1e, i)∗, with ∗ ∈ {v, e}, is smooth with fundamentaldomain D′ := P−1(D2), where D2 is a fundamental domain ofF2. The fibers ofπ : D′ → G0are almost always finite, since the measure of o−1(D2) is finite by assumption.

Let Q : V(F1) → V(Γ(F1,F2)) be the immersion (obtained by the definition), then byconstruction

valΓ(F1,F2)(v) =

{2 if v ∈ V(Γ(F1,F2)) \Q(V(F1))

valF1(v) if v ∈ Q(V(F1))

in particular Ms(F1) = Ms(Γ(F1,F2)).We define

σ : V(F2)→ V(Γ(F1,F2)), σ(v) = Q(ϕ−1(v)).

Since the two fields of graphs are connected, we obtain the condition (4) of the Defi-nition 2.4.8 and we have concluded the proof. �

49

The deployment of Γ(X × Z,X × {2, 3}) with respect to Γ(X × Z,X × {1}).

@

added vertices

subdivided edges

-2

0

2

-1

1

34

56

7

X

P

2.4.3 Reduction

As in Theorem 2.4.2, we introduce the concept of “reducibility”.

Definition 2.4.15. Let (F ′,P, σ) be a deployment ofF and letα1, α2 ⊂ E(F ′) be measurablesubsets of positive measure. The couple (αε1

1 , αε22 ), where ε1, ε2 ∈ {−1,+1}, is reducible if

1. α1 ∩ α2 = ∅ and P(αε11 ) = P(αε2

2 ),

2. r(αε11 ) ∩ r(αε2

2 ) = ∅ and o(αε11 ) = o(αε2

2 ),

3. r∣∣∣αi

and P∣∣∣αi

are injective for i = 1, 2,

4. the subsetsP(r(α1))) andP(r(α2)) are fundamental subsets (subset of a fundamentaldomain, Definition 2.2.49).

The definition is a bit more complicated than in the group case, since we are taking inconsideration subsets and not single edges.

Definition 2.4.16. Let (F ′,P, σ) be a deployment of F and let (αε11 , α

ε22 ) be a reducible

couple. We define a binary relation R = R(αε11 ,α

ε22 ) on V(F ′) as follows,

1 · r(eεii )R1 · r(eεi′

i′ ) if{

ei ∈ α1, ei′ ∈ α2,P(eεi

i ) = P(eεi′

i′ ) where {i, i′} = {1, 2} and 1 ∈ G.

50

Lemma 2.4.17. The binary relation R is an equivalence relation and its classes have at most twoelements.

Proof. Clearly R is reflexive and symmetric, we have to show that is transitive. We knowthat P(r(αεi

i )) is a fundamental subset, for i = 1, 2. By Remarks 2.2.54 and 2.2.56, P∣∣∣r(α

ε ji )

is

injective. Suppose that

1 · r(eε11 )R1 · r(eε2

2 ) = 1′ · r(eε33 )R1′ · r(eε4

4 ),

then

1 · P(r(eε22 )) = 1′ · P(r(eε3

3 ))⇒ 1 = 1′ and e2 = e3.

We can suppose that 12 ∈ α2 so 11, 14 ∈ α1, then

P(e1)ε1 = P(e2)ε2 = P(e4)ε1 ,

that implies e1 = e4 by injectivity of P∣∣∣αi

. �

Definition 2.4.18 (Folding). Let (F ′,P, σ) be a deployment ofF , let (αε11 , α

ε22 ) be a reducible

couple and let R the associated equivalence relation. We define a new deployment(F ′R,PR, σR) as follows. We set

V(F ′R) := V(F ′)/R and E(F ′R) := E(F ′) \ Gα1.

Let q : V(F ′) → V(F ′R) the quotient map, we define oR := q ◦ o and rR := q ◦ r. Since theequivalence relation is G-equivariant, we can still define a G action on F ′R. It is easy tocheck that F ′R is a smooth connected G-field of graphs. Since identified vertices have thesame P-image, the morphism P factorize to F ′R, so we define P′R the map in the quotient.Similarly we can define σR, since σ is a section of P.

Lemma 2.4.19. In the notation of the previous definition, ifµ(α1) = µ(α2) is finite, then Ms(F ′) =Ms(F ′R).

Proof. We need the finiteness of µ(α1), to be sure that Ms(F ′R) is well defined, in this case

the function valR −2 is integrable. We define Γ := F′/G, and ΓR := F

′

R/G

. It is enough toshow that M(Γ) = M(ΓR). We observe that ΓR is obtained from Γ by erasing some edgesand identifying the respective vertices. Since r is a measure-preserving isomorphism ofthe set of erased edges and erased vertices we have the equality M(Γ) = M(ΓR). �

2.4.4 Main proof

We observe that we have the following approximation property.Approximation Property: Let A ⊂ G0 be a subset of positive measure. If F ′ is a

deployment for F , then F ′∣∣∣A is a deployment for F

∣∣∣A, as G

∣∣∣A-fields of graphs. Moreover

if µ(An)→ 1, then

Ms(F

∣∣∣An

)→Ms(F ).

We state the analogue of Lemma 2.4.5. In this case d is a function and not a number,(2.4.11). The condition d = 1 means that the graph is a subgraph of the deployment,exactly as in the group case.

51

Lemma 2.4.20. Let (F , π) be a smooth connectedG-field of trees and let (F ′,P, σ) be a deploymentof (F , π). If d is constant equal to 1, then Ms(F ′) ≥Ms(F ).

Proof. Using the approximation property, we can suppose that the measure of the fun-damental domain of F ′ is finite. Since (F , π) is a field of trees, the map P : F ′ → F issurjective. We denote the quotients with

Γ := F/G, Γ′ := F

′/G.

The proof is the same of the group-case:

Ms(F ′) = M (Γ′) = µ(E(Γ′)) − µ(V(Γ′)) ≥ µ(E(Γ)) + µ(V(Γ′)) − µ(X) − µ(V(Γ′)).

�

Theorem 2.4.21. Let (F , π) be a smooth connected G-field of trees and let (F ′,P, σ) be a deploy-ment of (F , π). If the measure of a fundamental domain of F is finite, then Ms(F ′) ≥Ms(F ).

Proof. Let D a fundamental domain of F and let d as in Definition 2.4.11. We state thelast lemma.

Lemma 2.4.22. For every ε > 0 there exists a deployment (F ′ε ,Pε, σε) and a measurable subsetAε ⊂ G0 such that Ms(F ′ε ) = Ms(F ′), µ(Aε) ≥ 1 − ε and dε

∣∣∣Aε

= 1.

Now we show how to conclude to proof using the lemma, by the approximationproperty F ′ε

∣∣∣Aε

is a deployment of F∣∣∣Aε

and the relative d is constant to 1 by Lemma2.4.22, so by Lemma 2.4.20 we have

Ms(F′

ε

∣∣∣Aε

)≥Ms

(F

∣∣∣Aε

).

Again by the approximation property, taking the limit for ε→ 0 we get

Ms(F ′) ≥Ms(F ).

Now we prove Lemma 2.4.22

Proof. We have to prove that for each deployment (F ′1 ,P1, σ1) of (F , π), such that d1

∣∣∣A > 1

for A ⊂ D of positive measure, there exists a deployment (F ′2 ,P2, σ2) such that

1. Ms(F ′2 ) = Ms(F ′1 ),

2. 2µ ({x such that d2(x) < d1(x)}) ≥ µ(A).

Since the measure of the fundamental domain of F is finite, we can assume that |o−1(x)|is bounded for every x ∈ A. Let P1 = P1

∣∣∣G

(F ′1

∣∣∣σ1(V(F ))

) be the restriction map and we define

Z :=

e ∈ o−1(A) such that minp∈P−1

1 (e)`(p) > 1

,(we use the notation of Definition 2.4.11).

52

Let K be the set of all reducible couples in F ′1 , see Definition 2.4.15. By a standardargument we can find a countable subset K c

⊂ K such that every couple in K is a unionof intersections of couples inK c. For each couple C := (αε1

1 , αε22 ) ∈ K c we define

Er(C) :={e ∈ Z

∣∣∣∣ ∃p ∈ P−11 (e), `(p) minimal ,

∃i ∈ N such that Pi(p) ∈ αε j

j , Pi+1(p) ∈ αε j′

j′ , { j, j′} = {1, 2}},

where Pi projects a path to the i-th component. SinceF is a field of trees `(P1(p)) = `(e) = 1,so each path contains a couple of reducible edges. Hence⋃

C∈K c

Er(C) = Z.

We consider a finite subsetK f⊂ K

c such that

µ

Z \⋃

C∈K f

Er(C)

≤ 14,

and we number the elements ofK f . Let C1 the first couple, define the equivalence relationRC1 and the quotient deployment (F ′1 )RC1

as in the Definitions 2.4.16 and 2.4.18. Then weconsider the second couple C2 and we take the maximal reducible sub-couple C′2 of C2inside the quotient deployment (F ′1 )RC1

. We take the quotient relative this couple and wekeep doing this process until we have used all the couple ofK f . The obtained deployment(F ′2 ,P2, σ2) satisfies the required conditions. �

�

2.4.5 Cost of free groupoids

We can prove Theorem 2.4.1 under the assumption µ(Ψ) < ∞: gcost(G(Ψ)) = µ(Ψ).

Proof. Let G be a free groupoid over Ψ and let Φ be a generating set. If Φ has not finitemeasure there is nothing to prove. Otherwise we consider Γ(Φ,Ψ) as in Proposition2.4.12. We apply the Theorem 2.4.21 to Γ(Φ,Ψ) as a deployment of Γ(G,Ψ). We obtainMs(Γ(G,Φ)) ≥Ms(Γ(G,Ψ)) and so µ(Φ) ≥ µ(Ψ). �

If the measure of Ψ is infinite we can easily conclude that the measure of Φ is infinite,taking an increasing union of free sub-groupoids whose cost tends to infinity insideG(Ψ),as done in [19].

2.5 Groupoid Cost of a group

Each action of a group gives rise to a groupoid, as we defined in the Example 2.2.15.So we can associate to every group “many” groupoids. These groupoids may have finitecost, for example the groupoid action of a finitely generated group over a probability

53

space has cost bounded by the rank of the group. So we can associate to each group asubset of the real numbers, the set of all possible costs of its actions.

In general the structure of this set is not clear. The set is bounded if and only if thegroup is finitely generated. However the set can be arbitrary big, see Corollary 2.5.21, orit can be reduced to a single point, as in the case of free groups. Using free products, ilwill be easy to to construct a uncountable family of groups with the same groupoid cost,see Corollary 2.5.22.

Notation 2.5.1. Let G be a countable group and let a be an action of G on a standardprobability space (X, µ). We denote with G n X the groupoid action, defined in theExample 2.2.15. We define the cost of the action as gcost(a) := gcost (G n X).

We will use p.m.p. for probability measure preserving.

Definition 2.5.2. Let G be a countable group.

1. The cost of G is

cost(G) := inf{gcost(a)

∣∣∣ a free p.m.p. action of G}∈ R ∪ {∞}.

2. We denote the set of possible costs of the p.m.p. ergodic actions of G (mercuriale ofG) with

M(G) :={gcost(a)

∣∣∣ a p.m.p. ergodic action of G}⊂ R ∪ {∞}.

3. The finite and diffuse part are respectively

Mf (G) :=

{gcost(a)

∣∣∣ a p.m.p. ergodic action of G on a finite space},

Md(G) :=

{gcost(a)

∣∣∣ a p.m.p. ergodic action of G on a diffuse space}.

ClearlyM(G) =M f (G)qMd(G).

Proposition 2.5.3 (Gaboriau). For every countable group G,

M(G) ⊂ [cost(G), r(G)] and cost(G) ∈ M(G).

Proof. The Proposition VI.21 of [19] tells us that cost(G) ∈ Md(G). Let a be an ergodicp.m.p. action of G on (X, µ) and let b be an ergodic free p.m.p. action of G on (Y, ν).Consider the diagonal action a × b on (X ×Y, µ × ν). This action is free, since b is free. LetΦ be a generating set of G n X, we define {D1}1∈G such that

Φ =∐1∈G

D1 × {1}.

We define

Φ =∐1∈G

D1 ×Y × {1},

and we observe that Φ is a generating set for G n (X ×Y) and (µ × ν)(Φ) = µ(Φ). So weobtain gcost(a) ≥ gcost(a × b) ≥ cost(G) for every ergodic measure preserving action a. �

54

Combining this proposition with the result of Gaboriau cost(Fn) = n, see [18], we getthe following corollary.

Corollary 2.5.4. For the free group Fn, we haveM(Fn) = {n}.

An ergodic action on a finite set has to be transitive (on the support of the measure).Hence finite ergodic actions are in correspondence with finite index subgroups.

Definition 2.5.5. Let G be a countable group and H < G a finite index subgroup. Theaction of G on the quotient G/

H is transitive, hence ergodic with respect to the normalizedcounting measure. We denote this action by qH. By Proposition 2.3.13 we obtain

gcost(qH

)=r(H) + [G : H] − 1

[G : H]=r(H) − 1[G : H]

+ 1,

where [G : H] is the index of H in G.

Since any smooth and ergodic action is obtained in this way, we have

Mf (G) =

⋃H<G [G:H]<∞

{gcost

(qH

)}.

Theorem 2.5.6 (Abèrt, Nikolov; [3]). Let Hn < G be a decreasing sequence of finite indexsubgroups and let a be the associate profinite action of G. Then gcost(a) = limn gcost

(qHn

).

We do not know whether for a residually finite group we can obtain each possiblecost value in this way. Surely it is not always the case, for example simple groups do notadmit profinite actions.

2.5.1 Cost for direct products

Proposition 2.5.7. Let G be a countable Abelian and infinite group. ThenMd(G) = {1}.

Proof. It is easy to show that cost(G) = 1, see for example I-D of [19]. Let a be an ergodicp.m.p. action on a diffuse space and let H < G be a stabilizer of a point. Since G is Abelian,H < G is normal and the equivalence relation induced by a is the equivalence relationinduced by the quotient group G/

H. Let {hi}i∈N be a generating set for H and let Bi ⊂ X

be a sequence of subset of positive measure such that∑

i µ(Bi) ≤ ε. Let Ψ be a generatingset of (G n X)P of cost 1, then

Ψ ∪⋃i∈N

1i∣∣∣Bi

is a generating set for G n X, hence

gcost(G n X) = 1.

�

55

Example 2.5.8. For the free abelian group G = Zd, we have

M(Zd) = {1}⋃n∈N

{1 +

d − 1n

}.

It is enough to observe that a finite index subgroup of Zd has rank d and an arbitraryindex n. So the cost of the quotient action with respect to such a subgroup is

1 +rank − 1

index= 1 +

d − 1n

.

Similarly we can get the cost for all Abelian groups.

Notation 2.5.9. Let G be a group and let H < G be a subgroup. We write H < f .i. G when Hhas finite index in G.

Proposition 2.5.10. Let G := G1 × G2 be a direct product of groups.

1. We have

Md(G1 × G2) ⊃

⋃H1< f .i.G1

{1

[G1 : H1]· M

d(G2) + 1 −1

[G1 : H1]

}⋃

H2< f .i.G2

{1

[G2 : H2]· M

d(G1) + 1 −1

[G2 : H2]

}.

2. If a is a p.m.p. ergodic action of G1 ×G2 on a probability space (X, µ) such that either G1 orG2 is not aperiodic, then gcost(a) is in the set defined in (1).

Proof. 1. Let H < f .i. G2 and let a be a p.m.p. ergodic action of G1 on a diffuse space

(X, µ). We consider the product action of G = G1 × G2 on the space Y := X × G2/H

with respect to the product measure. This action is ergodic and we claim that

gcost(a × qH) := gcost (G nY) =1

[G2 : H]gcost(a) + 1 −

1[G2 : H]

.

Let Φ ⊂ G1 nX× {id} be a generating set, let {1i}i∈N be generators for H and let {Bi}i∈Nbe a sequence of subsets Bi ⊂ X such that∑

i∈N

µ(Bi) < ε and µ(Bi) > 0, ∀i ∈ N.

Then Φ ∪i

{1i∣∣∣Bi

}is a generating set for G nY

∣∣∣X×{id}

so

gcost(G nY

∣∣∣X×{id}

)= gcost (G1 n X × {id}) .

By Proposition 2.3.14, we have

gcost (a) = gcost(G nY

∣∣∣X×{id}

)+ 1 −

1[G2 : H]

=1

[G2 : H]gcost(a) + 1 −

1[G2 : H]

.

56

2. Suppose that the action of G2 is not aperiodic. For each x ∈ X we denote withStabGi(x) < Gi the Gi-stabilizer of x. By ergodicity the map

x 7→([G1 : StabG1(x)], [G2 : StabG2(x)]

),

is constant, so the action of G2 is smooth with orbit of the same cardinality [G2 :StabG2(x)] and the action of G1 is aperiodic. If G2 is finitely generated, by Lemma2.5.29,

1cost(a) ∈1

[G2 : StabG2(x)]M

d(G1) + 1 −1

[G2 : StabG2(x)].

In the general case, we can follow step by step the proof of Lemma 2.5.29. We usedthat the normal subgroup N is finitely generated only to get that the stabilizer of theaction of N do not increase the cost. This can be proved in this case since G1 andG2 commute, as we did in the first part. Morally the cost does not care about theisotropic part that commutes with the ergodic one.

�

We observe that none of these constructed actions is faithfull. We recall a simple fact.

Proposition 2.5.11 (Gaboriau). For every G1 and G2, we have cost(G1 × G2) = 1. Moreover ifG1 has an infinite-order element and G2 is infinite, then each free ergodic action has cost 1.

Proof. See Proposition VI.23 of [19]. �

With the same proof we obtain the following.

Proposition 2.5.12. Let G = G1×G2 be a direct product of infinite groups and let a be an ergodicaction of G on a probability space (X, µ). Suppose that the restricted action a

∣∣∣Gi

is aperiodic. Then

gcost(a) ≤ gcost(a∣∣∣Gi

).

Proof. Suppose that a∣∣∣G1

is aperiodic. Let Aε ⊂ X be a sequence of measurable subsetssuch that Aε meets every G1-orbit and µ(Aε) ≤ ε. Let {1i}i∈N be a generating set for G2 andlet Φ be a generating set for G1 n X. Then

Φ ∪⋃i∈N

1i∣∣∣A ε

2i

is a generating set for G n X, of cost less than or equal to µ(Φ) + 2ε. �

Corollary 2.5.13. Let G be any group, then

Md(Zk× G) = {1} ∪

⋃n∈N

{1nM

d(G) +(1 −

1n

)}.

If every free action of a direct products of groups has cost 1, then the Proposition2.5.10 is an equality.

57

Example 2.5.14. Let G = Fp × Fq be a direct product of free groups. Then the Propositions2.5.10 and 2.5.11 say

Md(Fp × Fq) ⊃ {1} ∪

⋃n∈N

{1 +

p − 1n

}∪

{1 +

q − 1n

}.

For p = 1 the previous corollary gives us the equality,

Md(Z × Fq) = {1} ∪

⋃n∈N

{1 +

q − 1n

}.

Remark 2.5.15. Among the finite index subgroups of a direct product, we have the directproduct of finite index subgroups. For G = Fp × Fq we obtain

Mf (Fp × Fq) ⊃

{p − 1

m+

q − 1n

+1

nm+ 1, n,m ∈ N

}.

We observe that Theorem 2.5.6 does not give new costs for ergodic actions for thedirect product of free groups.

2.5.2 Free products

Let G = G1 ∗ G2 be a free product of countable groups. We observe that for everyp.m.p. ergodic action a = a1 ∗ a2 of G on (X, µ), we have

G n X = (G1 n X) ∗ (G2 n X) .

Moreover Corollary 2.3.18 says us

gcost(a) = gcost(a1) + gcost(a2).

Smooth Case

We want to study the cost for free products of groups. We start with the analysis ofsmooth actions.

Proposition 2.5.16. Let a1 and a2 be p.m.p. smooth actions of G1 and G2 respectively, on thediffuse space (X, µ). We denote with Di a fundamental domain for ai. There exists a measurepreserving automorphism ϕ : X→ X such that the action of G1 ∗ G2 defined by a1 ∗ ϕ−1

◦ a2 ◦ ϕis ergodic if and only if µ(D1) + µ(D2) ≤ 1.

Proof. Suppose that a1 and a2 have orbits of cardinality 2. We consider the group

G′ = Z/2Z ∗

Z/2Z,

and let b be an ergodic action of G′ on (X, µ). We can find two automorphisms ϕ1 andϕ2 of X such that the actions of the two factors are orbit equivalent to ϕ1 ◦ a1 ◦ ϕ−1

1 andϕ2 ◦ a2 ◦ ϕ−1

2 , respectively. So ϕ1 ◦ a1 ◦ ϕ−11 ∗ ϕ2 ◦ a2 ◦ ϕ−1

2 is an ergodic action, since theorbits of the actions are the same of the orbits of b.

Let’s suppose now that a1 and a2 are arbitrary actions. We fix a little bit of notation.

58

a) Let Bi ⊂ X be the measurable subset where the action of ai is trivial.

b) Let D′i ⊂ X be a fundamental domain of ai on X \ Bi. Clearly D′i = Di \ Bi.

c) Let Ai ⊃ D′i be a measurable subset such that Gi n X∣∣∣Ai

has orbits of cardinality 2.

We can suppose that µ(D′2) ≤ µ(D′1) and up to an automorphism we can suppose that

1. A1 ⊃ A2 and D′1 ∩D′2 = ∅,

2. G2D′2 \D′2 ⊃ D1.

This is always possible, since

µ(D1) + µ(D2) ≤ 1⇒ µ(D1) + µ(D′2) + µ(B2) ≤ µ(G2D′2) + µ(B2)⇒ µ(D1) ≤ µ(G2D′2) − µ(D′2).

We claim that A2 meets every G-orbit. Let x ∈ X, we want to show that Gx ∩ A2 , ∅.

1. If x ∈ G2D′2 there is nothing to prove.

2. If x ∈ B2, then x ∈ G1D′1, so

G1x ∩D′1 , ∅ ⇒ G2G1x ∩D′2 , ∅.

We denote with Ri the equivalence relation induced by Gi on A2. By the first part ofthe proof, there exists an automorphism ϕ : A2 → A2 such that the equivalence relationR1 ∗ ϕ−1

R2ϕ is ergodic. We can extend ϕ to an automorphism of ϕ : X → X such thatϕ∣∣∣A2

= ϕ and the identity map on X\A2. Since A2 meets every orbit, a1 ∗ ϕa2ϕ−1 is a p.m.p.ergodic action. �

Now we want to study the smooth actions of a free product. Before stating the nextproposition we need some notation. Let a1 and a2 be actions of G1 and G2 respectively, ona finite space X equipped with the normalized counting measure. Let

X = X1i q . . .q X

kii ,

be the orbit decomposition with respect to the action ai, so that

ai = ⊕k j

j=1a ji ,

where a ji is the transitive action of Gi on X j

i induced by the restriction of ai. We denote

with |X ji | the cardinality of X j

i .

Proposition 2.5.17. Let a1 and a2 be actions of G1 and G2 respectively, on the atomic space (X, µ).There exists a bijection ϕ of X such that the free product a1 ∗ ϕa2ϕ−1 is transitive if and only if

C :=2∑

i=1

ki∑j=1

|Xji | − 1 ≥ |X| − 1.

59

Proof. Let Φi be a minimal generating set for the equivalence relation of ai on X. Weconsider Φi as a graph (without double edges, by minimality), with space of verticesX and edges Φi. The action a = a1 ∗ a2 is transitive if and only if the graph Φ1 ∪ Φ2 isconnected. Now we have only to observe that C = |E(Φ1)| + |E(Φ2)|. �

We remark that the cost of such an action is

gcost(a) = gcost(a1) + gcost(a2) =

2∑i=1

ki∑j=1

gcost(a ji )

|Xji |

.

Corollary 2.5.18. Knowing the cost and the orbit space of every finite action of G1 and G2, wecan determinateM f (G1 ∗ G2).

We could write an algorithm that can compute the cost of all actions on a set of fixedcardinality.

Diffuse case

We can state a stronger version of Proposition 2.5.16. We recall that a fundamentalset for an action of a group H on a space X is a subset D ⊂ Xwhere the restricted inducedequivalence relation (H n X)P

∣∣∣D is trivial, see Definition 2.2.49.

Proposition 2.5.19. Let a1 and a2 be p.m.p. actions of G1 and G2 respectively on the diffuse space(X, µ). We denote with Di a maximal fundamental set for ai.

1. If µ(D1) +µ(D2) < 1 then there exists a measure preserving automorphism ϕ : X→ X suchthat the action of G1 ∗ G2 defined by a1 ∗ ϕ ◦ a2 ◦ ϕ−1 is ergodic.

2. If a1 ∗ a2 is ergodic then µ(D1) + µ(D2) ≤ 1.

Proof. The second statement is clear, we have to prove the first one. Given ε > 0, it iseasy to construct smooth equivalence relations Rεi ⊂ Gi nXwith fundamental domain Dε

isuch that µ(Dε

1) + µ(Dε2) ≤ µ(D1) + µ(D2) + ε. By assumption, we can take ε > 0 such that

µ(Dε1) + µ(Dε

2) < 1. By Proposition 2.5.16, there exists an automorphism ϕ : X → X suchthat Rε1 ∗ ϕ∗R

ε2 is ergodic. So a1 ∗ ϕ ◦ a2 ◦ ϕ−1 is ergodic. �

We remark that there is no way to avoid the asymmetry. We can give now the firstproperty ofMd(G1 ∗ G2).

Theorem 2.5.20. Let G1 and G2 be countable groups. Then

Md(G1 ∗ G2) ⊂ [cost(G1) + cost(G2), r(G1) + r(G2)]

is an interval and {cost(G1) + cost(G2)} ∈ Md(G1 ∗ G2).

Proof. Let a be an ergodic action of minimal cost of G1 ∗ G2. Then a = a1 ∗ a2 and

gcost(a) = gcost(a1) + gcost(a2)⇒ cost(G1 ∗ G2) ≥ cost(G1) + cost(G2).

60

Let ai be a free ergodic action of minimal cost of Gi. Then

gcost(a1 ∗ a2) = cost(a1) + cost(a2)⇒ cost(G1 ∗ G2) ≤ cost(G1) + cost(G2)⇒

{cost(G1) + cost(G2)} = {cost(G1 ∗ G2)} ∈ Md(G1 ∗ G2).

We remark that action a1 ∗ a2 in general is not free, but there always exists a free actionwith the same cost.

Let a = a1 ∗ a2 be an ergodic action of G1 ∗G2. We want to construct a family {at}t∈R+ of

actions of G1 ∗ G2 such that

gcost(at) =

{gcost(a) − t if gcost(a) − t ≥ cost(G1 ∗ G2),cost(G1 ∗ G2) if gcost(a) − t ≤ cost(G1 ∗ G2).

Let t ∈ R+. If gcost(a) − t ≤ cost(G1 ∗ G2) then set λt = 1, otherwise consider λt ∈ [0, 1]such that

λt(cost(G1) + cost(G2)) + (1 − λt)gcost(a) = gcost(a) − t.

We consider the standard Borel space Xt = Xq [0, λt] with the measure

µt(A) =

{(1 − λt)µ(A) if A ⊂ X,

Leb(A) if A ⊂ [0, λt] where Leb is the Lebesgue measure.

We fix bi an action of Gi on [0, λt] with minimal cost. We define an action ati on Xt as

ati(1)(x) =

{ai(1)(x) if x ∈ X,bi(1)(x) if x ∈ [0, λt].

Then

gcost(at1) + gcost(at

2) =cost(G1)λt + (1 − λt)gcost(a1) + cost(G2)λt + (1 − λt)gcost(a2) =

=gcost(a) − t,

and we define at = a1 ∗ ϕ ◦ a2 ◦ ϕ−1 with ϕ as in Proposition 2.5.19. �

Examples

In order to determinate Md(G1 ∗ G2), we have to find an ergodic action of maximalcost (if it does exist). We want to study some examples. Let di be an ergodic action of Giand denote with ti the trivial action of Gi. Then d1 ∗ t2 and t1 ∗ d2 are ergodic actions, so

Md(G1 ∗ G2) ⊃ {Md(G1) + r(G2)} ∪ {Md(G2) + r(G1)}.

This formula allows to find a big family of examples.

Corollary 2.5.21. Let G be any countable group, then

Md(G ∗ Fn) = [cost(G) + n, r(G) + n].

Corollary 2.5.22. There exists an uncountable family of groups with the same cost-values.

61

Proof. There exist uncountably many groups {Gi}i∈I with 2 generators,

Md((Gi × Z) ∗ Z) = [2, 4], ∀i ∈ I.

�

Corollary 2.5.23. Let G1 be a group and let G2 be a non-finitely generated group. Then

Md(G1 ∗ G2) = [cost(G1) + cost(G2),∞].

More generally, we have the following.

Proposition 2.5.24. Let G1 and G2 be countable groups. We set

Mi := supx∈Md(Gi)

{x − r(Gi)} , κi := max

Mi, supH< f .i.Gi\{Gi}

[Gi : H][Gi : H] − 1

(gcost(qH) − r(Gi)

) .1. If M1 − r(G1) = κ1 ≥ κ2, then

Md(G1 ∗ G2) = [cost(G1) + cost(G2),M1 + r(G2)] .

2. If G := G1 = G2, then κ := κ1 = κ2 and we have

Md(G ∗ G) = [2cost(G), 2r(G) + κ] .

3. Suppose κ1 > κ2. Then

Md(G1 ∗ G2) = [cost(G1) + cost(G2),

max

M1 , supH< f .i.G1\{G1}

(gcost(qH) − r(G1)

)+

1[G1 : H]

κ2

.

Proof. Let a1 and a2 be actions of G1 and G2 respectively. We set

• Ei ⊂ X the measurable subset where the action ai has infinite orbits.

• S ji ⊂ X the measurable subset where the action ai has orbits of cardinality j.

• Set q j := j−1j .

• N ji := sup

{gcost( f ); f transitive action of Gi on a set with j points

}.

So we have

gcost(a1 ∗ a2) ≤∑i=1,2

Miµ(Ei) +∑

i=1,2, j≥2

N jiµ

(S j

i

)+

∑i=1,2

r(Gi)

1 − µ(Ei) −∑j≥2

µ(S j

i

) .62

By Proposition 2.5.16, the supremum ofMd(G1 ∗ G2) is

sup{Ei}, {S

ji }

r(G1) + r(G2) +∑i=1,2

µ(Ei) (Mi − r(Gi)) +∑

i=1,2, j≥2

q jµ(S j

i

) 1q j

(N j

i − r(Gi)) ,

where Ei and S ji have to satisfy∑

i=1,2

µ(Ei) +∑

i=1,2, j≥2

q jµ(S j

i

)≥ 1,∑

j≥2

µ(S j

i

)≤ 1.

This is a convex problem that gives easily the claimed solution. �

Corollary 2.5.25. 1. Let n > m ∈ N,Md(Zn∗ Zm) = [2,n + 1].

2. Let n,m ∈ N and let k the biggest divisor of n that is not n,

Md( Z/

nZ ∗Z/

mZ)

=

[2 − 1

n −1m , 2 −

mn(m−1)

]if n > m are primes,[

2 − 1n −

1m , 2

]if n and m are not primes,[

2 − 1n −

1m , 2 −min

{1

(n−1)k ,n

m(n−1)

}]if n is prime and m is not.

2.5.3 Normal Subgroups

Proposition 2.5.26. Let G be a countable group and let N < G be a normal finitely generatedsubgroup. ThenMd(G) ⊃ Md

( G/N

).

Proof. Let a be an action of G/N. We can think a as an action of G and by Corollary 2.3.11

the cost of these two actions is equal. �

Theorem 2.5.27. Let G be a countable group and let N < G be either a normal finite subgroup ora normal Abelian and finitely generated subgroup.

1. If N is finite, then

Md(G) ⊂

⋃N′<N

{|N′||N|M

d( G/

N)

+ 1 −|N′||N|

}.

2. If N is infinte, then

Md(G) ⊂

⋃N′< f .i.N

{|N′||N|M

d( G/

N)

+ 1 −|N′||N|

}∪ {1}.

Proof. The proof is a corollary of these three lemmas.

Lemma 2.5.28. Let a be a p.m.p. ergodic action of G on a diffuse space (X, µ). Let N < G be anormal subgroup. The orbits of the restricted action a

∣∣∣N have all the same cardinality.

63

Proof. Let x, y ∈ X and 1 ∈ G such that 1x = y. By normality, StabN(x) = {n ∈ N; nx = x}and StabN(y) are conjugate via 1. By ergodicity the function

x 7→ [N : StabN(x)] ∈ N ∪ {∞},

is constant. �

Lemma 2.5.29. Let G be a group and N < G be a normal finitely generated subgroup. Leta be an action of G and suppose that the orbit of the action of N have cardinality m. Thengcost(a) ∈ 1

mMd( G/

N)

+ 1 − 1m .

Proof. Let D ⊂ X be a fundamental domain of N. By the Proposition 2.3.14,

gcost(G n X) = gcost(G n X

∣∣∣D

)+ 1 −

1m.

We define the following action of G/N on D,

N1 ·Nx = N1x, ∀1 ∈ G, x ∈ X.

The action is well-defined since N is normal in G. The quotient map G → G/N extends

to a map of groupoids

π∗ : G n X→ G/N nD, (1, x) 7→ (N1,Nx),

(1, x)(h, y) = (1h, y), x = hy ∈ X⇒(N1,Nx)(Nh,Ny) = (N1Nh,Ny) = (N1h,Ny), Nx = NhNy = Nhy ∈ D.

Let Φ be a generating set for G/NnD. Let Φ ⊂ GnX be any subset such thatπ∗ : Φ→ Φ

is an isomorphism. Let Ψ be a generating set for (N n X)P⊂ G n X. Finally let S be a

generating set of finite measure for N n X∣∣∣D (that exists since N is finitely generated) and

let A ⊂ D be a set of measure less than ε. Then

Θ := Φ ∪Ψ ∪ S∣∣∣A ⊂ G n X,

is a generating set, since using the action of Φ on S∣∣∣A we get that S ⊂ 〈Θ〉 and so NnX ⊂ 〈Θ〉.

So we have

gcost( G/

N nD)

+ 1 − µ(D) ≥ gcost(G n X).

Conversely let Φ be a generating set for G n X, then π∗(Φ) ⊂ G/N nD is a generating

set and µ(Φ) ≥ µ(π∗(Φ)). We conclude using Proposition 2.3.14. �

Lemma 2.5.30. Let G be a group and let N < G be a normal subgroup. Let a be a p.m.p. ergodicaction of G. If the orbit of a

∣∣∣N are infinite, then gcost(a) ≤ gcost (N n X).

64

Proof. The proof is the same of Proposition 2.5.12. Let Ψ be a generating set for N n X.Let Bi ⊂ X be measurable subset of positive measure such that

∑i µ(Bi) < ε and such that

Bi meets every N-orbit. Let {1i}i∈N be a generating set for the group G. Then

Φ := Ψ ∪⋃

i

{1i∣∣∣Bi

},

is a generating set for G n X. Let x ∈ X and let n ∈ N such that n−1x ∈ Bi. By normality

1in1−1i = n′ ∈ N ⇒ 1i = n′1in−1

⇒

(1i, x) = (n′, 1in−1x)(1i,n−1x) ∈ 〈Φ〉 .

�

�

Remark 2.5.31. In Lemma 2.5.28 and 2.5.29 we did not use the assumption on the group.But the assumption is crucial in Lemma 2.5.30, since we use that the cost of all actionof an Abelian group is 1, see 2.5.7. We do not know if there exists other groups withthis property. A possible example could be finitely generated and presented amenablegroups, since the cost of all their profinite actions is 1, see [3]. Anyway this assumptionis crucial, as shown by the Proposition 2.5.10.

The inclusion is an equality if for every ergodic action of G/N on a diffuse space X

and for every N′ < N, there exists an ergodic action of G on Y, such that N < G acts withorbit of cardinality N/

N′ and fundamental domain D such that

gcost( G/

N nD)

= gcost(G n X

∣∣∣D

).

Now we show that it is not always an equality. We denote the cyclic group with

Cn := Z/nZ.

Proposition 2.5.32. For the group SL2(Z) = C4 ∗C2 C6, we have

Md(SL2(Z)) =

[1 +

112, 1 +

18

]q

[1 +

16, 1 +

13

].

Proof. Let a be a p.m.p. ergodic action of SL2(Z) on a diffuse space (X, µ). Consider thenormal subgroup C2 < SL2(Z). If the action of C2 is trivial, then the cost of the actionis the same of the cost of an action of PSL2(Z), 2.5.26. If it is free then also the action ofC4 =

⟨1⟩

is free, since C2 = {id, 12}. Let D be a fundamental domain of the action of C2 and

consider the associate action of PSL2(Z) = C2 ∗ C3 = SL2(Z)/C2

on D, as in the proof ofLemma 2.5.29. The subgroup C2 < PSL2(Z) acts freely and by Proposition 2.5.24, the costof this action is in the interval

12

[1 +

16, 1 +

14

],

65

since if the action of C2 is free, the fundamental domain of the action of C3 < PSL2(Z) hasmeasure at least 3

4 and

12

+34

(1 −

13

)+

14

= 1 +14.

By Lemma 2.5.30, we have that

Md(SL2(Z)) ⊂

{12

[1 +

16, 1 +

14

]+

12

}∪M

d(PSL2(Z)) =[1 +

112, 1 +

18

]q

[1 +

16, 1 +

13

].

In order to show the equality, we have only to show that each action of PSL2(Z), suchthat C2 < PSL2(Z) acts freely, extend to an action of SL2(Z) with the properties remarkedbefore. This can be done factor-wise. Consider an action a of PSL2(Z) on a diffuse space X,defineY := X×C2. Since C6 = C2×C3, we can define an action of C6 onY in the followingway:

1(x, z) = (π3(1)x, π2(1)z),

where π3 : C6 → C3 and π2 : C6 → C2 are the projections.For C4 we can not do the same, since it is not a direct product. Let D ⊂ X be a

fundamental domain for C2 < PSL2(Z). Fix two generators C4 =⟨1⟩

and C2 = 〈h〉, thenwe define

1(x, z) =

{(hx, z) if x ∈ D × C2,

(hx, z + 1) if x < D × C2.

We observe that C2 < C4 acts as C2 < C6 on Y, so we can define an action of SL2(Z)that has the required properties. �

The Theorem 2.5.27 predicted

Md(SL2(Z)) ⊂

[1 +

112, 1 +

13

].

66

Bibliography

[1] M. Abért, A. Jaikin-Zapirain, and N. Nikolov. The rank gradient from a combinatorialviewpoint. preprint, 2010.

[2] Miklós Abért and Weiss Benjamin. Bernoulli actions are weakly contained in anyfree action. preprint, 2011.

[3] Miklós Abért and Nikolay Nikolov. Rank gradient, cost of groups and the rankversus Heegaard genus problem. preprint, 2008.

[4] S. R. Adams and R. J. Spatzier. Kazhdan groups, cocycles and trees. Amer. J. Math.,112(2):271–287, 1990.

[5] Scott Adams. Trees and amenable equivalence relations. Ergodic Theory Dynam.Systems, 10(1):1–14, 1990.

[6] Aurélien Alvarez. Une théorie de Bass-Serre pour les relations d’équivalence et lesgroupoïdes boréliens. PhD thesis, 2008.

[7] C. Anantharaman-Delaroche and J. Renault. Amenable groupoids, volume 36 ofMonographies de L’Enseignement Mathématique [Monographs of L’Enseignement Math-ématique]. L’Enseignement Mathématique, Geneva, 2000.

[8] Nicolas Bergeron and Damien Gaboriau. Asymptotique des nombres de Betti, in-variants l2 et laminations. Comment. Math. Helv., 79(2):362–395, 2004.

[9] Martin R. Bridson and Charles F. Miller, III. Structure and finiteness properties ofsubdirect products of groups. Proc. Lond. Math. Soc. (3), 98(3):631–651, 2009.

[10] A. Connes and B. Weiss. Property T and asymptotically invariant sequences. IsraelJ. Math., 37(3):209–210, 1980.

[11] A. Connes, J. Feldman, and B. Weiss. An amenable equivalence relation is generatedby a single transformation. Ergodic Theory Dynamical Systems, 1(4):431–450 (1982),1981. ISSN 0143-3857.

[12] H. A. Dye. On groups of measure preserving transformation. I. Amer. J. Math., 81:119–159, 1959. ISSN 0002-9327.

[13] H. A. Dye. On groups of measure preserving transformations. II. Amer. J. Math., 85:551–576, 1963. ISSN 0002-9327.

67

[14] Inessa Epstein. Orbit inequivalent actions of non-amenable groups. preprint, 2008.

[15] J. Feldman, C. E. Sutherland, and R. J. Zimmer. Subrelations of ergodic equivalencerelations. Ergodic Theory Dynam. Systems, 9(2):239–269, 1989.

[16] Jacob Feldman and Calvin C. Moore. Ergodic equivalence relations, cohomology,and von Neumann algebras. I. Trans. Amer. Math. Soc., 234(2):289–324, 1977. ISSN0002-9947.

[17] Alex Furman. A survey of measured group theory. Proceedings of a Conference honoringRobert Zimmer’s 60th birthday, 2009.

[18] Damien Gaboriau. Mercuriale de groupes et de relations. C. R. Acad. Sci. Paris Sér. IMath., 326(2):219–222, 1998.

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

[20] Damien Gaboriau. Orbit equivalence and measured group theory. In Proceedingsof the ICM (Hyderabad, India, 2010), volume III, pages 1501–1527. Hindustan BookAgency, 2010.

[21] Damien Gaboriau and Russell Lyons. A measurable-group-theoretic solution to vonNeumann’s problem. Invent. Math., 177(3):533–540, 2009.

[22] Damien Gaboriau and Sorin Popa. An uncountable family of nonorbit equivalentactions of Fn. J. Amer. Math. Soc., 18(3):547–559 (electronic), 2005.

[23] Greg Hjorth. A converse to Dye’s theorem. Trans. Amer. Math. Soc., 357(8):3083–3103(electronic), 2005.

[24] Cyril Houdayer. Invariant percolation and measured theory of non-amenable groups[after gaboriau-lyons, ioana, epstein]. In Séminaire Bourbaki, pages Exp. No. 1039,01–33. Paris, 2011.

[25] Adrian Ioana. Orbit inequivalent actions for groups containing a copy of F2. Invent.Math., to appear.

[26] Alexander S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts inMathematics. Springer-Verlag, New York, 1995.

[27] Alexander S. Kechris and Benjamin D. Miller. Topics in orbit equivalence, volume 1852of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2004.

[28] Gilbert Levitt. On the cost of generating an equivalence relation. Ergodic TheoryDynam. Systems, 15(6):1173–1181, 1995.

[29] Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Classics in Mathe-matics. Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition.

[30] George W. Mackey. Ergodic theory, group theory, and differential geometry. Proc.Nat. Acad. Sci. U.S.A., 50:1184–1191, 1963.

68

[31] A. Ju. Ol′šanskiı. On the question of the existence of an invariant mean on a group.Uspekhi Mat. Nauk, 35(4(214)):199–200, 1980. ISSN 0042-1316.

[32] Donald Ornstein. Bernoulli shifts with the same entropy are isomorphic. Advancesin Math., 4:337–352 (1970), 1970. ISSN 0001-8708.

[33] Donald S. Ornstein and Benjamin Weiss. Ergodic theory of amenable group actions.I. The Rohlin lemma. Bull. Amer. Math. Soc. (N.S.), 2(1):161–164, 1980. ISSN 0273-0979.

[34] Jean Renault. A groupoid approach to C∗-algebras, volume 793 of Lecture Notes inMathematics. Springer, Berlin, 1980.

[35] Roman Sauer. L2-Invariants of Groups and Discrete Measured Groupoids. PhD thesis,2002.

[36] Yoshimichi Ueda. Notes on treeability and costs for discrete groupoids in operatoralgebra framework. In Operator Algebras: The Abel Symposium 2004, volume 1 of AbelSymp., pages 259–279. Springer, Berlin, 2006.

[37] Peter Walters. An introduction to ergodic theory, volume 79 of Graduate Texts in Mathe-matics. Springer-Verlag, New York, 1982. ISBN 0-387-90599-5.

[38] Richard Weidmann. The Nielsen method for groups acting on trees. Proc. LondonMath. Soc. (3), 85(1):93–118, 2002.

[39] Richard Weidmann. A rank formula for amalgamated products with finite amalgam.In Geometric methods in group theory, volume 372 of Contemp. Math., pages 99–106.Amer. Math. Soc., Providence, RI, 2005.

69