# Non-standard limits of graphs and some orbit equivalence invariants

Alessandro Carderi, Damien Gaboriau, Mikael de la Salle C.N.R.S.C.N.R.S.

###### Abstract

We consider probability measure preserving discrete groupoids, group actions
and equivalence relations in the context of general probability spaces. We
study for these objects the notions of cost, $\beta$-invariant and some
higher-dimensional variants. We also propose various convergence results about
$\ell^{2}$-Betti numbers and rank gradient for sequences of actions, groupoids
or equivalence relations under weak finiteness assumptions. In particular we
connect the combinatorial cost with the cost of the ultralimit equivalence
relations. Finally a relative version of Stuck-Zimmer property is also
considered.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Measured groupoids
    2. 2.2 Full pseudogroup
    3. 2.3 Regular representations and von Neumann algebras of a groupoid
    4. 2.4 Coarse structures and graphings
    5. 2.5 Actions
    6. 2.6 Presentation of p.m.p. groupoids
    7. 2.7 Ultraproducts
    8. 2.8 Realizability and ultraproducts
  3. 3 Graphings, cost and combinatorial cost
    1. 3.1 Graphings with finite size
    2. 3.2 Graphings with infinite size
    3. 3.3 Limit of graphed groupoids
    4. 3.4 Weak containment
    5. 3.5 Factors
    6. 3.6 Sofic groupoids
  4. 4 Group actions and cost
    1. 4.1 Farber sequences
    2. 4.2 Sequences of actions and non nested Farber sequences
    3. 4.3 Stuck-Zimmer property
    4. 4.4 “Relative” Stuck-Zimmer
  5. 5 $\ell^{2}$-Betti numbers
    1. 5.1 Ultraproducts of $\mathcal{G}$-simplicial complexes
    2. 5.2 Limits of $\ell^{2}$ Betti numbers: uniformly bounded case
    3. 5.3 Limits of $\ell^{2}$ Betti numbers: the general case

##  1 Introduction

Limits of discrete structures have attracted a lot of interest in the last
decade. We are interested in sequences of probability measure preserving
(p.m.p.) group actions, of graphs or of graphings and in the asymptotic
behavior of such invariants as the cost or the $\ell^{2}$-Betti numbers. In
the course of our investigations we were led to consider graphed p.m.p.
discrete groupoids (in short p.m.p. groupoids, see Definition 2.4) and to
introduce the ultraproducts $(\mathcal{G}_{\mathfrak{u}},\Phi_{\mathfrak{u}})$
of sequences of such objects. The use of a non principal ultrafilter
$\mathfrak{u}$ has the advantage of ensuring convergence and the existence of
limit objects, strongly related to more standard objects when some extra
assumption provides forms of convergence. Some other authors have considered a
study of sequences of group actions via ultraproducts (see for instance
[Ele10b, CKTD13, Car15, AF16, AP18]). The counterpart in our treatment is that
we have been led to develop some orbit equivalence theory in the framework of
groupoids on non-standard probability spaces.

The cost of p.m.p. countable equivalence relations with countable classes is
defined in terms of graphings (see [Lev95, Gab00]) and is an analogue of the
rank of a group. The extension to p.m.p. $s$-countable groupoids is quite
straightforward and has been considered by several authors (on standard Borel
spaces) for instance by [Ued06, Car11, AN12, Tak15]. The extension to the non-
standard setting is also straightforward. A graphing $\Phi=(A_{i})_{i\in I}$
(Definition 2.15) is a collection of bisections indexed by $I=\mathbb{N}$ or
some $\\{1,2,\cdots,N\\}$ and the _(groupoid) cost_ of the p.m.p. groupoid
$\mathcal{G}$ is the infimum of the costs of its generating graphings:

$\mathcal{C}(\mathcal{G})=\inf\left\\{\mathcal{C}(\Phi)\colon\Phi\text{
generating graphings of }\mathcal{G}\right\\}.$ (1)

It is the infimum of the “Haar” measure of the measurable generating subsets
of $\mathcal{G}$. When $\mathcal{G}$ is produced by some p.m.p. action
$\Gamma\curvearrowright^{a}(X,\mu)$ of a countable group, one denotes the cost
of $\mathcal{G}$ by $\mathcal{C}(a)$, not to be confused with the cost of the
underlying equivalence relation when the action is not free! Another possible
source of confusion is the following. A countable group $\Gamma$ is also a
p.m.p. groupoid. As such, its cost is the infimum of the cardinal of a set of
generators. In [Gab00] and several further references, the cost of a group was
defined as the infimum of the costs of all its (standard) free p.m.p. actions.
This latter invariant will subsequently be denoted by
$\mathscr{C}_{*}(\Gamma)$ with a subscript $*$ for the infimum. We observe in
Corollary 4.1(3) that $\mathscr{C}_{*}(\Gamma)$ is indeed an infimum over all
p.m.p. actions, free or not, standard or not. The supremum of the costs of all
free (standard) p.m.p. $\Gamma$-actions will be denoted by
$\mathscr{C}^{*}(\Gamma)$. The group $\Gamma$ has fixed price when
$\mathscr{C}_{*}(\Gamma)=\mathscr{C}^{*}(\Gamma)$. We introduce the analogous
“fixed price problem” (Question 3.25) for p.m.p. groupoids.

A key technical result in [Gab98, Étape 1] and [Gab00, Proposition IV.35]
claims that the cost of a p.m.p. equivalence relation can be computed inside a
given Lipschitz class of (finite cost) graphings. The same holds for p.m.p.
groupoids:
$\mathcal{C}(\mathcal{G})=\inf_{L}\mathcal{C}_{L}(\mathcal{G},\Phi)$ where the
$L$-_Lipschitz cost_ $\mathcal{C}_{L}(\mathcal{G},\Phi)$ of the graphed
groupoid $(\mathcal{G},\Phi)$ is the infimum of the costs of all graphings of
$\mathcal{G}$ which are $L$-Lipschitz equivalent to $\Phi$ (see Lemma 3.6 and
Lemma 3.9).

Of course, the speed of convergence of $\mathcal{C}_{L}(\mathcal{G},\Phi)$ to
$\mathcal{C}(\mathcal{G})$ as a function of $L$ depends on the particular
graphed groupoid we are considering. This dependance is what makes the spice
of the notion of combinatorial cost for a sequence of graphings (initially
introduced by G. Elek [Ele07] in the combinatorial context of sequences of
finite graphs): one works with a uniform Lipschitz scale $L$ along the
sequence (thus obtaining limits of $\mathcal{C}_{L}(\mathcal{G}_{n},\Phi)$)
and then one let the Lipschitz constant $L$ vary. If
$(\mathcal{G}_{n},\Phi_{n})_{n}$ is a sequence of graphed p.m.p. groupoids of
bounded size, we define the $\mathfrak{u}$-_combinatorial cost_ (Definition
3.7) of the sequence as

$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n}):=\inf_{L}\lim_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n}).$

The Lipschitz framework is appropriate for uniformly bounded sequences of
graphings (Section 3.1). For the general unbounded setting, we introduce the
more appropriate notions of coarse structure (Section 2.4) and coarse
equivalence (Section 3.2) for p.m.p. groupoids, inspired by Roe’s topological
analogues [Roe03] and we define the $\mathfrak{u}$-combinatorial cost in that
context (Definition 3.11).

For group actions, our first main result is the following:

######  Theorem 1.1 (Theorem 4.2).

Let $\Gamma$ be a finitely generated group. For every sequence $(a_{n})_{n}$
of p.m.p. $\Gamma$-actions we have:

$\mathcal{C}(a_{\mathfrak{u}})=c\mathcal{C}_{\mathfrak{u}}((a_{n})_{n})\geq\lim_{\mathfrak{u}}\mathcal{C}(a_{n})\geq\liminf_{n\to\infty}\mathcal{C}(a_{n})\geq\mathscr{C}_{*}(\Gamma).$
(2)

Moreover if the action $a_{\mathfrak{u}}$ is essentially free we have
$\mathscr{C}^{*}(\Gamma)\geq\mathcal{C}(a_{\mathfrak{u}})$ and hence if
$\Gamma$ has fixed price we obtain
$\lim_{\mathfrak{u}}\mathcal{C}(a_{n})=c\mathcal{C}_{\mathfrak{u}}((a_{n})_{n})=\mathcal{C}(a_{\mathfrak{u}})=\mathscr{C}_{*}(\Gamma)$.

We observe that this continuity statement fails when one removes the finite
generation assumption (see Remark 3.14).

This Theorem is the specialization to group actions of the following more
general statement for graphed groupoids:

######  Theorem 1.2 (Theorem 3.13).

If a sequence of p.m.p. graphed groupoids $(\mathcal{G}_{n},\Phi_{n})$ and its
ultraproduct groupoid $(\mathcal{G}_{\mathfrak{u}},\Phi_{\mathfrak{u}})$
satisfy
$\lim_{\mathfrak{u}}\mathcal{C}(\Phi_{n})=\mathcal{C}(\Phi_{\mathfrak{u}})<\infty$
(i.e. finite cost and “no loss of mass at infinity”), then

$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})=\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\geq\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n}).$

This allow us to interpret the original Elek’s combinatorial cost [Ele07]
($c\mathcal{C}((\mathcal{G}_{n},\Phi_{n})_{n}):=\inf_{L}\liminf\limits_{n\to\infty}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})$
see Remark 3.16, Formula (21)) in terms of cost for ultraproducts of graphed
groupoids.

######  Corollary 1.3 (Combinatorial cost vs cost (Corollary 3.17)).

If $(G_{n})_{n}$ is a sequence of finite graphs with uniformly bounded degree,
then the combinatorial cost is the infimum over all non principal ultrafilters
of the costs of the ultraproduct groupoids $\mathcal{G}_{\mathfrak{u}}$ of the
associated $(\mathcal{G}_{n},\Phi_{n})$:

$c\mathcal{C}((G_{n})_{n})=\inf\\{\mathcal{C}(\mathcal{G}_{\mathfrak{u}}):\mathfrak{u}\textrm{
non principal ultrafilter}\\}.$

We now concentrate on sofic groups, a class of groups defined in terms of
ultraproducts of finite structures (see Section 3.6).

######  Corollary 1.4 (Corollary 4.4).

If $\Gamma$ is a sofic group finitely generated by $S$ and
$(\mathcal{G}_{n},\Phi_{n})_{n}$ is a sofic approximation to $\Gamma$ (with
$S$-labelled graphings), then

$\mathscr{C}^{*}(\Gamma)\geq\mathcal{C}(\mathcal{G}_{\mathfrak{u}})=c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})\geq\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n})\geq\liminf_{n\to\infty}\mathcal{C}(\mathcal{G}_{n})\geq
1.$ (3)

If $\Gamma$ has moreover fixed price $\mathscr{C}_{*}(\Gamma)$, then
$\mathscr{C}_{*}(\Gamma)=c\mathcal{C}((\mathcal{G}_{n},\Phi_{n})_{n})$ and
hence if $\Gamma$ has fixed price $\mathscr{C}_{*}(\Gamma)=1$, we obtain
$c\mathcal{C}((\mathcal{G}_{n},\Phi_{n})_{n})=\lim_{n\to\infty}\mathcal{C}(\mathcal{G}_{n})=1$.

_Farber sequences_ are sequences of finite index subgroups $(\Gamma_{n})_{n}$
of $\Gamma$ giving particular instances of sofic approximations via the
natural actions $\Gamma\curvearrowright\Gamma/\Gamma_{n}$ (see Section 4.1).
If $\Gamma$ is finitely generated by $S$, we denote by
$\mathrm{Sch}(\Gamma/\Gamma_{n},S)$ the associated Schreier graph.

######  Corollary 1.5 (Corollary 4.9).

If $\Gamma$ is finitely generated by $S$ and $(\Gamma_{n})_{n}$ is a nested
Farber sequence, then
$\mathcal{C}(a_{\mathfrak{u}})=c\mathcal{C}_{\mathfrak{u}}(a_{n})=c\mathcal{C}(\mathrm{Sch}(\Gamma/\Gamma_{n},S)_{n})=\lim\limits_{n\to\infty}\mathcal{C}(a_{n})$.

######  Corollary 1.6 (Corollary 4.11).

If $\Gamma$ is finitely generated by $S$, has fixed price
$\mathscr{C}_{*}(\Gamma)$, and $(\Gamma_{n})_{n}$ is any (non necessarily
nested) Farber sequence, then we have:

$\lim\limits_{n\to\infty}\frac{\mathrm{rank}(\Gamma_{n})-1}{[\Gamma:\Gamma_{n}]}+1=c\mathcal{C}(\mathrm{Sch}(\Gamma/\Gamma_{n},S))=\mathscr{C}_{*}(\Gamma).$

This corollary is a far reaching extension of a theorem of Abért and Nikolov
[AN12, Theorem 1] (nested and Farber sequences) for which we provide an
alternative proof for (nested and) non-necessarily Farber sequences of finite
index subgroups – see Corollary 4.5.
The convergence of the sequence in Corollary 4.11 is not at all clear for non
fixed price groups, contrarily to [AN12, Theorem 1] where it is non-
increasing. This also gives a converse to [AGN17, Theorem 8] where an
inequality
$\lim\limits_{n\to\infty}\frac{\mathrm{rank}(\Gamma_{n})-1}{[\Gamma:\Gamma_{n}]}+1\leq
c\mathcal{C}(\mathrm{Sch}(\Gamma/\Gamma_{n},S))$ was obtained. The non
necessarily fixed price case is considered in Theorem 4.10.

These corollaries apply potentially to plenty of groups. Examples of groups
with fixed price $1$ include infinite amenable groups, infinite-conjugacy-
class (icc) inner amenable groups, direct products $\Gamma\times\Lambda$ where
$\Lambda$ is infinite and $\Gamma$ contains a fixed price $1$ subgroup, groups
with a normal (or even just commensurated) fixed price $1$ subgroup $N$, more
generally groups with a commensurated fixed price $1$ subgroup $C$ (Corollary
3.3) (this applies for instance to $\mathrm{SL}(d,\mathbb{Z}[1/p])$, $d\geq
3$), amalgamated free products of fixed price $1$ groups over infinite
amenable subgroups, Thompson’s group F, $\mathrm{SL}(n,\mathbb{Z})$ for $n\geq
3$, non-cocompact arithmetic lattices in connected semi-simple algebraic Lie
groups of $\mathbb{Q}$-rank at least $2$, groups generated by chain-commuting
infinite order elements (i.e., infinite order elements whose graph of
commutation is connected) sometimes called _Right Angled groups_ (this
includes Mapping Class Groups $\mathrm{MCG}(\Sigma_{g})$ of surfaces with
genus $g\geq 3$, $\mathrm{Out}({\bf F}_{n})$ for $n\geq 3$, Right Angled Artin
groups with connected defining graphs), more generally groups generated by a
sequence of subgroups $(\Gamma_{n})$ of fixed price $1$ such that the
intersections $\Gamma_{n}\cap\Gamma_{n+1}$ are infinite…

We introduce some terminology. A countable group $\Gamma$ is called a _Stuck-
Zimmer group_ if any p.m.p. aperiodic $\Gamma$-action on a standard Borel
space has a.s. finite stabilizers. The key point about Stuck-Zimmer groups
$\Gamma$ in our context, as observed in [ABB+17], is that under mild
divergence assumptions, all sequences $(\Gamma_{n})_{n}$ of finite index
subgroups give indeed Farber sequences (see Theorem 4.14). If $\Gamma$ is a
finitely generated Stuck-Zimmer group and $[\Gamma:\Gamma_{n}]\to\infty$, then
for every torsion free subgroup $\Lambda<\Gamma$, the induced action
$\Lambda\curvearrowright\Gamma/\Gamma_{n}$ defines a sofic approximation of
$\Lambda$. Thus when $\Gamma$ is torsion free and has fixed price
$\mathscr{C}_{*}(\Gamma)$, Corollary 4.11 applies:
$\lim_{n}\frac{\mathrm{rank}(\Gamma_{n})-1}{[\Gamma:\Gamma_{n}]}=\mathscr{C}_{*}(\Gamma)-1$.

We introduce a relative version of Stuck-Zimmer groups for which the mild
divergence assumption concerns some subgroup $N<\Gamma$. We obtain a general
result (Theorem 4.15) which specializes to the following:

######  Theorem 1.7 (See Theorem 4.18).

Let $\Lambda<\mathrm{SL}(d,\mathbb{Z})$ be a finite index subgroup and
$(\Gamma_{n})_{n}$ be any sequence of finite index subgroups of
$\Gamma=\Lambda\ltimes\mathbb{Z}^{d}$ such that
$[\mathbb{Z}^{d}:\Gamma_{n}\cap\mathbb{Z}^{d}]\underset{n\to\infty}{\longrightarrow}\infty$.
Then $\Gamma\curvearrowright\Gamma/\Gamma_{n}$ defines a sofic approximation
of $\Gamma$ and

$\lim_{n}\frac{\left(\mathrm{rank}(\Gamma_{n})-1\right)}{[\Gamma:\Gamma_{n}]}=0.$
(4)

This applies more generally for $\Lambda<\mathrm{SL}(d,\mathbb{Z})$ that
admits no $\Lambda$-invariant finite union of infinite index subgroups of
$\mathbb{Z}^{d}$ (see Theorem 4.18). In particular,

######  Theorem 1.8.

Let $\Lambda$ be any subgroup of $\mathrm{SL}(2,\mathbb{Z})$ containing a
hyperbolic element. Any sequence $(\Gamma_{n})_{n}$ of finite index subgroups
of $\Gamma:=\Lambda\ltimes\mathbb{Z}^{2}$ such that
$[\mathbb{Z}^{2}:\Gamma_{n}\cap\mathbb{Z}^{2}]\underset{n\to\infty}{\longrightarrow}\infty$
defines a sofic approximation of $\Gamma$ and

$\lim_{n}\frac{\left(\mathrm{rank}(\Gamma_{n})-1\right)}{[\Gamma:\Gamma_{n}]}=0.$
(5)

This holds for instance for the amenable group
$\Gamma=\Lambda\ltimes\mathbb{Z}^{2}=\left\langle\begin{pmatrix}1&1\\\
1&2\end{pmatrix}\right\rangle\ltimes\mathbb{Z}^{2}$.

Lück approximation theorem [Lüc94] considers a descending sequence
$(\Gamma_{n})_{n}$ of finite index normal subgroups with trivial intersection
of a countable group $\Gamma$ which acts freely cocompactly on a simplicial
complex $L$ and it relates the Betti numbers of $\Gamma_{n}\backslash L$ to
the $\ell^{2}$-Betti numbers of the action:

$\lim_{n\to\infty}\frac{b_{i}(\Gamma_{n}\backslash
L)}{[\Gamma:\Gamma_{n}]}=\beta^{(2)}_{i}(\Gamma\curvearrowright L).$ (6)

Bergeron-Gaboriau [BG04] have interpreted this convergence as a continuity
result for $\ell^{2}$-Betti numbers of projective systems of fields of
simplicial complexes for equivalence relations. This allowed them to extend
the framework so as to encompass non-normal subgroups and non trivial
intersection descending sequences of subgroups. They established the
convergence of the sequence and identified the limit as the $\ell^{2}$-Betti
number of a laminated space [BG04, Théorème 0.2, Théorème 3.1].

Our third main result generalizes this continuity statement in several ways:
we extend it from equivalence relations to groupoids, from finite quotients to
sofic and we consider arbitrary limits instead of projective ones. The use of
ultrafilters forces a kind of convergence of the objects as fields of
simplicial complexes with groupoid actions and we identify the limits. We
state our result under some boundedness assumption (see Section 5, see Theorem
5.15 for the version without the boundedness assumption):

######  Theorem 1.9 (Theorem 5.9).

For every $n\in\mathbb{N}$ let $(\mathcal{G}_{n},\Phi_{n})$ be a sofic graphed
p.m.p. groupoid over $X_{n}$, let $\Sigma_{n}$ be a $(\Phi_{n},L)$-uniformly
locally bounded $\mathcal{G}_{n}$-simplicial complex for some fixed
$L\in\mathbb{N}$. Then

$\lim_{\mathfrak{u}}\beta^{(2)}_{i}(\Sigma_{n},\mathcal{G}_{n})=\beta^{(2)}_{i}(\Sigma_{\mathfrak{u}},\mathcal{G}_{\mathfrak{u}}).$

In particular if the sequence of $\mathcal{G}_{n}$-simplicial complexes
$\Sigma_{n}$ is asymptotically uniformly $k$-connected (see Proposition 5.8),
then for every $i\leq k$

$\lim_{\mathfrak{u}}\beta^{(2)}_{i}(\Sigma_{n},\mathcal{G}_{n})=\beta^{(2)}_{i}(\mathcal{G}_{\mathfrak{u}}).$

