1 Introduction
One of the most relevant problems in the study of countable Borel equivalence relations on standard Borel spaces is clarifying the relationship between amenability, meant in the sense of [Reference Jackson, Kechris and Louveau13] (see Definition 3.2), and hyperfiniteness, which asserts that the equivalence relation is an increasing union of Borel equivalence relations whose equivalence classes have finite cardinality. While it is well known that hyperfiniteness implies amenability (see [Reference Slaman and Steel25] and [Reference Jackson, Kechris and Louveau13]*Proposition 2.13), whether the converse holds remains a notoriously difficult open problem in the subject ([Reference Jackson, Kechris and Louveau13]*§6.2.B).
A related unsolved question is the one concerning the relation between hyperfiniteness and measure-hyperfiniteness. Recall that a countable Borel equivalence relation over a standard Borel space X is measure-hyperfinite if, for every Borel probability measure
$\mu $
over X, there is some Borel set
$A \subseteq X$
with
$\mu (A) = 1$
and such that the restriction of E to A is hyperfinite. It is currently not known whether measure-hyperfiniteness implies hyperfiniteness, and a positive answer would imply that amenability and hyperfiniteness are equivalent, since, by the celebrated Connes-Feldman-Weiss theorem [Reference Connes, Feldman and Weiss6], amenability implies measure-hyperfiniteness.
In this paper, we contribute to these lines of inquiry focusing on treeable Borel equivalence relations, namely relations that admit acyclic Borel graphings (the study of these relations finds a large space in the literature; see, e.g., [Reference Adams1, Reference Jackson, Kechris and Louveau13, Reference Gaboriau10, Reference Hjorth12, Reference Miller20, Reference Chen, Poulin, Tao and Tserunyan3]). Typical examples are the orbit equivalence relations originating from free actions of virtually free groups – that is groups that have a free subgroup of finite index – and our first main result confirms hyperfiniteness for a vast class of measure-hyperfinite equivalence relations of this form. In what follows, given a group action
$G \curvearrowright X$
, we denote by
$E_G^X$
the orbit equivalence relation associated to the action, that is,
$x E_G^X y$
if and only if there is
$g \in G$
such that
$gx = y$
, for
$x,y \in X$
.
Theorem 1. Let F be a countable virtually free group, let X be a
$\sigma $
-compact Polish space, and let
$F \curvearrowright X$
be a continuous free action. If
$E_{F}^X$
is measure-hyperfinite – in particular, if
$E_{F}^X$
is amenable – then it is hyperfinite.
The reader interested in other known instances of (necessarily amenable) actions of nonamenable groups giving rise to hyperfinite equivalence relations, is referred to the recent string of papers [Reference Marquis and Sabok18, Reference Karpinski14, Reference Przytycki and Sabok23, Reference Kunnawalkam Elayavalli, Oyakawa, Shinko and Spaas17, Reference Oyakawa22, Reference Naryshkin and Vaccaro21], where various ad hoc classes of actions – mainly boundary actions – are considered.
Theorem 1 is a corollary of a more general criterion for hyperfiniteness that provides a partial answer to the question posed in [Reference Jackson, Kechris and Louveau13, §6.4.C], asking whether countable Borel equivalence relations that are both amenable and treeable are hyperfinite. This simpler version of the question whether amenability implies hyperfiniteness is motivated by the well-known fact that hyperfinite countable Borel equivalence relations are treeable. We partially solve this problem under the assumption of a novel strong form of amenability – still implied by hyperfiniteness – which we call hyper-u-amenability (Definition 3.4).
Theorem 2. Let E be a countable Borel equivalence relation on a standard Borel space. If E is treeable and hyper-u-amenable, then it is hyperfinite.
Before discussing the concept of hyper-u-amenability in more detail, we present some examples, and some corollaries of Theorem 2. The first corollary is, as hinted before, Theorem 1 itself, since all the equivalence relations considered therein are hyper-u-amenable (Corollary 3.9).
Our second application relates to a special case of the problem whether amenability implies hyperfiniteness, formulated in a famous question by Weiss in [Reference Weiss27], asking if all actions of countable amenable groups induce hyperfinite orbit equivalence relations. Although the general case remains beyond reach, this question has been positively answered for various classes of amenable groups ([Reference Weiss27, Reference Slaman and Steel25, Reference Jackson, Kechris and Louveau13, Reference Gao and Jackson11, Reference Schneider and Seward24, Reference Conley, Jackson, Marks, Seward and Tucker-Drob5]).
As we will see in Proposition 3.10, hyper-u-amenability is satisfied by orbit equivalence relations of Borel actions of countable amenable groups, hence Theorem 2 allows to solve affirmatively Weiss’ question in the treeable case.
Corollary 3. Let
$G \curvearrowright X$
be a Borel action of a countable amenable group on a standard Borel space. If
$E_G^X$
is treeable, then it is hyperfinite.
Finally, we show that hyper-u-amenability is automatic for amenable equivalence relations that are Borel bounded in the sense of [Reference Boykin and Jackson2] (Proposition 3.12), and obtain the following.
Corollary 4. Let E be a countable Borel equivalence relation on a standard Borel space X. If E is treeable, amenable, and Borel bounded, then it is hyperfinite.
The concept of hyper-u-amenability is itself based on an auxiliary notion which we call u-amenability (Definition 3.1). U-amenability is modeled on the notion of amenability as defined in [Reference Jackson, Kechris and Louveau13, Definitions 2.11 and 2.12], but it applies to equivalence relations E on standard Borel spaces X equipped with an extended metric
$\rho $
– typically originating from a graphing of E (see Section 2) – and depends on the additional structure encoded by
$\rho $
. More precisely, u-amenability strengthens amenability by requiring uniform convergence to zero – hence the prefix “u-” – for the invariance condition on the probability measures assigned to different points in the same orbit (see §3 for details).Footnote
1
The focus on Borel extended metric spaces is motivated by the breakthrough on Weiss’ question obtained in [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5] with the introduction and study of Borel asymptotic dimension (Definition 2.2). This notion, developed in the context of Borel extended metric spaces, not only provides a criterion for hyperfiniteness, but it moreover allows to solve certain instances of the so-called Union Problem – which asks whether increasing countable unions of hyperfinite equivalence relations are hyperfinite. Since its introduction, it has been discovered that Borel asymptotic dimension has many more applications than just the Weiss’ question (see, e.g., [Reference Naryshkin and Vaccaro21]), and it plays a major role in this paper as well.
Theorem 2 is in fact a consequence of the more technical Theorem 5.2, which applies to countable Borel equivalence relations E on a standard Borel space X that admit an acyclic Borel graphing 
that has a finite uniform bound on the degree of all vertices. More precisely, Theorem 5.2 asserts that if such an E is u-amenable with respect to the shortest path metric
$\rho _{\mathcal {G}}$
on X, then the Borel asymptotic dimension of
$(X, \rho _{\mathcal {G}})$
is finite hence, in particular, E is hyperfinite by [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Theorem 1.7].
Broadly speaking, to prove Theorem 5.2 we exploit u-amenability to define a partial Borel orientation on the acyclic graphing
$\mathcal {G}$
, which can then be used to show
$\text {asdim}_B(X, \rho _{\mathcal {G}}) < \infty $
. The idea of using amenability to define a Borel orientation on a graph has precursors in the measure-theoretic setting. More specifically, if the Borel space in question is equipped with a probability measure, then any amenable equivalence relation is hyperfinite on a set of full measure by [Reference Connes, Feldman and Weiss6] and, if the relation is additionally equipped with the structure of an acyclic graph, amenability (or hyperfiniteness) is also equivalent to the so-called end selection. This means that for each connected component (which has the structure of a connected tree) one can select either a point in it or at most two points from its Gromov boundary, and this selection is measurable (see [Reference Adams1] and [Reference Jackson, Kechris and Louveau13, §3.6]). Note however that a direct application of these methods is not possible in the setting considered in this paper: the equivalence between end selection and hyperfiniteness fails in the purely Borel setting, as there are hyperfinite acyclic Borel graphs for which it is impossible to select at most two ends from each component in a Borel way ([Reference Miller19, Remark 5.11]). The Borel orientations we shall build are, in fact, only partial. Additionally, the techniques used in the aforementioned results rely on taking a Banach limit, which cannot be done in a Borel way.
One disadvantage of u-amenability is that it depends on the metric in question – in particular, an equivalence relation might have, a priori, one graphing which is u-amenable and another which is not. It turns out, however, that if an equivalence relation E has a graphing that is an increasing union of graphs generating u-amenable equivalence relations, then the same holds for any other graphing of E (Proposition 3.5). This can thus be regarded as an intrinsic property of the equivalence relation itself, and we refer to it as hyper-u-amenability (Definition 3.4).
This last notion brings us back to the most general version of our criterion for hyperfiniteness, Theorem 2, which follows from Theorem 5.2 exploiting the aforementioned key fact that the finite Borel asymptotic dimension permits to solve certain instances of the Union Problem (see Proposition 2.3).
Summary
The paper is organized as follows. In Section 2 we cover the preliminaries, while in Section 3 we introduce u-amenability and hyper-u-amenability and provide some examples of equivalence relations with these properties. In Section 4 we prove some intermediate lemmas and the main criterion needed to prove Theorem 5.2, whose proof is presented in Section 5, along with the proofs of Theorem 2 (Corollary 5.3), Theorem 1, and Corollaries 3 and 4 (Corollary 5.4).
2 Preliminaries
2.1 Borel equivalence relations and Borel graphs
Let X be a standard Borel space. An equivalence relation E on X is Borel if
$E \subseteq X^2$
is Borel. The E-class of a point
$x \in X$
is denoted
$[x]_E$
. A Borel equivalence relation is finite (respectively countable) if all its equivalence classes are finite (respectively countable), and it is hyperfinite if it can be written as a union of an increasing sequence of finite Borel equivalence relations. Finally, a countable Borel equivalence relation E over X is measure-hyperfinite if, for every probability measure
$\mu $
over X, there exists some Borel subset
$A \subseteq X$
, with
$\mu (A) = 1$
, such that the restriction of E to A is hyperfinite.
Let X be a standard Borel space and let
$\rho $
be a Borel extended metric on X, that is a Borel metric
$\rho \colon X \times X \to [0, \infty ]$
that can also take value
$\infty $
. In this case, we call
$(X, \rho )$
a Borel extended metric space. For
$A \subseteq X$
and
$x \in X$
, we define
For
$r> 0$
and
$x \in X$
, we let
$B_\rho (x, r)$
denote the closed ball of radius r centered in x with respect to
$\rho $
. A Borel extended metric space is proper if
$| B_\rho (x,r) |< \infty $
for all
$x \in X$
and
$r> 0$
. Denote by
$E_\rho $
the Borel equivalence relation of finite distance
$\rho $
between points in X, that is
An equivalence relation E on a Borel extended metric space
$(X, \rho )$
is
$\rho $
-uniformly bounded if there exists
$r> 0$
such that every E-class has
$\rho $
-diameter smaller than r.
Given a subset
$R \subseteq X^2$
, we let 
and we write
$xRy$
as an abbreviation for
$(x,y) \in R$
, and
$x \neg R y$
for
$(x,y) \notin R$
. A Borel graph on X is a graph 
where R is a Borel subset of
$X^2$
that is symmetric, that is
$R = R^{-1}$
, and irreflexive, meaning that
$x \neg R x$
for all
$x \in R$
. Two vertices
$x,y \in X$
are R-adjacent if
$xRy$
. Given a vertex
$x \in X$
and an edge
$(y,z) \in R$
, we say that they are R-adjacent if either
$x=y$
or
$x =z$
. In both cases, we might drop “R-” and simply write adjacent if no confusion arises.
If
$\mathcal {G}$
is a Borel graph on X, let
$\rho _{\mathcal {G}}$
denote the Borel extended metric on X induced by the path distance, and abbreviate
$E_{\rho _{\mathcal {G}}}$
as
$E_{\mathcal {G}}$
. In this case, the equivalence class
$[x]_{E_{\mathcal {G}}}$
of
$x \in X$
, which we abbreviate as
$[x]_{\mathcal {G}}$
, is the connected component of x in
$\mathcal {G}$
. Given
$q_0, q_1 \in R$
, say
$q_0 = (x_0, x_1)$
and
$q_1 = (y_0, y_1)$
we define
For a vertex
$x \in X$
, the degree of x is the value
The graph
$\mathcal {G}$
is locally finite if
$\deg _{\mathcal {G}}(x) < \infty $
for all
$x \in X$
. Vertices of degree 1 are called leaves and the set of all leaves in
$\mathcal {G}$
is denoted
$\mathrm {leaves}(\mathcal {G})$
. The degree of
$\mathcal {G}$
is
A (Borel) graphing of a Borel equivalence relation
$E \subseteq X^2$
is a Borel graph
$\mathcal {G}$
on X such that
$E_{\mathcal {G}} = E$
. We say that E is treeable if there exists an acyclic graphing of E. The complete graphing of E is the Borel graph
$(X, E \setminus \Delta (X))$
, where
$\Delta (X) = \{(x, x) \in X^2 : x \in X\}$
is the diagonal of
$X^2$
.
Finally, for a subset
$Y \subseteq X$
and
$R \subseteq X^2$
, we write
$R|_Y$
for the restriction
$R \cap Y^2$
, and for a graph 
, we write
$\mathcal {G}|_Y$
for the graph
$(Y, R|_Y)$
.
2.2 Borel orientations and out-degree
A Borel orientation of
$\mathcal {G}= (X, R)$
is a Borel subset 
such that 
and 
. In other words, for every
$xRy$
, exactly one among 
and 
holds. The out-degree of a vertex
$x \in X$
is the value
We also define the out-degree of the pair 
as
Remark 2.1. Let 
be a Borel graph. Note that, in case
$\deg (\mathcal {G}) \in {\mathbb {N}} \cup \{\aleph _0\}$
, a standard application of the Lusin–Novikov uniformization theorem ([Reference Kechris15, Theorem 18.10]) shows that the maps
are Borel. In particular,
$\mathrm {leaves}(\mathcal {G}) = (\deg _{\mathcal {G}})^{-1}(1)$
is a Borel subset of X. Note moreover that, given a constant
$C> 0$
, the set
is Borel. Indeed, if
$\mathcal {G}_0$
is the complete graphing of
$E_{\mathcal {G}}$
, then
$Y = (\deg _{\mathcal {G}_0})^{-1}([0, C)])$
.
2.3 Borel asymptotic dimension
We recall the definition of Borel asymptotic dimension from [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5].
Definition 2.2 [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Definition 3.2].
Let
$(X,\rho )$
be a Borel extended metric space such that
$E_\rho $
is countable. The Borel asymptotic dimension of
$(X, \rho )$
, denoted
$\text {asdim}_B(X,\rho )$
, is the smallest
$d \in {\mathbb {N}}$
such that, for every
$r> 0$
, there exists a
$\rho $
-uniformly bounded Borel equivalence relation E on X with the property that, for every
$x \in X$
, the ball
$B_\rho (x,r)$
intersects at most
$d+1$
classes of E, and it is
$\infty $
if no such d exists.
Finite Borel asymptotic dimension is one of the main tools for accessing hyperfiniteness in this paper. Finite Borel asymptotic dimension provides, moreover, a tame framework where certain instances of the Union Problem can be solved affirmatively. This is synthesized in a precise manner in [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Theorem 7.3]. The proposition below isolates a specific instance of this result, in the context of Borel graphs.
Proposition 2.3. Let 
be locally finite Borel graphs and
$R_n \subseteq R_{n+1}$
, for all
$n \in {\mathbb {N}}$
. Suppose that
$\text {asdim}_B (X, \rho _{\mathcal {G}_n}) < \infty $
for all
$n \in {\mathbb {N}}$
. Then 
is hyperfinite.
Proof. Since
$R_n \subseteq R_{n+1}$
, we have
$$\begin{align*}\rho_{\mathcal{G}_{n+1}} \le \rho_{\mathcal{G}_n}. \end{align*}$$
The conclusion then directly follows from [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Theorem 7.3].
2.4 Schreier graphs and orbit equivalence relations
Let G be a group, let X be a standard Borel space, and let
$G \curvearrowright X$
be an action. The orbit equivalence relation
$E_G^X$
on X is defined as
$$ \begin{align*} x E_G^X y \text{ if and only if there is }g \in G \text{ such that }gx = y. \end{align*} $$
The relation
$E_G^X$
is countable if G is countable, and it is Borel if
$G \curvearrowright X$
is a Borel action. We recall that if G is a virtually free group – meaning that G has a free subgroup of finite index – and the action
$G \curvearrowright X$
is free, then
$E_G^X$
is treeable (see, e.g., [Reference Cohen4, Theorem 55 on p. 240]).
If S is a subset of G, the induced Schreier graph
$ \mathrm {Sch}(X, S)$
on X is defined by putting an edge between any distinct
$x,y \in X$
such that there is
$s \in S \cup S^{-1} \setminus \{ e \}$
with
$sx = y$
. If S is a generating set for G then
$E_{\mathrm {Sch}(X,S)} = E_G^X$
.
3 U-amenability and hyper-u-amenability
In this section we introduce u-amenability and hyper-u-amenability and provide some examples of equivalence relations with these properties.
Definition 3.1. Let
$(X,\rho )$
be a Borel extended metric space and let E be a countable Borel equivalence relation on X. We say that E is u-amenable with respect to
$\rho $
if
$E \subseteq E_\rho $
and if there are Borel maps
$$ \begin{align*} \lambda_n \colon E \to \mathbb{R}_{\ge 0}, \quad n \in {\mathbb{N}}, \end{align*} $$
such that, with the abbreviation 
,
-
1.
$\lambda _{n,x} \in \ell ^1([x]_{E})$
and
$\| \lambda _{n,x} \|_1 = 1$
for every
$n \in {\mathbb {N}}$
and
$x \in X$
, -
2.
$\sup _{\{ (x,y) \in E : \rho (x,y) < r \}} \| \lambda _{n,x} - \lambda _{n,y} \|_1 \to 0$
as
$n \to \infty $
, for every
$r> 0$
.
A Borel graph 
is u-amenable if
$E_{\mathcal {G}}$
is u-amenable with respect to
$\rho _{\mathcal {G}}$
. Note that, in this case, (2) is equivalent to
$$ \begin{align*} \sup_{ (x,y) \in R } \| \lambda_{n,x} - \lambda_{n,y} \|_1 \to 0, \quad n \to \infty. \end{align*} $$
The prefix “u-” stands for uniform, and emphasizes the difference between our definition and the more well-known 1-amenability – or simply amenability – for a countable Borel equivalence relation E introduced in [Reference Jackson, Kechris and Louveau13, Definition 2.12], which requires the existence of Borel functions
$\lambda _n \colon E \to \mathbb {R}_{\ge 0}$
as in Definition 3.1, but where condition (2) above is replaced by a weaker and, so to speak, pointwise condition. We recall it below.
Definition 3.2 [Reference Jackson, Kechris and Louveau13, Definitions 2.11 and 2.12].
Let X be a standard Borel space and let E be a countable Borel equivalence relation on X. We say that E is 1-amenable, or simply amenable, if there are Borel maps
$$ \begin{align*} \lambda_n \colon E \to \mathbb{R}_{\ge 0}, \quad n \in {\mathbb{N}}, \end{align*} $$
such that, with the convention 
,
-
1.
$\lambda _{n,x} \in \ell ^1([x]_{E})$
and
$\| \lambda _{n,x} \|_1 = 1$
for every
$n \in {\mathbb {N}}$
and
$x \in X$
, -
2.
$\| \lambda _{n,x} - \lambda _{n,y} \|_1 \to 0$
, as
$n \to \infty $
, whenever
$xEy$
.
The next lemma, which we isolate for later use, implies that u-amenability is preserved when taking subequivalence relations or subgraphs.
Lemma 3.3. Let X be a standard Borel space and let E be a countable Borel equivalence relation on X. Suppose that
$X_0 \subseteq X$
is a Borel subset, that
$\rho _0$
is an extended Borel metric on
$X_0$
, and let
$E_0$
be a countable Borel equivalence relation on X such that
$E_0 \subseteq E \cap E_{\rho _0}$
. Suppose finally that there are Borel maps
$$ \begin{align*} \lambda_n \colon E \to \mathbb{R}_{\ge 0}, \quad n \in {\mathbb{N}}, \end{align*} $$
such that
$\lambda _{n,x} \in \ell ^1([x]_{E})$
,
$\| \lambda _{n,x} \|_1 = 1$
and, for every
$r> 0$
,
$$ \begin{align} \sup_{\{ (x,y) \in E_0 : \rho_0(x,y) < r \}} \| \lambda_{n,x} - \lambda_{n,y} \|_1 \to 0, \quad n \to \infty. \end{align} $$
Then
$E_0$
is u-amenable with respect to
$\rho _0$
. In particular, if 
is a u-amenable Borel graph and 
is a Borel graph with
$R_0 \subseteq R$
, then
$\mathcal {G}_0$
is also u-amenable.
Proof. Use the Lusin–Novikov uniformization theorem ([Reference Kechris15, Theorem 18.10]) to find Borel functions
$F_k \colon X \to X$
, for
$k\in {\mathbb {N}}$
, such that
$E = \{(x,y) \in X^2 : \exists k \, (y = F_k(x)) \}$
. Consider the following two Borel functions
$$ \begin{align*} \begin{aligned}[c] N \colon E & \to {\mathbb{N}} \\ (x,y) &\mapsto \min \{k : x E_0 F_k(y) \}, \end{aligned} \qquad \begin{aligned}[c] P \colon E &\to X \\ (x,y) &\mapsto F_{N(x,y)}(y). \end{aligned} \end{align*} $$
For every
$n \in {\mathbb {N}}$
, define finally the Borel functions
$$ \begin{align*} \lambda^{\prime}_n \colon E_0 &\to \mathbb{R}_{\ge 0} \\ (x,y) & \mapsto \sum_{\substack{z \in [x]_{E}, \\ P(x, z) = y }}\lambda_{n,x}(z). \end{align*} $$
The sequence
$(\lambda ^{\prime }_n)_{n \in {\mathbb {N}}}$
witnesses that
$E_0$
is u-amenable with respect to
$\rho _0$
. Indeed, given
$n\in {\mathbb {N}}$
and
$x \in X_0$
, we have
$$ \begin{align*} \| \lambda^{\prime}_{n,x} \|_1 = \sum_{y \in [x]_{E_0}} \lambda^{\prime}_{n,x}(y) = \sum_{y \in [x]_{E_0}} \sum_{\substack{z \in [x]_{E}, \\ P(x, z) = y }}\lambda_n(x, z) = \sum_{y \in [x]_{E}} \lambda_{n,x}(y) = \| \lambda_{n,x} \|_1 = 1. \end{align*} $$
Finally, to verify that the sequence
$(\lambda ^{\prime }_n)_{n \in {\mathbb {N}}}$
satisfies item (2) of Definition 3.1, note that if
$xE_0y$
and
$w \in [x]_{E}$
then
$N(x, w) = N(y,w)$
by definition of N, hence
$P(x,w) = P(y, w)$
. This, in particular, implies that
$$ \begin{align} \sum_{\substack{w \in [x]_{{E}}, \\ P(x,w) = z}} \lambda_{n,x}(w) - \sum_{\substack{\bar w \in [y]_{{E}}, \\ P(y,\bar w) = z}} \lambda_{n,y} (\bar w) = \sum_{\substack{w \in [x]_{{E}}, \\ P(x,w) = z}} \lambda_{n,x}(w) - \lambda_{n,y}(w), \end{align} $$
which in turn gives
Item (2) of Definition 3.1 for
$(\lambda ^{\prime }_n)_{n \in {\mathbb {N}}}$
hence follows by (3.1).
Definition 3.4. Let X be a standard Borel space. A countable Borel equivalence relation E on X is hyper-u-amenable if the complete graphing of E is an increasing union of Borel u-amenable graphs on X, that is, if there are u-amenable Borel graphs 
, for
$n \in {\mathbb {N}}$
, such that
$R_n \subseteq R_{n+1}$
and
$E = \bigcup _{n \in {\mathbb {N}}} R_n$
.
We show in the next proposition that, if E admits a graphing which is an increasing union of u-amenable graphs, then all graphings of E, including the complete one, have this property. We moreover prove that the u-amenable graphs can always be assumed to have finite degree.
Proposition 3.5. Let X be a standard Borel space and let
$E \subseteq X^2$
be a countable Borel equivalence relation. Suppose that E has a Borel graphing
$\mathcal {H}$
which is increasing union of u-amenable Borel graphs. If
$\mathcal {G}$
is any other graphing of E, then
$\mathcal {G}$
is an increasing union of u-amenable Borel graphs of finite degree. In particular, E is hyper-u-amenable.
Proof. Let 
be a graphing witnessing hyper-u-amenability of E. There exist therefore, for
$n \in {\mathbb {N}}$
, u-amenable Borel graphs 
such that
$$\begin{align*}S = \bigcup_{n=1}^\infty S_n, \quad S_n \subseteq S_{n+1}, \quad n \in {\mathbb{N}}. \end{align*}$$
Without loss of generality, we may assume that each
$\mathcal {H}_n$
has finite degree. To see this, note that by [Reference Feldman and Moore8] there is a countable group G, enumerated as
$\{ g_n \} _{ n\in {\mathbb {N}}}$
, and a Borel action
$G \curvearrowright X$
such that
$E = E_G^X$
. Denote by
$T_n$
the edge relation of the Schreier graph
$\mathrm {Sch}(X, \{ g_0, \dots , g_{n} \})$
. Given
$n \in {\mathbb {N}}$
, the graph 
has finite degree since
$\mathrm {Sch}(X, \{ g_0, \dots , g_{n} \})$
does, it is u-amenable by Lemma 3.3 since
$\mathcal {H}_n$
is, and we moreover have both
$S_n \cap T_n \subseteq S_{n+1} \cap T_{n+1}$
and
$S = \bigcup _{n \in {\mathbb {N}}} (S_n \cap T_n)$
.
Suppose next that 
is another graphing of E, define
and set 
. We show that
$\mathcal {G}$
is an increasing union of the
$\mathcal {G}_n$
’s, and that these are u-amenable and with finite degree.
The inclusion
$R_n \subseteq R_{n+1}$
follows since
$$ \begin{align} \rho_{\mathcal{H}_{n+1}} \le \rho_{\mathcal{H}_n}. \end{align} $$
Since
$E = E_{\mathcal {G}} = E_{\mathcal {H}}$
, for every edge
$xRy$
there is a sufficiently large n such that
$xE_{\mathcal {H}_n}y$
, that is,
$\rho _{\mathcal {H}_n}(x, y) < \infty $
. By (3.3), it then follows that
$x R_m y$
with
$m = \max \{ n, \rho _{\mathcal {H}_n}(x, y) \}$
, and thus
$R = \bigcup _{n \in {\mathbb {N}}} R_n$
. Moreover, the inequality
$$ \begin{align} \rho_{\mathcal{G}_n} \ge \frac{1}{n}\rho_{\mathcal{H}_n}. \end{align} $$
implies
$\deg (\mathcal {G}_n) \le \deg (\mathcal {H}_n)^n < \infty $
. Finally, (3.4) and Lemma 3.3, applied to
$E_{\mathcal {H}_n}$
and
$E_{\mathcal {G}_n}$
, imply that the graphs
$\mathcal {G}_n$
are u-amenable.
3.1 Examples
3.1.1 Topologically amenable actions
The first class of u-amenable equivalence relations that we consider comes from continuous, topologically amenable actions of finitely generated groups on compact spaces, of which we briefly recall the definition.
Definition 3.6. Let G be a countable group and X a Polish space. A continuous action
$G \curvearrowright X$
is topologically amenable if for every compact subset
$K \subseteq X$
there are continuous maps
$$ \begin{align*} p_n \colon X \times G \to \mathbb{R}_{\ge 0}, \quad n \in {\mathbb{N}}, \end{align*} $$
such that, with the convention 
,
-
1.
$p_{n,x} \in \ell ^1(G)$
and
$\| p_{n,x} \|_1 = 1$
for every
$n \in {\mathbb {N}}$
and
$x\in X$
, -
2.
$\sup _{x \in K} \| g\cdot p_{n,x} - p_{n,gx} \|_1 \to 0$
as
$n \to \infty $
, for every
$g \in G$
, and where
$g \cdot p_{n,x}(h) = p_{n,x}(g^{-1}h)$
.
Proposition 3.7. Let G be a countable group and X a Polish space. Suppose that
$G \curvearrowright X$
is a continuous, topologically amenable action, let
$K \subseteq X$
be a compact set, and let
$S \subseteq G$
be finite. Then the graph
$\mathrm {Sch}(X, S)|_K$
is u-amenable.
Proof. Let
$(p_n)_{n \in {\mathbb {N}}}$
be a sequence of maps witnessing topological amenability of
$G \curvearrowright X$
for
$K \subseteq X$
, and define the Borel maps
$$ \begin{align*} \lambda_n \colon E_G^X &\to \mathbb{R}_{\ge 0} \\ (x,y) &\mapsto \sum_{\substack{g \in G \\ g^{-1}x = y}} p_{n,x}(g). \end{align*} $$
Then the sequence
$\lambda _n$
satisfies the assumption of Lemma 3.3 with
$E = E_G^X$
,
$E_0 = E_{\mathrm {Sch}(X, S)|_K}$
and
$\rho _0 = \rho _{\mathrm {Sch}(X, S)|_K}$
, hence the graph
$\mathrm {Sch}(X, S)|_K$
is u-amenable.
We report a result from [Reference Frisch, Kechris, Shinko and Vidnyánszky9, Appendix A] which, when combined with the Connes–Feldman–Weiss theorem, relates topological amenability to measure-hyperfiniteness of
$E_G^X$
in the case of continuous actions on Polish spaces.
Theorem 3.8 ([Reference Connes, Feldman and Weiss6],[Reference Frisch, Kechris, Shinko and Vidnyánszky9, Appendix A]).
Let
$G \curvearrowright X$
be a continuous action of a countable group on a Polish space. The following are equivalent:
-
1.
$G \curvearrowright X$
is topologically amenable, -
2.
$E_G^X$
is measure-hyperfinite and every stabilizer is amenable.
We use the equivalence above to prove the following corollary of Proposition 3.7.
Corollary 3.9. Let
$G \curvearrowright X$
be a continuous action of a countable group on a
$\sigma $
-compact Polish space. If the stabilizer of every point is amenable and
$E_G^X$
is measure-hyperfinite, then
$E_G^X$
is hyper-u-amenable. In particular,
$E_G^X$
is hyper-u-amenable whenever
$E_G^X$
is measure-hyperfinite (e.g., if
$E_G^X$
is amenable) and the action is free.
Proof. By Theorem 3.8, the action
$G \curvearrowright X$
is topologically amenable. Since X is
$\sigma $
-compact, there is an increasing sequence of compact sets
$K_n$
such that
$X = \bigcup _{n \in {\mathbb {N}}} K_n$
. Let
$\{ g_n \}_{n \in {\mathbb {N}}}$
be an enumeration of G and define
Each
$\mathcal {G}_n$
is u-amenable by Proposition 3.7, and since the sequence
$(\mathcal {G}_n)_{n \in {\mathbb {N}}}$
is increasing, and its union is the complete graphing of
$E_G^X$
, it follows that
$E_G^X$
is hyper-u-amenable.
3.1.2 Actions of amenable groups
Proposition 3.10. Let G be a countable amenable group, let X be a standard Borel space, and let
$G \curvearrowright X$
be a Borel action. Then
$E_G^X$
is hyper-u-amenable.
Proof. Let
$\{ g_n \}_{n \in {\mathbb {N}}}$
be an enumeration of G and let 
be the complete graphing of E. For every
$m\in {\mathbb {N}}$
consider the subgroup 
and the corresponding Schreier graph 
. Denote the edge relation on
$\mathcal {G}_m$
as
$R_m$
. Note that the graphs
$\mathcal {G}_m$
have finite degree, that
$R_m \subseteq R_{m+1}$
for all
$m \in {\mathbb {N}}$
, and that
$E_G^X \setminus \Delta (X) = \bigcup _{m \in {\mathbb {N}}} R_m$
. To see that
$E_G^X$
is hyper-u-amenable, it remains to show that all
$\mathcal {G}_m$
’s are u-amenable.
To do this, fix
$m \in {\mathbb {N}}$
, and let
$(F_{n})_{n \in {\mathbb {N}}}$
be a Følner sequence for the subgroup
$G_m$
. U-amenability of
$\mathcal {G}_m$
is then witnessed by the family
$(\lambda _n)_{n \in {\mathbb {N}}}$
of Borel functions defined as
$$ \begin{align*} \lambda_n \colon E_{\mathcal{G}_m} &\to \mathbb{R}_{\ge 0} \\ (x,y) &\mapsto \frac{1}{|F_n|} \left| \{ g \in F_n : gx = y \}\right|.\\[-38pt] \end{align*} $$
We remark that the proof above actually shows that if G is a finitely generated amenable group and S is some finite generating set, then the Schreier graph
$\mathrm {Sch}(X, S)$
is u-amenable.
3.1.3 Borel bounded equivalence relations
The last class of examples of hyper-u-amenable equivalence relations that we provide is that of amenable Borel bounded equivalence relations, of which we recall the definition below. For
$f , g \in {\mathbb {N}}^{{\mathbb {N}}}$
, we write
$f=^\ast g$
(and
$f \le ^\ast g$
) if
$f(n) = g(n)$
(respectively
$f(n) \le g(n)$
) for all but finitely many
$n \in {\mathbb {N}}$
.
Definition 3.11 [Reference Boykin and Jackson2].
Let X be a standard Borel space. A countable Borel equivalence relation
$E \subseteq X^2$
is Borel bounded, if for every Borel function
$\varphi \colon X \to {\mathbb {N}}^{{\mathbb {N}}}$
, there is a function
$\psi \colon X \to {\mathbb {N}}^{{\mathbb {N}}}$
such that
$\varphi (x) \le ^* \psi (x)$
for all
$x \in X$
, and that
$\psi (x) =^*\psi (y)$
whenever
$xEy$
.
Hyperfinite equivalence relations are Borel bounded ([Reference Boykin and Jackson2]) and, remarkably, it is not known whether every countable Borel equivalence relation is Borel bounded, although Thomas proved in [Reference Thomas26, Theorem 5.2] that equivalence relations that are not Borel bounded exist, if Martin’s conjecture on degree invariant Borel maps holds.
Proposition 3.12. Let X be a standard Borel space and let
$E \subseteq X^2$
be an amenable, Borel bounded, countable Borel equivalence relation. Then E is hyper-u-amenable.
Proof. Let
$\lambda _n \colon E \to \mathbb {R}_{\ge 0}$
be a sequence of Borel functions witnessing amenability of E, so in particular
$\lambda _{n,x} \in \ell ^1([x]_{E})$
and
$\| \lambda _{n,x} \|_1 = 1$
for every
$n \in {\mathbb {N}}$
and
$x \in X$
, and
$$\begin{align*}\| \lambda_{n,x} - \lambda_{n,y} \|_1 \to 0, \quad n \to \infty, \text{ whenever }xEy. \end{align*}$$
Let G be a countable group, enumerated as
$\{ g_n \}_{n\in {{\mathbb {N}}}}$
, along with a Borel action
$G \curvearrowright X$
such that
$E = E_G^X$
([Reference Feldman and Moore8]). Define the Borel function
$\varphi \colon X \to {\mathbb {N}}^ {\mathbb {N}}$
as
By Borel boundedness there exists a Borel map
$\psi : X \to {\mathbb {N}}^{{\mathbb {N}}}$
such that
$\psi (x) =^* \psi (y)$
if
$x E y$
, and that
$\varphi (x) \le ^* \psi (x)$
for all
$x \in X$
.
For
$k \in {\mathbb {N}}$
, define a graph 
by setting
$x R_k y$
if
-
(a)
$y = g_ix$
and
$x = g_jy$
, for some
$i, j \le k$
, -
(b)
$\psi (x)(n) = \psi (y)(n)$
, for all
$n \ge k$
, -
(c)
$\max \{\varphi (x)(n), \varphi (y)(n)\} \le \psi (x)(n)$
, for all
$n \ge k$
.
It is clear that
$R_k \subseteq R_{k+1}$
for all
$k \in {\mathbb {N}}$
and that
$E = \bigcup _{k \in {\mathbb {N}}} R_k$
. It remains to show that each subgraph
$\mathcal {G}_k$
is u-amenable. To do so, given
$n \in {\mathbb {N}}$
and
$x \in X$
, define 
. We claim that this sequence witnesses u-amenability of
$\mathcal {G}_k$
, for any
$k\in {\mathbb {N}}$
. Indeed, note that if
$x R_k y$
and
$n \ge k$
, then
$\psi (x)(n) = \psi (y)(n)$
and
$\varphi (x)(n) \le \psi (x)(n)$
, hence
$$\begin{align*}\|\lambda^\prime_{n, x} - \lambda^\prime_{n, y}\|_1 = \|\lambda_{\psi(x)(n), x} - \lambda_{\psi(x)(n), y}\|_1 < \frac1n. \end{align*}$$
By the triangle inequality, we thus get that
$$\begin{align*}\|\lambda^\prime_{n, x} - \lambda^\prime_{n, y}\|_1 \le \frac{r}{n}, \quad n \ge k, \, x, y \in X \text{ s.t. } \rho_{\mathcal{G}_k}(x,y) \le r, \end{align*}$$
and therefore
$\sup _{\{ (x,y) \in E_{\mathcal {G}_k} : \rho _{\mathcal {G}_k}(x,y) < r \}} \| \lambda ^{\prime }_{n,x} - \lambda ^{\prime }_{n,y} \|_1 \to 0$
as
$n \to \infty $
, for every
$r> 0$
.
4 Graphs with partial orientations
Given a Borel graph 
with finite degree, in this section we provide technical conditions sufficient to deduce
$\text {asdim}_B(X, \rho _{\mathcal {G}}) < \infty $
.
This is done gradually: we first consider the case where there is a Borel orientation 
with 
, in which case a direct application of some results in [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5] implies that
$\text {asdim}_B (X,\rho _{\mathcal {G}}) \le 1$
(Proposition 4.1). We then relax our assumptions and show that
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 3$
if R admits partial Borel orientations such that the nonoriented edges can be chosen to be arbitrarily far away from each other (Lemma 4.2).
Finally, in Lemma 4.5 we relax even further our assumptions and prove the main technical result of the paper:
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 3$
holds if R can be partitioned in two sets,
$R_0 \sqcup R_1$
, such that
$R_0$
admits a Borel orientation with out-degree at most 1 and 
is an acyclic Borel graph with
$\deg (\mathcal {G}_1) \le 2$
verifying a series of other conditions. The resulting criterion will be essential to deduce finite Borel asymptotic dimension for treeable u-amenable equivalence relations in Theorem 5.2.
The intended setup is that of acyclic Borel graphs, and we recommend the reader keep this case in mind while attempting to gain some intuition on the hypotheses in the statements of this section.
4.1 Orientation with out-degree at most 1
In this subsection, we focus on graphs where a Borel orientation, or a partial, yet rather large, Borel orientation, exists.
Proposition 4.1. Let 
be a Borel graph with
$\deg (\mathcal {G}) < \infty $
. Suppose that there exists a Borel orientation 
such that 
. Then
$\text {asdim}_B (X,\rho _{\mathcal {G}}) \le 1$
.
Proof. Since 
has out-degree at most one, the following bounded-to-one Borel function
$f : X \to X$
is well-defined:
Since 
, we see that the Borel set
is equal to R. This means that the Borel graph 
is equal to
$\mathcal {G}$
, hence
$\text {asdim}_B (X,\rho _{\mathcal {G}}) \le 1$
by [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Corollary 8.3].
Lemma 4.2. Let 
be a Borel graph with
$\deg (\mathcal {G}) < \infty $
. Suppose that for each
$r> 0$
there is a symmetric Borel subset
$Q \subseteq R$
such that
-
1.
$\rho _{\mathcal {G}}(q_0, q_1)> r$
whenever
$q_0, q_1 \in Q$
represent distinct edgesFootnote
2
, -
2. the graph
$(X, R \setminus Q)$
admits a Borel orientation with out-degree at most 1.
Then
$\text {asdim}_B (X,\rho _{\mathcal {G}}) \le 3$
.
Proof. Fix
$r> 0$
. We aim to build a
$\rho _{\mathcal {G}}$
-uniformly bounded Borel equivalence relation
$E \subseteq E_{\mathcal {G}}$
such that
$B_{\rho _{\mathcal {G}}}(x, r)$
intersects at most four E-classes, for every
$x \in X$
. To do so, let
$Q \subseteq R$
be satisfying the assumptions of the lemma for
$2r$
, that is
$$ \begin{align} \rho_{\mathcal{G}}(q_0, q_1)>2 r \text{ whenever } q_0, q_1 \in Q \text{ are distinct. } \end{align} $$
Consider 
. By (2) and Proposition 4.1 we have
$\text {asdim}_B (X,\rho _{\mathcal {G}_0}) \le 1$
, which means that there is a
$\rho _{\mathcal {G}_0}$
-uniformly bounded (and thus
$\rho _{\mathcal {G}}$
-uniformly bounded) Borel equivalence relation E such that for every
$x \in X$
the ball
$B_{\rho _{\mathcal {G}_0}}(x, 2r)$
intersects at most two distinct E-classes. We claim that, for every
$x \in X$
, the ball
$B_{\rho _{\mathcal {G}}}(x, r)$
intersects at most 4 E-classes.
To see this, let
$Y \subseteq X$
be the set of all vertices that are adjacent to some edge in Q. Fix
$x \in X$
. If
$B_{\rho _{\mathcal {G}}}(x, r) \cap Y = \emptyset $
, then
$$ \begin{align*} B_{\rho_{\mathcal{G}}}(x, r) = B_{\rho_{\mathcal{G}_0}}(x, r) \subseteq B_{\rho_{\mathcal{G}_0}}(x, 2r) \end{align*} $$
and thus
$B_{\rho _{\mathcal {G}}}(x, r)$
intersects at most two E-classes.
Suppose next that
$B_{\rho _{\mathcal {G}}}(x, r) \cap Y \ne \emptyset $
. Then by (1') there is (up to symmetry) a unique edge
$ (y, z) \in Q$
such that at least one among y and z belongs to
$B_{\rho _{\mathcal {G}}}(x, r)$
. Without loss of generality, we may assume
$y \in B_{\rho _{\mathcal {G}}}(x, r)$
. In this case, again by (1'), we have
$$\begin{align*}B_{\rho_{\mathcal{G}}}(x, r) \subseteq B_{\rho_{\mathcal{G}}}(y, 2r) \subseteq B_{\rho_{\mathcal{G}_0}}(y, 2r) \cup B_{\rho_{\mathcal{G}_0}}(z, 2r). \end{align*}$$
We deduce that
$B_{\rho _{\mathcal {G}}}(x, r)$
intersects at most 4 different E-classes.
4.2 Acyclic graphs with degree at most 2
If 
is an acyclic Borel graph with
$\deg (\mathcal {G}) \le 2$
, then it is always possible to remove a very sparse set of edges so that the resulting graph has connected components whose size is uniformly bounded by a given constant. In Lemma 4.4 we prove that this can be done while also ensuring that the set of removed edges is Borel and far away from leaves.
Remark 4.3. Let 
be an acyclic Borel graph with
$\deg (\mathcal {G}) \le 2$
. Then each nontrivial connected component
$[x]_{\mathcal {G}}$
of
$\mathcal {G}$
is isomorphic to one of the following graphs, depending on the number of leaves it has:
-
(i) if
$|\mathrm {leaves}([x]_{\mathcal {G}})| = 0$
then
$[x]_{\mathcal {G}} \cong (\mathbb {Z}, S_{\mathbb {Z}} \cup S_{\mathbb {Z}}^{-1})$
, where , -
(ii) if
$|\mathrm {leaves}([x]_{\mathcal {G}})| = 1$
then
$[x]_{\mathcal {G}} \cong ({\mathbb {N}}, S_{{\mathbb {N}}} \cup S_{{\mathbb {N}}}^{-1})$
, where . -
(iii) if
$|\mathrm {leaves}([x]_{\mathcal {G}})| = 2$
then there is
$n \in {\mathbb {N}}$
such that
$[x]_{\mathcal {G}} \cong (\{1 ,\dots , n \}, S_n \cup S_n^{-1})$
, where .
,
.
.Set 
for
$i = 0, 1, 2$
. We then have
$X = X_0 \sqcup X_1 \sqcup X_2$
and each
$X_i$
is Borel. Indeed,
$X_2$
is Borel, being the set of vertices whose connected component is finite (see Remark 2.1),
$X_1$
is Borel since it is the set of vertices with infinite connected component and finite distance from
$\mathrm {leaves}(\mathcal {G})$
, and
$X_0$
is the complement of
$X_1 \sqcup X_2$
.
We will implicitly use these facts in the next proof.
Lemma 4.4. Let 
be an acyclic Borel graph with
$\deg (\mathcal {G}) \le 2$
and fix
$r> 0$
. There is a symmetric Borel set
$Q \subseteq R$
such that
-
1.
$\rho _{\mathcal {G}}(q_0, q_1)> r$
whenever
$q_0, q_1 \in Q$
represent distinct edgesFootnote
3
, -
2.
$\rho _{\mathcal {G}}(x,y) \ge r$
whenever
$x \in X$
is adjacent to an edge in Q, and
$y \in \mathrm {leaves}(\mathcal {G})$
, -
3.
$\left |[x]_{\mathcal {G}_0}\right | \le 2r +4$
, with , for any
$x \in X$
.
, for any 
Proof. We can split the proof in three cases, following the decomposition
$X = X_0 \sqcup X_1 \sqcup X_2$
as in Remark 4.3. Let 
for
$i = 0,1,2$
.
For
$X_0$
, namely the set of vertices whose connected component is infinite, consider the Borel graph
$(R_0, S)$
where, given two distinct
$q_0, q_1 \in R_0$
, we set
$q_0 S q_1$
if
$\rho _{\mathcal {G}}(q_0, q_1) \le r$
. The graph
$(R_0, S)$
has finite degree since
$\mathcal {G}$
does, hence by [Reference Kechris, Solecki and Todorcevic16, Propositions 4.2 and 4.3] there exists a maximal S-independent Borel set
$Q_0 \subseteq R_0$
, that is
$q_0 \neg S q_1$
for all
$q_0, q_1 \in Q_0$
and every
$q \in R_0$
is S-adjacent to some element in
$ Q_0$
. It then follows that
$Q_0 \cup Q_0^{-1}$
has the desired properties for
$(X_0, R_0)$
.
Next, in
$X_1$
, let
$Q_1$
be the set of all edges
$(x, y) \in R_1$
such that, for some nonzero
$k \in {\mathbb {N}}$
, one has
$$ \begin{align*} \rho_{\mathcal{G}}(x, \mathrm{leaves}(\mathcal{G})) = k(r+2),\ \rho_{\mathcal{G}}(y, \mathrm{leaves}(\mathcal{G})) = k(r+2) + 1. \end{align*} $$
Then
$Q_1 \cup Q_1^{-1}$
satisfies the required conditions for
$(X_1, R_1)$
.
Finally, in
$X_2$
, since the equivalence relation induced by
$(X_2, R_2)$
is finite and since
$\mathrm {leaves}(\mathcal {G})$
is a Borel set, using a Borel selector (see [Reference Kechris15, Theorem 12.16 and Exercise 18.14]) it is possible to find a Borel set
$A \subseteq X_2 \cap \mathrm {leaves}(\mathcal {G})$
such that A contains exactly one leaf from each connected component of
$(X_2, R_2)$
. One can then define
$Q_2$
as the set those edges
$(x, y) \in R_2$
such that, for some nonzero
$k \in {\mathbb {N}}$
,
$$ \begin{align*} \rho_{\mathcal{G}}(x,A) = k(r+2),\ \rho_{\mathcal{G}}(y, A) = k(r+2) + 1, \ \rho_{\mathcal{G}}(y, \mathrm{leaves}(\mathcal{G}) \setminus A) \ge r. \end{align*} $$
Then
$Q_2 \cup Q_2^{-1}$
is as required for
$(X_2, R_2)$
.
4.3 Main criterion
Lemma 4.5. Let 
be a Borel graph with
$\deg (\mathcal {G}) < \infty $
. Suppose that for every
$r> 0$
there exist two Borel graphs 
and 
such that
-
(C.1)
$R = R_0 \sqcup R_1$
, -
(C.2)
$\mathcal {G}_0$
admits a Borel orientation with out-degree at most 1, -
(C.3)
for all
$x \in X$
, -
(C.4)
$\mathcal {G}_1$
is acyclic, -
(C.5) if
$1 < |[x]_{\mathcal {G}_1}| < \infty $
and for every
$y \in \mathrm {leaves}(\mathcal {G}_1 \cap [x]_{\mathcal {G}_1})$
, then
$ |[x]_{\mathcal {G}_1}|> r$
.
with out-degree at most 1,
for all 
for every 
Then
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 3$
.
Proof. We aim to apply Lemma 4.2 to
$\mathcal {G}$
. In order to do so, fix
$r> 0$
and find Borel graphs 
and 
satisfying the assumptions of the present lemma for the value
$2r+4$
. In particular,
$\mathcal {G}_0$
and
$\mathcal {G}_1$
satisfy (C.1)-(C.4) and
Condition (C.3) entails
$\deg (\mathcal {G}_1) \le 2$
, hence we can apply Lemma 4.4 to find a symmetric Borel subset
$Q \subseteq R_1$
such that
-
(i)
$\rho _{\mathcal {G}}(q_0, q_1)> r$
whenever
$q_0, q_1 \in Q$
represent distinct edges, -
(ii)
$\rho _{\mathcal {G}_1}(x,y) \ge r$
whenever
$x \in X$
is
$R_1$
-adjacent to an edge in Q, and
$y \in \mathrm {leaves}(\mathcal {G}_1)$
, -
(iii)
$\left |[x]_{(X, R_1 \setminus Q)}\right | \le 2r+4$
for any
$x \in X$
.
Define 
. We show now how to construct a Borel orientation 
on
$\mathcal {G}_2$
such that 
is a Borel orientation of
$(X, R \setminus Q)$
with out-degree at most 1. In order to define such 
, consider the Borel sets (see Remark 2.1)
Condition (C.3) implies that if
$x \in Y_0$
and
$y \in [x]_{\mathcal {G}_1}$
has 
, then
$y\in \mathrm {leaves}(\mathcal {G}_1)$
. If there were two distinct leaves
$y_0,y_1\in [x]_{\mathcal {G}_1}$
with 
, for
$i = 0,1$
, then by (C.5') we would get
$|[x]_{\mathcal {G}_1}|> 2r+4$
. This fact, combined with (iii), is sufficient to deduce that, for every
$x \in X$
, there exists at most one vertex
$y \in [x]_{\mathcal {G}_2}$
with 
. In other words, if 
, then
$|A_0 \cap [x]_{\mathcal {G}_2}| = 1$
for every
$x \in Y_0$
.
On the other hand, since
$E_{\mathcal {G}_2}$
is a finite equivalence relation by (iii), and since finite Borel equivalence relations admit Borel selectors whose image is Borel (see [Reference Kechris15, Theorem 12.16 and Exercise 18.14]), there exists a Borel set
$A_1 \subseteq Y_1$
such that
$|A_1 \cap [x]_{\mathcal {G}_2}| = 1$
for every
$x\in Y_1$
.
Set 
. Since
$\deg (\mathcal {G}_2) \le 2$
, the following is a well-defined orientation on
$\mathcal {G}_2$
By construction, 
is a Borel orientation of
$(X, R \setminus Q)$
with out-degree at most 1.
In order to apply Lemma 4.2 and conclude the proof, it suffices to show that if
$(x_0, y_0), (x_1, y_1) \in Q$
are such that
$x_0 \ne x_1$
and
$x_0 \ne y_1$
, then
$\rho _{\mathcal {G}}(x_0, x_1)> r$
. Without loss of generality, we may assume that the shortest path in
$\mathcal {G}$
connecting
$x_0$
to
$x_1$
only has edges in
$R \setminus Q$
(note that the shortest path connecting
$x_0$
to
$x_1$
cannot be composed exclusively of edges in Q by (i), unless
$r < 1$
, in which case
$\rho _{\mathcal {G}}(x_0, x_1)> r$
is automatic). Arguing as in Proposition 4.1, one sees that the Borel function
$f \colon X \to X$
is well-defined. Since
$x_0, x_1$
, as well as the shortest path connecting them, are in the same connected component of
$(X,R \setminus Q)$
, and since 
has out-degree at most 1, it is possible to prove by induction on
$\rho _{\mathcal {G}}(x_0,x_1)$
that
$$ \begin{align} \rho_{\mathcal{G}}(x_0, x_1) = \min \{ n+m : f^n(x_0) = f^m(x_1) \}. \end{align} $$
Note that, by (ii),
$x_0$
is not a leaf of
$\mathcal {G}_1$
, hence by (C.3) we deduce 
. This implies in particular that either
$x_0 = f(x_0)$
or
$x_0 R_1 f(x_0)$
, and thus
$f(x_0) \in [x_0]_{\mathcal {G}_1}$
. The same argument can be inductively repeated to infer that
$$ \begin{align*} f^k(x_0) \in [x_0]_{\mathcal{G}_1} \text { and either } f^k(x_0) = f^{k+1}(x_0) \text{ or } f^k(x_0) R_1 f^{k+1}(x_0), \quad k= 0,\dots, \lceil r \rceil. \end{align*} $$
The same statement can be proved verbatim for
$x_1$
.
Thus, if
$[x_0]_{\mathcal {G}_1} \ne [x_1]_{\mathcal {G}_1}$
, then
$f^k(x_0) \ne f^j(x_1)$
for all
$0 \le k, j \le r$
. If, on the other hand,
$[x_0]_{\mathcal {G}_1} = [x_1]_{\mathcal {G}_1}$
, then condition (i) implies
$f^k(x_0) \ne f^j(x_1)$
whenever
$k+j \le r$
. In either case, using (4.1), we conclude that
$\rho _{\mathcal {G}}(x_0, x_1)> r$
.
5 U-amenability and finite Borel asymptotic dimension
In this section, we prove the main technical result of the paper, Theorem 5.2, asserting that a u-amenable acyclic Borel graph with finite degree has finite Borel asymptotic dimension, and thus induces a hyperfinite equivalence relation.
Before proceeding with the proof, we introduce some useful notation. Given a graph 
and
$xRy$
, define the graph
which is the graph obtained from
$\mathcal {G}$
after removing the edge
$xRy$
. Note that, in case
$\mathcal {G}$
is acyclic, then
$$ \begin{align*} [x]_{\mathcal{G}_{x,y}} = \{z \in [x]_{\mathcal{G}} \colon \rho_{\mathcal{G}}(z, x) < \rho_{\mathcal{G}}(z, y)\}, \, [y]_{\mathcal{G}_{x,y}} = \{z \in [x]_{\mathcal{G}} \colon \rho_{\mathcal{G}}(z, y) < \rho_{\mathcal{G}}(z,x)\}, \end{align*} $$
and moreover
$$ \begin{align} [x]_{\mathcal{G}} = [y]_{\mathcal{G}} = [x]_{\mathcal{G}_{x,y}} \sqcup [y]_{\mathcal{G}_{x,y}}. \end{align} $$
Finally, for
$\lambda \in \ell ^1([x]_{\mathcal {G}})$
and
$A \subseteq [x]_{\mathcal {G}}$
, we write
$\lambda (A)$
for the sum
$\sum _{x \in A} \lambda (x)$
.
Lemma 5.1. Let 
be an acyclic Borel graph and let
$\lambda : E_{\mathcal {G}} \to \mathbb {R}_{\ge 0}$
be a Borel function such that
$\lambda (x, \cdot )$
, which we abbreviate as
$\lambda _x$
, belongs to
$\ell ^1([x]_{\mathcal {G}})$
for all
$x \in X$
. Then the maps
$$\begin{align*}\begin{aligned}[c] \theta_0 \colon R &\to \mathbb{R} \\ (x,y) &\mapsto \lambda_{x}([x]_{\mathcal{G}_{x,y}}) \end{aligned} \qquad \begin{aligned}[c] \theta_1 \colon R &\to \mathbb{R} \\ (x,y) &\mapsto \lambda_{y}([y]_{\mathcal{G}_{x,y}}) \end{aligned} \end{align*}$$
are Borel.
Proof. It suffices to prove the statement for
$\theta _0$
, since
$\theta _1(x,y) =\theta _0(y,x)$
. By the Lusin–Novikov uniformization theorem ([Reference Kechris15, Theorem 18.10]) there are Borel functions
$F_n \colon X \to X$
, for
$n \in {\mathbb {N}}$
, such that
$E_{\mathcal {G}} = \{(x,y) \in X^2 : \exists n \, (y = F_n(x)) \}$
. We inductively define a sequence of Borel functions
$w_n \colon R \to \mathbb {R}$
as follows:
Since
$\mathcal {G}$
is acyclic, the sequence
$(w_n)_{n \in {\mathbb {N}}}$
pointwise converges to
$\theta _0$
, which is therefore Borel.
Theorem 5.2. Let 
be an acyclic Borel graph with
$\deg (\mathcal {G}) < \infty $
. If
$\mathcal {G}$
is u-amenable then
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 1$
. In particular,
$E_{\mathcal {G}}$
is hyperfinite.
Proof. We aim to apply Lemma 4.5 to
$\mathcal {G}$
. To do so, fix
$r> 0$
. By u-amenability there exists a Borel map
$$\begin{align*}\lambda \colon E_{\mathcal{G}} \to \mathbb{R}_{\ge 0} \end{align*}$$
such that
$\lambda _x \in \ell ^1([x]_{\mathcal {G}})$
with
$\| \lambda _x \|_1 = 1$
for all
$x \in X$
, and such that
$$ \begin{align} \| \lambda_x - \lambda_y \|_1 < \frac{1}{12}, \quad \text{if } \rho_{\mathcal{G}}(x, y) \le r +2, \, x,y \in X. \end{align} $$
Let
$\theta _0, \theta _1 \colon R \to \mathbb {R}_{\ge 0}$
be the maps defined as
which are Borel by Lemma 5.1 (see (5.1) for the definition of
$\mathcal {G}_{x,y}$
).
Consider the set of edges
The set
$R_0$
is Borel since
$\theta _0$
and
$\theta _1$
are. Given
$xRy$
we have
$$ \begin{align*} \left|(1 - \theta_0(x, y)) - \theta_1(x, y)\right| \stackrel{({5.2})}{=} \left|\lambda_x([y]_{\mathcal{G}_{x,y}}) - \lambda_y([y]_{\mathcal{G}_{x,y}})\right| \stackrel{({5.3})}{<} 1/12. \end{align*} $$
Hence, if
$xR_0y$
, then exactly one between either
$$ \begin{align} \theta_0(x, y)> 7/12\ \text{ and }\ \theta_1(x, y) < 5/12 \end{align} $$
or
$$ \begin{align} \theta_0(x, y) < 5/12 \ \text{ and }\ \theta_1(x, y)> 7/12 \end{align} $$
holds. Using (5.4)-(5.5), along with
$\theta _0(x,y) = \theta _1(y,x)$
, we define a Borel orientation 
by setting
Let 
and 
. We verify now that
$\mathcal {G}_0 = (X, R_0)$
with orientation 
and
$\mathcal {G}_1$
satisfy the five conditions of Lemma 4.5, which is enough to conclude the proof, since
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 3$
implies that
$\text {asdim}_B(X, \rho _{\mathcal {G}}) \le 1$
, by [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Theorem 1.1].
(C.1): this condition holds by definition.
(C.2): let
$x \in X$
and suppose that
$y_0, y_1 \in X$
are distinct such that 
and 
. As
$\mathcal {G}$
is acyclic, the trees
$[y_0]_{\mathcal {G}_{x, y_0}}$
and
$[y_1]_{\mathcal {G}_{x, y_1}}$
are disjoint subsets of
$[x]_{\mathcal {G}}$
, and therefore we have
which is a contradiction.
(C.3): suppose that
$y_0, y_1$
and
$y_2$
are three distinct points in
$[x]_{\mathcal {G}}$
such that either 
or
$x R_1 y_i$
holds for all
$i=0, 1, 2$
. Then
$[y_0]_{\mathcal {G}_{x, y_0}}, [y_1]_{\mathcal {G}_{x, y_1}}$
and
$[y_2]_{\mathcal {G}_{x, y_2}}$
are disjoint and we have
(C.4): this condition is automatic since
$\mathcal {G}$
is acyclic.
(C.5): assume that there are two leaves
$x_0, x_1$
in the same connected component
$[x]_{\mathcal {G}_1}$
of
$\mathcal {G}_1$
such that there are
$y_0, y_1 \in X$
with 
and 
. Note that
$[y_0]_{\mathcal {G}_{x_0, y_0}}$
and
$[y_1]_{\mathcal {G}_{x_1, y_1}}$
are disjoint. If
$\rho _{\mathcal {G}_1}(x_0, x_1) \le r$
then
$\rho _{\mathcal {G}_1}(y_0, y_1) \le r+2$
hence
This is a contradiction, hence
$\rho _{\mathcal {G}_1}(x_0, x_1)> r$
which in turn gives
$|[x]_{\mathcal {G}_1}|> r$
.
Hyperfiniteness of
$E_{\mathcal {G}}$
follows by [Reference Conley, Jackson, Marks, Seward and Tucker-Drob5, Theorem 1.7].
We put all pieces finally together and deduce Theorem 2, and its corollaries Theorem 1, Corollary 3, and Corollary 4.
Corollary 5.3. Let E be a countable Borel equivalence relation which is treeable and hyper-u-amenable. Then E is hyperfinite.
Proof. Let
$\mathcal {G}$
be an acyclic Borel graph such that
$E_{\mathcal {G}} = E$
. By Proposition 3.5 the graph
$\mathcal {G}$
is a union of an increasing sequence of u-amenable subgraphs
$\mathcal {G}_n$
that have finite degree. The graphs
$\mathcal {G}_n$
are acyclic, and therefore
$\text {asdim}_B(X, \rho _{\mathcal {G}_n}) < \infty $
for all
$n \in {\mathbb {N}}$
, by Theorem 5.2. The conclusion then follows by Proposition 2.3.
Corollary 5.4. Let X be a standard Borel space and let
$E \subseteq X^2$
be a treeable countable Borel equivalence relation. Suppose that either one of the following three assumptions holds:
-
1. E is measure-hyperfinite and
$E = E_G^X$
for an action
$G \curvearrowright X$
by a countable group such that the stabilizer of every point is amenable, and there is a Polish
$\sigma $
-compact topology on X for which such action is continuous, -
2.
$E = E_G^X$
for some Borel action
$G \curvearrowright X$
by a countable amenable group G, -
3. E is amenable and Borel bounded.
Then E is hyperfinite.
Acknowledgements
We thank Marcin Sabok and Anush Tserunyan for their helpful remarks on an earlier version of this work, which revealed that our methods leading to Theorem 2 also apply to actions of free groups with infinitely many generators and more generally of virtually free groups. We also thank Zoltán Vidnyánszky for helpful discussions and suggestions. We are finally grateful to the referee for their useful and pertinent remarks which sensibly improved the readability of the paper.
Competing interests
The author has no competing interest to declare.
Funding statement
Both authors were funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2044 – 390685587, Mathematics Münster – Dynamics – Geometry – Structure, the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 427320536 – SFB 1442, and by the ERC Advanced Grant 834267 – AMAREC. The first-named author was also partially funded by the Dynasnet European Research Council Synergy project – grant number ERC-2018-SYG 810115, as well as the Marvin V. and Beverly J. Mielke Endowed Fund through the Institute of Advanced Study.
Open access
