A nonamenable “factor” of a euclidean space
Ádám Timár
Alfréd Rényi Institute of Mathematics

arXiv:1712.08210v1 [math.PR] 21 Dec 2017

Reáltanoda u. 13-15.,
H-1053 Budapest
madaramit[at]gmail.com

Abstract
Answering a question of Benjamini, we present an isometry-invariant random partition of the euclidean space R3 into infinite connected indinstinguishable pieces, such that the adjacency graph defined
on the pieces is the 3-regular infinite tree. Along the way, it is proved that any finitely generated amenable
Cayley graph (or more generally, amenable unimodular random graph) can be represented in R3 as an
isometry-invariant random collection of polyhedral domains (tiles). A new technique is developed to
prove indistinguishability for certain constructions, connecting this notion to factor of iid’s.

1

Introduction

Definition 1. Let G be a finite or infinite graph. Say that the set P is a tiling of Rd that represents G (or
a representation by tiles, or tiling representation of G), if the following hold.
1. Every element of P is a connected open polytope (a tile) in R3 . A polytope may be unbounded, with
infinitely many hyperfaces.
2. The elements of P are pairwise disjoint, the union of their closures is R3 .
3. Every ball in Rd intersects finitely many elements of P.
4. Say that two elements of P are adjacent, if their closures share a d − 1-dimensional face. Then the
graph defined on P this way is isomorphic to G.
We call the elements of P pieces or tiles of P.
Representing a Cayley graph of a countable group G as a periodic tiling of Rd is not possible for most
G. A natural relaxation of periodicity is to take a random tiling, whose distribution is invariant under the
isometries of Rd . Instead of congruent tiles, one can ask for the probabilistic analogue of congruence, and
require the tiles to be indistinguishable.
This research was supported by a Marie Curie Intra European Fellowship within the 7th European Community Framework
Programme, by the Hungarian National Research, Development and Innovation Office, NKFIH grant K109684, and by grant
LP 2016-5 of the Hungarian Academy of Sciences.

1

Question 1.1. (Itai Benjamini) Is there an invariant measurable random tiling representation of T3 in R3
such that the tiles in this representation are indistinguishable?
Invariance is understood with regard to the isometries of R3 , but we will look at other possible interpretations as well. By the indistinguishability of the tiles we mean the following. Let X be the set of all open
subsets of the euclidean space R3 , and consider the Hausdorff metric on it. Suppose that some A ⊂ X is
Borel measurable, and is closed under isometries of R3 (i.e., if a set is in A then all its isometric copies are
also in A). One can think of A as the collection of subsets satisfying a certain measurable property: having
some given congruence class, boundedness, some given lower/upper density, various topological properties...
We say that the pieces of a random partition of R3 are indistinguishable if for any such A either every piece
of the partition is in A almost surely, or none of them. It is easy to check that if there are bounded tiles
with positive probability, then they are either all congruent, or they fail to be indistinguishable.
It is well known that if the infinite 3-regular tree T3 is embedded into Rd in an Aut(T3 )-invariant way
then the expected number of vertices in a fixed cube is finite; see Proposition 3.5 for a sketch of the proof of
this folklore statement. (From now on, Aut(G) will denote the automorphism group of a given graph G. If
G is a diagram, i.e. it has colored and oriented edges, then we only consider automorphisms that preserve
the orientations and colors.) It is not hard to prove that there exists no tiling as in Question 1.1 in R2 , see
Remark 6.1. Given all these negative results, one may expect that a partition as in the question does not
exist. However, we prove that the answer to the question is positive. Our construction works for any Rd ,
d ≥ 3; it is stated for d = 3 to make the proof a bit simpler. We mention that in his original formulation,
Benjamini did not require the tiles to be polyhedra, but any kind of domains. We included this condition in
the definition of a representation by tiles because our construction works even with this extra requirement.
Theorem 1.2. There exists a random tiling of R3 that represents T3 , has indistinguishable pieces, and
has a distribution that is invariant under the isometries of R3 . The representation can be viewed as an
Aut(T3 )-invariant map from V (T3 ) to the set of tiles.
The second part claims that the map from T3 to the tiles will be invariant under the automorphisms
of T3 . In fact, we will first construct such a map, and then show that the corresponding tiling is invariant
under the group of isometries Isom(R3 ) of R3 . To put it in a slightly simplified way, an important issue will
be the distinction between random maps from T3 that are Aut(T3 )-invariant, and maps whose image set in
Rd is Isom(R3 )-invariant. Section 3 will address some related questions.
A major ingredient is the following:
Theorem 1.3. Let G be a transitive amenable one-ended graph. Then there is an Isom(R3 )-invariant
random tiling of R3 that represents G, such that every tile is bounded. The representation can be viewed as
a map from V (T3 ) to the set of tiles, which is Aut(T3 )-invariant, moreover, is a factor of iid.
See Definition 6 for the definition of a factor of iid (fiid). We will prove the above theorem for the more
general case of amenable unimodular random graphs G; see Theorem 5.3.
Returning to the initial question, to what extent are Cayley graphs G representable as an invariant tiling
of Rd with indistinguishable tiles, our method gives a positive answer not only for T3 but also for all amenable
groups.
Theorem 1.4. Let G be a transitive amenable graph. Then there is a random tiling of R3 with indistinguishable tiles, such that the adjacency graph of the tiling is G, and such that the tiling is invariant under
2

the isometries of R3 . The representation can be viewed as an Aut(T3 )-invariant map from V (T3 ) to the set
of tiles.
In the remainder of this section, we sketch the proof of Theorem 1.2 from Theorem 1.3.
Observation (Damien Gaboriau)

The usual Cayley graph of the Baumslag-Solitar group BS(1,2)=

ha, b|a−1 ba = b2 i can be partitioned into connected pieces such that the adjecency graph between the pieces
is T3 .
Choose the pieces for this partition to be the orbits of the generator b. We will call them fibers. We leave
a formal proof that the adjacency graph on the fibers is T3 to the interested reader, see Figure 1.1 for an
illustration.

Figure 1.1: Part of the Cayley graph of BS(1,2). Red lines (“fibers”) as partition classes provide a partition
whose adjacency graph is T3 . (Image by Jens Bossaert.)

The proof of Theorem 1.2 is based on the following steps:
1. Represent BS(1,2)=: G in R3 as an isometry-invariant tiling, using Theorem 1.3.
2. Take the unions of tiles over each fiber in this representation (more precisely, the interior of the union
of their closures), to obtain a representation of T3 .
Much of the work will be in ensuring that the resulting tiles are in fact indistinguishable. Proving indistinguishability is usually highly non-trivial, see [7] for the case of the infinite components of Bernoulli percolation
on Cayley graphs. A definition of indistinguishable decorated connected components of an automorphisminvariant random subgraph (percolation) of an underlying Cayley graph will be needed, which will be similar
to our definition of indistinguishable tiles from a tiling, as above. Components of an invariant random
subgraph of a Cayley graph turn into a unimodular random graph, when looking at the component of the
origin, with the rest of the Cayley graph thought of as a (unimodular) decoration. Indistinguishability then
transforms into ergodicity (extremality) of this unimodular probability measure. We will make the component of a fixed origin (as a unimodular decorated graph) be ergodic, instead of directly showing the slightly
weaker claim that the components of the percolation are indistinguishable. The advantage of addressing
this property is that the usual definition of indistinguishability uses the automorphisms of the undelying
graph while ergodicity of unimodular measures does not refer to that. We will have different graphs G and
3