Our approach with ultraproducts allows us to relate the Laplace operators for
the finite objects to that of our limit object (compare [ES05, Proposition
6.1] or [Tho08] where the finite induced operators do not clearly appear as
Laplace operators). Observe however that we make a crucial use of a Lemma of
Thom [Tho08] (see Lemma 5.12). The above theorem is also related to a (recent
and independent) work of Schrödl [Sch18] on $\ell^{2}$-Betti numbers and
Benjamini-Schramm convergence (see also [Ele10a]). Indeed, similarly to the
case of local-global convergence of graphs (Remark 3.21), Benjamini-Schramm
limits of random simplicial complexes can be expressed in terms of the
ultraproduct of the sequence of the associated field of simplicial complexes
(see Remark 5.7 and Remark 5.21).

As a corollary of the above theorem, we obtain the following geometric
generalization of Lück approximation Theorem for (non-nested, non normal)
sequences of subgroups:

######  Corollary 1.10 (Corollary 5.10).

Let $\Gamma$ be a countable group acting freely cocompactly on a simplicial
complex $L$. Let $(\Gamma_{n})_{n}$ be a (non necessarily nested) Farber
sequence of finite index subgroups. Then for every $i$ we have:

$\lim\limits_{n\to\infty}\frac{b_{i}(\Gamma_{n}\backslash
L)}{[\Gamma:\Gamma_{n}]}=\beta^{(2)}_{i}(\Gamma\curvearrowright L).$

In particular, if $L$ is $k$-connected, then for every $i\leq k$ we have:

$\lim\limits_{n\to\infty}\frac{b_{i}(\Gamma_{n})}{[\Gamma:\Gamma_{n}]}=\beta^{(2)}_{i}(\Gamma).$

More generally, we obtain the following generalization of [BG04, Theorem 3.1]
for non nested, non Farber sequences:

######  Corollary 1.11 (Corollary 5.11).

Let $(\Gamma_{n})_{n}$ be any sequence of finite index subgroups of a finitely
generated group $\Gamma$. Assume $\Gamma$ acts freely cocompactly on the
simplicial complex $\Sigma$. Let $a_{\mathfrak{u}}:\Gamma\curvearrowright
X_{\mathfrak{u}}$ be the ultraproduct of the actions
$a_{n}:\Gamma\curvearrowright\Gamma/\Gamma_{n}$ and
$\mathcal{N}_{\mathfrak{u}}:=\\{(x,\gamma)\in
X_{\mathfrak{u}}\times\Gamma:\gamma x=x\\}$ its maximal totally isotropic
subgroupoid. Then for every $i\leq k$ we have

$\lim\limits_{n\in\mathfrak{u}}\frac{b_{i}(\Gamma_{n}\backslash\Sigma)}{[\Gamma:\Gamma_{n}]}=\beta^{(2)}_{i}(\mathcal{N}_{\mathfrak{u}}\backslash\left(X_{\mathfrak{u}}\times\Sigma\right),{\mathcal{R}}_{\mathfrak{u}}),$

where
${\mathcal{R}}_{\mathfrak{u}}=\mathcal{G}_{\mathfrak{u}}/\mathcal{N}_{\mathfrak{u}}$
is the p.m.p. equivalence relation of the action $a_{\mathfrak{u}}$ and
$\mathcal{N}_{\mathfrak{u}}\backslash\left(X_{\mathfrak{u}}\times\Sigma\right)$
is the ${\mathcal{R}}_{\mathfrak{u}}$-simplicial complex defined in Example
2.25.

We indicate now how these approximation results must be modified when the
boundedness assumptions are not satisfied.

Let $\Gamma$ be a finitely generated residually finite group and let
$(\Gamma_{n})_{n\in\mathbb{N}}$ be a nested sequence of finite index normal
subgroups with trivial intersection. Lück approximation theorem
$\frac{b_{1}(\Gamma_{n})}{[\Gamma:\Gamma_{n}]}\to\beta_{1}^{(2)}(\Gamma)$ does
not hold in general when $\Gamma$ is not finitely presented, as exemplified by
torsion groups (thus $b_{1}(\Gamma_{n})=0$) with positive first $L^{2}$-Betti
number [LO11]. This defect can be fixed by taking a double limit as exposed
below and this idea will then be pushed to the framework of ultraproduct
(Theorem 5.15).

######  Proposition 1.12.

Let
$\Gamma=\langle\gamma_{1},\gamma_{2},\cdots,\gamma_{d}|r_{1},r_{2},\cdots,r_{k},\cdots\rangle$
be a presentation of $\Gamma$ with finitely many generators. Let $L$ be the
associated ($2$-dimensional) Cayley $\Gamma$-complex and let $L_{j}$ be the
$\Gamma$-invariant co-compact sub-complex associated with the first $j$
relations $r_{1},r_{2},\cdots,r_{j}$. Then

$\beta_{1}^{(2)}(\Gamma)=\lim\limits_{j\to\infty}\lim\limits_{n\to\infty}\frac{b_{1}(\Gamma_{n}\backslash
L_{j})}{[\Gamma:\Gamma_{n}]}.$

The substance of the counter-examples of [LO11] relies on the fact that these
limits cannot be exchanged. Indeed on the one hand,
$\lim\limits_{n\to\infty}\frac{b_{1}(\Gamma_{n}\backslash
L_{j})}{[\Gamma:\Gamma_{n}]}=\beta_{1}^{(2)}(\Gamma\curvearrowright L_{j})$ by
Lück approximation theorem [Lüc94], and
$\beta_{1}^{(2)}(\Gamma\curvearrowright L_{j})$ decreases with $j$ to
$\beta_{1}^{(2)}(\Gamma)$. On the other hand, for every $n$, we have
$b_{1}(\Gamma_{n}\backslash L_{j})=0$ for large enough $j$ since the canonical
surjective maps $\pi_{1}(\Gamma_{n}\backslash
L_{j})\to\pi_{1}(\Gamma_{n}\backslash L_{k})$ (for $j\leq k$) produce as
direct limit the torsion group $\Gamma_{n}$, so that
$\pi_{1}(\Gamma_{n}\backslash L_{j})$ is generated by torsion elements for
large enough $j$ and its abelianization is thus finite.

More generally, in higher dimension, we obtain the following.

######  Proposition 1.13.

Let $\Gamma$ be a residually finite group and let
$(\Gamma_{n})_{n\in\mathbb{N}}$ be a nested sequence of finite index normal
subgroups with trivial intersection. If $\Gamma$ acts freely on the
$d$-connected simplicial complex $L$, we write $L$ as an increasing union
$L=\cup\nearrow L_{j}$ of $\Gamma$-invariant co-compact sub-complexes $L_{j}$.
The inclusions $L_{j}\subset L_{k}$ for $j\leq k$ induce linear maps
$H_{d}(\Gamma_{n}\backslash L_{j},\mathbb{C})\to H_{d}(\Gamma_{n}\backslash
L_{k},\mathbb{C})$ between the $d$-dimensional homology of the compact
quotients. Then

$\beta_{d}^{(2)}(\Gamma)=\lim\limits_{j\to\infty}\lim\limits_{j\leq
k,\,k\to\infty}\lim\limits_{n\to\infty}\dim_{\mathbb{C}}\operatorname{Im}\Bigl{(}H_{d}(\Gamma_{n}\backslash
L_{j},\mathbb{C})\to H_{d}(\Gamma_{n}\backslash L_{k},\mathbb{C})\Bigr{)}.$

This proposition follows from Theorem 5.15 and the fact that, for free p.m.p.
actions, the $L^{2}$-Betti numbers of the equivalence relation generated by
the action agree with the ones of the group itself. The above result holds
more generally for Farber sequence of subgroups.

In [Ele07], Elek introduced another quantity for a graph sequence
$(G_{n})_{n}$: the $\beta$-invariant over the field $\mathbb{K}$:

$\beta_{\mathbb{K}}((G_{n})_{n}):=\inf_{q}\liminf_{n\to\infty}\frac{|E(G_{n})|-\dim_{\mathbb{K}}V_{q}(G_{n})}{|V(G_{n})|}-1,$

where $|E(G_{n})|$ and $|V(G_{n})|$ are the number of edges and vertices and
where $V_{q}(G_{n})$ is the $\mathbb{K}$-vector space spanned by the cycles of
length $\leq q$ in the space of $1$-chains. Equivalently (when
$|V(G_{n})|\to\infty$), this is also

$\beta_{\mathbb{K}}((G_{n})_{n}):=\inf_{q}\liminf_{n\to\infty}\frac{b_{1}(G_{n}^{q})}{|V(G_{n})|},$

where $G_{n}^{q}$ is obtained from the graph $G_{n}$ by gluing $2$-cells along
every cycle of length $\leq q$.

Inspired by that, we introduce higher dimensional invariants for uniformly
bounded vertex degrees sequences of graphs $(G_{n})_{n}$. We consider
$R^{q}(G_{n})$, the $q$-Rips complex of $G_{n}$ for all integers $q$ and we
introduce the _$d$ -dimensional $\beta$-invariant_:

$\beta_{d,\mathbb{K}}((G_{n})_{n}):=\lim_{q\to\infty}\lim_{p\to\infty}\lim_{\mathfrak{u}}\frac{\dim_{\mathbb{K}}\mathrm{Im}\left(H_{d}(R^{q}(G_{n}),\mathbb{K})\to
H_{d}(R^{q+p}(G_{n}),\mathbb{K})\right)}{|V_{n}|}.$

If $\mathbb{K}=\mathbb{Q}$ and $(G_{n})_{n}$ has uniformly bounded degree,
Theorem 5.15 implies
$\beta_{d,\mathbb{\mathbb{Q}}}((G_{n})_{n})=\beta_{d}^{(2)}({\mathcal{R}}_{\mathfrak{u}})$
where ${\mathcal{R}}_{\mathfrak{u}}$ is the ultraproduct p.m.p. equivalence
relation of the sequence of graphs $(G_{n})_{n}$ (with well defined coarse
structure, see Remark 2.33). In particular, if $(G_{n})_{n}$ correspond to a
sofic approximation of a countable group $\Gamma$, one gets
$\beta_{d,\mathbb{\mathbb{Q}}}((G_{n})_{n})=\beta_{d}^{(2)}(\Gamma)$.

We briefly mention an extension we do not consider in this version in order to
limit the length of the present article. There exists also a notion of coarse
equivalence between pairs of sequences $(\mathcal{G}_{n},\Phi_{n})_{n}$ and
$(\mathcal{H}_{n},\Psi_{n})_{n}$ of graphed groupoids (compare [AF16] and
[Kai17] which considers finite structures). The groupoids $\mathcal{G}_{n}$
and $\mathcal{H}_{n}$ are in particular stably orbit equivalent, so that they
are related by a compression constant
$\iota(\mathcal{G}_{n},\mathcal{H}_{n})$. When the sequence of compression
constants is bounded, the ultraproduct groupoids $\mathcal{G}_{\mathfrak{u}}$
and $\mathcal{H}_{\mathfrak{u}}$ are orbit equivalent (with compression
constant
$\iota(\mathcal{G}_{\mathfrak{u}},\mathcal{H}_{\mathfrak{u}})=\lim\limits_{\mathfrak{u}}\iota(\mathcal{G}_{n},\mathcal{H}_{n})$)
and their costs and $\ell^{2}$-Betti numbers are related as the standard ones:

$\mathcal{C}(\mathcal{H}_{\mathfrak{u}})-1=\iota(\mathcal{G}_{\mathfrak{u}},\mathcal{H}_{\mathfrak{u}})(\mathcal{C}(\mathcal{G}_{\mathfrak{u}})-1)\
\text{ and
}\beta_{j}^{(2)}(\mathcal{H}_{\mathfrak{u}})=\iota(\mathcal{G}_{\mathfrak{u}},\mathcal{H}_{\mathfrak{u}})\beta_{j}^{(2)}(\mathcal{G}_{\mathfrak{u}}).$

Warning: We have obtained some of our main results (especially Theorem 3.13) a
couple of years ago. We discovered during the “Measured Group Theory” ESI
workshop in Vienna (February 2016) that some of our results had a non trivial
intersection with some ongoing work of Abért-Tóth (especially the first
equality in our Theorem 1.1 in the case of local-global convergent sequences
and our Corollary 1.6). Some accident prevented us from releasing our papers
simultaneously, but the overlaps with [AT17] must be considered parallel and
independent results.

#### Acknowledgments:

We are grateful to Luiz Cordeiro and László Márton Tóth for their comments and
their careful reading of a preliminary version (November 2018). We also thank
Gabor Elek pointing out some references. The three authors are supported by
the ANR project GAMME (ANR-14-CE25-0004). The first named author is supported
by the ERC Consolidator Grant No. 681207. The second and third named authors
are supported by the CNRS and by the LABEX MILYON (ANR-10-LABX-0070) of
Université de Lyon, within the program “Investissements d’Avenir"
(ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). The
third author is also supported by the ANR project AGIRA (ANR-16-CE40-0022). We
are grateful to the Erwin Schrödinger Institute for Mathematics and Physics
for hospitality during “Measured group theory” program in 2016.

##  2 Preliminaries

In this text we will work with probability spaces, often denoted by
$(X,\mathscr{B},\mu)$ or simply by $(X,\mu)$ whenever the $\sigma$-algebra can
be safely omitted from the notation. We will make no further assumption on the
probability spaces and in particular we will not assume the $\sigma$-algebra
to be countably generated. While working in this context one has to be more
careful with some standard definitions since the classical Lusin-Novikov’s
uniformization theorem and the von Neumann-Jankow selection theorem do not
hold. Therefore we will carefully define all the objects we will need.

A _partial isomorphism_ from the probability space $(X,\mu)$ to $(Y,\nu)$ is a
bi-measurable bijection $\varphi:\operatorname{dom}(\varphi)\subset
X\to\operatorname{tar}(\varphi)\subset Y$ between measurable subsets of $X$
and $Y$ which preserves the measure.

######  Definition 2.1.

A countable _fibred space_ over $X$ consists in a measure space
$(\mathcal{F},\mathscr{A},\widetilde{\mu})$ and a measurable map
$\pi\colon\mathcal{F}\rightarrow X$ such that there is a measurable subset
$\widetilde{\mathcal{F}}\subset X\times\mathbb{N}$ (for the product
$\sigma$-algebra and product measure) and a bi-measurable measure preserving
bijection $u\colon\mathcal{F}\to\widetilde{\mathcal{F}}$ such that
$u(f)\in\\{\pi(f)\\}\times\mathbb{N}$ for every $f$.

######  Remark 2.2.

By definition, countable fibred spaces are the measurable subspaces of the
trivial fibred space $X\times\mathbb{N}$. Partitioning each $A\in\mathscr{A}$
into the measurable subsets $A_{i}:=A\cap X\times\\{i\\}$ shows that:

  * •

the map $x\in X\mapsto|\pi^{-1}(x)\cap A|$ is measurable and

$\tilde{\mu}(A)=\int_{X}\left|\pi^{-1}(x)\cap A\right|d\mu(x);$ (7)

  * •

the subset $\pi(A)=\cup_{i}\pi(A_{i})$ is measurable;

  * •

if $|\pi^{-1}(x)\cap A|\leq 1$ for almost every $x\in X$, then
$\pi\bigr{|}_{A}:A\to\pi(A)$ is a measure preserving isomorphism;

  * •

any measurable section $\varphi:B\subset X\to\mathcal{F}$ of $\pi$ is a
measure preserving isomorphism between $B$ and $\varphi(B)$ (consider for
$B_{i}:=\varphi^{-1}(X\times\\{i\\})$).

When $X$ and $\mathcal{F}$ are standard Borel spaces and
$\pi\colon\mathcal{F}\to X$ is a measurable map with countable fibers, the
standard selection theorem of Lusin-Novikov [LN35] produce measurable sections
allowing to realize $\mathcal{F}$ as a Borel subset of $X\times\mathbb{N}$.
The _height_ $H(\mathcal{F})$ of a fibred space $\mathcal{F}$ is the essential
supremum of the function $x\mapsto|\pi^{-1}(x)|$ for $x\in X$. We say that
$\mathcal{F}$ has _finite height_ if $H(\mathcal{F})$ is finite. The _fibred
product_ $(\mathcal{F}_{1}*\mathcal{F}_{2},\mathscr{A},\pi)$ of two countable
fibred spaces $(\mathcal{F}_{1},\mathscr{A}_{1},\pi_{1})$ and
$(\mathcal{F}_{2},\mathscr{A}_{2},\pi_{2})$ over $X$ is defined as usual by

$(\mathcal{F}_{1},\pi_{1})*(\mathcal{F}_{2},\pi_{2}):=\left\\{(x,y)\in\mathcal{F}_{1}\times\mathcal{F}_{2}:\
\pi_{1}(x)=\pi_{2}(y)\right\\},$

(in short $\mathcal{F}_{1}*\mathcal{F}_{2}$) equipped with the projection
$\pi(x,y)=\pi_{1}(x)=\pi_{2}(y)$ and the $\sigma$-algebra coming from the
injection into $X\times\mathbb{N}\times\mathbb{N}$ if $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$ are realized inside $X\times\mathbb{N}$. This is easily seen
to be independent of the realizations.

###  2.1 Measured groupoids

The main object of study of this text will be measured groupoids.

######  Definition 2.3.

A _groupoid_ $\mathcal{G}$ over the set $X$ is the data of

  * •

a set $\mathcal{G}$ containing $X$; the elements of $X$ are called the units
of $\mathcal{G}$,

  * •

a source map $s:\mathcal{G}\rightarrow X$ and a target map
$t:\mathcal{G}\rightarrow X$ which are the identity when restricted to $X$,

  * •

for every $g$ and $h\in\mathcal{G}$ such that $s(g)=t(h)$ there is a product
$gh\in\mathcal{G}$ satisfying $s(gh)=s(h)$ and $t(gh)=t(g)$.

  * •

for every $g\in\mathcal{G}$ there exists a unique inverse
$g^{-1}\in\mathcal{G}$ such that $s(g^{-1})=t(g)$, $t(g^{-1})=s(g)$,
$gg^{-1}=t(g)$ and $g^{-1}g=s(g)$.

for which we require that the following identities hold

  * •

the product is associative, that is $g(hk)=(gh)k$ whenever this is defined,

  * •

for every $g\in\mathcal{G}$ we have that $t(g)g=gs(g)=g$.

In this text we will always assume that every groupoid is $s$-countable, i.e.,

  * •

for every $x\in X$ the set $s^{-1}(x)$ is countable.

Observe that the multiplication induces a map
$(\mathcal{G},s)*(\mathcal{G},t)\rightarrow\mathcal{G}$.

######  Definition 2.4.

A _p.m.p. groupoid_ over $(X,\mu)$ is a groupoid $\mathcal{G}$ over $X$
equipped with a $\sigma$-algebra $\mathscr{A}$ and a measure $\widetilde{\mu}$
such that

  * •

$(\mathcal{G},\mathscr{A},\widetilde{\mu},s)$ and
$(\mathcal{G},\mathscr{A},\widetilde{\mu},t)$ are both countable fibred spaces
over $(X,\mu)$,

  * •

the maps $g\in\mathcal{G}\mapsto g^{-1}\in\mathcal{G}$ and
$(g,h)\in(\mathcal{G},s)\ast(\mathcal{G},t)\mapsto gh$ are measurable.

In particular, the measure $\widetilde{\mu}$ coincides with both fibred
measures for $s$ and $t$ (see (7)). Observe that we restrict ourselves to
measured groupoids with countable fibers, a.k.a. discrete, or countable, or
$r$-discrete (see [ADR00]); but we do not assume that the base space $X$ is
standard.

Let $\mathcal{G}$ be a groupoid over $X$. The _isotropy group_ at $x\in X$ is
the group $\mathcal{G}_{x}:=\\{g\in\mathcal{G}:s(g)=t(g)=x\\}$. When the
isotropy groups are all trivial, the groupoid is called a _principal groupoid_
or an _equivalence relation_. For p.m.p. groupoids, the triviality is required
only almost surely.

######  Example 2.5 (Group action groupoid).

Let $\Gamma$ be a countable group acting on a probability space $(X,\mu)$
preserving the measure. Then $\mathcal{G}_{\Gamma\curvearrowright
X}:=\Gamma\times X$ (with the product measured structure) is a p.m.p. groupoid
over the probability space $X$ (identified with the subset $\\{1\\}\times X$
of $\Gamma\times X$) where $s(\gamma,x)=x$, $t(\gamma,x)=\gamma x$ and
$(\gamma,x)(\gamma^{\prime},x^{\prime})=(\gamma\gamma^{\prime},x^{\prime})$ if
$\gamma^{\prime}x^{\prime}=x$.

######  Example 2.6.

Lusin-Novikov’s uniformization theorem [LN35] (see also [Kec95, Theorem
18.10]), implies that if $(X,\mu)$ is a standard Borel space and
${\mathcal{R}}\subset X\times X$ is an Borel p.m.p. equivalence relation with
countable classes (see [FM77]), then ${\mathcal{R}}$ is a p.m.p. principal
groupoid as in Definition 2.4 where $s$ and $t$ are respectively the second
and first coordinate projections $X\times X\to X$.

######  Example 2.7 (Equivalence relation associated to p.m.p. actions).

We warn the reader that, given a p.m.p. groupoid $\mathcal{G}$ over $X$, the
underlying equivalence relation
${\mathcal{R}}_{\mathcal{G}}:=\\{(s(x),t(x)):x\in\mathcal{G}\\}$ is in general
_not a p.m.p. groupoid_ in the sense of Definition 2.4, even for the
equivalence relation ${\mathcal{R}}_{\Gamma\curvearrowright X}=\\{(x,\gamma
x):x\in X,\gamma\in\Gamma\\}$ coming from a p.m.p. action of a countable group
$\Gamma$.

For example, consider the space $(X=[-1,1],\mathscr{B},\mu)$ when
$\mathscr{B}$ is the $\sigma$-algebra of all Borel-measurable subsets $B$ of
$[-1,1]$ satisfying $B=-B$, and $\mu$ the normalized Lebesgue measure. Let
$\Omega\subset(0,1]$ be a subset which is not Lebesgue-measurable. The map
$\varphi:x\mapsto-x$ on $\Omega\cup-\Omega$ and $x\mapsto x$ on its complement
is a measurable p.m.p. involution of $([-1,1],\mathscr{B},\mu)$. It defines a
p.m.p. action $\alpha$ of $\Gamma=\mathbb{Z}/2\mathbb{Z}$ on $[-1,1]$. Then
$\mathcal{G}_{\alpha}$ is a p.m.p. groupoid (Example 2.5), but
${\mathcal{R}}_{\alpha}=[-1,1]\cup\\{(x,-x):x\in\Omega\cup-\Omega\\}$ is not a
p.m.p. groupoid, since $x\mapsto|{\mathcal{R}}(x)|$ is not measurable (see
Remark 2.2 (1)). Indeed the field of isotropy groups $x\mapsto\mathcal{G}_{x}$
is not measurable in any reasonable sense.

Anticipating Definition 2.11, the map $\varphi$ is measurably isotropic but
not totally isotropic. If instead, $\Omega=X$, then the corresponding action
$\beta:\Gamma\curvearrowright X$ is totally free but not measurably free.

However, if the fixed-point set $\mathrm{Fix}(\gamma):=\\{x\in X:\gamma
x=x\\}$ is measurable for every $\gamma\in\Gamma$, then
${\mathcal{R}}_{\Gamma\curvearrowright X}$ is a p.m.p. principal groupoid
(define the $\sigma$-algebra on ${\mathcal{R}}_{\Gamma\curvearrowright X}$ as
the set of all countable unions of sets of the form $\\{(x,\gamma x):x\in
A\\}$ for $A\subset X$ measurable and $\gamma\in\Gamma$; the fixed-point set
condition takes care of the intersections). We warn the reader that the
condition that $\mathrm{Fix}(\gamma)$ is measurable is not necessary for
${\mathcal{R}}_{\Gamma\curvearrowright X}$ to carry a p.m.p. principal
groupoid structure. An example is given by
$\Gamma=\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2\mathbb{Z}\curvearrowright
X=[-1,1]$ is defined by $(\varepsilon_{1},\varepsilon_{2})\cdot
x=(-1)^{\varepsilon_{2}}\alpha(\varepsilon_{1})x$ for the action $\alpha$ of
$\mathbb{Z}/2\mathbb{Z}$ considered above. Indeed,
$\mathrm{Fix}(0,1)=\Omega\cup-\Omega$ is not measurable, but
${\mathcal{R}}_{\Gamma\curvearrowright X}$ is just $\\{(x,\pm x):x\in X\\}$
and clearly carries a p.m.p. groupoid structure.

More generally given an at most countable collection of partial isomorphisms
$\Phi=(\varphi_{i})_{i}$ of $(X,\mu)$, we can define an equivalence relation
${\mathcal{R}}$ by declaring that two points $(x,y)$ in $X$ are equivalent if
there exists $(i_{1},\ldots,i_{l})\in\mathbb{N}^{l}$ and
$(\varepsilon_{1},\ldots,\varepsilon_{l})\in\\{-1,1\\}^{l}$ such that
$\varphi_{i_{1}}^{\varepsilon_{1}}\ldots\varphi_{i_{l}}^{\varepsilon_{l}}(x)=y$.
If moreover for every $\Phi$-word
$\varphi=\varphi_{i_{1}}^{\varepsilon_{1}}\ldots\varphi_{i_{l}}^{\varepsilon_{l}}$,
the fixed-point set $\\{x:\varphi(x)=x\\}$ is measurable, that is if the
associated groupoid is realizable, then ${\mathcal{R}}$ is a p.m.p. groupoid
for the $\sigma$-algebra generated by $\\{(x,\varphi(x)):x\in A\\}$ where
$\varphi$ is a $\Phi$-word and $A\subset\operatorname{dom}(\varphi)$
measurable (see Section 2.6 and 2.8).

###  2.2 Full pseudogroup

From now on, let us fix a p.m.p. groupoid $\mathcal{G}$ over $(X,\mu)$.

######  Definition 2.8.

A _measurable bisection_ of a p.m.p. groupoid $\mathcal{G}$ is a measurable
subset $\varphi\subset\mathcal{G}$ such that the restriction of $s$ and $t$ to
$\varphi$ are injective. These restrictions are partial isomorphisms (Remark
2.2). Thus every bisection $\varphi$ delivers an associated partial
isomorphism $\hat{\varphi}:=t\circ(s\bigr{|}_{\varphi})^{-1}$ of $(X,\mu)$.

######  Lemma 2.9.

If $\varphi$ and $\psi$ are bisections of the p.m.p. groupoid $\mathcal{G}$,
then the product $\varphi\psi:=\\{gh:g\in\varphi,h\in\psi,s(g)=t(h)\\}$ is a
bisection.

###### Proof.

We have to prove that $\varphi\psi$ is a measurable subset of $\mathcal{G}$.
By Remark 2.2 it is enough to show that $(s\bigr{|}_{\varphi\psi})^{-1}$ is
measurable. First observe that a point $x\in X$ belongs to $s(\varphi\psi)$ if
and only if there is $g\in\varphi$, $h\in\psi$ such that $s(h)=x$ and
$s(g)=t(h)=\hat{\psi}(x)$. So
$s(\varphi\psi)=s(\psi)\cap\hat{\psi}^{-1}(s(\varphi))$ is measurable.
Moreover
$(s\bigr{|}_{\varphi\psi})^{-1}(x)=(s\bigr{|}_{\varphi})^{-1}(\hat{\psi}(x))(s\bigr{|}_{\psi})^{-1}(x)$
is measurable, as the composition of the map
$x\mapsto((s\bigr{|}_{\varphi})^{-1}(\hat{\psi}(x)),(s\bigr{|}_{\psi})^{-1}(x))\in(\mathcal{G},s)\ast(\mathcal{G},t)$,
which is measurable by definition of fibred products, and of the product map
$(\mathcal{G},s)\ast(\mathcal{G},t)\to\mathcal{G}$ which is measurable by
assumption. ∎

We observe that there is a countable family $\\{\varphi_{i}\\}_{i}$ of
measurable bisections which covers $\mathcal{G}$ in the sense
$\cup_{i}\varphi_{i}=\mathcal{G}$. Indeed, the assumption that
$(\mathcal{G},s)$ (respectively $(\mathcal{G},t)$) is a fibred space over $X$
provides countable families $\\{\varphi_{i}^{s}\\}_{i}$
and$\\{\varphi_{j}^{t}\\}_{j}$ of measurable subsets which both cover
$\mathcal{G}$ and on which $s$ (resp. $t$) is injective. The family
$\\{\varphi_{i}^{s}\cap\varphi_{j}^{t}\\}_{i,j}$ does the job. The next remark
thus follows:

######  Remark 2.10.

The space of units of $X\subset\mathcal{G}$ is a measurable subset of
$\mathcal{G}$ (since $X=\cup_{i}\varphi_{i}^{-1}\varphi_{i}$), and the
measures $\mu$ and $\widetilde{\mu}$ coincide on $X$. For every bisection
$\varphi$, its unit set $\varphi\cap X$ is thus measurable (contrarily to the
isotropy set $\mathrm{Fix}(\varphi)=\\{g\in\varphi:s(g)=t(g)\\}$, see Example
2.7). Similarly the product $(g,h)\in(\mathcal{G},s)\ast(\mathcal{G},t)\mapsto
gh\in\mathcal{G}$ maps measurable subsets to measurable subsets.

The _full pseudogroup_ of $\mathcal{G}$, denoted $[[\mathcal{G}]]$, is the set
of measurable bisections of $\mathcal{G}$ modulo null-sets. The full
pseudogroup admits a natural metric, the $L_{1}$ distance, defined by
$d(\varphi,\psi):=\widetilde{\mu}(\varphi\Delta\psi)$ and a _trace_ , the
measure of the fixed points, which can be defined by the formula
$\tau(\varphi):=\widetilde{\mu}(X\cap\varphi)$. It is easy to observe that
this trace is the restriction of the trace of the associated $II_{1}$ von
Neumann algebra, see Section 2.3.

It can be endowed with the following operations:

  * •

for $\varphi,\psi\in[[\mathcal{G}]]$, their product is
$\varphi\psi=\\{gh:g\in\psi,h\in\psi,s(g)=t(h)\\}$;

  * •

for $\varphi\in[[\mathcal{G}]]$, its inverse is
$\varphi^{-1}=\\{g^{-1}:g\in\varphi\\}$;

  * •

for $\varphi,\psi\in[[\mathcal{G}]]$ their intersection is $\varphi\cap\psi$;

  * •

if $\varphi,\psi\in[[\mathcal{G}]]$ are such that $s(\varphi)\cap
s(\psi)=\emptyset$ and $t(\varphi)\cap t(\psi)=\emptyset$, then the union or
join $\varphi\vee\psi$ is the bisection $\varphi\cup\psi$.

Moreover the following relations are satisfied

  * •

the product is associative;

  * •

all the idempotents ($\varphi\varphi=\varphi$) commute;

  * •

for every $\varphi\in[[\mathcal{G}]]$ we have
$\varphi\varphi^{-1}\varphi=\varphi$.

######  Definition 2.11.

A measurable bisection $\varphi$ of a p.m.p. groupoid $\mathcal{G}$ is

  1. 1.

_measurably isotropic_ if for every measurable subset $U\subset s(\varphi)$ we
have $\mu(\hat{\varphi}(U)\Delta U)=0$;

  2. 2.

_totally isotropic_ : if $s(g)=t(g)$ for $\tilde{\mu}$-almost every
$g\in{\varphi}$;

  3. 3.

_measurably free_ if for every measurable subset $A\subset s(\varphi)$ of
positive measure there exists a measurable subset $B\subset A$ such that
$\mu(\hat{\varphi}(B)\Delta B)\not=0$;

  4. 4.

_totally free_ if $s(g)\neq t(g)$ for $\tilde{\mu}$-almost every
$g\in{\varphi}$.

In a standard Borel probability space, there is no difference between totally
and measurably isotropic (resp. free). Example 2.7 illustrates these notions.

######  Proposition 2.12.

Every bisection $\varphi$ of a p.m.p. groupoid $\mathcal{G}$ admits a
measurable decomposition $\varphi=\mathrm{Fix}_{\mathscr{B}}(\varphi)\sqcup
M_{F}(\varphi)$ (unique up to a null set) such that

  * •

$\mathrm{Fix}_{\mathscr{B}}(\varphi)$ is measurably isotropic;

  * •

$M_{F}(\varphi)$ is measurably free.

Moreover, the measurably free part $M_{F}(\varphi)$ admits a countable
measurable partition $M_{F}(\varphi)=\sqcup_{i}A_{i}$ (up to a null set) such
that $\mu(s(A_{i})\cap t(A_{i}))=0$ and
$\widetilde{\mu}(\cup_{i=1}^{n}A_{i})\geq(1-(2/3)^{n})\widetilde{\mu}(M_{F}(\varphi))$.

Observe that the isotropy set (or fixed-point set)
$\mathrm{Fix}(\varphi):=\\{g\in\varphi:s(g)=t(g)\\}$ is a possibly non-
measurable subset of $\mathrm{Fix}_{\mathscr{B}}(\varphi)$ (see Example 2.7).

###### Proof.

Define $a\leq 1$ as the supremum of $\widetilde{\mu}(\cup_{i}B_{i})$ over all
countable union of measurable subsets of $\varphi$ satisfying
$\widetilde{\mu}(s(B_{i})\cap t(B_{i}))=0$. Observe that $a$ is a maximum: if
for every $n$ we have a collection $\\{C_{j}^{n}\\}_{j}$ satisfying
$\widetilde{\mu}(\cup_{j}C_{j}^{n})\geq a-1/n$, then the collection
$\\{B_{i}\\}_{i}=\\{C_{j}^{n}\\}_{j,n}$ satisfies
$\widetilde{\mu}(\cup_{i}B_{i})=a$. Pick such a family $\\{B_{i}\\}_{i}$
attaining the maximum and set $F:=\varphi\setminus\cup_{i}B_{i}$.

$F$ is measurably isotropic for otherwise $F$ would contain a measurable
subset $V$ such that $\widetilde{\mu}(s(V)\Delta t(V))\not=0$, and the subset
$W=V\cap s^{-1}(s(V)\setminus t(V))$ is non null and satisfies $\mu(s(W)\cap
t(W))=0$, thus contradicting the maximality of
$\widetilde{\mu}(\cup_{i}B_{i})$. Set
$\mathrm{Fix}_{\mathscr{B}}(\varphi):=F$.

By taking restrictions of each $B_{i}$ one can assume that the family
$\\{B_{i}\\}_{i}$ is a partition of
$M_{F}(\varphi):=\varphi\setminus\mathrm{Fix}_{\mathscr{B}}(\varphi)$.

The next step is to modify the family so that
$\widetilde{\mu}(B_{1})\geq\frac{1}{3}\widetilde{\mu}(M_{F}(\varphi))$. This
is done, inductively on $i$. Set $B_{1}^{1}:=B_{1}$ and inductively set
$B_{i}^{\prime}=\\{g\in B_{i}:s(g)\in t(B_{1}^{i-1})\textrm{ or }t(g)\in
s(B_{1}^{i-1})\\}$ and $B_{1}^{i}:=B_{1}^{i-1}\cup(B_{i}\setminus
B_{i}^{\prime})$ for $i>1$. Set $B_{1}^{\prime}=\cup_{i}B_{1}^{i}$ and observe
that $\\{B_{i}^{\prime}\\}_{i}$ is again a partition of $M_{F}(\varphi)$
satisfying $\mu(s(B_{i}^{\prime})\cap t(B_{i}^{\prime}))=0$. Moreover,
$M_{F}(\varphi)\setminus B_{1}^{\prime}$ is contained in the union
$(s\bigr{|}_{\varphi})^{-1}\circ
t(B^{\prime}_{i})\cup(t\bigr{|}_{\varphi})^{-1}\circ s(B^{\prime}_{i})$ so
that
$\widetilde{\mu}(B_{1}^{\prime})\geq\frac{1}{3}\widetilde{\mu}(M_{F}(\varphi))$.

By repeating the preceding argument inductively for all $B_{i}$, we obtain in
the end that
$\widetilde{\mu}(B_{i})\geq\frac{1}{3}\widetilde{\mu}(M_{F}(\varphi)\setminus\cup_{j<i}B_{j})$,
which finishes the proof.

The uniqueness up to a null set is clear, as a bisection which is
simultaneously measurably isotropic and measurably free has measure $0$. ∎

###  2.3 Regular representations and von Neumann algebras of a groupoid

Let $\mathcal{G}$ be a p.m.p. groupoid over $(X,\mu)$.

If $\varphi\in[[\mathcal{G}]]$, define a partial isometry $\lambda(\varphi)$
(the left-regular representation of $[[\mathcal{G}]]$) on
$L^{2}(\mathcal{G},\widetilde{\mu})$ as follows. If $f\in
L^{2}(\mathcal{G},\widetilde{\mu})$ one defines $\lambda(\varphi)f(g):=0$ if
$t(g)\notin t(\varphi)$ and $\lambda(\varphi)f(g):=f(h^{-1}g)$ otherwise,
where $h$ is the unique element of $\varphi$ such that $t(h)=t(g)$. For
example, for $\psi\in[[\mathcal{G}]]$,
$\lambda(\varphi)\chi_{\psi}=\chi_{\varphi\psi}$. The left von Neumann algebra
of $\mathcal{G}$ is
${\mathcal{L}}(\mathcal{G})=\lambda([[\mathcal{G}]])^{\prime\prime}$. It
carries a normal faithful trace $\tau=\langle\cdot\chi_{X},\chi_{X}\rangle$.
The von Neumann subalgebra generated by the idempotents of $[[\mathcal{G}]]$
(the indicator functions of measurable subsets of $X$) is isomorphic to
$L^{\infty}(X,\mu)$. Its commutant is the right von Neumann algebra
${\mathcal{L}}^{\prime}(\mathcal{G})$, generated by the right-regular
representation $\rho$ which is characterized by
$\rho(\varphi)\chi_{\psi}=\chi_{\psi\varphi^{-1}}$.

###  2.4 Coarse structures and graphings

We now define a notion of coarse structure on a p.m.p. groupoid, inspired by
[Roe03].

######  Definition 2.13.

A _coarse structure_ on a p.m.p. groupoid $\mathcal{G}$ is a collection
$\mathcal{E}$ of measurable subsets of $\mathcal{G}$, called the _controlled
sets_ , which contains the units and is closed under the formation of
measurable subsets, inverses, products and finite unions. A coarse structure
is _generating_ if $\mathcal{G}$ is the union of all controlled sets. A coarse
structure on $\mathcal{G}$ has _bounded geometry_ if for every controlled set
$E$, the measurable function $x\in X\mapsto|E\cap s^{-1}(x)|$ is essentially
bounded.

A _coarse structure_ on a sequence $(\mathcal{G}_{n})_{n}$ of p.m.p. groupoids
over $X_{n}$ is a collection of sequences $(E_{n})_{n}$ of measurable subsets
$E_{n}\subset\mathcal{G}_{n}$, called the _controlled sequences_ , which is
closed under the same operations. This means that if the sequences
$(E_{n})_{n}$ and $(F_{n})_{n}$ are controlled, then $(E_{n}^{-1})_{n}$,
$(E_{n}F_{n})_{n}$ and $(E_{n}\cup F_{n})_{n}$ are also controlled. A coarse
structure $\mathcal{E}$ on $(\mathcal{G}_{n})_{n}$ has _bounded geometry_ if
for every $(E_{n})\in\mathcal{E}$, the measurable function
$n\in\mathbb{N},x\in X_{n}\mapsto|E_{n}\cap s^{-1}(x)|$ is essentially
bounded.

Note that, if $(\lambda_{n})_{n}$ is a probability measure on $\mathbb{N}$
with full support, a coarse structure on a sequence $(\mathcal{G}_{n})$ is the
same notion as a coarse structure on the p.m.p. groupoid
$\cup_{n}\mathcal{G}_{n}$ over the disjoint union $\cup_{n}X_{n}$ equipped
with the probability measure $\sum_{n}\lambda_{n}\mu_{n}$. Moreover the
notions of bounded geometry agree.

We will almost always assume that the coarse structures are _countably
generated_ , i.e., that there is a sequence of controlled sets $E_{k}$ such
that every controlled set is contained in one of the $E_{k}$ (respectively
there is a sequence $(E_{k,n})_{n}\in\mathcal{E}$ such that every controlled
sequence $(E_{n})$ is contained in one of the $(E_{k,n})_{n}$).

######  Example 2.14.

A sequence $(G_{n})_{n}$ of finite graphs with vertex set $X_{n}$ defines a
coarse structure on the sequence of groupoids $X_{n}\times X_{n}$ (the
transitive equivalence relation on the set $X_{n}$ equipped with the uniform
probability measure), by saying that $(E_{n})_{n}$ is controlled if
$\sup_{n}\sup_{(x,y)\in E_{n}}d(x,y)<\infty$. This coarse structure has
bounded geometry if and only if the sequence $(G_{n})_{n}$ has (uniformly)
bounded degree.

The main source of coarse structures on a p.m.p. groupoid are graphings, that
we now define.