H on the same vertex set. A subset of the vertex set induces a set of edges in H and in G as well. We
will switch from viewing it as a subgraph of H, with some decoration from G and the rest of H, to viewing
it as a subgraph of G with some decoration from H and the rest of G. When doing so, the definition of
indistinguishability that is independent of the underlying graph (G or H) will be useful. See Definitions 3
and 5.
The construction in Theorem 1.3 is such, that instead of directly partitioning R3 into tiles whose adjacency
graph is G, we will map to each vertex of G a tile in R3 , together with a “scenery” (which is the rest of the
tiling, from the viewpoint of this tile). This map will be a fiid from G. The usefulness of fiid constructions
may be surprising in this setup, since the main question is not directly connected to locality or graph
convergence. The reason that a big part of our construction needed to be fiid is because of our way of
proving indistinguishability of the final tiles in the representation of T3 . If we have a percolation on a Cayley
graph or diagram G with indistinguishable infinite components (pieces), and have any fiid decoration of
these vertices, the resulting decorated pieces will also be indistinguishable. (For the definition of a Cayley
diagram, see the paragraph before Lemma 2.2 and see Definition 3 for indistinguishability in the case of
(decorated) graphs.) This claim is proved in Lemma 2.2, which we call “Decoration lemma”. Applying it to
the (deterministic, but Aut(G)-invariant) partition into fibers of the Cayley diagram BS(1,2), we obtain that
the tiling that we assign to BS(1,2) as a decoration will produce indistinguishable unions of tiles over the
fibers. This is almost what we need, except for that with this viewpoint we constructed an Aut(G)-invariant
partition of G, with tiles of R3 assigned to the fibers as an Aut(G)-invariant (fiid) decoration, but instead we
want the tiling to be invariant under the isometries of R3 . So the question is whether one can switch from
the Aut(G)-invariant object to an Isom(R3 )-invariant object. This will be guaranteed essentially by Lemma
3.3, which we called “Duality lemma”. Informally, the lemma says (in a somewhat more general context)
the following. Suppose that there is a random drawing of some Cayley diagram H on the vertex set V (G),
and the distribution of this random drawing is Aut(G)-invariant. (Note that the drawn edges of H may
have nothing to do with E(G), the latter only has importance when we define Aut(G)-invariance!) Now, we
can switch and view the random decoration H on G as the fixed graph, and G as the random decoration
on H. The lemma says that then this random copy of G on H will be Aut(H)-invariant. This duality is
close to what we need. First, the Aut(G)-invariant decoration of V (G) by tiles in R3 can be taken to be a
decoration by Z3 and some extra information that describes the tiles. The duality lemma tells us that this
extra information and G on Z3 is Aut(Z3 )-invariant. This can then be turned to be Isom(R3 )-invariant by
applying a uniform isometry from Isom(R3 )/Aut(Z3 ). (The setup of the Lemma 3.3 is more general, which is
needed because we do not actually draw Z3 on the entire V (G), but only on a subset of it. See the corollary
after the lemma for a less technical formulation.)
The paper is organized as follows. In the next section we provide the necessary definitions and the
proof of the “Decoration lemma”. The Duality lemma (Lemma 3.3) is presented in Section 3, together with
examples illustrating the need for the lemma. Theorem 1.3 will follow from the more general Theorem 5.3,
which claims that one-ended unimodular amenable graphs have representations by invariant random tilings
consisting of bounded tiles. (Note that here the tiles are not expected to be indistinguishable.) This will be
proved in Section 5. In that section, the special case when G is a one-ended unimodular tree is proved first,
and then it is extended to any one-ended amenable unimodular graph, using the fact that such graphs have
one-ended fiid spanning trees, [11]. For the proof that a one-ended unimodular tree T can be represented by
an invariant tiling, we will need a technical lemma, verified in Section 4. This lemma will provide us with
4

a fiid sequence of coarser and coarser partitions Pn of V (T ) such that “many of the” parts in the partition
are connected subgraphs of T with 2n points. With proper care, one can define on each such part a piece of
the cubic grid (as a fiid), and so that in the limit we get a copy of Z3 on V (T ). This grid can be extended
to a tiling as desired, using the usual embedding of Z3 in R3 . The importance of the connectedness of some
pieces in Pn will be coming from the fact that such pieces can be nicely represented by tiles within a cube
(as shown on Figure 5.1). These nice representations will be defined in such a way that their limit is the
representation of T by a tiling of R3 , as desired. Finally, Section 6 presents the proof of the main theorem,
whose sketch we have provided already. The Decoration lemma is applied therein, to ensure that the tiles
that represent T3 are indistinguishable. Here and in the proof of Theorem 5.3, one will need the Duality
lemma to obtain Isom(R3 )-invariance of the construction from the fact that it is Aut(G)-invariant.

2

Definitions; the “Decoration lemma”

The next few definitions can be found in [1], together with some equivalent characterizations.
Definition 2. (Unimodular random graphs) Let G∗ be the set of all finite-degree connected rooted
(multi)graphs up to rooted isomorphism. Define a distance on G∗ by d((G, o), (G0 , o0 )) := min{1/r : BG (o, r)
and BG0 (o0 , r) are rooted isomorphic}. This defines a compact topology on G∗ . Let G∗∗ be the set of finitedegree connected rooted graphs with another distinguished vertex, and up to isometries. Similarly to G∗ ,
a compact topology can be defined on G∗∗ . Let µ be some probability distribution on G∗ . We say that µ
defines a unimodular random graph if for every Borel function f : G∗∗ → R+ , the following is true
E(

X

X
f (G, x, y)) = E(
f (G, y, x))

y

(2.1)

y

where (H, x) is the random element of G∗ of distribution µ. The above equation is called the Mass Transport
Principle (MTP).
Definition 3. (Ergodic unimodular random graphs) Call a subset A ⊂ G∗ an invariant property, if it is
Borel measurable and closed under the change of root (that is, if (G, o) ∈ A and x ∈ V (G), then (G, x) ∈ A).
A unimodular random graph (Γ, o) is extremal or ergodic, if for every such A either (Γ, o) ∈ A almost surely
or (Γ, o) 6∈ A almost surely.
We first define decorated graphs. This will be equivalent to what is called marked graphs in [1], but it is
adjusted to our setting better.
Definition 4. (The space of decorated graphs, G∗deco ) Fix some complete separable metric space X.
Consider rooted graphs (G, o) together with some decoration of (G, o), where a decoration means a set V 0
of extra vertices and a set E 0 of extra edges or oriented edges on V (G) ∪ V 0 added to G, and some partial
coloring χ of V (G) ∪ V 0 ∪ E(G) ∪ E 0 with elements of X. Denote such a graph by (G, o; V 0 , E 0 , χ), but
we will often drop χ from the notation. Two such decorated rooted graphs will be equivalent if there is a
rooted isomorphism that maps them to each other, maps the extra vertices and extra edges into each other
isomorphically, and preserving the coloring from X. Call the space of these equivalence classes G∗deco . We
will usually refer to elements of G∗deco through representatives of the equivalence classes. Consider (G, o)
with decoration V 0 , E 0 as above and (Ḡ, ō) with decoration V̄ 0 , Ē 0 . Say that they are at distance at most
5

1/r if there is a rooted isomorphism that maps the r-neighborhood of o in (V (G) ∪ V 0 , E(G) ∪ E 0 ) to the rneighborhood of ō in (V (Ḡ)∪ V̄ 0 , E(Ḡ)∪ Ē 0 ), and in such a way that it isometrically maps the r-neighborhood
of o in G to the r-neighborhood of ō in Ḡ, and in such a way that the X-labels of the vertices and edges in
this ball that are mapped to each other differ by at most 1/r. (In particular, uncolored vertices and edges
are mapped bijectively to uncolored vertices and edges.)
The definition of ergodicity extends to decorated unimodular graphs without any change.
Let us mention that it is possible to have multiple decorations on a graph (or to further decorate a
decorated graph), by extending the space X in the natural way. One important example for us is when we
have a connected component C of the origin in some percolation ω on a graph G, and we look at (C, o) as a
rooted graph decorated with G, ω. Then we will further take some factor of iid decoration of C, which may
also use information from the decoration G, ω.
Let ω be some Aut(G)-invariant percolation (random subgraph) of a Cayley graph (or diagram) G.
Denote by Γ the infinite connected component of a fixed vertex o in ω. We may consider ω as a decoration
of the random graph (Γ, o). Referring to this as (Γ, o, ω), we will say that (Γ, o) is decorated with scenery
ω. The decorated graph (Γ, o, ω) is unimodular, see e.g. [1].
Definition 5. Say that ω has indistinguishable components almost surely, if (Γ, o) is ergodic. Say that the
components of ω are indistinguishable with scenery, if (Γ, o, ω) is ergodic.
Remark 2.1. There is a simple example of a random invariant tiling of Rd that represents T3 for d ≥ 2 if we
do not require the pieces to be indistinguishable. It has bounded partition classes of different scales (which
implies right away that some tiles can be distinguished, using their sizes). See Figure 2.1 for the intuitive
picture of the tiling. For simplicity, we do the construction of a T5 -partition in R2 . Consider a sequence of
i 2
i 2
2
random vectors (vi )∞
i=−∞ , such that vi ∈ [0, 2 ] and vi+1 − vi ∈ 2 Z . In other words, v0 ∈ [0, 1] is uniform,

for i < 0 define vi ≡ vi+1 mod 2i , and for i > 0 define vi+1 = vi + i , where i ∈ {0, 2i }2 is uniform. Define
sets of the form vi + w + 2i (1/5, 2/5) with w ∈ 2i Z2 and sets vi + w + 2i (3/5, 4/5) with w ∈ 2i Z2 . Let the
collection of all such sets be Ki . Finally, define Si to be the collection of sets K \ ∪{L̄ : L ∈ Ki−1 }, as K
ranges over Ki . Then ∪i Si is a translation-invariant T5 -partition. By applying a random uniform element
of the factor of Isom(R2 ) by its subgroup of translations, we can make it isometry-invariant.
Let G = (V (G), E(G)) be an arbitrary graph or decorated graphs. Put iid Lebesgue[0,1] random variables
on its vertices. Consider some decoration of V (G). Intuitively, we call it a factor of iid or fiid, if the value
of the decoration of every v ∈ V (G) is determined by the labels in a bounded neighborhood of G up to an
arbitrarily small error. That is, the decoration is determined locally, using the random labels. From now on,
we will reserve the word labelling to such a collection of iid Lebesgue[0, 1] numbers on the vertices used in a
fiid, to distinguish it from other maps from the vertex set, such as decorations or colorings.
Definition 6. Let X be some separable metric space, G = (V (G), E(G)) be an arbitrary graph with iid
Lebesgue[0,1] labels λ ∈ [0, 1]V (G) on its vertices. Say that a function f : (λ, o) 7→ x from [0, 1]V (G) × V (G)
to X is a factor of iid or fiid, if it is measurable, and for any isomorphism γ of G, f (γλ, γx) = f (λ, x).
See e.g. [6] for more details.
A uniform number c from [0, 1] can be used to define two independent uniform numbers c1 , c2 from
[0, 1]. Namely, if c = .ξ1 ξ2 ξ3 . . . is the binary expansion of c (so ξi ∈ {0, 1}), then c1 := .ξ1 ξ3 ξ5 . . . and
6