######  Definition 2.15 (Graphings).

Let $\mathcal{G}$ be a p.m.p. groupoid over the probability space $(X,\mu)$. A
_graphing_ of $\mathcal{G}$ is an at most countable ordered collection of
bisections $\Phi=(\varphi_{i})_{i}$ indexed by $i\in\mathbb{N}$ or
$i\in\\{1,\dots,N\\}$ for an integer $N$. A graphing is _generating_ if the
smallest groupoid which contains all the bisections $\varphi_{i}$ is
$\mathcal{G}$ itself. By a _p.m.p. graphed groupoid_ $(\mathcal{G},\Phi)$ we
mean a p.m.p. groupoid $\mathcal{G}$ for which a generating graphing $\Phi$
has been prescribed.

The _size_ of $\Phi$, denoted by $|\Phi|$, is the number of bisections which
compose $\Phi$. A _$\Phi$ -word of length $k$_ is a product of $k$ elements of
$\Phi$ and $\Phi^{-1}$. The set of $\Phi$-words of length at most $k$ is
denoted by $\Phi^{k}$. We will also denote by $\overline{\Phi}$ the subset of
$\mathcal{G}$ composed of all elements of elements in $\Phi$, that is
$\overline{\Phi}=\\{g\in\mathcal{G}:\ g\in\varphi\in\Phi\\}$. Observe that
$\overline{\Phi^{k}}=\overline{\Phi}^{k}$. A generating graphing
$\Phi=(\varphi_{i})_{i}$ of a p.m.p. groupoid $\mathcal{G}$ induces also a
_length_ as follows:

$\ell_{\Phi}:\mathcal{G}\rightarrow\mathbb{N},\
g\mapsto\min\left\\{k\in\mathbb{N}:g\in\overline{\\{\varphi_{1},\ldots,\varphi_{k}\\}}^{k}\right\\}.$
(8)

The empty word (the $\Phi$-word of length $0$) is the bisection $X$ (the space
of units). The length of every unit is $0$. We will denote by
$B_{\ell_{\Phi}}(L)$ the ball of length $L$:
$B_{\ell_{\Phi}}(L):=\\{g\in\mathcal{G}:\ell_{\Phi}(g)\leq L\\}$.

######  Remark 2.16 (Coarse structures vs graphings).

If $(\mathcal{G},\Phi)$ is a graphed p.m.p. groupoid, then the collection of
measurable subsets on which $\ell_{\Phi}$ is bounded is a countably generated
coarse structure with bounded geometry: the _coarse structure associated to
$\Phi$_. Similarly, if $(\mathcal{G}_{n},\Phi_{n})$ is a sequence of graphed
groupoids, then the collection of all the sequences
$(E_{n}\subset\mathcal{G}_{n})_{n}$ satisfying $\sup_{n\in\mathbb{N},g_{n}\in
E_{n}}\ell_{\Phi_{n}}(g_{n})<\infty$ is a countably generated coarse structure
with bounded geometry on $(\mathcal{G}_{n})$.

The precise choice of the length function (8) is not important, we could as
well have chosen a sequence $(a_{i})_{i}$ of positive real numbers tending to
$+\infty$, and define instead the shortest-path length obtained by assigning
to every $h\in\varphi_{i}$ the length $a_{i}$:

$g\mapsto\min\left\\{\sum_{j=1}^{k}a_{i_{j}}:k\in\mathbb{N},i\in\mathbb{N}^{k},\varepsilon\in\\{-1,1\\}^{k},g\in\varphi_{i_{1}}^{\varepsilon_{1}}\varphi_{i_{2}}^{\varepsilon_{2}}\dots\varphi_{i_{k}}^{\varepsilon_{k}}\right\\}.$

Different choices for $a_{i}$ give Lipschitz equivalent lengths and they all
give the same coarse structure as (8) on (sequences of) graphed groupoids.

Conversely, the reader can check that any countably generated coarse structure
with bounded geometry on a p.m.p. groupoid is the coarse structure associated
to a graphing. Such a graphing is generating if and only if the coarse
structure is.

######  Example 2.17.

A group is naturally a groupoid, a (generating) graphing is a (generating)
subset, and when $G$ is finitely generated by $S$, $\Phi=S$ and $a_{i}=1$ for
the elements of $S$, then the above length is the usual word length. On the
contrary, when the generating set $S$ is infinite, then $\ell_{\Phi}$ is not
bounded on $S$ and thus $S$ it is not controlled for the coarse structure
considered in Remark 2.16.

###  2.5 Actions

######  Definition 2.18.

A (measurable) _action_ $\theta$ of a p.m.p. groupoid $\mathcal{G}$ on the
fibred space $(\mathcal{F},\pi)$ (both over the probability space $(X,\mu)$)
is a measurable map
$\theta:(\mathcal{G},s)\ast(\mathcal{F},\pi)\to\mathcal{F},(g,f)\mapsto\theta_{g}f$
such that:

  * •

$\theta_{g}$ is bijection from $\pi^{-1}(s(g))$ to $\pi^{-1}(t(g))$,

  * •

$\theta_{gh}=\theta_{g}\theta_{h}$ whenever $t(h)=s(g)$.

Besides its standard fibred structure $\pi_{s}:(g,f)\mapsto s(g)=\pi(f)$, the
fibred product $(\mathcal{G},s)\ast(\mathcal{F},\pi)$ admits also the target
fibred structure $\pi_{t}:(g,f)\mapsto t(g)$, and $\theta$ is a morphism of
fibred spaces
$\theta:((\mathcal{G},s)\ast(\mathcal{F},\pi),\pi_{t})\to(\mathcal{F},\pi)$
(i.e. $\pi_{t}(g,f)=\pi(\theta_{g}f)$). As for actions of groups, we will
often forget $\theta$ and we will write $gf$ for $\theta_{g}f$. If
$\mathcal{E}\subset\mathcal{G}$ and $\mathcal{D}\subset\mathcal{F}$ are
measurable subsets, we denote by $\mathcal{E}\mathcal{D}$ the image of the
restriction of the action to $\mathcal{E}$ and $\mathcal{D}$, i.e., the image
of
$\theta:(\mathcal{E},s)*(\mathcal{D},\pi)\rightarrow\mathcal{F},(g,f)\mapsto\theta_{g}f$.
Observe that $\mathcal{E}\mathcal{D}$ is measurable (same proof as Remark
2.10). The _$\mathcal{G}$ -orbit_ of $\mathcal{D}\subset\mathcal{F}$ is
$\mathcal{G}\mathcal{D}$. A _fundamental domain_ for the action of
$\mathcal{G}$ on $\mathcal{F}$ is a measurable subspace
$\mathcal{D}\subset\mathcal{F}$ such that the action $\theta$ induces an
isomorphism of fibred spaces
$\left(\left(\mathcal{G},s\right)*\left(\mathcal{D},\pi\right),\pi_{t}\right)\simeq(\mathcal{F},\pi)$
(for the target fibration $\pi_{t}$).

By a $\mathcal{G}$-_fibred space_ , we mean a fibred space $\mathcal{F}$
equipped with a prescribed $\mathcal{G}$-action.

######  Remark 2.19.

Let $\mathcal{G}$ be a p.m.p. groupoid and let $\mathcal{F}$ be a
$\mathcal{G}$-fibred space. Then we can define a _quotient_
$\mathcal{F}/\mathcal{G}$ to be the quotient of $\mathcal{F}$ by the
equivalence relation induced by the action of $\mathcal{G}$. If there exists a
fundamental domain $\mathcal{D}\subset\mathcal{F}$, then this quotient is
naturally isomorphic to $\mathcal{D}$. In particular it has a measurable
structure and it is itself a fibred space. Observe also that the induced
quotient map from $\mathcal{F}$ to $\mathcal{F}/\mathcal{G}$ is a measurable
map of fibred spaces.

######  Example 2.20.

A p.m.p. subgroupoid $\mathcal{H}$ of a p.m.p. groupoid $\mathcal{G}$ over $X$
is a measurable subset $\mathcal{H}\subset\mathcal{G}$ which is also a
groupoid over $X$ with respect to the restriction of the product, inverse,
source and target. Clearly $\mathcal{G}$ is a subgroupoid of itself.

If $\mathcal{H}<\mathcal{G}$ is a p.m.p. subgroupoid, then $\mathcal{H}$
carries two actions on $\mathcal{G}$: the _action by left multiplication_
$\theta^{l}$ on $(\mathcal{G},t)$ given by $\theta^{l}_{g}h=gh$, and the
_action by right multiplication_ $\theta^{r}$ on $(\mathcal{G},s)$ given by
$\theta^{r}_{g}h=hg^{-1}$. Both these actions admit a fundamental domain. Let
us show it for the action on the left. If $\\{\varphi_{i}\\}_{i}$ are
bisections such that $\cup_{i}\varphi_{i}=\mathcal{G}$, then we can define
$\mathcal{D}\subset\mathcal{G}$ inductively as follows. Set
$\mathcal{D}_{0}:=X$, the set of units of $\mathcal{G}$. Assume that
$\mathcal{D}_{k}$ is constructed for some $k\in\mathbb{N}$ such that for every
bisection $\psi$ of $\mathcal{H}$ we have that
$\psi\mathcal{D}_{k}\cap\mathcal{D}_{k}=\emptyset$. Then by hypothesis
$\mathcal{H}\mathcal{D}_{k}\subset\mathcal{G}$ is measurable and take the
first $i$ such that
$\tilde{\mu}(\varphi_{i}\setminus\mathcal{H}\mathcal{D}_{k})\neq 0$. Put
$\mathcal{D}_{k+1}:=\mathcal{D}_{k}\cup(\varphi_{i}\setminus\mathcal{H}\mathcal{D}_{k})$.
It is easy to observe now that $\mathcal{D}:=\cup_{k}\mathcal{D}_{k}$ is a
fundamental domain for the action on the left of $\mathcal{H}$ on
$\mathcal{G}$.

######  Example 2.21.

If $(\mathcal{G},\Phi)$ is a p.m.p. graphed groupoid, then we can define the
_Cayley graph_ $Cay(\mathcal{G},\Phi)$ of $\mathcal{G}$ as follows. The set of
vertices is $V:=\mathcal{G}$ which is a fibred space over $X$ with respect to
the source map and the set of edges is
$E=\sqcup_{\varphi\in\Phi}\\{(h,g):h\in\varphi,g\in\mathcal{G},t(g)=s(h)\\}$
where the endpoints of the edge $(h,x)$ are $x$ and $hx$. Then the set of
edges $E$ is also a fibred space via $(h,x)\mapsto s(x)$ and $\mathcal{G}$
acts on the graph $Cay(\mathcal{G},\Phi)$ by right multiplication. A
fundamental domain of $E$ is given by
$\sqcup_{\varphi\in\Phi}\\{(h,s(h)):h\in\varphi\\}$.

######  Example 2.22.

If $\mathcal{F}_{1},\mathcal{F}_{2}$ are $\mathcal{G}$-fibred spaces over $X$,
then so is $\mathcal{F}_{1}\ast\mathcal{F}_{2}$, for the diagonal action
$g(f_{1},f_{2})=(gf_{1},gf_{2})$.

Let us assume that the p.m.p. graphed groupoid $\mathcal{G}$ acts on the
fibred space $\mathcal{F}$ and let $\mathcal{D}\subset\mathcal{F}$ be a
fundamental domain. Similarly to (8), we can define a length function
$\ell_{\Phi,\mathcal{D}}$ on $\mathcal{F}$ by the formula

$\ell_{\Phi,\mathcal{D}}:\mathcal{F}\rightarrow\mathbb{N},\
f\mapsto\min\left\\{k\in\mathbb{N}:f\in\overline{\\{\varphi_{1},\dots,\varphi_{k}\\}}^{k}\mathcal{D}\right\\}.$
(9)

By definition we have $\ell_{\Phi}=\ell_{\Phi,X}$ both for the left and right
actions of $\mathcal{G}$ on itself.

More generally, if $\mathcal{E}$ is a coarse structure on a p.m.p. groupoid
$\mathcal{G}$ acting on a fibred space $\mathcal{F}$ with a fundamental domain
$\mathcal{D}$, the collection
$\mathcal{E}_{*}\mathcal{D}:=\\{E\mathcal{D}:E\in\mathcal{E}\\}$ of measurable
subsets of $\mathcal{F}$ defines a notion of bounded sets in $\mathcal{F}$.
Similarly, if $\mathcal{G}_{n}$ acts on $\mathcal{F}_{n}$ with a fundamental
domain $\mathcal{D}_{n}$, and $\mathcal{E}$ is a coarse structure on
$(\mathcal{G}_{n})_{n}$, then
$\mathcal{E}_{*}(\mathcal{D}_{n}):=\\{(E_{n}\mathcal{D}_{n})_{n}:(E_{n})_{n}\in\mathcal{E}\\}$
defines a notion of bounded measurable sets on the disjoint unions
$\cup_{n}\mathcal{F}_{n}$. When $\mathcal{E}$ is given by a (sequence of)
graphing(s), then these notions of boundedness coincide with the boundedness
according to the length (9).

###  2.6 Presentation of p.m.p. groupoids

The notion of presentation of groupoids has been introduced in [Alv08].

######  Definition 2.23.

A _homomorphism_ of p.m.p. groupoids $T:\mathcal{G}\rightarrow\mathcal{H}$ is
a measurable map commuting with source, target, products and inversion. In
particular, it sends the units of $\mathcal{G}$ to the units of $\mathcal{H}$,
since $X=\\{g\in\mathcal{G}:s(g)=t(g),g^{2}=g\\}$. We say that a homomorphism
is _p.m.p._ if the map between the unit spaces is measure preserving.

A homomorphism of groupoids is _units-preserving_ if the induced map at the
level of units is an isomorphism of probability spaces. In particular a units-
preserving homomorphism is always a p.m.p. homomorphism.

A groupoid $\mathcal{N}$ is _totally isotropic_ if every element
$n\in\mathcal{N}$ is isotropic: $s(n)=t(n)$. As an example every groupoid
$\mathcal{G}$ admits the totally isotropic subgroupoid consisting of all its
isotropic elements. Observe however that such a subgroupoid is not p.m.p. in
general, see Example 2.7. However it is the case whenever $\mathcal{G}$ is
realizable, see Definition 2.41.

A totally isotropic subgroupoid $\mathcal{N}<\mathcal{G}$ is _normal_ if for
every $g\in\mathcal{G}$ and $n\in\mathcal{N}_{s(g)}$, we have
$gng^{-1}\in\mathcal{N}_{t(g)}$. As for groups, normal subgroupoids are
designed for forming quotients.

######  Proposition 2.24.

Let $\mathcal{G}$ be a p.m.p. groupoid and let $\mathcal{N}<\mathcal{G}$ be a
totally isotropic normal p.m.p. subgroupoid. Then the quotient
$\mathcal{G}/\mathcal{N}$ is a p.m.p. groupoid and the quotient map
$Q:\mathcal{G}\rightarrow\mathcal{G}/\mathcal{N}$ is a p.m.p. and units-
preserving homomorphism of p.m.p. groupoids.

###### Proof.

We have already observed in Example 2.20 that if $\mathcal{N}<\mathcal{G}$ is
a p.m.p. subgroupoid, then the left action of $\mathcal{N}$ on $\mathcal{G}$
admits a fundamental domain $\mathcal{D}\subset\mathcal{G}$. If $\mathcal{N}$
is a normal totally isotropic groupoid, then this fundamental domain is also a
fundamental domain for the action on the right. Indeed, since
$\mathcal{G}=\mathcal{N}\mathcal{D}$, every element $g\in\mathcal{G}$ can be
written as $g=nd=d(d^{-1}nd)$ so $\mathcal{G}=\mathcal{D}\mathcal{N}$.
Moreover if $g,g^{\prime}\in\mathcal{D}$ and $n,n^{\prime}\in\mathcal{N}$ are
such that $gn=g^{\prime}n^{\prime}$, then
$gng^{-1}g=g^{\prime}n^{\prime}g^{\prime-1}g^{\prime}$ and hence
$g=g^{\prime}$ and $gng^{-1}=g^{\prime}n^{\prime}g^{\prime-1}$ which implies
that $n=n^{\prime}$. This implies that the quotient $\mathcal{G}/\mathcal{N}$
is naturally a fibred space with respect to $s(g\mathcal{N})=s(g)$ and
$t(g\mathcal{N})=t(g)$. We can define the multiplication as usual, if
$g\mathcal{N},h\mathcal{N}\in\mathcal{G}/\mathcal{N}$ are such that
$s(g)=t(h)$, then $g\mathcal{N}h\mathcal{N}=gh\mathcal{N}$ and this is well
defined. The inverse can be defined analogously and it is a routine check that
these operations turn $\mathcal{G}/\mathcal{N}$ into a p.m.p. groupoid and $Q$
is a measurable map between p.m.p. groupoids. ∎

The argument of the proof above gives also the following.

######  Example 2.25 (Quotient fibred space action).

If $\mathcal{F}$ is a $\mathcal{G}$-fibred space and $\mathcal{N}<\mathcal{G}$
is a totally isotropic normal measurable subgroupoid, then the quotient p.m.p.
groupoid $\mathcal{G}/\mathcal{N}$ acts measurably on the fibred quotient
space $\mathcal{N}\backslash\mathcal{F}$.

As an example we can consider a realizable groupoid $\mathcal{G}$ (see
Definition 2.41) and its totally isotropic subgroupoid $\mathcal{N}$
consisting of all the isotropy elements of $\mathcal{G}$. It is normal and the
quotient $\mathcal{G}/\mathcal{N}$ is the associated equivalence relation
(principal groupoid) on the unit space $X$ of $\mathcal{G}$.

If $\mathcal{N}<\mathcal{G}$ is a totally isotropic subgroupoid the smallest
normal subgroupoid of $\mathcal{G}$ containing $\mathcal{N}$ is denoted by
$\langle\mathcal{N}\rangle^{\mathcal{G}}<\mathcal{G}$. It remains totally
isotropic. Observe that there are countably many bisections
$\\{\varphi_{i}\\}_{i}$ such that $\mathcal{G}=\cup_{i}\varphi_{i}$ and
countably many bisections $\\{\psi_{j}\\}_{j}$ such that
$\mathcal{N}=\cup_{j}\psi_{j}$. Then $\langle\mathcal{N}\rangle^{\mathcal{G}}$
is the subgroupoid generated by $\\{\psi_{j}\varphi_{i}\psi_{j}^{-1}\\}_{i,j}$
and therefore we have that $\langle\mathcal{N}\rangle^{\mathcal{G}}$ is a
p.m.p. subgroupoid of $\mathcal{G}$.

Assume now that $\mathcal{G}$ and $\mathcal{H}$ are p.m.p. groupoids and let
$T:\mathcal{G}\rightarrow\mathcal{H}$ be a p.m.p. and units-preserving
homomorphism of p.m.p. groupoids. Then the set
$\mathcal{N}:=\\{g\in\mathcal{G}:\ T(g)\text{ is a unit}\\}$ is a normal
subgroupoid of $\mathcal{G}$ and moreover $\mathcal{G}/\mathcal{N}$ is
canonically isomorphic to $\mathcal{H}$.

A _generating system_ $\Psi=(\psi_{i})_{i\in I}$ is an at most countable
family of partial isomorphisms
$\psi_{i}:\operatorname{dom}(\psi_{i})\to\operatorname{tar}(\psi_{i})$ of
$(X,\mathscr{B},\mu)$. The _free p.m.p. groupoid_ $\mathcal{F}(\Psi)$ over $X$
on $\Psi$ is defined as follows:

$\mathcal{F}(\Psi):=\left\\{(w,x):w\text{ is a reduced $\Psi$-word and
}x\in\operatorname{dom}(w)\right\\}$

with the space of units associated with the empty word:
$X\simeq\\{\emptyset\\}\times X$; with source and target maps $s(w,x):=x$ and
$t(w,x):=w(x)$; with product $(w^{\prime},x^{\prime})(w,x):=(w^{\prime}w,x)$
(where $w^{\prime}w$ stands for its reduced form) whenever the condition
$x^{\prime}=s(w^{\prime},x^{\prime})=t(w,x)=w(x)$ holds and with inverse
$(w,x)^{-1}:=(w^{-1},w(x))$. Pick an enumeration $(w_{i})_{i\in\mathbb{N}}$ of
the reduced $\Psi$-words; consider the two injections
$J_{s}:\mathcal{F}(\Psi)\to X\times\mathbb{N}$, $(w_{i},x)\mapsto(x,i)$ and
$J_{t}:\mathcal{F}(\Psi)\to X\times\mathbb{N}$, $(w_{i},x)\mapsto(w_{i}(x),i)$
and observe that they induce the same measurable structure on
$\mathcal{F}(\Psi)$ (the map $(x,i)\mapsto(w_{i}(x),i)$ is a bimeasurable
bijection between the images).