Figure 2.1: Representation of the 5-regular tree T5 in Rd by a tiling, which can be made Isom(Rd )-invariant
by applying a suitable random isometry to it.

c2 := .ξ2 ξ4 ξ6 . . . are iid uniform. Therefore, in fiid constructions, we often assume that there are more than
one random [0, 1]-labels on each vertex at our disposal, all independent from the others. Our construction of
fiid maps will be via some local algorithm, and for convenience we often do not formalize how to turn it into
a factor of iid rule. But it is always possible to turn such local rules into fiid: any additional randomness
that is needed locally, can be extracted from the iid labels on the vertices, and one could fix a rule for this
extraction that is applied for every vertex. E.g., we will make local choices from finite sets without specifying
the particular rule that will be used (e.g., choose the vertex of the set whose iid-label is the smallest).
Given some group G and a finite set of generators {s1 , . . . , sk }, a Cayley diagram is a graph on vertex set
G, and an oriented edge from x ∈ G to y ∈ G if xgi = y, in which case we color this edge by gi . A Cayley
graph is constructed from a Cayley diagram if we forget about the orientations and the colors of the edges.
We say that two Cayley diagrams are isomorphic if there is a graph isomorphism between them that also
preserves the orientations and colors of the edges. By a slight abuse of terminology, but without ambiguity,
we will use notation Z3 both for the group, the Cayley graph, and the Cayley diagram with respect to the
standard generators. It will always be clear from the context, which one is understood.
Lemma 2.2 (Decoration lemma). Let G be a Cayley graph or Cayley diagram, and ω be an Aut(G)-invariant
percolation. Let δ be some factor of iid decoration on G, ω, where the iid labels λ : V (G) → [0, 1] used for
the factor are independent from the percolation. Suppose that all the components (pieces) of ω are infinite
and indistinguishable. Then they are also indistinguishable in the full decoration of ω with the fiid.
It follows that for any fiid decoration of the fibers of B(1,2) (which are trivially indistinguishable subgraphs), the decorated fibers are indistinguishable.
The lemma is true more generally: ergodicity of a unimodular random (decorated) graph is preserved by
additional fiid decorations. To reduce the amount of technicalities needed, we decided to include only the
simpler version that we need here. The proof is far from surprising, only the necessary notation makes it
cumbersome.
7

Proof.

Proving by contradiction, suppose that there is some invariant event that (G, ω, (δ(λ, v))v∈V (G) )

satisfies with probability less than 1 and greater than 0. Applying δ −1 , we get an invariant event of probability
less than 1 and greater than 0. So it is enough to prove that (G, ω) decorated with the iid labels λ on V (G)
has indistinguishable decorated ω-components. We will prove the equivalent statement that the ω-component
of a fixed vertex o is ergodic as a unimodular graph with decoration G and λ.
For a vertex x ∈ V (G), let B(x, R) be the rooted ball of radius R around x in G. We think about
B(x, R) as a graph, but keep track of the root. From now on, let F be the σ-algebra for the percolation ω
on rooted graph (G, o), and F Λ be the product σ-algebra of F and that of the λ-labellings. Starting from o,
run delayed simple random walk on ω, which is defined as follows. If we are in a vertex x, choose uniformly
a G-neighbor y of x. If y is a neighbor of x in ω, then move to y, otherwise stay in x. Let Xn be the n’th
step of this walk; so X0 = o. One can view this random walk as a process on rooted graphs decorated with
ω (with root in the vertex where the walker is), and also as a process on rooted graphs decorated with ω
and λ. Both processes are stationary with respect to the delayed random walk (Theorem 4.1 in [1]).
Let I be the invariant σ-field of F with respect to the transition operator of the delayed simple random
walk, with probability space given by the percolation ω. Ergodicity of the percolation is equivalent to
saying that for every A ∈ F, E(1(A)|I) = P(A) almost everywhere. Our goal is to show that for every
AΛ ∈ F Λ , E(1(AΛ )|I Λ ) = P(AΛ ) almost everywhere. It is enough to show this for every cylinder event
AΛ . So let us assume that AΛ is determined by the restriction of ω and λ to B(o, R), with some R > 0.
Denote by B Ω (x) the pair (B(x, R), ω|B(x,R) ). Let B Ω,Λ (x) be B Ω (x) together with the labels from λ, that
is, (B(x, R), ω|B(x,R) , λ|B(x,R) ) = (B Ω (x), λ|B(x,R) ). Whether an (ω, λ) configuration on (G, o) is in AΛ is
determined by the configuration in B(o, R), that is, by B Ω,Λ (o). Therefore, we can say B Ω,Λ (o) ∈ AΛ without
ambiguity (but by a slight abuse of terminology), as an equivalent to (ω, λ) ∈ AΛ ) on (G, o).
By Birkhoff’s ergodic theorem we have
n


1X
1(B Ω,Λ (Xi ) ∈ AΛ ) → E 1(B Ω,Λ (Xi ) ∈ AΛ ) I Λ
n i=1

(2.2)

almost surely, and our goal is to prove that the right hand side is P(AΛ ) almost surely. In order to do
that, first we will show that the expectation of the left hand side converges to P(AΛ ), and then prove that
the second moment tends to 0. We can assume that AΛ consists of elements where B Ω is equal to some
fixed BˆΩ . Then we obtain the result for more general AΛ by taking disjoint unions. Let Λ0 be the set of λ
configurations on the R-ball of G, λ|B(o,R) , such that (B Ω (o), λ|B(o,R) ) = B Ω,Λ (o) is in AΛ . We know that
AΛ = {(BˆΩ , λ) : λ ∈ Λ0 }. By the independence of ω and λ, we have
P(AΛ ) = P(BˆΩ )P(Λ0 )

(2.3)

For simplicity, introduce ξi = 1(B Ω,Λ (Xi ) ∈ AΛ ).

Pn
Pn
Ω
∼ ˆΩ
Now, E( i=1 ξi ) = E
i=1 1(B (Xi ) = B )P(λ|B(Xi ,R) ∈ Λ0 ) . (Here probabilies and expectations
are understood jointly with respect to the unimodular measure and the random walk.) By the stationarity
of the delayed random walk, P(λ|B(Xi ,R) ∈ Λ0 ) = P(λ|B(Xj ,R) ∈ Λ0 ) = P(Λ0 ) for every i, j. Denote
N (n) := {i ∈ {1, . . . , n} : B Ω (Xi ) ∼
= BˆΩ } . Using the fact that the λ-labels and the random walk are

8

independent, we obtain
n
n
X
X

E(
ξi ) = E
1(B Ω (Xi ) ∼
= BˆΩ )P(λ|B(Xi ,R) ∈ Λ0 ) = E(N (n))P(Λ0 ).
i=1

(2.4)

i=1

Apply the ergodic theorem to our random walk with only the ω environment and forgetting about the λ. By

Pn
∼ BˆΩ ) → E 1(B Ω (o) =
∼ BˆΩ ) I =
assumption, the ω-environment is ergodic, therefore N n(n) = n1 i=1 1(B Ω (Xi ) =
P(ω̂) almost surely. Thus (2.4) can be rewritten as
n
1 X
E(
ξi ) → P(BˆΩ )P(Λ0 ).
n i=1

(2.5)

If distG (x, y) > 2R, then λ|B(x,R) is independent from λ|B(y,R) , and hence 1(B Ω,Λ (x) ∈ AΛ ) and 1(B Ω,Λ (y) ∈ AΛ )
are independent. It is well known that there is a constant c such that for any x ∈ V (G), the expected number
√
of steps X1 , . . . , Xn when we are in x is less than c n; see e.g. the argument after Theorem 8.2 in [8] that
Pn
works for any infinite graph. All this put together gives a second moment bound Var( n1 i=1 ξi ) ≤ Cn−1/2 .
Pn
Let us summarize what we have seen about n1 i=1 ξi . First, it is almost surely convergent, by (2.2).
Secondly, the second moment of this sequence tends to 0, so the limit random variable is almost surely a
constant. Then, by (2.5) and (2.3) this constant is P(AΛ ). We conclude that
n

1X
ξi = P(AΛ ).
n→∞ n
i=1
lim

Comparing this to (2.2), we obtain that the labelled graph has a trivial invariant σ-field I Λ . This is what
we wanted to prove.
The proof of the previous lemma inspired the following question, which seems to be open, somehow
surprisingly.
Conjecture 2.3. Let (G, o) be an ergodic unimodular random graph of bounded degrees, and (Xn ) be
delayed random walk started from o. Then the distribution of (G, Xt ) converges to the initial unimodular
measure almost surely.

3

Duality

To motivate the present section, we point at the fact that there exists an Isom(Rd )-invariant embedded copy
of T3 in Rd that is not Aut(T3 )-invariant (as a map from T3 to this copy). See the next proposition for
the proof. This observation highlights that there are two possible interpretations to having an “invariant”
copy of one space in the other, and these two may not always hold at the same time. Our constructions
for Theorems 1.2 and 1.3 will, however, work in both senses of invariance, thanks to the correspondance
established in this section.
Proposition 3.1. Let d ≥ 2. There exists an Isom(Rd )-invariant random embedded copy of the 5-regular
tree T5 in Rd that does not arise as the image set of an Aut(T5 )-invariant random map from T5 to Rd .

9

We mention that the random copy of T5 in the claim is such that the vertices form a point process of
infinite intensity. If one requires finite intensity, then there is no such random copy; see Proposition 3.5.
Proof. Choose a uniform point in each of the tiles in the construction of Remark 2.1, and connect two by a
straight line if and only if their tiles are adjacent. One almost surely gets an Isom(Rd )-invariant embedding
of T5 into Rd if d ≥ 3. (If d = 2, one can define some broken line segment between the two points in
adjacent tiles so that no two such segments intersect. We leave the details to the interested reader.) On
the other hand, suppose that φ were an Aut(T5 )-invariant random map from T5 to Rd whose image set were
the above-constructed random embedded copy of T5 . Then for every vertex v one could uniquely define a
“parent” w as the neighbor whose tile separates the tile of v from infinity. The rule to define the parent is
Aut(T5 )-invariant. But then every vertex would be the parent of 4 other vertices, and would have a single
parent, giving a MTP contradiction.
Let H and G be Cayley graphs or diagrams, and suppose that there exist random measurable sets

U ⊂ V (G) and E + = {x, y} : x, y ∈ U whose distribution is Aut(G)-invariant. If the graph (U, E + ) is
almost surely isomorphic to H, then we say that it is an invariant random decoration of U in G by H. If
E + is given as a fiid, then we call it a fiid random decoration of U in G by H.
We need to define several spaces of decorated graphs, which will make the beginning of this section a
bit technical. The reason why these seemingly similar definitions are needed is the following. Suppose we
have two connected graphs, one having red edges and the other one having blue edges, and that they share
some nonempty subset of their vertices. Then we can view their union as a multigraph with edges of two
colors, or, alternatively, one can view the red graph as a graph decorated by the blue edges, or vica versa.
These different viewpoints give different classes of rooted automorphisms, and hence the conditions for being
unimodular are also different for them. If, furthermore, one of the graphs is transitive and it is unimodular
with the above decoration, then one expects this decoration to be invariant with respect to automorphisms.
But in order to make sense of this claim, one again has to be careful because of potentially differing rooted
equivalences in the two viewpoints. This section clarifies such issues.
Let G be some transitive graph, and fix some metric space X. Say that two decorated copies (G, V 0 , E 0 )
and (G, V 00 , E 00 ) (as in Definition 4, with possible coloring χ by X on the edges and vertices, which we supress
in notation) are equivalent, if there is a bijection β : V (G) ∪ V 0 → V (G) ∪ V 00 such that β|V (G) is the identity,
and such that β defines a graph isomorphism between (V (G) ∪ V 0 , E(G) ∪ E 0 ) and (V (G) ∪ V 00 , E(G) ∪ E 00 ),
and β also preserves the colors from X. Let the set of all decorations of G up to this equivalence be Deco(G).
If G is a transitive graph and o is a fixed vertex, there is a natural map φ from Deco(G) to G∗deco .
For a representative (G, V 0 , E 0 , χ) = (G, V 0 , E 0 ) ∈ Deco(G), let φ(G, V 0 , E 0 ) be the equivalence class of
(G, o; V 0 , E 0 ) in G∗deco . (We hide the extra partial coloring decoration χ from the notation from now on.)
This definition does not depend on which representative (G, V 0 , E 0 ) we took for its class in Deco(G), because
the equivalence defining the elements of Deco(G) is more refined than the rooted isomorphisms in G∗deco .
Hence φ is well defined. But it may not be injective: to see this, let G be Z2 , and let ω1 be its decoration
where all horizontal edges {(x, y), (x + 1, y)} are colored red, and let ω2 be its decoration when all vertical
edges {(x, y), (x, y + 1)} are colored red. Then ω1 6= ω2 in Deco(G), but φ(ω1 ) = φ(ω2 ).
To continue the previous example, consider the random subgraph ω of Z2 that consists of all horizontal
edges with probability 1/2, and all vertical edges with probability 1/2. If we think about (Z2 , ω) as an

10

Aut(Z2 )-invariant probability measure on Deco(Z2 ), then it is supported on a two-point subset of Deco(Z2 ).
Looking at (Z2 , ω) as a (unimodular) random decorated graph from G∗deco , we have a probability measure
supported on a single point of G∗deco . It is easy to see that φ : Deco(G) → G∗deco maps two elements of
Deco(G) to the same point if and only if they are on the same orbit of the stabilizer of o in Aut(G). Hence,
if the stabilizer is trivial (e.g., when G is a Cayley diagram), then this map in injective, and one can use it
to pull back probability measures on G∗deco to Deco(G). In this case, a unimodular random element of G∗deco
gives rise to an invariant random decoration of G, through φ−1 , as presented in the next lemma. (Recall the
definition of φ from the beginning of the previous paragraph.)
Lemma 3.2. Let G be a Cayley diagram, φ be the map from Deco(G) to G∗deco as defined above. Then φ
is injective. If a unimodular probability measure PG∗deco is given on G∗deco , then the pull-back φ−1 (PG∗deco ) of
the unimodular measure PG∗deco is well defined. Furthermore, it is an Aut(G)-invariant random element of
Deco(G).
Proof.

Suppose that (G, V 0 , E 0 ) and (G, V 00 , E 00 ) are mapped to the same element of G∗deco by φ. This

means that for the fixed root o there is a rooted automorphism of (G, o) that takes (V 0 , E 0 ) to (V 00 , E 00 ).
Since the only rooted isomorphism of (G, o) is the identity, this is only possible if (G, V 0 , E 0 ) = (G, V 00 , E 00 ) in
Deco(G). Hence φ is injective, and one can define a probability measure PDeco(G) on Deco(G), as a pull-back
of PG∗deco by φ.
To prove the second half, consider an automorphism γ of G. Pick an arbitrary event A, with respect to
the Borel σ-algebra on Deco(G). Define the following mass transport. Let every vertex x ∈ G send mass
1 to vertex γx if the event φ(A) holds. Then the expected mass sent out is PG∗deco (φ(A)) = PDeco(G) (A).
By the unimodularity of (G, o; V 0 , E 0 ) and the MTP, this is the same as the expected mass received, which
is PG∗deco (φ(γ −1 A)) = PDeco(G) (γ −1 A). Since this is true for any A and automorphism γ, we obtain the
invariance of PG∗deco as claimed.
We define a bigraph to be a quadruple G = (VG , EG , VH , EH ), where VG is a set of vertices, EG is a set
of edges on VG such that (VG , EG ) is a connected graph, VH ⊂ VG , and EH is a set of edges on VH such that
(VH , EH ) is connected. We allow some further coloring χ : VG ∪ EG ∪ VH ∪ EH → X by the elements of some
metric space X, but we supress this coloring in our notation (however, when we speak about isomorphisms
and distances of rooted bigraphs, colors have to be taken into account). If, furthermore, there is given a
distinguished vertex o ∈ VG , then we call (G, o) a rooted bigraph. We do not distinguish rooted bigraph
(VG , EG , VH , EH , o) from rooted bigraph (VG0 , EG0 , VH 0 , EH 0 , o0 ) if there is a bijection between VG and VG0
that maps o to o0 , and generates bijections between EG and EG0 , VH and VH 0 , EH and EH 0 . Such a bijection
will be a called a rooted isomorphism between the rooted bigraphs. Let the set of all rooted bigraphs up to
this equivalence be denoted by G∗bigraph . Given some Borel probability measure on G∗bigraph , we will call it
a random bigraph. Unimodularity can be defined similarly as for rooted graphs or marked graphs, through
the validity of the Mass Transport Principle 2.1.
Given a bigraph as above, define its dual G∗ = (VH , EH , VG , EG ) as the graph (VH , EH ), with decoration
(VG , EG ) added to it. Suppose now that H is a.s. isomorphic to a Cayley graph. If o ∈ VH , then we can
define the action of the set of rooted automorphisms Aut(H, o) of (H, o) on (G∗ , o) as follows. Let Aut(H, o)
act on VH (defined through some fixed isomorphism between (VH , EH ) and H), let it act on VG \ VH as the
identity, and define its action on the edges EG and EH through its action on the endpoints.
11

Consider an element (G, o) = (VG , EG , VH , EH , o) of G∗bigraph , and suppose that o ∈ VH (⊂ VG ). Then
one can map (G∗ , o) to an element of G∗deco , namely, to the graph (VH , EH ) with root in o and decoration
V 0 = VG \ VH , E 0 = EG (using notation from Definition 4). This map is well defined, that is, if we take
two rooted bigraphs that are rooted equivalent (and hence represent the same element of G∗bigraph ), then the
elements of G∗deco assigned to their duals will also be rooted equivalent. This is true because the definition of
rooted equivalence on G∗bigraph and on G∗deco coincides for the present objects, the same structures have to be
preserved. Conversely, for the same reason, this map is injective from {(G, o) ∈ G∗bigraph : o ∈ VH } to G∗deco .
Lemma 3.3. (Duality lemma) Let (G, o) = (VG , EG , VH , EH , o) be a unimodular random bigraph. Define
oH ∈ VH to be a random root, distributed as o conditioned on o ∈ VH . Then (G∗ , oH ) is unimodular. If
(VH , EH ) is almost surely isomorphic to some fixed Cayley diagram H, then (G∗ , oH ) is Aut(H)-invariant.
A corollary is the following more natural formulation:
Corollary 3.4. Let G be a Cayley graph or Cayley diagram, and let H be a Cayley diagram. Let α be
a random map α : V (G) → V (H) that is bijective and satisfies α(idG ) = idH . Suppose that the diagram
α−1 (H) is Aut(G)-invariant. Then α(G) is Aut(H)-invariant.
Proof of Lemma 3.3. Let f : {((VH , EH , VG , EG ), oH , x)} → [0, ∞] be an arbitrary Borel measurable function, as in the definition of unimodularity. This can be extended to a function f ∗ : {((VG , EG , VH , EH ), o, x)} →
[0, ∞], defined to be 0 if o or x is not in VH and f ∗ ((VG , EG , VH , EH ), o, x) = f ((VH , EH , VG , EG ), o, x) otherwise. The function f ∗ satisfies the Mass Transport Principle, by the unimodularity of (G, o). Therefore f
also satisfies it, and since it was arbitrary, we obtain that (G∗ , oH ) is unimodular.
For the second half of the claim apply Lemma 3.2.
The next proposition is an application of the duality lemma. It will be needed later, and we have not
found it in the literature, so we include a sketchy proof. By a “random copy” of T3 in Rd we mean that there
is some (Isom(Rd )-invariant) point process V in Rd and a graph defined on V that is isomorphic to T3 . The
intensity of a point process is the expected number of points in a unit cube.
Proposition 3.5. Let T be an Isom(Rd )-invariant random copy of T3 in Rd , d ≥ 1. Then V (T ) has infinite
intensity in Rd .
Proof. Suppose to the contrary, that V (T ) has finite intensity c. Let T be as in the claim. Consider Z to be
a copy of the Cayley diagram of c−d Zd in Rd , translated by a uniform element of Isom(c−d Rd )/Aut(c−d Zd ).
Then the joint distribution of (T, Z) is invariant under Isom(Rd ). The two point processes V (T ) and V (Z)
have the same intensities, hence there exists an invariant perfect matching m between them almost surely
(e.g. consider the stable matching as in ?? if (T, Z) has only trivial symmetries almost surely; the other,
more straightforward case is left for the interested reader). One can use m to define a 3-regular tree TZ on
V (Z), by adding a (new) edge between two vertices if their m-pairs are adjacent. This tree on the copy
Z of Zd is Aut(Zd )-invariant, by the Isom(Rd ) invariance of our construction. One can randomly 3-color
the edges of TZ to get a Cayley diagram of the 3-fold free product of the 2-element group with itself. Do
this independently from all other randomness, and call this resulting Cayley diagram F . Then we obtain
an Aut(Zd )-invariant copy of the F on Zd . By Corollary 3.4, this gives rise to an Aut(F )-invariant copy
of Zd on V (F ). Let Pi be a uniform random partition of Zd into 2i times 2i cubes. Then the Pi is also
Aut(F )-invariant. Let Fi be the subgraph of F consisting of edges whose endpoints are in the same piece
12

of Pi . As i tends to infinity, degFi (x) → 3 for a fixed vertex x. But as soon as degFi (x) > 2, the Fi has
some infinite component, contradicting the fact that Pi consists of only finite parts. This final contradiction
shows that V (T ) cannot have finite intensity.
The duality lemma inspired more questions of similar flavor, which the author is investigating with
Beringer in a paper under preparation, [4].

4

Dyadic fiid partitions with some connected pieces

If P if some partition of a set X, denote by P(x) the class of x ∈ X in P.
Lemma 4.1. Let T = (T, o) be an ergodic unimodular random tree with one end and degrees at most d.
Then there exists a fiid nonempty subset U ⊂ V (T ) that induces a connected subgraph of T , and a fiid
sequence (Qn ) of coarser and coarser partitions of U such that any x, y ∈ U is in the same class of Qn if n
is large enough, and for every x ∈ U there are infinitely many n such that T |Qn (x) is connected and has 2n
elements.
Proof.

Given some x ∈ V (T ), define Tx as the finite subtree induced by vertices in T that are separated

from infinity by x (including x). Observe that for every x ∈ V (T )
|Tx | ≤ 1 + (d − 1)maxx∼y,y∈Tx |Ty |,

(4.1)

where x ∼ y indicates that x and y are adjacent in T . For k > 0, define Sk (T ) = Sk = {x ∈ V (T ) : |Tx | ≥ 2k }.
The set Sk induces a subtree of T ; we will refer to this subtree as T (Sk ).
For sets A and B, say that A cuts B if A ∩ B 6= ∅ and B \ A 6= ∅. If P is a partition, say that P cuts B
if some class A ∈ P cuts B.
Fix an arbitrary sequence n1 < n2 < n3 < . . . with the property that ni+1 /ni > 3 + 2 log(d) for every
i. Define P00 as the partition consisting of classes {x}, x ∈ V (T ). Given i ∈ N, suppose that partition Pji−1
has been defined for every 0 ≤ j < i, and that
(1) every class of Pji−1 induces a connected subgraph of T ;
(2) whenever j 0 < j, Pji−1 is coarser than Pji−1
. In other words, Pji−1 does not cut any class of Pji−1
.
0
0
i−1
(3) Every class of Pi−1
either has 2ni−1 elements, or it is a singleton.

We will define Pji for every j ≤ i, such that (1) − (3) is satisfied by {Pji , j ≤ i} (with i − 1 replaced by i).
Let Li (T ) be the set of vertices of T (Sni ) that have degree 1 in T (Sni ). If x ∈ Li (T ), then we have
2ni ≤ |Tx | ≤ 1 + (d − 1)2ni ,

(4.2)

using (4.1) and the fact that the neighbors of x ∈ Li (T ) in Tx are not in Sni . Note also that if x, y ∈ Li (T ),
x 6= y, then Tx ∩ Ty = ∅. For every x ∈ Li (T ), we will take a connected subgraph Cx of Tx such that x ∈ Cx ,
and |Cx | = 2ni . Furthermore, Cx will be such that for every j < i the number of classes in Pji−1 that are
cut by Cx is at most 1. Such a Cx exists for the following reason. Starting from c1 := {x}, define a sequence

13

of connected subgraphs c1 ⊂ c2 ⊂ c3 ⊂ . . . in Tx , by always adding one vertex to the previously chosen set
(so |ck \ ck−1 | = 1). The rule for this sequence is that whenever our current set ck cuts some class π of Pji−1
for some j < i, we will add vertices from π to the sequence as long as π gets fully contained in some cm .
There may be more than one j and π(j) ∈ Pi−1
that is cut by ck , but by (2) there is always a smallest one
j
with regard to containment, and so we only need to follow the above rule for this smallest π until it gets
fully contained. Such a growing sequence exists, and by definition, it always cuts at most one class of Pji−1
for every j < i. We have just seen that a Cx as above exists; choose Cx randomly (using some pre-fixed
fiid rule) among all the possible choices satisfying the above constraints. The Cx are pairwise disjoint over
x ∈ Li (T ), because the Tx are pairwise disjoint.
We introduce notation T (1) := T . Having chosen Cx for every x ∈ Li (T ), consider the infinite component
T (2) (i) = T (2) of T \ Li (T ), and repeat the above procedure for this new tree T (2) . (We hide dependence on
(2)

i for the sake of simpler notation.) We can define Tx , Sni (T (2) ), Li (T (2) ) as above, and apply the above
procedure, using the restrictions of the Pji−1 to T (2) , which restrictions still satisfy (1) and (2). Note that
condition (3) was not used in the above construction of Cx .
Repeat the above procedure for the series T (k) (i) = T (k) as k = 1, 2, . . ., defined recursively and similarly
(k)

to the way we defined T (2) . One arrives to a family of pairwise disjoint connected subgraphs Cx
(k)

x ∈ Li (T (k) ), of size 2ni each. The family of all these Cx

of T (k) for

(as k = 1, 2, . . ., and x ∈ Li (T (k) )), together with

all the singletons not contained in any of them, defines a partition of T . Call this partition Pii . We mention
that
P(o ∈ ∪k Li (T (k) )) ≤ 2−ni ,

(4.3)
(k)

as can be seen by an easy mass transport argument where x ∈ Li (T (k) ) sends mass 1 to every point of Tx .
Now,
P(o is in some Cx(k) ) ≥ inf |Cx(k) |/|Tx(k) | ≥ 2ni /(d2ni ) ≥ 1/d

(4.4)

x

using (4.2) and a standard MTP argument. So we have that
P(o is in a class of size 2ni of Pii ) ≥ 1/d

(4.5)

For every j < i, define Pji to be the collection of all classes in Pji−1 that are not cut by any of the classes
in Pii , and let all vertices outside of these classes be singletons in Pji . The Pji defined this way satisfy (1),
(2) and (3) with i − 1 replaced by i. Define Qj := limi→∞ Pji as a weak limit. The partition Qj inherits the
property that every class of it induces a connected subgraph of T . Then, using (4.5), we have
P(o is in a class of size 2nj of Qj ) ≥ P(|Pjj (o)| = 2nj ) −

X

P(Pjj (o) is cut by Pii ) ≥ 1/d − 2

i>j

∞
X

d2nj /2ni ,

i=j+1

(4.6)
as we explain next. There are two ways for the class π =
Li (T

(k)

Pjj (o)

to be cut by

Pii .

The first one is if

) ∩ π 6= ∅ for some k ∈ N. If this is not the case, there is another way: if there is an x ∈ V (T ) such

that π is the (single) class of Pjj that Cx ∈ Pii (as in the above construction) cuts. The probability for the
“first way” can be bounded using Chebyshev’s inequality:
P(Li ∩ π 6= ∅) ≤ E(|Li ∩ π|),

14

where Li = ∪k Li (T (k) ). For the right hand side we have the following upper bound, where supess|π| denotes
the essential supremum of the size of π = Pjj (o) with regard to the random graph and partition (in our case
we have supess|π| ≤ d2nj ).

E(|Li ∩ π|) ≤

X

P(|π| = `)

X

P(|π| = `)

X

`
X

P(|π ∩ Li | = m |π| = `)m/` ≤

m=0

`