######  Remark 2.26.

If $\Phi$ is a generating graphing of a p.m.p. groupoid $\mathcal{G}$, then
the associated partial isomorphisms $\hat{\Phi}:=(\hat{\varphi}_{i})_{i}$ (see
Definition 2.8) is a generating system. Moreover mapping each bisection
$\hat{\varphi}_{i}$ of $\mathcal{F}(\hat{\Phi})$ to the associated bisection
$\varphi_{i}$ of $\mathcal{G}$ extends to a p.m.p. and units-preserving
homomorphism $T_{\Phi}:\mathcal{F}(\hat{\Phi})\rightarrow\mathcal{G}$. This
map is clearly surjective and we denote its kernel by
$\mathcal{N}_{\Phi}\subset\mathcal{F}(\hat{\Phi})$: it is a normal totally
isotropic groupoid.

A _relator system_ $R=(R_{w})_{w}$ of a generating system $\Psi$ is a
collection, indexed by the reduced $\Psi$-words $w$, of measurable subsets of
their fixed points sets $R_{w}\subset\\{x\in\operatorname{dom}(w):w(x)=x\\}$.
Observe that a relator system gives rise to a totally isotropic subgroupoid of
$\mathcal{F}(\Psi)$, namely the subgroupoid generated by the restrictions
$w\bigr{|}_{R_{w}}$. We denote by $\mathcal{N}_{R}^{\Psi}$ the (totally
isotropic) normal subgroupoid in $\mathcal{F}(\Psi)$ it generates.

######  Definition 2.27.

A _presentation_ of a p.m.p. groupoid $\mathcal{G}$ is given by a
– generating system $\Psi=(\psi_{i})_{i\in I}$ on $(X,\mathscr{B},\mu)$
– a relator system $R$ of $\Psi$
– a p.m.p. and units-preserving isomorphism
$T_{\Phi}:\mathcal{F}(\Psi)/\mathcal{N}_{R}^{\Psi}\rightarrow\mathcal{G}$

###  2.7 Ultraproducts

From now on we will denote by $\mathfrak{u}$ a non-principal ultrafilter on
$\mathbb{N}$. We say that a property $P(n)$ holds $\mathfrak{u}$-almost surely
(denoted $P(n)$ for $\mathfrak{u}\textrm{-a.e. }n$) if $\\{n:P(n)\\}$ belongs
to $\mathfrak{u}$.

######  Definition 2.28.

Let $(X_{n})_{n\in\mathbb{N}}$ be a sequence of sets. The _ultraproduct_ of
the sequence $(X_{n})_{n}$ is the set

$X_{\mathfrak{u}}:=\left(\prod_{n\in\mathbb{N}}X_{n}\right)/\sim_{\mathfrak{u}}\quad\text{
where }\quad(x_{n})_{n}\sim_{\mathfrak{u}}(y_{n})_{n}\ \text{ if }\
x_{n}=y_{n}\textrm{ for }\mathfrak{u}\textrm{-a.e. }n.$

We denote by $x_{\mathfrak{u}}$ and $A_{\mathfrak{u}}$ respectively elements
and subsets of $X_{\mathfrak{u}}$. For a sequence
$(x_{n})_{n}\in\prod_{n\in\mathbb{N}}X_{n}$, we denote by
$[x_{n}]_{\mathfrak{u}}$ its class in $X_{\mathfrak{u}}$ and similarly for a
sequence of subsets $A_{n}\subset X_{n}$, we denote its class by
$[A_{n}]_{\mathfrak{u}}$ (i.e., the image of $\prod_{n}A_{n}$ in the quotient
$X_{\mathfrak{u}}$). The construction of ultraproducts of probability spaces
is due to Loeb, see [CKTD13] or [Car15] for a more modern treatment.

######  Theorem 2.29.

For every $n\in\mathbb{N}$ let $(X_{n},\mu_{n})$ be a probability space and
let $X_{\mathfrak{u}}$ be the ultraproduct of the sequence $(X_{n})_{n}$. Then
there exists a probability measure $\mu_{\mathfrak{u}}$ on $X_{\mathfrak{u}}$
such that

  1. 1.

for every sequence of measurable subsets $(A_{n}\subset X_{n})_{n}$ the set
$[A_{n}]_{\mathfrak{u}}$ is $\mu_{\mathfrak{u}}$-measurable and
$\mu_{\mathfrak{u}}([A_{n}]_{\mathfrak{u}})=\lim_{n\in\mathfrak{u}}\mu_{n}(A_{n})$,

  2. 2.

for every $\mu_{\mathfrak{u}}$-measurable subset $A_{\mathfrak{u}}\subset
X_{\mathfrak{u}}$ there exists a sequence of measurable sets $(A_{n}\subset
X_{n})_{n}$ such that
$\mu_{\mathfrak{u}}(A_{\mathfrak{u}}\Delta[A_{n}]_{\mathfrak{u}})=0$.

######  Definition 2.30.

If $\varphi_{n}$ is a partial isomorphisms of $X_{n}$ for every $n$, then the
map
$[\varphi_{n}]_{\mathfrak{u}}:[x_{n}]_{\mathfrak{u}}\mapsto[\varphi_{n}(x_{n})]_{\mathfrak{u}}$
is also a partial isomorphism from
$[\operatorname{dom}(\varphi_{n})_{\mathfrak{u}}]$ to
$[\operatorname{tar}(\varphi_{n})]_{\mathfrak{u}}$, called the _ultraproduct
partial isomorphism_.

We now define the ultraproducts of p.m.p. groupoids with a coarse structure.

######  Proposition 2.31 (Ultraproducts of coarse p.m.p. groupoids).

Let $(\mathcal{G}_{n})_{n}$ be a sequence of p.m.p. groupoids on $X_{n}$.

1– Let $\mathcal{E}$ be a countably generated coarse structure with bounded
geometry on $(\mathcal{G}_{n})_{n}$. There is a unique structure of p.m.p.
groupoid over $X_{\mathfrak{u}}$ on

$\mathcal{G}_{\mathfrak{u}}:=\\{(g_{n})_{n}:\exists(E_{n})_{n}\in\mathcal{E},g_{n}\in
E_{n}\\}/\sim_{\mathfrak{u}}$

for the groupoid operations
$s([g_{n}]_{\mathfrak{u}}):=[s(g_{n})]_{\mathfrak{u}}$,
$t([g_{n}]_{\mathfrak{u}}):=[t(g_{n})]_{\mathfrak{u}}$,
$[g_{n}]_{\mathfrak{u}}[h_{n}]_{\mathfrak{u}}:=[g_{n}h_{n}]_{\mathfrak{u}}$
and $[g_{n}]_{\mathfrak{u}}^{-1}:=[g_{n}^{-1}]_{\mathfrak{u}}$ and for which
$\mathcal{E}_{\mathfrak{u}}:=\\{[E_{n}]_{\mathfrak{u}}:(E_{n})_{n}\in\mathcal{E}\\}$
is a countably generated and generating coarse structure with bounded
geometry.

2– If $\mathcal{E}$ is the coarse structure associated to a sequence of
graphings $\Phi_{n}=(\varphi_{n}^{i})_{i}$, then

$\mathcal{G}_{\mathfrak{u}}=\\{(g_{n})_{n}:\sup_{n}\ell_{\Phi_{n}}(g_{n})<\infty\\}/\sim_{\mathfrak{u}}$

and $\mathcal{E}_{\mathfrak{u}}$ is the coarse structure associated to the
graphing $\Phi_{\mathfrak{u}}=([\varphi_{n}^{i}]_{\mathfrak{u}})_{i}$ and this
graphing is generating.

######  Definition 2.32.

The p.m.p. groupoid $\mathcal{G}_{\mathfrak{u}}$ defined in Proposition 2.31
is called the _ultraproduct groupoid_ of the coarse sequence
$((\mathcal{G}_{n})_{n},\mathcal{E})$.

In the simplest case of bounded degree graphs, we recover the ultraproduct
graphs considered for example in [HLS14, Section 9]:

######  Example 2.33 (Ultraproduct of bounded degree graphs).

Let $(G_{n}=(X_{n},\mathrm{Edg}_{n}))_{n}$ be a sequence of bounded degree
finite graphs. Then the ultraproduct of the groupoids $X_{n}\times X_{n}$ for
the coarse structure considered in Example 2.14 is the p.m.p. equivalence
relation ${\mathcal{R}}_{\mathfrak{u}}$ on $X_{\mathfrak{u}}$ given by
$[x_{n}]_{\mathfrak{u}}\sim[y_{n}]_{\mathfrak{u}}$ if and only if
$\lim_{\mathfrak{u}}d(x_{n},y_{n})<\infty$. Moreover, the coarse structure on
the ultraproduct is generated by

$\mathrm{Edg}_{\mathfrak{u}}:=[\mathrm{Edg}_{n}]_{\mathfrak{u}}=\\{([x_{n}]_{\mathfrak{u}},[y_{n}]_{\mathfrak{u}}):\lim_{\mathfrak{u}}d(x_{n},y_{n})=1\\}.$

###### Proof of Proposition 2.31.

The fact that the operations are well defined and turn
$\mathcal{G}_{\mathfrak{u}}$ into a groupoid over $X_{\mathfrak{u}}$ is clear.
The issue is to define the measure space structure on
$\mathcal{G}_{\mathfrak{u}}$. For every $(E_{n})_{n}\in\mathcal{E}$, we can
consider the ultraproduct measure space
$[E_{n}]_{\mathfrak{u}}\subset\mathcal{G}_{\mathfrak{u}}$. By our assumption
of bounded geometry, it is a finite height fibred space over
$X_{\mathfrak{u}}$, for both maps $s$ and $t$. Moreover if
$(F_{n})_{n}\in\mathcal{E}$ contains $(E_{n})_{n}$, then this measure space
structure on $[E_{n}]_{\mathfrak{u}}$ coincides with the restriction of the
measure space structure on $[F_{n}]_{\mathfrak{u}}$. Taking a sequence
$((E_{k,n})_{n})_{k}\subset\mathcal{E}$ generating $\mathcal{E}$, we obtain a
$\sigma$-algebra and a measure on $\mathcal{G}_{\mathfrak{u}}$ for which $s$
and $t$ define fibred space structures, and for which every
$(E_{n})_{n}\in\mathcal{E}$ defines a measurable subset
$[E_{n}]_{\mathfrak{u}}$ on $\mathcal{G}_{\mathfrak{u}}$. The fact that
$\\{[E_{n}]_{\mathfrak{u}}:(E_{n})\in\mathcal{E}\\}$ is a coarse structure is
immediate from (2) in Theorem 2.29. The measurability of the inverse and
product follow from the measurability of these operations on $\mathcal{G}_{n}$
and the fact that $\mathcal{E}$ is stable under these operations. This coarse
structure is generating by definition of $\mathcal{G}_{\mathfrak{u}}$, and is
countably generated because $\mathcal{E}$ was assumed to be countably
generated.

The verification that $\mathcal{E}_{\mathfrak{u}}$ coincides with the coarse
structure defined by $\Phi_{\mathfrak{u}}$ is routine. ∎

######  Definition 2.34.

Similarly to Definition 2.30 we can define the notion of ultraproduct of
bisections. Assume that $(E_{n})_{n}\in\mathcal{E}$ and for every $n$ take a
bisection $\varphi_{n}$ contained in $E_{n}$, then
$[\varphi_{n}]_{\mathfrak{u}}\subset\mathcal{G}_{\mathfrak{u}}$ is a
bisection.

######  Corollary 2.35.

If two sequences of generating graphings $\Phi_{n}$ and $\Psi_{n}$ of p.m.p.
groupoids $\mathcal{G}_{n}$ are _$\mathfrak{u}$ -coarsely equivalent_ (i.e.,
for every sequence $g_{n}\in\mathcal{G}_{n}$,
$\lim_{\mathfrak{u}}\ell_{\Phi_{n}}(g_{n})<\infty$ if and only if
$\lim_{\mathfrak{u}}\ell_{\Psi_{n}}(g_{n})<\infty$), then the ultraproduct
graphings $\Phi_{\mathfrak{u}}$ and $\Psi_{\mathfrak{u}}$ define the same
groupoid with coarse structure.

###### Proof.

The assumption of coarse equivalence means that for every $M$, there is
$M^{\prime}$ such that, for $\mathfrak{u}\textrm{-a.e. }n$,
$\ell_{\Phi_{n}}(g)\leq M\implies\ell_{\Psi_{n}}(g)\leq M^{\prime}$, and
conversely $\ell_{\Psi_{n}}(g)\leq M\implies\ell_{\Phi_{n}}(g)\leq
M^{\prime}$. Indeed, if for every $n$, we define
$M_{n}=\sup\\{\ell_{\Psi_{n}}(g):g\in\mathcal{G}_{n},\ell_{\Phi_{n}}(g)\leq
M\\}$, and pick $g_{n}\in\mathcal{G}_{n}$ with $\ell_{\Phi_{n}}(g_{n})\leq M$
and $\ell_{\Psi_{n}}(g)=M_{n}$ if $M_{n}<\infty$ and $\ell_{\Psi_{n}}(g)\geq
n$ otherwise, we obtain that $M^{\prime}:=\lim_{\mathfrak{u}}M_{n}<\infty$.
This allows to identify the groupoids

$\\{(g_{n})_{n}:\sup_{n}\ell_{\Phi_{n}}(g_{n})<\infty\\}/\sim_{\mathfrak{u}}$

and

$\\{(g_{n})_{n}:\sup_{n}\ell_{\Psi_{n}}(g_{n})<\infty\\}/\sim_{\mathfrak{u}},$

and Proposition 2.31 shows that this identification is measurable and measure
preserving. ∎

######  Remark 2.36.

In Corollary 2.35, it is crucial that the two graphings are
$\mathfrak{u}$-coarsely equivalent: sequences of different graphings can give
rise to rather unrelated limits. For instance, the transitive equivalence
relation on a finite set has many different generating graphings (all
connected graphs with this finite set as vertex set). However their
ultraproducts can be completely different according, for instance, to whether
one takes a sequence of expanders, in which case the ultraproduct equivalence
relation is strongly ergodic, or a sequence of Hamiltonian cycles in which
case the ultraproduct is not ergodic.

######  Remark 2.37.

The structure of a graphed groupoid does not fundamentally depend on the order
of the bisections of the graphing. However, the order becomes crucial when we
consider a sequence of $\Phi_{n}=(\varphi_{i})_{i\in I_{n}}$ and its
ultraproduct. But when the size $(|\Phi_{n}|)_{n}$ is bounded, i.e., the
$I_{n}$ are contained in a finite subset $J\subset\mathbb{N}$, then a sequence
$(\sigma_{n})_{n}$ of permutations of $J$ is indeed essentially constant under
the ultrafilter $\mathfrak{u}$ (indeed the underlying coarse structure is
canonical). It follows in this case that the ultraproduct groupoid does not
depend on the order and the ultraproduct graphing is unique up to a single
permutation of the indices. The same holds when instead of assuming $J$
finite, we assume that the permutations $\sigma_{n}$ converges to a
_permutation_ of $\mathbb{N}$, i.e., if for every $j$,
$\lim_{\mathfrak{u}}\sigma_{n}(j)<\infty$ and
$\lim_{\mathfrak{u}}\sigma_{n}^{-1}(j)<\infty$ (for example if
$\sup_{n}\sigma_{n}(j)<\infty$ and $\sup_{n}\sigma_{n}^{-1}(j)<\infty$). This
is a particular case of Corollary 2.35.

We can now give a similar construction of ultraproduct for
$\mathcal{G}$-fibred spaces.

######  Definition 2.38.

Let us assume that for every $n\in\mathbb{N}$ the p.m.p. groupoid
$\mathcal{G}_{n}$ acts on the fibred spaces $(\mathcal{F}_{n},\pi_{n})$ and
let $\mathcal{D}_{n}\subset\mathcal{F}_{n}$ be a fundamental domain such that
the sequence $n\mapsto H(\mathcal{D}_{n})$ is bounded111Recall that
$H(\mathcal{D}_{n})$ is the height of $\mathcal{D}_{n}$: the essential
supremum of the function $x\mapsto|\pi_{n}^{-1}(x)\cap\mathcal{D}_{n}|$.. Let
$\mathcal{E}$ be a countably generated coarse structure with bounded geometry
on $(\mathcal{G}_{n})_{n}$, for example the coarse structure coming from a
sequence of graphings. Set

$\displaystyle\mathcal{F}_{\mathfrak{u}}:=\left\\{(f_{n})_{n}\in\prod\mathcal{F}_{n}:\
\exists(E_{n})_{n}\in\mathcal{E}\textrm{ such that }f_{n}\in
E_{n}D_{n}\textrm{ for every }n\right\\}/\sim_{\mathfrak{u}}$
$\displaystyle(f_{n})_{n}\sim_{\mathfrak{u}}(f^{\prime}_{n})_{n}\ \text{ if }\
f_{n}=f^{\prime}_{n}\textrm{ for }\mathfrak{u}\textrm{-a.e. }n.$

We also set
$\pi_{\mathfrak{u}}([f_{n}]_{\mathfrak{u}}):=[\pi_{n}(f_{n})]_{\mathfrak{u}}$.
Observe that for every $(E_{n})_{n}\in\mathcal{E}$, the fibred spaces
$E_{n}\mathcal{D}_{n}$ over $\pi_{n}(E_{n}\mathcal{D}_{n})$ have bounded
height, and therefore their ultraproduct
$[E_{n}\mathcal{D}_{n}]_{\mathfrak{u}}$ is a fibred space over
$[\pi_{n}(E_{n}\mathcal{D}_{n})]_{\mathfrak{u}}$. So as for the groupoids we
equip $\mathcal{F}_{\mathfrak{u}}$ with the inductive limit measure space
structure which turns $(\mathcal{F}_{\mathfrak{u}},\pi_{\mathfrak{u}})$ into a
fibred space, and on which the groupoid $\mathcal{G}_{\mathfrak{u}}$ acts by
the formula
$[g_{n}]_{\mathfrak{u}}[f_{n}]_{\mathfrak{u}}:=[g_{n}f_{n}]_{\mathfrak{u}}$.
Observe that a fundamental domain is given by $\mathcal{D}_{\mathfrak{u}}$,
the ultraproduct of the sequence $(\mathcal{D}_{n})_{n}$, whose height is
$\lim_{\mathfrak{u}}H(\mathcal{D}_{n})$.

Let us observe that the definition of the ultraproduct does depend on the
sequence of fundamental domains. One can also check that if $\mathcal{F}_{n}$
is the Cayley graph of $\mathcal{G}_{n}$ with respect to $\Phi_{n}$ as
explained in Example 2.21, then the ultraproduct of these fibred spaces is the
Cayley graph of $\mathcal{G}_{\mathfrak{u}}$ with respect to
$\Phi_{\mathfrak{u}}$.

Consider the setting of Proposition 2.31. If
$\varphi_{n}\in[[\mathcal{G}_{n}]]$ is a controlled sequence of measurable
bisections, on the one hand by Proposition 2.31 we can regard
$[\varphi_{n}]_{\mathfrak{u}}$ as an element of
$[[\mathcal{G}_{\mathfrak{u}}]]$. On the other hand since the full
pseudogroups of the groupoids are metric spaces we can also consider the image
of $(\varphi_{n})_{n}$ in the metric ultraproduct
$\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$ of the sequence
$([[\mathcal{G}_{n}]])_{n}$. In order to avoid confusions, we will for a
moment denote by $[\varphi_{n}]_{\mathfrak{u}}^{d}$ the element of
$\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$ that represents the sequence of
elements $\varphi_{n}\in[[\mathcal{G}_{n}]]$. The following lemma follows
easily from our construction.

######  Lemma 2.39.

There is a unique isometric embedding of $[[\mathcal{G}_{\mathfrak{u}}]]$ into
$\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$ sending
$[\varphi_{n}]_{\mathfrak{u}}$ to $[\varphi_{n}]_{\mathfrak{u}}^{d}$ for every
controlled sequence of bisections. An element
$[\varphi_{n}]_{\mathfrak{u}}^{d}\in\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$
lies in the image if and only if for every $\varepsilon>0$ there exists a
sequence $\psi_{n}\subset\varphi_{n}$ with
$d(\varphi_{n},\psi_{n})\leq\varepsilon$ for $\mathfrak{u}\textrm{-a.e. }n$
and such that $(\psi_{n})_{n}$ is controlled. Moreover the embedding extends
to an embedding of the von Neumann algebra
${\mathcal{L}}(\mathcal{G}_{\mathfrak{u}})$ into the von Neumann algebra
ultraproduct $\prod_{\mathfrak{u}}{\mathcal{L}}(\mathcal{G}_{n})$.

For a sequence $(\varphi_{n})_{n}$ satisfying the condition in Lemma 2.39, we
will drop the notation $[\varphi_{n}]_{\mathfrak{u}}^{d}$ and use only
$[\varphi_{n}]_{\mathfrak{u}}$ to denote both the element of
$\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$ and the corresponding element of
$[[\mathcal{G}_{\mathfrak{u}}]]$.

We have a similar situation for $\mathcal{G}_{n}$-fibred spaces.

######  Lemma 2.40.

Let us assume that for every $n\in\mathbb{N}$ the p.m.p. graphed groupoid
$(\mathcal{G}_{n},\Phi_{n})$ acts on the fibred space
$(\mathcal{F}_{n},\pi_{n})$ and let $\mathcal{D}_{n}\subset\mathcal{F}_{n}$ be
a fundamental domain such that the sequence $n\mapsto H(\mathcal{D}_{n})$ is
bounded. For every $n$ the full pseudogroup $[[\mathcal{G}_{n}]]$ acts on the
Hilbert space $\mathrm{L}^{2}(\mathcal{F}_{n})$. Then the Hilbert space
$\mathrm{L}^{2}(\mathcal{F}_{\mathfrak{u}})$ embeds into the metric
ultraproducts $\prod_{\mathfrak{u}}\mathrm{L}^{2}(\mathcal{F}_{n})$ and if
$\varphi_{\mathfrak{u}}=[\varphi_{n}]_{\mathfrak{u}}$ is a measurable section
of $\mathcal{F}_{\mathfrak{u}}$ (where $\varphi_{n}$ are measurable sections
of $\mathcal{F}_{n}$), then the image of $\chi_{\varphi_{\mathfrak{u}}}$ is
$[\chi_{\varphi_{n}}]_{\mathfrak{u}}^{d}$. Moreover the above mentioned
embedding of $[[\mathcal{G}_{\mathfrak{u}}]]$ inside the metric ultraproduct
$\prod_{\mathfrak{u}}[[\mathcal{G}_{n}]]$ is compatible with the action and
the passage to von Neumann algebras.

###  2.8 Realizability and ultraproducts

######  Definition 2.41.

A p.m.p. groupoid $\mathcal{G}$ over the probability space
$(X,\mathscr{B},\mu)$ is said to be _realizable_ if every measurably isotropic
bisection $\varphi$ is totally isotropic (Definition 2.11).

In other words $\mathcal{G}$ is realizable if and only if every totally free
bisection is measurably free or equivalently if and only if
$\mathrm{Fix}_{\mathscr{B}}({\varphi})=\mathrm{Fix}({\varphi}):=\\{g\in\varphi:s(g)=t(g)\\}$.
The following is classic.

######  Lemma 2.42.

Every p.m.p. groupoid on a standard Borel probability space is realizable.

Realizable groupoids are the groupoids that can be studied point-wise and
those groupoids that have a free factor onto a standard Borel space, see
Theorem 3.28. Therefore, up to some extent, realizable groupoids behave like
standard one.

######  Lemma 2.43 (Realizability).

The ultraproduct $(\mathcal{G}_{\mathfrak{u}},\Phi_{\mathfrak{u}})$ of a
sequence of realizable graphed p.m.p. groupoids $(\mathcal{G}_{n},\Phi_{n})$
is itself realizable. Moreover every bisection
$\varphi_{\mathfrak{u}}=[\varphi_{n}]_{\mathfrak{u}}$ satisfies up to null
sets

$[\mathrm{Fix}_{\mathscr{B}_{n}}({\varphi_{n}})]_{\mathfrak{u}}=[\mathrm{Fix}({\varphi_{n}})]_{\mathfrak{u}}=\mathrm{Fix}(\varphi_{\mathfrak{u}})=\mathrm{Fix}_{\mathscr{B}_{\mathfrak{u}}}(\varphi_{\mathfrak{u}})$

and $[M_{F}(\varphi_{n})]_{\mathfrak{u}}=M_{F}[(\varphi_{n})]_{\mathfrak{u}}$.

###### Proof.

First observe that since the ultraproduct groupoid
$\mathcal{G}_{\mathfrak{u}}$ is generated by the bisections of the form
$[\varphi_{n}]_{\mathfrak{u}}$ it is enough to prove that for every
$\varphi_{\mathfrak{u}}=[\varphi_{n}]_{\mathfrak{u}}$ we have that
$[\mathrm{Fix}({\varphi_{n}})]_{\mathfrak{u}}=\mathrm{Fix}_{\mathscr{B}_{\mathfrak{u}}}(\varphi_{\mathfrak{u}})$.
This follows easily from Proposition 2.12. Indeed consider a decomposition
given by Proposition 2.12, that is $M_{F}(\varphi_{n})=\sqcup_{i}A_{n}^{i}$
such that
$\mu(\cup_{i=1}^{k}A_{n}^{i})\geq(1-(2/3)^{k})\mu(M_{F}(\varphi_{n}))$ and
$\mu_{n}(A_{n}^{i}\cap\varphi(A_{n}^{i}))=0$. Then clearly we get
$[M_{F}(\varphi_{n})]_{\mathfrak{u}}=\cup_{i}[A_{n}^{i}]_{\mathfrak{u}}$ and
$\mu_{\mathfrak{u}}(\varphi_{\mathfrak{u}}([A_{n}^{i}]_{\mathfrak{u}})\cap[A_{n}^{i}])=0$.
In particular
$M_{F}[(\varphi_{n})]_{\mathfrak{u}}\supset[M_{F}(\varphi_{n})]_{\mathfrak{u}}$.
Therefore
$\mathrm{Fix}_{\mathscr{B}_{\mathfrak{u}}}(\varphi_{\mathfrak{u}})\subset\operatorname{dom}(\varphi_{\mathfrak{u}})\setminus[M_{F}(\varphi_{n})]_{\mathfrak{u}}$
which by hypothesis corresponds to
$[\mathrm{Fix}({\varphi_{n}})]_{\mathfrak{u}}$. On the other hand we clearly
have that
$[\mathrm{Fix}({\varphi_{n}})]_{\mathfrak{u}}\subset\mathrm{Fix}(\varphi_{\mathfrak{u}})$
and hence
$[\mathrm{Fix}({\varphi_{n}})]_{\mathfrak{u}}=\mathrm{Fix}_{\mathscr{B}_{\mathfrak{u}}}(\varphi_{\mathfrak{u}})$
as claimed. ∎

For a p.m.p. groupoid $\mathcal{G}$ we will now denote by $\mathcal{G}^{P}$
the associated equivalence relation. As we have already remarked, if
$\mathcal{G}$ is realizable, then $\mathcal{G}^{P}$ is a p.m.p. equivalence
relation. The following is easy to prove.

######  Lemma 2.44.

Given a sequence of realizable graphed p.m.p. groupoids
$(\mathcal{G}_{n},\Phi_{n})$ we have that the ultraproduct of
$\mathcal{G}_{n}^{P}$ is $\mathcal{G}_{\mathfrak{u}}^{P}$.

In general it is not clear what should be the size of a “class” or “orbit” in
a p.m.p. groupoid, see Example 2.7. However for realizable groupoids the
situation is much more clear and we have the following. For a groupoid
$\mathcal{G}$ over the space $X$ we will set $|x|_{\mathcal{G}}:=|\\{t(g):\
s(g)=x\\}|$, the cardinality of the class of the associated equivalence
relation.

######  Lemma 2.45.

Let $(\mathcal{G}_{n},\Phi_{n})$ be a sequence of realizable graphed groupoids
such that $\lim_{\mathfrak{u}}|\Phi_{n}|$ is finite. Then for
$\mu_{\mathfrak{u}}$-almost every $[x_{n}]_{\mathfrak{u}}\in X_{\mathfrak{u}}$
we have
$|[x_{n}]_{\mathfrak{u}}|_{\mathcal{G}_{\mathfrak{u}}}=\lim_{\mathfrak{u}}|x_{n}|_{\mathcal{G}_{n}}$.
In particular if for every $k\in\mathbb{N}$ we have
$\lim_{\mathfrak{u}}\mu_{n}(\\{x\in X_{n}:|x|_{\mathcal{G}_{n}}\leq k\\})=0$,
then for $\mu_{\mathfrak{u}}$-almost every $[x_{n}]_{\mathfrak{u}}\in
X_{\mathfrak{u}}$ we have that
$|[x_{n}]_{\mathfrak{u}}|_{\mathcal{G}_{\mathfrak{u}}}$ is infinite.

###### Proof.

By the above lemma we can assume that all the $\mathcal{G}_{n}$ are
equivalence relations. For $x_{n}\in X_{n}$ set $|x_{n}|_{n,k}:=|\\{t(g):\
s(g)=x,\ g\in\overline{\Phi}_{n}^{k}\\}|$ and define similarly
$|x_{\mathfrak{u}}|_{\mathfrak{u},k}$. Remark that if for some $k$ we have
that $|x_{n}|_{n,k}=|x_{n}|_{n,k+1}$, then for every $i$ we have that
$|x_{n}|_{n,k}=|x_{n}|_{n,k+i}$. Observe also that Lemma 2.43 implies that for
$\mu_{\mathfrak{u}}$-almost every $[x_{n}]_{\mathfrak{u}}\in X_{\mathfrak{u}}$
we have
$|[x_{n}]_{\mathfrak{u}}|_{\mathfrak{u},k}=\lim_{\mathfrak{u}}|x_{n}|_{n,k}$
and therefore we can combine the two facts to obtain the desired result. ∎

##  3 Graphings, cost and combinatorial cost

The notion of cost of p.m.p. groupoids (on standard Borel spaces) has been
considered by several authors (see for instance [Ued06, Car11, AN12, Tak15]).

Let $\mathcal{G}$ be a p.m.p. groupoid. Following [Lev95], we define the
_cost_ of the graphing $\Phi=(\varphi_{i})_{i}$ of $\mathcal{G}$ as

$\mathcal{C}(\Phi):=\sum_{i}\widetilde{\mu}(\varphi_{i})$ (10)

and the _(groupoid) cost_ of the p.m.p. groupoid $\mathcal{G}$ as the infimum
of the costs of its generating graphings:

$\mathcal{C}(\mathcal{G})=\inf_{\Psi}\mathcal{C}(\Psi),$ (11)

where $\Psi$ ranges among all the generating graphings of $\mathcal{G}$. It is
the infimum of the $\widetilde{\mu}$-measures of measurable generating subsets
of $\mathcal{G}$.

######  Example 3.1.

Let $\Gamma={\bf F}_{p}\times{\bf F}_{q}$ the direct product of two free
groups ($p,q\geq 2$) and $\alpha$ be a p.m.p. $\Gamma$-actions on standard
Borel space where ${\bf F}_{p}$ acts freely and ${\bf F}_{q}$ trivially. Then
the groupoid $\mathcal{G}_{\alpha}$ of the $\Gamma$-action has
$\mathcal{C}(\mathcal{G}_{\alpha})=p$: The underlying equivalence relation
${\mathcal{R}}_{\alpha}={\mathcal{R}}_{{\bf F}_{p}}$ has cost $p$ [Gab00] and
every generating graphing of $\mathcal{G}_{\alpha}$ induces a generating
graphing of ${\mathcal{R}}_{\alpha}$. This gives
$\mathcal{C}(\mathcal{G}_{\alpha})\geq p$. Taking the graphing
$\Phi=(\varphi_{h})_{h}\cup(\varphi_{g})_{g}$ where $h$ (resp. $g$) runs over
a set of standard generators of ${\bf F}_{p}$ (resp. ${\bf F}_{q}$) with
$\varphi_{h}:=h\times X$ and $\varphi_{g}:=g\times A_{g}$ for $A_{g}$ an
arbitrarily small ${\bf F}_{p}$-complete section, one gets a generating
graphing of cost close to $p$.

When the space is not standard, replace “free action” by “measurably free”,
“trivial action” by “measurably isotropic” and make use of "the" standard
factor from Theorem 3.28.

Recall that
– $N<\Gamma$ is _q-normal_ if $\Gamma$ admits a generating set $S$ such that
$s^{-1}Ns\cap N$ is infinite for each $s\in S$
– $N<\Gamma$ is _weakly-q-normal_ if there exists a well ordered family of
intermediate subgroups $N=N_{0}<N_{1}<\cdots<N_{\eta}=\Gamma$ such that
$N^{\prime}_{j}:=\cup_{i<j}N_{i}$ is q-normal in $N_{j}$.

######  Proposition 3.2.

In the standard or realizable situation:
– If $N<\Lambda$ is _q-normal_ subgroup and $\alpha$ is a p.m.p.
$\Gamma$-action such that $N$ acts aperiodically, then
$\mathcal{C}(\mathcal{G}_{\alpha})\leq\mathcal{C}(\mathcal{G}_{\alpha\upharpoonright
N})$.
– If $N<\Gamma$ is an infinite _weakly-q-normal_ subgroup and $\alpha$ is a
free p.m.p. $\Gamma$-action, then
$\mathcal{C}({\mathcal{R}}_{\Gamma})=\mathcal{C}(\mathcal{G}_{\alpha})\leq\mathcal{C}(\mathcal{G}_{\alpha\upharpoonright
N})=\mathcal{C}({\mathcal{R}}_{N})$.

###### Proof.

Let $\Phi_{0}$ be a generating graphing of $\mathcal{G}_{\alpha\upharpoonright
N}$. If $N<\Lambda$ is q-normal, $\Lambda$ is generated by a family of $s\in
S_{\Lambda}$ such that $|s^{-1}Ns\cap N|=\infty$. Then $\Lambda$ admits a
graphing $\Phi=\Phi_{0}\cup\Phi_{\Lambda}^{*}$ where $\Phi_{\Lambda}^{*}$ has
arbitrarily small cost: a family of bisections $\Phi_{\Lambda}^{*}=(s\times
A_{s})_{s\in S_{\rho}}$ where the $A_{s}$ are complete $\left(s^{-1}Ns\cap
N\right)$-sections with $\sum_{s}\tilde{\mu}(A_{s})\leq\epsilon$ for any
prescribed $\epsilon>0$. This generates since for every $x\in X$, there are
$n_{1},n_{2}\in N$ such that $n_{1}x\in A_{s}$ and $s=n_{2}^{-1}sn_{1}$. Then
$(s,x)=(n_{2}^{-1},sn_{1}x).(s,n_{1}x).(n_{1},x)$ and
$(n_{2}^{-1},sn_{1}x),(n_{1},x)$ belong to the groupoid generated by
$\Phi_{0}$ while $(s,n_{1}x)\in s\times A_{s}$.

The proof for the weakly-q-normal case goes of course by a transfinite
induction. The induction assumption is that $N_{\rho}$ admits a graphing
$\Phi_{\rho}=\Phi_{0}\cup\Phi^{*}_{\rho}$ where $\Phi^{*}_{\rho}$ can be
chosen of arbitrarily small cost.

If $\rho=j+1$ is a successor, then $N^{\prime}_{\rho}=N_{j}$ and $N_{j}$ is
q-normal in $N_{\rho}$. Thus the groupoid of the $N_{\rho}$-action is
generated by adding a small cost graphing $\Phi^{**}_{\rho}$ to
$\Phi_{j}=\Phi_{0}\cup\Phi^{*}_{j}$.

If $\rho$ is a limit ordinal, then up to enumerating
$N^{\prime}_{\rho}=\\{\gamma_{p}\\}_{p\in\mathbb{N}}$, one selects a
increasing sequence $(N_{j_{p}})_{p}$ (where $j_{p}$ is the smallest $j$ such
that $\gamma_{1},\cdots,\gamma_{p}\in N_{j}$) and the subgroupoid generated by
the restriction of $\alpha$ to $N^{\prime}_{\rho}$ is generated by
$\Phi_{\rho}=\Phi_{0}\cup\Phi^{*}_{j_{1}}\cup\Phi^{*}_{j_{2}}\cup\cdots\cup\Phi^{*}_{j_{p}}\cup\cdots$
where $\sum_{p}\mathcal{C}(\Phi^{*}_{j_{p}})$ can be chosen arbitrarily small
by assumption.

Thus $N^{\prime}_{\rho}$ being q-normal in $N_{\rho}$, its groupoid is
generated by further adding a small cost graphing $\Phi^{**}_{\rho}$.

∎

######  Corollary 3.3.

Groups with a commensurated fixed price $1$ subgroup $C$ have fixe price $1$.

###  3.1 Graphings with finite size

For the sake of simplicity, we shall first only consider graphings of bounded
size and generalize Elek’s combinatorial cost in this setting. In that case,
the length defined in (8) of Section 2.4 is bilipschitz-equivalent to the
length
$\ell^{\prime}_{\Phi}(g)=\min\\{k\in\mathbb{N}:g\in\overline{\Phi}^{k}\\}$: if
$\Phi=(\varphi_{1},\varphi_{2},\cdots,\varphi_{D})$, we have
$\ell^{\prime}_{\Phi}\leq\ell_{\Phi}\leq D\ell^{\prime}_{\Phi}$ . We will
treat the general case in Section 3.2.

######  Definition 3.4.

Let $\Phi$ and $\Psi$ be two graphings of finite size of the p.m.p. groupoid
$\mathcal{G}$ and $L$ be a natural number. We say that

  1. 1.

$\Psi$ _$L$ -Lipschitz embeds in_ $\Phi$ (or $\Phi$ _$L$ -Lipschitz contains_
$\Psi$), denoted by $\Psi\subset_{L}\Phi$, if every bisection
$\psi_{k}\in\Psi$ is piecewise a restriction of words of length at most $L$ in
the alphabet $\Phi$ and their inverses ($\widetilde{\mu}$-mod $0$);

  2. 2.

the graphings $\Phi$ and $\Psi$ are _$L$ -Lipschitz equivalent_, denoted
$\Phi\overset{\mathcal{L}ip}{\sim}_{L}\Psi$, if $\Psi\subset_{L}\Phi$ and
$\Phi\subset_{L}\Psi$;

Two graphings of finite size $\Phi$ and $\Psi$ are said _Lipschitz equivalent_
(denoted $\Phi\overset{\mathcal{L}ip}{\sim}\Psi$) if they are $L$-Lipschitz
equivalent for some $L\in\mathbb{N}$. Clearly two graphings $\Phi$ and $\Psi$
are Lipschitz equivalent if and only if their length functions $\ell_{\Phi}$
and $\ell_{\Psi}$ on $\mathcal{G}$ are Lipschitz equivalent. Observe that
being Lipschitz equivalent is an equivalence relation (while being
$L$-Lipschitz equivalent is not transitive).

If a graphing $\Phi$ of the p.m.p. groupoid $\mathcal{G}$ Lipschitz contains a
generating graphing, then $\Phi$ itself is generating.

The $L$-_Lipschitz cost_ of the graphed groupoid $(\mathcal{G},\Phi)$ is the
infimum of the costs of all graphings of $\mathcal{G}$ which are $L$-Lipschitz
equivalent to $\Phi$,

$\mathcal{C}_{L}(\mathcal{G},\Phi):=\inf\left\\{\mathcal{C}(\Psi)\colon\Psi\overset{\mathcal{L}ip}{\sim}_{L}\Phi\right\\}.$

######  Remark 3.5.

In the definition of the $L$-_Lipschitz cost_ , we can restrict to graphings
$\Psi$ of size bounded by the number of words of length $\leq L$ in the
elements of $\Phi$ and its inverse.

The following lemma claiming that the cost can be computed inside a given
Lipschitz class of (finite cost) graphings was observed for equivalence
relations in [Gab98, Étape 1] and [Gab00] (see also Lemma 3.9). We give a
proof for completeness.

######  Lemma 3.6 (Gaboriau [Gab00, Proposition IV.35]).

Let $(\mathcal{G},\Phi)$ be a graphed groupoid where the graphing $\Phi$ has
finite size. The cost of $\mathcal{G}$ can be computed inside the Lipschitz
class of $\Phi$, i.e.,

$\mathcal{C}(\mathcal{G})=\inf_{L}\mathcal{C}_{L}(\mathcal{G},\Phi).$ (12)

###### Proof.

Fix $\varepsilon>0$. Let $\Psi$ be a generating graphing of $\mathcal{G}$ such
that $\mathcal{C}(\Psi)\leq\mathcal{C}(\mathcal{G})+\varepsilon$. Take a
positive integer $M$ such that
$\tilde{\mu}(\overline{\Phi}\setminus\overline{\Psi}^{M})\leq\varepsilon$,
where we recall that $\overline{\Phi}$ is the subset of $\mathcal{G}$ given by
the images of the bisections defining $\Phi$. For $L\in\mathbb{N}$ we define