≤ supess|π|

P(|π ∩ Li | = m |π| = `)m ≤

m=0

`

≤ supess|π|

`
X

P(|π| = `)P(o ∈ Li |π| = `) ≤ supess|π|P(o ∈ Li ) ≤ d2nj 2−ni ,

`

using (4.3) for the last inequality. To summarize,
P(Li ∩ π 6= ∅) ≤ d2nj 2−ni .

(4.7)

Now let us continue with an upper bound on the probability of the “second way” for π = Pjj (o) to be cut
(k)

by Pii , assuming that it is not cut by Li . Note that {Tx

: x ∈ Li (T (k) ), k ∈ N+ } is a partition of T . So the
(k)

assumption that π is not cut by Li implies that there is a unique k and x ∈ Li (T (k) ) such that π ⊂ Tx .
We know that Cx (as above) cuts at most one of the classes of Pjj . If there exists such a class, denote it by
π̄, otherwise let π̄ := ∅. Then
P(π is cut by Cx |Li ∩ π = ∅) = P(o ∈ π̄|Li ∩ π = ∅) ≤

d2nj
|π̄|
≤ ni .
|Tx |
2

To see (4.6), note that the sum of this and the right side of (4.7), over all i > j, gives an upper bound for
the total probability of Pjj (o) being cut in a later stage.
The inequality (4.6) shows that for every j, o is in a non-singleton class of Qj with probability at least
1/2d (using the condition on the (ni )). By the Borel-Cantelli lemma, with positive probability o is contained
in a non-singleton class of Qj (that is, a class of size 2nj ) for infinitely many j. By the ergodicity of T , there
are vertices with this property almost surely, let their set be U . The set U is in fact defined by an fiid, as
claimed in the lemma, because the sequence (Qj ) is a fiid. The sequence (Qj ) satisfies the other claimed
properties in the lemma as well.
Although we are not going to use the next lemma, we claim it as a straightforward consequence of Lemma
4.1.
Lemma 4.2. Let G = (G, o) be an ergodic unimodular random graph with one end and degrees at most
d. Then there exists a fiid nonempty subset U ⊂ V (G) that induces a connected subgraph of G, and a fiid
sequence (Pn ) of coarser and coarser partitions of U such that any x, y ∈ U is in the same class of Pn if n
is large enough, and for every x ∈ U there are infinitely many n such that T |Pn (x) is connected and has 2n
elements.
Proof. Choose an fiid 1-ended spanning tree of G, as in [11]. Apply Lemma 4.1 to this spanning tree.

15

5

Representation of a unimodular one-ended tree by a tiling

Given a copy of the graph or diagram Z3 , say that we expand it to R3 , if we fill up every cube (as a subgraph)
of Z3 with a unit cube of R3 (as a polyhedron). In other word, we think about Z3 as being embedded in R3 in
the usual way. If x is a vertex of the Z3 that was expanded to R3 , we assign a cube Cubex = x + [−1/2, 1/2]3
to x.
Theorem 5.1. Let T be an ergodic unimodular random tree with one end and degrees at most d. Then
there is an fiid decoration of a fiid subset U of V (T ) with the Cayley diagram Z3 (meaning that a cubic
grid is defined on U as vertex set). Expanding this Z3 to R3 , there is a tiling of R3 that represents T , and a
bijection from V (T ) to the tiles, and this bijection as well as its inverse preserves adjacency. The tiling and
the bijection are both given as a fiid.
We mention that the copy of Z3 and the tiling in the theorem is defined only up to isometries.
Proof.

As before, for x ∈ V (T ), let Tx be the subgraph of T induced by those vertices of T that are

separated from infinity by x (including x). For x, y ∈ V (T ), say that y ≤ x, if y ∈ Tx . Let Qn and U
be as in Lemma 4.1; recall that T |U is connected. Let V top be the set of x ∈ U such that for some m,
T |Qm (x) is connected and y ≤ x for every y ∈ Qm (x). For every xV top choose a maximal m = m(x) with
this property. The conclusion of Lemma 4.1 says that V top is nonempty. Let V1top = {x ∈ V top , 6 ∃y ∈ V top
such that y ∈ Tx }. Define Vntop recursively, to be the set of points x ∈ V top such that there exists a y < x
top
with y ∈ Vn−1
and such that for every y < x with y ∈ V top , we have y ∈ Vktop for some k < n.

From now on, Z3 will denote the Cayley diagram. First we define a fiid copy of the graph Z3 on the
vertex set U (that is, a fiid decoration of U in G by Z3 ). As n = 1, 2, . . ., consider the elements x of Vntop ,
and define a 2bm(x)/3c × 2b(m(x)+1)/3c × 2b(m(x)+2)/3c grid L(x) on Qm(x) (x) = Qm (x), with edges oriented
and colored by the first, second and third generator of Z3 , respectively, as in the Cayley diagram of Z3 ,
and in such a way, that it respects all the L(y) defined in earlier steps (in other words, if y < x, y ∈ V top ,
then define L(x) so that L(y) ⊂ L(x) and the colors and orientations agree). Beyond this constaint, the
adjacencies of the actual points of Qm (x) in this grid can be determined arbitrarily, but one should follow
some fixed fiid rule (as usual). By Lemma 4.1, every point u ∈ U is in infinitely many Qm (x). Hence the
limit of the L(x) has to be Z3 , or an infinite half-space, quarter-space or eigth-space of Z3 – however, only
the first one is possible, by a simple MTP argument (otherwise one could assign points of the border to the
vertices, mapping infinitely many to some border points). Again by Lemma 4.1, any two points of U are in
the same Qm -class if m is large enough. Therefore, the limit of the L(x) is in fact a connected copy of Z3
on U , which we defined as a fiid.
In the rest of the proof we explain how to decorate every point v of V (T ) by a tile τ (v) of R3 , where R3 is
given as the expansion of the Z3 that we just constructed on V (T ). These tiles will be polyhedra, bricks with
finitely many possible holes in them, such that the holes are also bricks. The collection {τ (v) : v ∈ V (T )}
will give a partition of R3 , with adjacency relation isomorphic to that of T . In other words, we will define a
representation of T by a tiling. This will be done as a fiid.
For a polyhedron H and  > 0, let Thin(H, ) be the subset of H of points at distance at least  from
the complement of H. Recall V top ⊂ U ⊂ V (T ), now we will partition V (T ) to pieces so that every piece
corresponds bijectively to one point of V top . Namely, as x ∈ V top , let F(x) = {y : y ∈ Tx , there is no
element of V top but x on the x − y path in T }. The set {F(x) : x ∈ V top } is in fact a partition of V (T ).
16

Figure 5.1: Representing T by a tiling. Here v1 , v2 ∈ V1top , and v ∈ V2top . Qm(v1 ) (v1 ) = Q1 (v1 ), Qm(v2 ) (v2 ) =
Q2 (v2 ) and Qm(v3 ) (v3 ) = Q3 (v3 ) are circled. When we start the construction of the representation of Tv ,
the representation of Tv1 and Tv2 is already given (the yellow domains and the ones surrounded by them on
the right).

Before we proceed, let us highlight a certain property of V top . The set V top inherits a tree structure T (V top )
from T : let v ∈ U and w ∈ U be adjacent, if w separates v from infinity in T , and any other vertex of V top
either separates both v and w from infinity, or none of them. Consider the subgrid L(x) (as defined above),
which contains all the L(y) for y ∈ Tx ∩ U . We will expand these subgrids first, to obtain a brick, and then
we remove all the smaller bricks inside it, that correspond to the elements of V top that x separates from
infinity in T (V top ). This way we will get a tiling in the limit, that represents T (V top ). We turn this into a
tiling representation of T next.
As k = 1, 2, . . ., for every x ∈ Vktop and y ranging over F(x), we will define tiles τ (x) and τ (y). First,
define recursively
τ 0 (x) = Thin(∪v∈L(x) Cubev , 2−k ) \ ∪y<x,y∈V top τ 0 (y).
Now extend the definition to all z ∈ V (T ), by defining it for every z ∈ F(x), z 6= x, x ∈ V top . Fix
x ∈ V top . Define a polyhedral subset τ 0 (z) of τ 0 (x), such that it satisfies the following properties, but
otherwise arbitrarily. For every y ∈ V top with y < z < x, we will have τ 0 (y) ⊂ τ 0 (z) ⊂ τ 0 (x), and
furthermore, ∂τ 0 (y) ∩ ∂τ 0 (z) = ∅ and ∂τ 0 (z) ∩ ∂τ 0 (x) = ∅. Finally, if z 0 < z then τ 0 (z 0 ) ⊂ τ 0 (z) and
∂τ 0 (z 0 ) ∩ ∂τ 0 (z) = ∅. Such a definition of the τ 0 (z) is possible locally, and we can make it an fiid by fixing
some central rules for these choices. Finally, for each v ∈ V (T ), define τ (v) := τ 0 (v) \ ∪w∈Tv τ 0 (w). See
Figure 5.1 for a summary of the construction.
The properties in Definition 1 are trivially satisfied by the above construction, only the third one requires
some reasoning. So consider some fixed ball B in the R3 that arose by expanding Z3 . We may assume that
B has radius less than 1/3, and that the center of B is in Z3 . Choose x ∈ U such that V (Tx ), viewed as a
subset of Z3 ⊂ R3 , has convex hull that contains B. By construction, then the only tiles that may intersect
B are τ (y), y ∈ Tx .
The next lemma will be needed to extend Theorem 5.1 and construct an invariant tiling representation
of an arbitrary amenable unimodular graph with one end.

17

Let  > 0 be arbitrary, A, B ⊂ R3 . Define v(A, B, ) := {x ∈ R3 : dist(x, A) < min(dist(x, B), )}, and
let Vor(A, B, ) be the connected component of v(A, B, ) containing A.
Lemma 5.2. Let G0 be a finite connected graph represented by a collection P of polyhedra, and ∆ ⊂ R3
be the union of the closures of these polyhedra. Let x, y ∈ V (G), and I be a path in G0 between x and y.
Then G0 ∪ {{x, y}} can also be represented in ∆, by a collection P 0 of polyhedra such that P (v) = P 0 (v)
whenever v 6∈ I. Furthermore, let γxy be a broken line segment in R3 connecting P (x) to P (y), and suppose
that there exists an 0 > 0 such that the 0 -neighborhood N (γxy , 0 ) of γxy is contained in ∆. Then P 0 can
be constructed so that if we restrict P and P 0 to ∆ \ N (γxy , 0 ) then they coincide (in other words, outside
of N (γxy , 0 ), the polyhedra of P are unchanged when P 0 is constructed). Finally, all of the above can be
constructed as a deterministic function of P (so that it is equivariant with any isometry of R3 ).
Proof.

It is enough to prove the second half of the claim, with γxy given. Figure 5.2 gives an intuitive

summary of the coming proof: one can grow a path between P (x) and P (y) while only modifying P (v) with
v ∈ I.
To explain formally what is summarized on Figure 5.2, consider γ = γxy . For A ⊂ R3 , c > 0, denote by
∞

N (A, c) the c-neighborhood of A in the L∞ norm. To define this norm, we have to fix the coordinate axes
as a deterministic function of P, which is clearly possible by some properly chosen rule that uses the finitely
many extremal points of the polyhedra of P. So in the remainder of this proof, all distances are understood
as L0 , with axes fixed as a fiid from G. (The point of using this distance is to have the neighborhoods of
line segments be polyhedra.) Let D1 , . . . , Dm be the tiles that γ crosses, in this consecutive order as we go
from x to y. Pick an  > 0 such that N ∞ (γ, ) ⊂ N (γxy , 0 ), and Di \ N (γ, ) is connected for every i.
0
Define Γ0 = N ∞ (γ, /2) and D00 = P (x) ∪ Γ0 \ P (y). Suppose Γj−1 and Dj−1
have been defined. Let
S
j−1
−j
0
Γj = Vor(∪i=1 ∪ Γi , P (y), 2 ) and Dj = Dj ∪ Γj \ ( i<j Di ∪ Γj−1 ), where we use the L∞ distance in the

definition of Vor. To finish, for every v ∈ V (G) such that P (v) = Dj for some j, define P 0 (v) = Dj0 . For all
other v ∈ V (G), let P 0 (v) = P (v).

Figure 5.2: Adding an extra edge to a representation by tiles. Note that in dimension 3, the slim tunnel
between the two tiles does not disconnect the other tiles.

The notion of amenability was extended from transitive (unimodular) graphs to unimodular random
graphs by Aldous and Lyons in [1]. See Section 8 of [1] for the definition and some equivalent characterizations.
The next theorem contains Theorem 1.3 as a special case.

18

Theorem 5.3. Let G be an ergodic amenable unimodular random graph that has one end almost surely,
and degrees at most d. Then there is an Isom(R3 )-invariant random tiling of R3 that represents G, such
that every tile is bounded. One can define a map from V (G) to tiles in R3 that represent G, and this map
and the representation can be defined as a factor of iid.
Proof. We prove the second assertion first. Let T be an fiid 1-ended spanning tree percolation of G (that
is, T ⊂ G and (G, T ) is unimodular). The existance of such an fiid percolation is shown in [11]. (The weaker
claim that there is a spanning tree percolation with 1 or 2 ends was shown in [1].) Apply Theorem 5.1 to
obtain a fiid decoration of T by a tiling M that represents T in R3 (up to isometries; this will be understood
without mention in all paragraphs of this proof but the last one). For every edge e ∈ E(G) define πe to be
the path in T that connects the endpoints of e.
We will define a collection of broken line segments (“curves”) γe ⊂ R3 as e ∈ E(G) \ E(T ), with the
following properties:
(1) No two of these curves will intersect.
(2) If v0 , . . . , vn are the vertices of πe in consecutive order (so in particular, v0 and vn are the endpoints
of e), then γe connects M(v0 ) and M(vn ), and crosses no other polyhedron in M but the M(vi ), in
consecutive order).
Once this family {γe : e ∈ E(G) \ E(T )} is constructed, two consequences will follow. First, every M(x) is
crossed by only finitely many of the γe (because x is in finitely many of the πe ). This implies the second
important property: the infimum of the distance of a γe from all the other γe0 is positive (because only finitely
many of the γe0 enter the finitely many polyhedra that γe crosses). Let this infimum be e (> 0). Now, apply
Lemma 5.2 to a γe , with  := e /3, and P the set of tiles in M that γe intersects. Then the modification of
the polyhedra of M happens in pairwise disjoint parts of R3 , hence they can be done simultaneously for all
the e. Also, every tile of M is being modified finitely many times (for exactly those e where γe intersects the
tile). The original M had the property that any ball in R3 intersects only finitely many tiles of it. Hence the
modified M will also have this property, because each of the tiles of M is contained in the union of finitely
many new tiles. It follows that the resulting tiling is an fiid representation of G, as in in Definition 1. Thus,
to obtain a fiid decoration of G by a tiling that represents it, we only have to define the family of curves
that satisfies properties (1) and (2) above.
Let En be the set of edges e in E(G) \ E(T ) that have the following properties: the total number of
points in the finite components of T \ πe is less than n and |πe | ≤ n. One can check that
• the graph ∪e∈En πe has only finite components;
• ∪n En = E(G) \ E(T ).
The second item is trivial. The first item follows from noticing that any path πe has a unique point that
is “closest to infinity” in T , meaning that any infinite simple path from a point of πe contains this point.
Hence for any two paths πe and πe0 that intersect each other, one of them is such that its point closest to
infinity also separates the other path from infinity in T . From this it is easy to deduce the first item above.
As n = 1, 2, . . ., do the following. For every (finite) component C of ∪e∈En πe and e such that πe ∩ C 6= ∅,
define the path γe such that it satisfies property (2) above. Furthermore, do this in such a way that γe does

19

not intersect any of the (finitely many) other γe0 with πe0 ∩ C 6= ∅, nor does it intersect any of the finitely
many γe0 that were defined in some step before n (there are finitely many such γe0 that intersect C). By
construction, the family {γe : e ∈ E(G) \ E(T )} has properties (1) and (2).
This family can be used to construct a fiid decoration of G by a tiling that represents G, as we have
explained above. To finish, we want to turn this into an Isom(R3 )-invariant tiling that represents G. First,
we can look at the fiid decoration of V (T ) = V (G) by the Cayley diagram Z3 , as in Theorem 5.1. On top
of this decoration of G by a copy of Z3 , consider the further decoration by a tiling that represents G as
constructed above. Apply the Duality lemma (Lemma 3.3), to obtain a decoration of Z3 which is Aut(Z3 )invariant and represents G by tiles. Now take the expansion R3 of Z3 , which is the space where the tiles are
sitting in, and pick a uniform random element g ∈ Isom(R3 )/Aut(Z3 ). Take a random translate of the copy
of Z3 and the tiles by g in R3 . The resulting random decorated copy of Z3 in R3 is Isom(R3 )-invariant.

Proof of Theorem 1.3. Follows as a special case of Theorem 5.3.

6

Representing T3 by indistinguishable tiles