$\overline{\Psi_{L}}:=\overline{\Psi}\cap\overline{\Phi}^{L}$

and observe that $\cup_{L}\overline{\Psi_{L}}=\overline{\Psi}$ which implies
that $\cup_{L}\overline{\Psi_{L}}^{M}=\overline{\Psi}^{M}$, thus there exists
$L_{0}$ such that
$\tilde{\mu}(\overline{\Phi}\setminus\overline{\Psi_{L_{0}}}^{M})\leq
2\varepsilon$. There is a graphing of finite size $\Theta_{0}$ such that
$\overline{\Theta}_{0}=\overline{\Psi_{L_{0}}}\cup(\overline{\Phi}\setminus\overline{\Psi_{L_{0}}}^{M})$
satisfying
$\mathcal{C}(\Theta_{0})\leq\mathcal{C}(\Psi)+2\varepsilon\leq\mathcal{C}(\mathcal{G})+3\varepsilon$
and $\Theta_{0}\subset_{L_{0}}\Phi$. On the other hand,
$(\overline{\Phi}\setminus\overline{\Psi_{L_{0}}}^{M})\subset_{1}\Theta_{0}$
and $(\overline{\Phi}\cap\overline{\Psi_{L_{0}}}^{M})\subset_{M}\Theta_{0}$ so
that $\Phi\subset_{M}\Theta_{0}$. ∎

We now define the notion of $\mathfrak{u}$-combinatorial cost.

######  Definition 3.7 (Elek [Ele07]).

Let $(\mathcal{G}_{n},\Phi_{n})_{n}$ be a sequence of graphed p.m.p. groupoids
of bounded size. The $\mathfrak{u}$-_combinatorial cost_ of the sequence is

$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n}):=\inf_{L}\lim_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})$
(13)

###  3.2 Graphings with infinite size

We consider the general case where we allow graphings with unbounded or
infinite size.

######  Definition 3.8.

Let $\Phi$ and $\Psi$ be two graphings of the p.m.p. groupoid $\mathcal{G}$,
and $M=(M_{k})_{k\in\mathbb{N}}\in\mathbb{N}^{\mathbb{N}}$ a sequence of
natural numbers. We say that

  1. 1.

$\Psi$ _$M$ -coarsely embeds in_ $\Phi$ (or $\Phi$ _$M$ -coarsely contains_
$\Psi$), denoted by $\Psi\subset_{c,M}\Phi$, if for every $k\in\mathbb{N}$,
the bisection $\psi_{k}\in\Psi$ is piecewise a restriction of words of length
at most $M_{k}$ in the alphabet $\\{\varphi_{1},\ldots,\varphi_{M_{k}}\\}$ and
their inverses ($\widetilde{\mu}$-mod $0$);

  2. 2.

the graphings $\Phi$ and $\Psi$ are _$M$ -coarsely equivalent_, denoted
$\Phi\overset{c}{\sim}_{M}\Psi$, if $\Psi\subset_{c,M}\Phi$ and
$\Phi\subset_{c,M}\Psi$;

The graphings $\Phi$ and $\Psi$ are said _coarsely equivalent_ (denoted
$\Phi\overset{c}{\sim}\Psi$) if they are $M$-coarsely equivalent for some
$M\in\mathbb{N}^{\mathbb{N}}$. Clearly two graphings $\Phi$ and $\Psi$ are
coarsely equivalent if and only if their length functions $\ell_{\Phi}$ and
$\ell_{\Psi}$ on $\mathcal{G}$ have the same bounded sequences.

When both $\Phi$ and $\Psi$ have finite size, they are coarsely equivalent if
and only they are Lipschitz equivalent. So coarse equivalence is the natural
generalization of Lipschitz equivalence for graphings with infinite size.

If a graphing $\Phi$ of the p.m.p. groupoid $\mathcal{G}$ coarsely contains a
generating graphing, then $\Phi$ itself is generating.

The $M$-_coarse cost_ of the graphed groupoid $(\mathcal{G},\Phi)$ is defined
as the infimum of the costs of all graphings of $\mathcal{G}$ which are
$M$-coarsely equivalent to $\Phi$,

$\mathcal{C}_{M}(\mathcal{G},\Phi):=\inf\left\\{\mathcal{C}(\Psi)\colon\Psi\overset{c}{\sim}_{M}\Phi\right\\}.$

We remark that $\Phi$ coarsely embeds into $\Psi$ if and only if for every
$k$, there is $k^{\prime}$ such that $\\{\varphi_{1},\dots,\varphi_{k}\\}$
Lipschitz embeds into $\\{\psi_{1},\dots,\psi_{k^{\prime}}\\}$. This allows to
generalize in a straightforward way all the statements proved for graphings
with bounded size. For example, Lemma 3.6 still holds in this setting for
graphings of finite cost.

######  Lemma 3.9.

Let $(\mathcal{G},\Phi)$ be a graphed groupoid where the graphing $\Phi$ has
finite cost. The cost of $\mathcal{G}$ can be computed inside the coarse class
of $\Phi$, i.e.,

$\mathcal{C}(\mathcal{G})=\inf_{M}\mathcal{C}_{M}(\mathcal{G},\Phi).$ (14)

###### Proof.

Let $\Phi=(\phi_{i})_{i}$. Let $\varepsilon>0$. Choose $k$ such that
$\mathcal{C}((\phi_{i})_{i>k})\leq\varepsilon$. Consider the finite graphing
$\Phi^{\prime}=(\phi_{i})_{i\leq k}$, and define
$\mathcal{G}^{\prime}\subset\mathcal{G}$ the groupoid generated by
$\Phi^{\prime}$. Clearly
$\mathcal{C}(\mathcal{G})\leq\mathcal{C}(\mathcal{G}^{\prime})+\varepsilon$.
By Lemma 3.6 there is an integer $L_{0}$ and a finite size graphing
$\Psi^{\prime}$ which is $L_{0}$-Lipschitz equivalent to $\Phi^{\prime}$ and
such that
$\mathcal{C}(\Psi)\leq\mathcal{C}(\mathcal{G}^{\prime})+\varepsilon$. Then the
graphing $\Psi$ obtained as the union of $\Psi^{\prime}$ and
$(\phi_{i})_{i>k}$ is coarsely equivalent to $\Phi$ and satisfies
$\mathcal{C}(\Psi^{\prime})\leq\mathcal{C}(\mathcal{G})+2\varepsilon$. ∎

######  Remark 3.10.

The proof shows more: for every $\varepsilon>0$ there is $i_{\varepsilon}$ and
a graphing $\Psi$ of finite size which is coarsely equivalent to
$\\{\varphi_{1},\dots,\varphi_{i_{\varepsilon}}\\}$ and such that the graphing
$\Psi\cup(\varphi_{j})_{j>i_{\varepsilon}}$ has cost
$\leq\mathcal{C}(\mathcal{G})+\varepsilon$.

We generalize Definition 3.7 of combinatorial cost to possibly unbounded
graphings.

######  Definition 3.11.

Let $(\mathcal{G}_{n},\Phi_{n})_{n}$ be a sequence of graphed p.m.p.
groupoids. The $\mathfrak{u}$-_combinatorial cost_ of the sequence is

$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n}):=\inf_{M\in\mathbb{N}^{\mathbb{N}}}\lim_{n\in\mathfrak{u}}\mathcal{C}_{M}(\mathcal{G}_{n},\Phi_{n})$
(15)

When $\Phi_{n}$ have size bounded by $D$, we recover Definition 3.7. This
deserves a small justification. Consider first some integer $L$. It follows
from Remark 3.5 that $\mathcal{C}_{L}(\mathcal{G},\Phi_{n})$ can be computed
for a graphing $\Psi_{n}$ of size bounded by $(2D)^{L}$. This graphing is in
particular $M$-coarsely equivalent to $\Phi_{n}$ for $M$ the constant sequence
$((2D)^{L})_{k\in\mathbb{N}}$. In particular
$\mathcal{C}_{M}(\mathcal{G},\Phi_{n})\leq\mathcal{C}_{L}(\mathcal{G},\Phi_{n})$
and

$\inf_{M\in\mathbb{N}^{\mathbb{N}}}\lim_{n\in\mathfrak{u}}\mathcal{C}_{M}(\mathcal{G}_{n},\Phi_{n})\leq\lim_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G},\Phi_{n}).$

Conversely, if $M\in\mathbb{N}^{\mathbb{N}}$ and $\Psi_{n}$ is $M$-coarsely
equivalent to $\Phi_{n}$, put $L_{0}:=\max_{i\leq D}M_{i}$ and
$L_{1}:=\max_{i\leq L_{0}}M_{i}$. Then we have
$\Phi_{n}\subset_{L_{0}}\\{\psi_{1},\dots,\psi_{L_{0}}\\}$ and
$\\{\psi_{1},\dots,\psi_{L_{0}}\\}\subset_{L_{1}}\Phi_{n}$. In particular
$\mathcal{C}_{\max(L_{0},L_{1})}(\mathcal{G}_{n},\Phi_{n})\leq\mathcal{C}_{M}(\mathcal{G}_{n},\Phi_{n})$
and

$\inf_{L\in\mathbb{N}}\lim_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})\leq\lim_{n\in\mathfrak{u}}\mathcal{C}_{M}(\mathcal{G},\Phi_{n}).$

###  3.3 Limit of graphed groupoids

######  Proposition 3.12.

Consider a sequence of graphed p.m.p. groupoids $(\mathcal{G}_{n},\Phi_{n})$
of bounded size. Take $L\in\mathbb{N}$.

  1. (i)

If for $\mathfrak{u}$-almost every $n$ the bisection $\psi_{n}$ of
$\mathcal{G}_{n}$ is $L$-Lipschitz embedded in $\Phi_{n}$, then
$[\psi_{n}]_{\mathfrak{u}}$ $L$-Lipschitz embeds in
$[\Phi_{n}]_{\mathfrak{u}}$.

  2. (ii)

If the bisection $\psi_{\mathfrak{u}}$ of $\mathcal{G}_{\mathfrak{u}}$ is
$L$-Lipschitz embedded in $\Phi_{\mathfrak{u}}$, then there exists a sequence
of bisections $\psi_{n}$ of $\mathcal{G}_{n}$ such that
$[\psi_{n}]_{\mathfrak{u}}=\psi_{\mathfrak{u}}$ and such that $\psi_{n}$ is
$L$-Lipschitz embedded in $\Phi_{n}$ for $\mathfrak{u}$-almost every
$n\in\mathbb{N}$.

  3. (iii)

Let $\Psi_{\mathfrak{u}}$ be a finite size graphing of the ultraproduct
$\mathcal{G}_{\mathfrak{u}}$ which $L$-Lipschitz contains
$\Phi_{\mathfrak{u}}$. Then there exists a sequence of bounded size graphings
$\Psi_{n}$ of $\mathcal{G}_{n}$ such that
$[\Psi_{n}]_{\mathfrak{u}}=\Psi_{\mathfrak{u}}$ and such that $\Psi_{n}$
$L$-Lipschitz contains $\Phi_{n}$ for $\mathfrak{u}$-almost every
$n\in\mathbb{N}$. Moreover if $\Psi_{\mathfrak{u}}$ is $L$-Lipschitz
equivalent to $\Phi_{\mathfrak{u}}$, then we can choose $\Psi_{n}$ to be
$L$-Lipschitz equivalent to $\Phi_{n}$.

###### Proof.

Let $D:=\max_{n}|\Phi_{n}|$. We let $W$ be the finite set of formal words of
length at most $L$ in the letters $\varphi^{i}$ for $i\in\\{1,\ldots,D\\}$ and
their inverses. For $w\in W$, denote by $w_{n}$ and $w_{\mathfrak{u}}$ the
corresponding p.m.p. bisection of $\mathcal{G}_{n}$ and
$\mathcal{G}_{\mathfrak{u}}$ respectively. We set

$A_{n}^{w}:=\\{x\in\operatorname{dom}(\psi_{n}):\ \psi_{n}(x)=w_{n}(x)\\}.$

Let us first show (i). By hypothesis $\cup_{w\in
W}A_{n}^{w}=\operatorname{dom}(\psi_{n})$ for $\mathfrak{u}\textrm{-a.e. }n$.
Since $W$ is finite we have that
$\operatorname{dom}([\psi_{n}]_{\mathfrak{u}})=[\operatorname{dom}(\psi_{n})]_{\mathfrak{u}}=\cup_{w}[A_{n}^{w}]_{\mathfrak{u}}$
and moreover
$[\psi_{n}]_{\mathfrak{u}}\bigr{|}_{[A_{n}^{w}]_{\mathfrak{u}}}=w_{\mathfrak{u}}\bigr{|}_{[A_{n}^{w}]_{\mathfrak{u}}}$.
This is exactly that $\psi_{\mathfrak{u}}$ $L$-Lipschitz embeds in
$\Phi_{\mathfrak{u}}$.

The proof of (ii) is similar. For every $w\in W$ we can find $B_{n}^{w}\subset
X_{n}$ such that

  * •

$B_{n}^{w}\cap B_{n}^{w^{\prime}}=\emptyset$ for $w,w^{\prime}\in W$ with
$w\neq w^{\prime}$;

  * •

$[B_{n}^{w}]_{\mathfrak{u}}=A^{w}_{\mathfrak{u}}$ up to a nullset for every
$w\in W$;

  * •

$\cup_{w\in
W}[B_{n}^{w}]_{\mathfrak{u}}=\operatorname{dom}(\psi_{\mathfrak{u}})$ up to a
nullset.

For every couple of words $w,w^{\prime}\in W$ with $w\neq w^{\prime}$ we
observe that
$\operatorname{tar}\left(w_{\mathfrak{u}}\bigr{|}_{[B_{n}^{w}]_{\mathfrak{u}}}\right)$
is disjoint from
$\operatorname{tar}\left(w^{\prime}_{\mathfrak{u}}\bigr{|}_{[B_{n}^{w^{\prime}}]}\right)$
since they are restriction of the same bisection on two disjoint sets.
Therefore, since $W$ is finite, we can assume that the measurable sets
$B_{n}^{w}$ also satisfy the following property:

  * •

$\operatorname{tar}\left(w_{n}\bigr{|}_{B_{n}^{w}}\right)\cap\operatorname{tar}\left(w^{\prime}_{n}\bigr{|}_{B_{n}^{w^{\prime}}}\right)=\emptyset$
for $w,w^{\prime}\in W$ with $w\neq w^{\prime}$.

Set $\psi_{n}$ to be the join of the partial authomorphism
$w_{n}\bigr{|}_{B_{n}^{w}}$. Clearly $\psi_{n}$ $L$-Lipschitz embeds in
$\Phi_{n}$ and $[\psi_{n}]=\psi_{\mathfrak{u}}$ outside a nullset.

For (iii), let us only prove the moreover part. The first is similar and left
to the reader. Denote $\Phi_{n}=(\varphi_{n}^{k})_{1\leq k\leq D}$ and
$\Psi_{\mathfrak{u}}=(\psi_{\mathfrak{u}}^{k})_{1\leq k\leq D^{\prime}}$.
Suppose we have
$\Psi_{\mathfrak{u}}\overset{\mathcal{L}ip}{\sim}_{L}[\Phi_{n}]_{\mathfrak{u}}$
for some $L\in\mathbb{N}$. (ii) gives us a sequence $(\Psi_{n})_{n}$ of size
$D^{\prime}$ such that $\Psi_{n}$ $L$-Lipschitz embeds into $\Phi_{n}$. Let
$V$ be the finite set of formal words of length at most $L$ in the letters
$\psi^{i}$ for $i\in\\{1,\ldots,D^{\prime}\\}$ and their inverses and for
$v\in V$ we denote by $v_{n}$ and $v_{\mathfrak{u}}$ the corresponding p.m.p.
bisection of $\mathcal{G}_{n}$ and $\mathcal{G}_{\mathfrak{u}}$ respectively.
For every $k\leq D$ we set

$U^{k}_{n}:=\\{x\in\operatorname{dom}(\varphi^{k}_{n}):\
\varphi^{k}_{n}(x)=v_{n}(x)\text{ for some }v\in V\\}.$

Observe that
$\lim_{\mathfrak{u}}\mu_{n}(\operatorname{dom}(\varphi^{k}_{n})\setminus
U^{k}_{n})=0$. We define $\Psi^{\prime}_{n}$ to be the union of $\Psi_{n}$ and
the restriction of $\varphi^{i}_{n}$ to
$\operatorname{dom}(\varphi^{i}_{n})\setminus U_{n}^{i}$ for $i\leq k$. Then
clearly $\Phi_{n}$ $L$-Lipschitz embeds in $\Psi^{\prime}_{n}$. Since we have
added only restrictions of elements in $\Phi_{n}$, it follows that
$\Psi^{\prime}_{n}$ still $L$-Lipschitz embeds in $\Phi_{n}$. Finally
$\Psi^{\prime}_{n}$ and $\Psi_{n}$ differ only for finitely many elements
whose support has arbitrarily small measure, therefore
$[\Psi_{n}]_{\mathfrak{u}}=[\Psi^{\prime}_{n}]_{\mathfrak{u}}=\Psi_{\mathfrak{u}}$.
∎

Let us observe that if $\Phi_{n}$ have uniformly bounded size, then
$\lim_{\mathfrak{u}}\mathcal{C}(\Phi_{n})=\mathcal{C}(\Phi_{\mathfrak{u}})<\infty$
and in general this condition amounts to a uniform summability of the measures
of the domains of the bisections of $\Phi_{n}$. As a consequence of the above
proposition we obtain the following theorem.

######  Theorem 3.13.

If a sequence of p.m.p. graphed groupoids $(\mathcal{G}_{n},\Phi_{n})$ and its
ultraproduct groupoid $(\mathcal{G}_{\mathfrak{u}},\Phi_{\mathfrak{u}})$
satisfy
$\lim_{\mathfrak{u}}\mathcal{C}(\Phi_{n})=\mathcal{C}(\Phi_{\mathfrak{u}})<\infty$,
then

$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})=\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\geq\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n}).$

######  Remark 3.14.

The reverse inequality

$\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\leq\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n})$
(16)

is generally not true. Consider, for instance, the free group on $2$
generators (more generally a finitely generated group $\Gamma$ of cost
$\mathscr{C}_{*}(\Gamma)>1$), with finite generating set $S$ and with a
decreasing sequence $(\Gamma_{n})_{n}$ of finite index normal subgroups with
trivial intersection. The sequence of finite Schreier graphs for
$(\Gamma/\Gamma_{n},S)$ defines a sequence $\Phi_{n}=(\varphi_{s})_{s\in S}$
of graphings of the transitive equivalence relation $\mathcal{G}_{n}$ on the
finite spaces $X_{n}=\Gamma/\Gamma_{n}$ thus of cost
$1-\frac{1}{[\Gamma:\Gamma_{n}]}$. The ultraproduct groupoid $\mathcal{G}$ is
given by a free action of $\Gamma$ on $X_{\mathfrak{u}}$ which has cost $>1$.
This example is exactly what justifies the use of the combinatorial cost
[Ele07] or of the groupoid cost [AN12] (see Cor. 4.5, where instead of a naked
Schreier graph as above, the isotropy subgroups are taken into account).

######  Remark 3.15.

The following inequalities hold in general without any boundedness assumption:

$\displaystyle c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})$
$\displaystyle\geq$
$\displaystyle\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n})$ (17)
$\displaystyle c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})$
$\displaystyle\geq$ $\displaystyle\mathcal{C}(\mathcal{G}_{\mathfrak{u}}).$
(18)

(17) is clear from the definition of combinatorial cost, while (18) holds
since the first part of the argument below is still valid in this context.

On the contrary, the other inequalities

$\displaystyle\mathcal{C}(\mathcal{G}_{\mathfrak{u}})$ $\displaystyle\geq$
$\displaystyle\lim\limits_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n})$ (19)
$\displaystyle\mathcal{C}(\mathcal{G}_{\mathfrak{u}})$ $\displaystyle\geq$
$\displaystyle c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})$
(20)

both require some boundedness assumption as exemplified by a residually finite
fixed price $1$ group such as $\Gamma={\bf F}_{\infty}\times\mathbb{Z}$ with a
decreasing sequence of finite index normal subgroups with trivial
intersection. The groupoid cost for the action on any finite quotient is
infinite, and similarly for the combinatorial cost. But the ultraproduct free
action has cost $1$ [Gab00, Proposition VI.23].