Proof of Theorem 1.2. Let G be the Cayley diagram of BS(1,2) in the representation < a, b|a−1 ba = b2 >.
By Theorem 5.3, one can define a copy of Z3 on a fiid subset U of V (G) as a fiid, and also a tiling of the copy
of R3 that we get as an expansion of this Z3 , where the tiling represents G. Note that the tiling constructed
so far is Aut(G)-invariant, but using the method in the last paragraph of the previous proof, the tiling can
be turned into an Isom(R3 )-invariant representation of G.
Let P be the (deterministic) subgraph consisting of edges of G that are colored by b in the Cayley diagram
of G. The infinite clusters (that we will call fibers) are all biinfinite paths, and they are (deterministically)
indistinguishable with scenery (G, P), because any of them can be taken to any other by an automorphism
that preserves the fibers. For each fiber, take the union of the tiles that decorate the vertices in that fiber.
This union is a connected infinite tile, because the tiles corresponding to a fiber form a connected set with
regard to adjacency of tiles. The fibers with their original decorations with tiles are indistinguishable by the
Decoration Lemma (Lemma 2.2). Hence the unions of the tiles over the fibers are also indistinguishable.
We have concluded that the pieces are indistinguishable. Their adjacency graph is T3 by definition. This
finishes the proof.
Remark 6.1. There is no representation of T3 in R2 by an ergodic random tiling of indistinguishable tiles,
as shown by the following proof by contradiction. Suppose there is such a partition, denote by D0 the tile of
the origin o, and by D1 , D2 , D3 its neighbors. There exists an r > 0 such that with positive probability there
exists a ball B of radius r with center in D0 , such that B intersects each of D1 , D2 and D3 (call such balls
D0 -trifurcating). Suppose that with positive probability there exist three D0 -trifurcating balls B1 , B2 , B3
that are pairwise disjoint. Let the center of Bi be oi , and denote some arbitrarily chosen intersection point
of the i’th ball with Dj by xji , for j = 1, 2, 3. There exist paths Pij between oi and xji (j = 1, 2, 3) inside
Bi whose interiors are pairwise disjoint. Also, all these 9 paths have pairwise disjoint interiors, because
the Bi are pairwise disjoint. Furthermore, there is a path Pj within Dj that contains xj1 , xj2 and xj3 , and
S
such that Pj \ {xj1 , xj2 , xj3 } is disjoint from all the previously defined paths. The union i,j Pij ∪ Pj can be