Even with $\sup_{n}\mathcal{C}(\Phi_{n})<\infty$, uniform summability is
needed: If instead of $\Phi_{n}=(\varphi_{s})_{s\in S}$ in the example of
Remark 3.14 one subdivides the bisections $\varphi_{s}$ into singletons, we
obtain the generating graphing
$\Phi^{\prime}_{n}=(\varphi^{\prime}_{v,s}=(v,sv))_{v\in\Gamma/\Gamma_{n},s\in
S}$,
$\mu(\operatorname{dom}(\varphi^{\prime}_{v,s}))=\frac{1}{[\Gamma:\Gamma_{n}]}$.
Then $\mathcal{G}_{\mathfrak{u}}$ is the trivial groupoid $X_{\mathfrak{u}}$
and in particular has cost $0$, whereas
$c\mathcal{C}_{\mathfrak{u}}(\mathcal{G}_{n},\Phi_{n})\geq\lim_{\mathfrak{u}}\mathcal{C}(\mathcal{G}_{n})=1$,
thus contradicting (19) and (20).

###### Proof of Theorem 3.13.

Let $M\in\mathbb{N}^{\mathbb{N}}$ and $\Psi_{n}$ be a graphing of
$\mathcal{G}_{n}$ such that $\Phi_{n}\overset{c}{\sim}_{M}\Psi_{n}$. By
Corollary 2.35, $\Psi_{\mathfrak{u}}$ is a generating graphing of
$\mathcal{G}_{\mathfrak{u}}$ and in particular

$\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\leq\mathcal{C}(\Psi_{\mathfrak{u}})\leq\lim_{\mathfrak{u}}\mathcal{C}(\Psi_{n}).$

Taking the infimum over $\Psi_{n}$ we obtain

$\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\leq\lim_{\mathfrak{u}}\mathcal{C}_{M}(\mathcal{G}_{n},\Phi_{n}).$

This shows (without the uniform integrability assumption) that

$\mathcal{C}(\mathcal{G}_{\mathfrak{u}})\leq
c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n}).$

For the converse inequality, fix $\varepsilon>0$. By Remark 3.10 there are
integers $i_{0}$ and $L$ and a finite graphing of
$\mathcal{G}_{\mathfrak{u}}$,
$\Psi^{\prime}_{\mathfrak{u}}\overset{\mathcal{L}ip}{\sim}_{L}(\varphi_{\mathfrak{u}}^{1},\dots,\varphi_{\mathfrak{u}}^{i_{0}})$
such that the graphing
$\Psi_{\mathfrak{u}}:=\Psi^{\prime}_{\mathfrak{u}}\cup(\varphi_{\mathfrak{u}}^{i})_{i>i_{0}}$
has cost $\leq\mathcal{C}(\mathcal{G}_{\mathfrak{u}})+\varepsilon$. By
Proposition 3.12 for every $n$ there is a graphing
$\Psi^{\prime}_{n}\overset{\mathcal{L}ip}{\sim}_{L}(\varphi_{n}^{1},\dots,\varphi_{n}^{i_{0}})$
such that $[\Psi^{\prime}_{n}]_{\mathfrak{u}}=\Psi^{\prime}_{\mathfrak{u}}$.
In particular, there is $M\in\mathbb{N}^{\mathbb{N}}$ such that
$\Psi_{n}:=\Psi^{\prime}_{n}\cup(\varphi_{n}^{i})_{i>i_{0}}$ is $M$-coarsely
equivalent to $\Phi_{n}$. Finally,

$\lim_{\mathfrak{u}}\mathcal{C}(\Psi_{n})=\lim_{\mathfrak{u}}\mathcal{C}(\Psi^{\prime}_{n})+\lim_{\mathfrak{u}}\mathcal{C}((\varphi_{n}^{i})_{i>i_{0}}).$

The first term is equal to $\mathcal{C}(\Psi^{\prime}_{\mathfrak{u}})$ by
linearity, and the second term is equal to
$\mathcal{C}((\varphi_{\mathfrak{u}}^{i})_{i>i_{0}})$ by the uniform
integrability assumption. In particular we obtain

$\lim_{\mathfrak{u}}\mathcal{C}(\Psi_{n})=\mathcal{C}(\Psi_{\mathfrak{u}})\leq\mathcal{C}(\mathcal{G}_{\mathfrak{u}})+\varepsilon.$

Taking the infimum over all $\varepsilon$ we obtain
$c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})\leq\mathcal{C}(\mathcal{G}_{\mathfrak{u}})$,
which proves the theorem.∎

######  Remark 3.16 (Elek’s combinatorial cost).

Initially, the combinatorial cost [Ele07] was introduced as an invariant for
sequences of finite graphs with uniformly bounded degree $\leq D$. If
$(G_{n})_{n}$ is such a sequence of graphs, then we have already discussed a
canonical coarse structure on the sequence, see Example 2.14, and commented
about the ultraproduct of the sequence in Example 2.33.

The original combinatorial cost $c\mathcal{C}$ of the sequence $(G_{n})_{n}$
uses $\liminf\limits_{n\to\infty}$ instead of $\lim\limits_{n\in\mathfrak{u}}$
(compare Definition 3.7):

$c\mathcal{C}((G_{n})_{n}):=\inf_{L}\liminf\limits_{n\to\infty}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n}).$
(21)

We claim that:

$c\mathcal{C}((G_{n})_{n})=\inf\\{c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n}):\mathfrak{u}\textrm{
non principal ultrafilter}\\}.$ (22)

The inequality $\leq$ holds since,
$\liminf\limits_{n\to\infty}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})\leq\lim\limits_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})$
for every $L$. Concerning the reverse inequality, for every $\varepsilon>0$,
there is an $L$ such that
$\liminf\limits_{n\to\infty}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})\leq
c\mathcal{C}((G_{n})_{n})+\varepsilon$ and there is a non principal
ultrafilter $\mathfrak{u}$ such that
$\liminf\limits_{n\to\infty}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})=\lim\limits_{n\in\mathfrak{u}}\mathcal{C}_{L}(\mathcal{G}_{n},\Phi_{n})$.
Observe that, interleaving the terms of two sequences of graphs with different
combinatorial costs, indicates that a strict inequality
$c\mathcal{C}((G_{n})_{n})<c\mathcal{C}_{\mathfrak{u}}((\mathcal{G}_{n},\Phi_{n})_{n})$
may happen for some ultrafilters. Moreover, it is not clear to us whether the
infimum in (22) is realized by some ultrafilter.

######  Corollary 3.17 (Combinatorial cost vs cost).

If $(G_{n})_{n}$ is a sequence of finite graphs with uniformly bounded degree,
then the combinatorial cost is the infimum over all non principal ultrafilters
of the costs of the ultraproduct groupoids $\mathcal{G}_{\mathfrak{u}}$ of the
associated coarse groupoids $\mathcal{G}_{n}$:

$c\mathcal{C}((G_{n})_{n})=\inf\\{\mathcal{C}(\mathcal{G}_{\mathfrak{u}}):\mathfrak{u}\textrm{
non principal ultrafilter}\\}.$

###  3.4 Weak containment

We now mimic the powerful notion of weak containment introduced by Kechris
[Kec10, Section 10 (C)].

######  Definition 3.18 (Weak containment for graphed groupoids).

The graphed groupoid $(\mathcal{H},\Psi)$ on $(Y,\mathscr{A},\nu)$ is _weakly
contained in_ the graphed groupoid $(\mathcal{G},\Phi)$ on
$(X,\mathscr{B},\mu)$, in symbol,

$(\mathcal{H},\Psi)\prec(\mathcal{G},\Phi)$

if $\Psi=(\psi_{j})_{j\in J}$ and $\Phi=(\varphi_{j})_{j\in J}$ have the same
sets of indices and for any finite set $K\subset[[\mathcal{H}]]$ and every
$\varepsilon>0$, there is a map $\pi\colon K\to[[\mathcal{G}]]$ satisfying
$\pi(\psi_{j})=\varphi_{j}$ for every $\psi_{j}\in K\cap\Psi$,
$d(\pi(\psi\psi^{\prime}),\pi(\psi)\pi(\psi^{\prime}))\leq\varepsilon$ and
$|\tau(\psi)-\tau(\pi(\psi))|<\varepsilon$ for every $\psi,\psi^{\prime}\in K$
such that $\psi\psi^{\prime}\in K$.

Note that if $B\in K$ is a _unit bisection_ of $\mathcal{H}$, (meaning
$B\subset Y$ or equivalently $B^{2}=B$), then the condition
$d(\pi(B),\pi(B)^{2})\leq\varepsilon$ implies that $\pi(B)$ is at distance
$\leq\varepsilon$ from a unit bisection. So in the definition of weak
containment, we can always assume that $\pi$ maps unit bisections to unit
bisections, and also that disjoint unit bisections are mapped to disjoint unit
bisections. Moreover, if $\varphi$ is any bisection, then the _conjugation_
satisfies $\varphi B\varphi^{-1}=\overline{\varphi}(B)$. One thus recovers
Kechris’ notion of weak containment for group actions.

If $\mathscr{A}$ is separable222When $\mathscr{A}$ is not separable, the same
holds if one allows an ultrafilter on a larger index set than $\mathbb{N}$, as
in Proposition 3.32., then $(\mathcal{H},\Psi)\prec(\mathcal{G},\Phi)$ if and
only if there is a trace preserving embedding of $[[\mathcal{H}]]$ into the
metric ultraproduct of $\prod_{\mathfrak{u}}[[\mathcal{G}]]$ sending each
$\varphi_{j}$ to $[\psi_{j}]_{\mathfrak{u}}$, see Proposition 3.32.

######  Proposition 3.19.

Assume $(\mathcal{H},\Psi)\prec(\mathcal{G},\Phi)$ and let $\psi$ be a
$\Psi$-word and let $\varphi$ be the corresponding $\Phi$-word, then

  1. 1.

$\widetilde{\nu}(\psi)=\widetilde{\mu}(\varphi)$; thus
$\mathcal{C}(\Psi)=\mathcal{C}(\Phi)$;

  2. 2.

$\tau(\psi)=\tau(\varphi)$ (equal measure of units);

  3. 3.

$\widetilde{\nu}(M_{F}(\psi))\leq\widetilde{\mu}(M_{F}(\varphi))$ (the
measurably free part from Proposition 2.12 is monotonic).

###### Proof.

The first two items are easy and left to the reader.

For the measurably free part, use finitely many elements from a partition
given by Proposition 2.12. ∎

######  Definition 3.20 (Weak equivalence for graphed groupoids).

The graphed groupoids $(\mathcal{H},\Psi)$ and $(\mathcal{G},\Phi)$ are weakly
equivalent, in symbols,

$(\mathcal{H},\Psi)\sim_{w}(\mathcal{G},\Phi)$

if $(\mathcal{H},\Psi)\prec(\mathcal{G},\Phi)$ and
$(\mathcal{G},\Phi)\prec(\mathcal{H},\Psi)$.

######  Remark 3.21 (Local-global convergence).

Hatami, Lovász and Szegedy [HLS14] have defined a notion of local-global
convergence for sequences of bounded-degree graphs. This enters rather well in
our setting, the only difference being that they consider unlabeled and
unoriented graphs whereas we have mainly focused on labeled graph(ing)s. In
order to interpret the local-global convergence in our setting, let us say
that a subset $\Phi\subset\mathcal{G}$ of a p.m.p. groupoid is a _bounded
degree combinatorial graphing_ if $\Phi$ is measurable, symmetric
($\Phi^{-1}=\Phi$) and $x\mapsto|s^{-1}(x)\cap\Phi|$ is essentially bounded on
$X$. Note that a symmetric subset of $\mathcal{G}$ is a combinatorial graphing
if and only if it is a finite union of bisections.

If $\mathcal{G}$ is the equivalence relation on a finite set, we recover the
classical notion of combinatorial graph. If $\mathcal{G}$ is a p.m.p.
equivalence relation on a standard probability space, then we recover the
notion of graphing as in [KM04]. In that paper Hatami, Lovász and Szegedy
first define a notion of convergence, and then they identify the limiting
objects as graphings in their sense. To be more precise, we wish to point out
that the limiting object is not unique: the well-defined limiting object is a
_weak-equivalence class of combinatorial graphings_ , as we define now.

Let $\mathcal{G}$ and $\mathcal{H}$ be p.m.p. graphings with combinatorial
graphings $\Phi$ and $\Psi$. Write $\Phi=\cup_{j=1}^{n}\varphi_{j}$ as a
finite union of bisections. We say that $(\mathcal{H},\Psi)$ is weakly
contained in $(\mathcal{G},\Phi)$ if for any finite set
$K\subset[[\mathcal{H}]]$ and every $\varepsilon>0$, there is a map $\pi\colon
K\to[[\mathcal{G}]]$ satisfying $\cup_{j=1}^{n}\pi(\psi_{j})=\Phi$ if
$\psi_{j}\in K$ for every $j$,
$d(\pi(\psi\psi^{\prime}),\pi(\psi)\pi(\psi^{\prime}))\leq\varepsilon$ and
$|\tau(\psi)-\tau(\pi(\psi))|<\varepsilon$ for every $\psi,\psi^{\prime}\in K$
such that $\psi\psi^{\prime}\in K$.

As above if $\mathscr{A}$ is separable, then $(\mathcal{H},\Phi)$ is weakly
contained in $(\mathcal{G},\Psi)$ if and only if there is a trace preserving
embedding of $[[\mathcal{H}]]$ into the metric ultraproduct of
$\prod_{\mathfrak{u}}[[\mathcal{G}]]$ sending each $\Phi$ to $\Psi$. The same
holds _mutatis mutandis_ for non separable $\mathscr{A}$. In particular this
notion does not depend on the decomposition
$\Phi=\varphi_{1}\cup\dots\cup\varphi_{n}$.

One says that $(\mathcal{G},\Phi)$ and $(\mathcal{H},\Psi)$ are weakly
equivalent if $(\mathcal{G},\Phi)$ is weakly contained in $(\mathcal{H},\Psi)$
and conversely $(\mathcal{H},\Psi)$ is weakly contained in
$(\mathcal{G},\Phi)$.

Then one can easily check that a sequence $(G_{n})$ of bounded-degree graphs
converges locally-globally in the sense of [HLS14] if and only if the weak
equivalence class of the graphed equivalence relation
$(\mathcal{G}_{\mathfrak{u}},\mathrm{Edg}_{\mathfrak{u}})$ (see Example 2.33)
does not depend on the free ultrafilter $\mathfrak{u}$. More generally, the
sequence $(G_{n})$ local-global converges along $\mathfrak{u}$ towards a
p.m.p. equivalence relation ${\mathcal{R}}$ with a combinatorial graphing
$\Psi$ if and only if $({\mathcal{R}},\Psi)$ is weakly equivalent to
$(\mathcal{G}_{\mathfrak{u}},\mathrm{Edg}_{\mathfrak{u}})$.

Let us mention that ultraproducts of bounded degree finite graphs as
combinatorial graphings were already considered in [Ele10b] (we thank G. Elek
for pointing this article out after a preliminary version of our text has
circulated).

The following extends a result of Kechris [Kec10, end of Section 10 (C)] from
group actions to graphed groupoids:

######  Theorem 3.22 (weak containment and cost).

If $(\mathcal{H},\Psi)\prec(\mathcal{G},\Phi)$ and $\Phi$ has finite cost,
then $\mathcal{C}(\mathcal{H})\geq\mathcal{C}(\mathcal{G})$. In particular,
the cost is an invariant of the weak equivalence class of
$(\mathcal{G},\Phi)$.

###### Proof.

First observe that the graphings $\Phi=(\varphi_{j})_{j\in J}$ and
$\Psi=(\psi_{j})_{j\in J}$ have the same cost (see Proposition 3.19).

Let $\varepsilon_{0}>0$. By (the proof of) Lemma 3.9, there exists a
generating graphing $\Psi^{\prime}=(\psi^{\prime}_{i})_{i\in I}$ of
$\mathcal{H}$ such that:
(1) $\mathcal{C}(\Psi^{\prime})\leq\mathcal{C}(\mathcal{H})+\varepsilon_{0}$;
(2) there are finite subsets $J_{0}\subset J$ and $I_{0}\subset I$ such that
$\Psi^{\prime}_{0}:=(\psi^{\prime}_{i})_{i\in I_{0}}$ generates the same
groupoid as $\Psi_{0}:=(\psi_{j})_{j\in J_{0}}$ (even Lipschitz equivalent,
but this will be of no use here),
(3) there is a bijection $r:J\setminus J_{0}\to I\setminus I_{0}$ such that
$\psi_{j}=\psi^{\prime}_{r(j)}$ for each $j\in J\setminus J_{0}$.

Let $K\subset[[\mathcal{H}]]$ be a finite subset containing
$\Psi^{\prime}_{0}$ and $\varepsilon>0$, and let $\pi\colon
K\to[[\mathcal{G}]]$ be as in the definition of weak containment. Denote by
$\mathcal{G}_{K,\varepsilon}$ the groupoid generated by
$\pi(\Psi^{\prime}_{0})=\\{\pi(\psi^{\prime}_{i})\\}_{i\in I_{0}}\\}$. By (2)
and the definition of weak containment,
$\lim_{K,\varepsilon}d(\varphi_{j},\varphi_{j}\cap\mathcal{G}_{K,\varepsilon})=0$
for every $j\in J_{0}$. In particular there is $K,\varepsilon$ such that
$\sum_{j\in
J_{0}}d(\varphi_{j},\varphi_{j}\cap\mathcal{G}_{K,\varepsilon})\leq\varepsilon_{0}$.
Taking $\varepsilon$ small enough we can also assume that
$\mathcal{C}(\pi(\Psi^{\prime}_{0}))\leq\mathcal{C}(\Psi^{\prime}_{0})+\varepsilon_{0}$.
It follows that the graphing of $\mathcal{G}$ obtained as the union of
$\pi(\Psi^{\prime}_{0})$, of
$(\varphi_{j}\setminus(\varphi_{j}\cap\mathcal{G}_{K,\varepsilon}))_{j\in
J_{0}}$ and of $(\varphi_{j})_{j\in J\setminus J_{0}}$ is generating and has
cost less than

$\mathcal{C}(\Psi^{\prime}_{0})+\varepsilon_{0}+\varepsilon_{0}+\mathcal{C}((\varphi_{j})_{j\in
J\setminus
J_{0}})=\mathcal{C}(\Psi^{\prime})+2\varepsilon_{0}\leq\mathcal{C}(\mathcal{H})+3\varepsilon_{0}.$

One concludes that $\mathcal{C}(\mathcal{G})\leq\mathcal{C}(\mathcal{H})$ as
$\varepsilon_{0}$ was arbitrary. ∎

###  3.5 Factors

Recall that homomorphisms of p.m.p. groupoids are defined in Definition 2.23.

######  Definition 3.23.

A homorphism $T$ between the p.m.p. groupoids $\mathcal{G}$ and
$\mathcal{G}^{\prime}$ over the probability spaces $(X,\mu)$ and
$(X^{\prime},\mu^{\prime})$ is a _factor map_ if $T$ maps $\widetilde{\mu}$ to
$\widetilde{\mu}^{\prime}$. In this case $\mathcal{G}^{\prime}$ is a _factor_
of $\mathcal{G}$.

Be aware that the condition on the measures $\widetilde{\mu}$ and
$\widetilde{\mu}^{\prime}$ entails that the factor map is essentially onto and
is “class-bijective”, i.e., $T(g)$ is a unit if and only if $g$ itself is a
unit $\widetilde{\mu}$-almost surely; in particular
$\widetilde{\mu}(T^{-1}(X^{\prime})\setminus X)=0$ and $T$ is p.m.p. in the
sense of Definition 2.23.

The second author takes the opportunity to mention that this notion was
introduced in the framework of standard equivalence relations in [Gab05a,
Definition p. 1815 and Lemma 2.3 and 2.4] and to correct an obvious misprint
there: replace one-to-one by bijective.

For instance, a group morphism $\Gamma\to\Gamma^{\prime}$ is a factor in our
sense if and only if it is an isomorphism. In fact, we can completely
characterize the groupoids which factors over a given group.

######  Remark 3.24 (p.m.p. actions of p.m.p. groupoids).

If $\mathcal{G}^{\prime}$ is a countable group $\Gamma$ (seen as a groupoid
over a point), then every p.m.p. action of $\Gamma$ on $X$ gives rise to a
factor $\mathcal{G}_{\Gamma^{\prime}\curvearrowright X}\to\Gamma$ sending
$(\gamma,x)$ to $\gamma$, and conversely every factor $\mathcal{G}\to\Gamma$
arises this way. In general one can interpret factors
$\mathcal{G}\to\mathcal{G}^{\prime}$ as _p.m.p. actions of the p.m.p. groupoid
$\mathcal{G}^{\prime}$ on $X$_ (not to be confused with the different notion
of actions – not p.m.p. – of a groupoid considered in Section 2.5). Free
actions correspond to factors ${\mathcal{R}}\to\mathcal{G}^{\prime}$ where