20

regarded as a graph on 12 vertices embedded in R2 . This graph contains K3,3 as a minor (contract the
paths Pj to one vertex, as j = 1, 2, 3), contradicting the fact that this graph is embedded in the plane. This
contradiction shows that the probability of having three pairwise disjoint D0 -trifurcating balls B1 , B2 , B3 is
zero. Therefore, all D0 -trifurcating balls have to be within the r-neighborhoods of at most two r-balls a.s..
Call a ball of radius r a trifurcating ball, if it intersects a tile D and all the neighboring tiles of D. We have
seen that the probability of having three pairwise disjoint D0 -trifurcating balls is 0. Consequently, since there
are countably many tiles D in the tiling, the probability that any of them has 3 pairwise disjoint trifurcating
balls is 0. We know that with positive probability there do exist trifurcating balls. Define a mass transport
(8r2 π)−1 from every point of D to every point of D that is in a trifurcating ball. The expected mass sent
out is less than 1. (Here we are applying the continuous version of the MTP, as defined in [2].) The expected
mass received is equal to P(o is in a trifurcating ball)E(Area(D0 )|o is in a trifurcating ball). Therefore,
conditioned on that o is in a trifurcating ball, D0 has finite area. By ergodicity and indistinguishability,
then all tiles have the same, finite area c almost surely. Choose a uniform point in each of the tiles, let the
set of all these chosen points be X, and consider the graph T3 on X that they inherit from the tiling. It is
well known (see Proposition 3.5) that such an invariant representation of T3 in R2 is not possible if the set
of vertices has finite intensity as a point process. But then, using invariance, a unit square in R2 contains
infinitely many elements of X with positive probability. Hence the expected number of points of X in this
square is infinite, contradicting the fact that a tile of area c contains 1 point of X (which implies by the
MTP that a unit cube contains 1/c points in expectation).

7

Some questions

An alternative, discrete formulation of the original question remains open:
Question 7.1. (Itai Benjamini) Is there an invariant percolation on Z3 such that connected components
are indistinguishable, and their adjacency graph is the 3-regular tree T3 ?
Several follow-up questions can be asked about the tiling in our construction, which were raised by
Benjamini:
Question 7.2. Consider some invariant random tiling of Rd (d ≥ 3) that represents T3 . What can we say
about the volume growth of the tiles? Can the tiles be convex?
Remark 7.3. One of these questions was whether there is a “tree factor” in R2 × R/Z. The answer seems
to be positive. As long as the space is amenable and BS(0,1) can be embedded there, our proof seems to
work.
In light of Theorems 1.2 and 1.4, it is natural to ask whether any Cayley graph (or unimodular random
graph) G can be represented by indistinguishable tiles. Our proof shows the validity of this claim when
G arises by contracting the components of some automorphism-invariant percolation on some amenable
transitive graph (diagram).
Question 7.4. Let G be a transitive graph. When is there an invariant random tiling of R3 with indistinguishable tiles, such that the adjacency graph of the tiling is G?
Some further directions are about finding the greatest generality of the Duality lemma, and its analogue
for factor of iid’s, which is work in progress.
21

Acknowledgements
This work was started at the Bernoulli Center (CIB) conference “Statistical physics on transitive graphs”. I
thank Itai Benjamini, Damien Gaboriau, Russ Lyons, Gábor Pete, Mikael De La Salle and Romain Tessera
for inspiring conversations.

References
[1] Aldous, D., Lyons, R. (2007) Processes on unimodular random networks Electron. J. Probab., 12,
1454-1508.
[2] Benjamini, I. and Schramm, O. (2001) Percolation in the hyperbolic plane. J. Amer. Math. Soc.,
14(2):487-507 (electronic).
[3] Benjamini, I., Lyons, R., Peres, Y., Schramm, O. (1999) Group-invariant percolation on graphs
Geom. Funct. Anal. 9, 29-66.
[4] Beringer, D., Timár, Á. (2017) Duality of unimodular random decorations of unimodular networks
(work in progress).
[5] Holroyd, A., Peres, Y. (2003) Trees and matchings from point processes Electron. Commun. Probab.
Volume 8, no. 3, 17-27.
[6] Lyons, R. (2017) Factors of IID on trees Combin. Probab. Comput. 26, no. 2, 285-300.
[7] Lyons, R., Schramm, O. (1999) Indistinguishability of percolation clusters Ann. Probab. 27, no. 4,
1809-1836.
[8] Pete, G. (2015) Probability and geometry on groups. Lecture notes for a graduate course, Version of
3 August 2015. http://www.math.bme.hu/~gabor/PGG.pdf
[9] Timár, Á. (2004) Tree and Grid Factors of General Point Processes, Electronic Communications in
Probability 9, 53-59.
[10] Timár, Á. (2017) Invariant tilings and unimodular decorations of Cayley graphs, to appear in “Unimodularity in Randomly Generated Graphs”, Contemporary Mathematics, American Mathematical
Society.
[11] Timár, Á. (2017) Spanning trees of one-ended amenable graphs, preprint.

22

