# Borel Combinatorics of Abelian Group Actions

Su Gao  School of Mathematical Sciences and LPMC, Nankai University, Tianjin
300071, P.R. China<EMAIL_ADDRESS>,  Steve Jackson  Department of
Mathematics, University of North Texas, 1155 Union Circle #311430, Denton, TX
76203, U.S.A<EMAIL_ADDRESS>,  Edward Krohne<EMAIL_ADDRESS>and
Brandon Seward  Department of Mathematics, University of California San Diego,
San Diego, CA 92093, U.S.A<EMAIL_ADDRESS>
###### Abstract.

We study the free part of the Bernoulli action of $\mathbb{Z}^{n}$ for $n\geq
2$ and the Borel combinatorics of the associated Schreier graphs. We construct
orthogonal decompositions of the spaces into marker sets with various
additional properties. In general, for Borel graphs $\Gamma$ admitting weakly
orthogonal decompositions, we show that $\chi_{B}(\Gamma)\leq 2\chi(\Gamma)-1$
under some mild assumptions. As a consequence, we deduce that the Borel
chromatic number for $F(2^{\mathbb{Z}^{n}})$ is $3$ for all $n\geq 2$. Weakly
orthogonal decompositions also give rise to Borel unlayered toast structures.
We also construct orthogonal decompositions of $F(2^{\mathbb{Z}^{2}})$ with
strong topological regularity, in particular with all atoms homeomorphic to a
disk. This allows us to show that there is a Borel perfect matching for
$F(2^{\mathbb{Z}^{n}})$ for all $n\geq 2$ and that there is a Borel lining of
$F(2^{\mathbb{Z}^{2}})$.

###### 2020 Mathematics Subject Classification:

Primary 03E15, 05C63; Secondary 05A18, 05C15

The first author acknowledges the partial support of his research by the
National Natural Science Foundation of China (NSFC) grants 12250710128 and
12271263. Research of the second author was partially supported by the U.S.
NSF grant DMS-1800323.

###### Contents

  1. 1 Introduction
  2. 2 Orthogonal markers and structures for $F(2^{\mathbb{Z}^{n}})$
    1. 2.1 Review of clopen rectangular partition construction
    2. 2.2 Review of orthogonal marker region construction
    3. 2.3 Connected orthogonal marker regions
  3. 3 Orthogonal Decompositions in $F(2^{\mathbb{Z}^{n}})$
  4. 4 Weakly Orthogonal Decompositions
  5. 5 Topological regularity
  6. 6 Borel Perfect Matchings in $F(2^{\mathbb{Z}^{n}})$
    1. 6.1 Charges, corner functions, and finite Stokes theorems
    2. 6.2 Currents and extensions of partial matchings
    3. 6.3 An orthogonal decomposition with bounded charge
    4. 6.4 The construction of a Borel perfect matching
  7. 7 Borel Linings

##  1\. Introduction

This paper is a contribution to the fast developing field of Borel
combinatorics, which studies combinatorics of definable graphs and other
structures on Polish spaces. For an overview of the entire field we refer the
reader to the surveys [15] and [18].

The object of study for Borel combinatorics is a Borel graph $G$ on a Polish
space $X$. Two main concepts that have been extensively explored are proper
colorings and perfect matchings. A proper coloring of $G$ is a map
$c:V(G)\to\kappa$, where $\kappa$ is a cardinal, such that for any $x,y\in
V(G)$ with $(x,y)\in E(G)$, $c(x)\neq c(y)$. A perfect matching of $G$ is a
map $m:V(G)\to V(G)$ such that for all $x\in V(G)$, $(x,m(x))\in E(G)$ and
$m^{2}(x)=x$. Since these concepts are all functions, we may impose
definability conditions on them and consider, for instance, continuous or
Borel proper colorings (equipping the cardinal $\kappa$ with the discrete
topology) and continuous or Borel perfect matchings, etc.

The Borel graphs considered in this paper are Schreier graphs of marked group
actions. A marked group is a pair $(\Gamma,S)$, where $\Gamma$ is a group and
$S$ is a finite generating set of $\Gamma$. Usually we also require $S=S^{-1}$
and $1_{\Gamma}\not\in S$. When the generating set is standard or otherwise
understood, we omit specifying the set $S$ and say that $\Gamma$ is a marked
group. The Cayley graph $G(\Gamma,S)$ of a marked group $(\Gamma,S)$ is
defined by

$V(G(\Gamma,S))=\Gamma$

and

$E(G(\Gamma,S))=\\{(g,h)\in\Gamma^{2}\,:\,\exists s\in S\ h=sg\\}.$

When there is a Borel action of a marked group $\Gamma$ on a Polish space $X$,
the Schreier graph of the action $\Gamma\curvearrowright X$ on $X$, denoted
$\Sigma(\Gamma,S)$, is defined by

$V(\Sigma(\Gamma,S))=X$

and

$E(\Sigma(\Gamma,S))=\\{(x,y)\in X^{2}\,:\,\exists s\in S\ y=s\cdot x\\}.$

The Schreier graph will be particularly nice when the action
$\Gamma\curvearrowright X$ is free; in this case the Schreirer graph on each
orbit of the action will be a copy of the Cayley graph $G(\Gamma,S)$.

In this paper the particular marked groups that we consider are
$\mathbb{Z}^{n}$ with their standard sets of generators $\\{\pm
e_{1},\dots,\pm e_{n}\\}$ where for $1\leq i\leq n$, the $i$-th coordinate of
$e_{i}$ is $1$ and the other coordinates are $0$. Most of the time we will be
considering the Bernoulli shift action of $\mathbb{Z}^{n}$ on
$2^{\mathbb{Z}^{n}}=\\{0,1\\}^{\mathbb{Z}^{n}}$, where for
$g\in\mathbb{Z}^{n}$ and $x\in 2^{\mathbb{Z}^{n}}$,

$(g\cdot x)(h)=x(g+h)$

for all $h\in\mathbb{Z}^{n}$. In addition, since we are mostly interested in
free actions, we consider the free part of the Bernoulli shift action:

$F(2^{\mathbb{Z}^{n}})=\\{x\in 2^{\mathbb{Z}^{n}}\,:\,\forall 0\neq
g\in\mathbb{Z}^{n}\ g\cdot x\neq x\\}.$

The systematic study of Borel combinatorics started with [16], in which
Kechris, Solecki, and Todorcevic introduced and studied the notion of Borel
chromatic numbers. When there exists a Borel proper coloring $c:V(G)\to\kappa$
for a countable cardinal $\kappa$, we call the least such $\kappa$ the Borel
chromatic number for $G$. A fundamental result proved in [16] states that, if
in a Borel graph $G$ every vertex has degree $\leq k$ for some finite $k$,
then the Borel chromatic number of $G$ is $\leq k+1$. Marks [17] showed that
this bound is optimal using Borel determinacy methods. He constructed marked
group actions which give rise to Borel acyclic $k$-regular graphs with their
Borel chromatic numbers achieving any number from $2$ to $k+1$. More recently,
Conley, Jackson, Marks, Seward, and Tucker-Drob [4] improved these examples to
hyperfinite Borel graphs, more specifically, Borel graphs which come from
marked group actions where the orbit equivalence relation is hyperfinite.

In the case of $F(2^{\mathbb{Z}^{n}})$, it is well known by an ergodicity
argument that the Borel chromatic number is at least $3$, although the
chromatic number of the Cayley graph of $\mathbb{Z}^{n}$ is $2$. For
$F(2^{\mathbb{Z}})$ it is also well known that the Borel chromatic number is
exactly $3$. For $F(2^{\mathbb{Z}^{n}})$ where $n\geq 2$, Gao and Jackson [9]
constructed a continuous proper coloring with $4$ colors. In [11] the authors
of the present paper proved that the continuous chromatic number of
$F(2^{\mathbb{Z}^{n}})$, where $n\geq 2$, is exactly $4$. We also announced
that the Borel chromatic number of $F(2^{\mathbb{Z}^{n}})$ is $3$. In this
paper we present a proof.

######  Theorem 1.1.

Suppose $n\geq 2$ and $\mathbb{Z}^{n}\curvearrowright X$ is a free Borel
action of $\mathbb{Z}^{n}$ on a Polish space $X$. Then the Borel chromatic
number of the Schreier graph on $X$ is $3$.

A classical theorem of König in graph theory (which is a special case of
Hall’s marriage theorem) asserts that if $G$ is a $k$-regular bipartite graph
then $G$ has a perfect matching. The Borel version of the statement turns out
to be false in general. Marks [17] constructed, for every $k\geq 2$, a
$k$-regular acyclic Borel bipartite graph with no Borel perfect matching.
These Borel graphs come from actions of free groups with finitely many
generators. In this paper we prove that there is a Borel matching for
$F(2^{\mathbb{Z}^{n}})$ for any $n\geq 2$.

######  Theorem 1.2.

Suppose $n\geq 2$ and $\mathbb{Z}^{n}\curvearrowright X$ is a free Borel
action of $\mathbb{Z}^{n}$ on a Polish space $X$. Then there is a Borel
perfect matching for the Schreier graph on $X$.

A related concept in combinatoric is proper edge-coloring for a graph $G$,
which is a map $k:E(G)\to\kappa$, where $\kappa$ is a cardinal, such that for
any $e,f\in E(G)$ such that $e$ and $f$ share exactly one vertex, $k(e)\neq
k(f)$. The least cardinal $\kappa$ that admits a proper edge-coloring
$k:E(G)\to\kappa$ is called the edge chromatic number of $G$. A classical
theorem of Vizing states that if in a graph $G$ every vertex has degree $\leq
k$, then the edge chromatic number of $G$ is $\leq k+1$. By a theorem of
König, a $k$-regular bipartite graph $G$ has edge chromatic number $k$. The
Borel versions of these results turn out all to be false in general. Marks
[17] constructed $k$-regular acyclic Borel graphs which all have Borel
chromatic number $2$ but the Borel edge chromatic numbers vary arbitrarily
from $k$ to $2k-1$.

Recently, Grebík–Rozhoň [14] and Weilacher [22] independently showed that the
Borel edge chromatic number for $F(2^{\mathbb{Z}^{n}})$, where $n\geq 2$, is
$2n$. This implies our Theorem 1.2. Bencs–Hrǔsková–Tóth [1] showed the same
theorem for $n=2$, which is a weaker result but sufficient to deduce our
theorem. Of course, the methods used in these proofs are all different from
the one presented in this paper. In contrast, in [11] the authors of the
present paper showed that the continuous edge chromatic number of
$F(2^{\mathbb{Z}^{2}})$ is $5$. More recently, Gao–Wang–Wang–Yan [12] showed
that the continuous edge chromatic number of $F(2^{\mathbb{Z}^{n}})$ for
$n\geq 2$ is exactly $2n+1$.

In this paper we also consider the combinatorial concepts of line section and
lining in a Schreier graph of a marked group action. Following [11], a line
section of $\Sigma(\Gamma,S)$ is a subgraph $G$ where each vertex in $G$ has
degree $2$. If $G$ is a line section, we call each connected component of $G$
a $G$-line. A line section $G$ is complete if $G$ meets every orbit of the
action. A line section $G$ is single if for each $x\in X$, the intersection of
$G$ with the orbit of $x$ is a nonempty single $G$-line. A lining $G$ is a
single line section where the vertex set of $G$ is the entire space, and in
particular it is a complete line section. A line section $G$ on $X$ is Borel
(clopen, resp.) if for each generator $e\in S$, the set $\\{x\in
X\,:\,(x,e\cdot x)\in G\\}$ is Borel (clopen, resp.).

The authors of the present paper studied the existence of clopen line sections
in [11]. We showed that there do not exist clopen single line sections of
$F(2^{\mathbb{Z}^{2}})$; in particular, there are no clopen linings of
$F(2^{\mathbb{Z}^{2}})$. In this paper we prove that there exists a Borel
lining of $F(2^{\mathbb{Z}^{2}})$.

######  Theorem 1.3.

Suppose $\mathbb{Z}^{2}\curvearrowright X$ is a free Borel action of
$\mathbb{Z}^{2}$ on a Polish space $X$. Then there is a Borel lining for the
Schreier graph on $X$.

Recently, Chandgotia–Unger [3] has proved the existence of Borel linings in
higher dimensions with a different method.

The method we use to prove all these combinatorial results can be collectively
called the orthgonal marker method. The simplest form of this method was first
developed by Gao and Jackson in [9] to tackle the hyperfiniteness problem for
countable abelian group actions. Later Schneider and Seward [19] extended the
orthogonal marker method to countable locally nilpotent groups and used it to
show the hyperfiniteness of the orbit equivalence relations of their actions.
It was already clear in [9] that the orthognal marker regions we constructed
not only can facilitate a proof of hyperfiniteness but also allows us to prove
results of combinatorial nature about the Schreier graphs. In fact, it was
shown in [9] that for any $n\geq 2$, there is a continuous proper coloring of
$F(2^{\mathbb{Z}^{n}})$ with $4$ colors.

In this paper we further develop the orthogonal marker method and use it to
prove our theorems stated above. In Section 2 we first present a review of the
orthogonal marker method and prove some improvements. In general, an
orthogonal marker structure is a sequence $\\{\mathcal{R}_{k}\\}_{k\geq 1}$ of
partitions of the phase space $F(2^{\mathbb{Z}^{n}})$ such that each element
in $\mathcal{R}_{k}$ (which we refer to as a marker region) is a finite subset
of an orbit with certain properties. We regard each $\mathcal{R}_{n}$ as a
layer of the orthogonal marker structure, and orthogonality refers to the
relationship between marker regions from different layers. The main
improvement we explore in Section 2 is that, by controlling the geometric
parameters used in the construction of $\mathcal{R}_{k}$, we are able to
obtain orthogonal marker regions that are connected. It turns out that
connectedness is a key consideration in the construction of combinatorial
objects such as proper colorings, perfect matchings, and linings.

Starting from Section 3 we adopt a slightly different point of view when we
consider an orthogonal marker structure $\\{\mathcal{R}_{k}\\}_{k\geq 1}$.
Here, for each $k\geq 1$ we consider all the partitions $\mathcal{R}_{m}$ for
$m\geq k$ and the coarsest common refinement of all of them, denoted
$\mathcal{A}_{k}$. The elements of $\mathcal{A}_{k}$ are called $k$-atoms of
the orthogonal marker structure. We also consider the decomposition of
$\mathcal{A}_{k}$ into finite connected components and define notions of
strong and weak orthogonality. In Section 4 we work with weakly orthogonal
decompositions with polynomial bound and some additional boundedness condition
on the orthogonality constant and prove some results about their Borel
chromatic numbers. These results imply Theorem 1.1. We also show that weak
orthogonal decompositions give rise to a combinatorial structure known as
toast in the literature (defined in [10] and [11]). In particular, we show
that there exists a Borel unlayered toast on $F(2^{\mathbb{Z}^{n}})$ for all
$n\geq 1$.

In Section 5 we prove the main technical theorem of this paper about orthgonal
decompositions. We show that for $n=2$, the orthogonal marker structure
$\\{\mathcal{R}_{k}\\}_{k\geq 1}$ can be constructred so that all $k$-atoms
are homeomorphic to disks. This has consequences about the exact structures of
$k$-atoms as well as their relationship with the $(k-1)$-atoms, which allow us
to perform constructions in Section 6 of a Borel perfect matching (Theorem
1.2) and in Section 7 of a Borel lining (Theorem 1.3).

##  2\. Orthogonal markers and structures for $F(2^{\mathbb{Z}^{n}})$

We review the orthogonal marker structures for the equivalence relation
$F_{n}$ given by the left shift action of the group $\mathbb{Z}^{n}$ on the
free part $F(2^{\mathbb{Z}^{n}})$ of the space $2^{\mathbb{Z}^{n}}$. These
arguments are presented in detail in [9]. Here we review the construction,
summarize the main results, and present some improvements. In §3 we will
introduce a slightly different point of view which we refer to as an
orthogonal decomposition. The notion of an orthogonal decomposition will be a
key component of many of our arguments.

###  2.1. Review of clopen rectangular partition construction

A frequent way to construct clopen rectangular partitions is to start with
$d$-marker sets. We recall this definition.

######  Definition 2.1.

Let $d>0$ be an integer. A $d$-marker set $M_{d}\subseteq
F(2^{\mathbb{Z}^{n}})$ is a set satisfying the following:

  1. (1)

$\forall x\neq y\in M_{d}\ \rho(x,y)>d$.

  2. (2)

$\forall x\in F(2^{\mathbb{Z}^{n}})\ \exists y\in M_{d}\ \rho(x,y)\leq d$.

We often refer to $d$ as a marker distance. We say the $d$-marker set $M_{d}$
is clopen if the set $M_{d}$ is a relatively clopen set in
$F(2^{\mathbb{Z}^{n}})$.

For each marker distance $d$ there is a clopen partition $\mathcal{R}_{d}$ of
$F(2^{\mathbb{Z}^{n}})$ into rectangles with side lengths in $\\{d,d+1\\}$.
More precisely, $\mathcal{R}_{d}$ is a subequivalence relation of $F_{n}$ with
the property that on each $F_{n}$ class $[x]$,
$\mathcal{R}_{d}\restriction[x]$ is a partition of $[x]$ into finite sets,
each of which is a rectangle in the sense that it is of the form $R\cdot y$
for some $y\in[x]$ where $R\subseteq\mathbb{Z}^{n}$ is a rectangle (i.e.,
$R=\mathbb{Z}^{n}\cap\prod_{i}[a_{i},b_{i}]$). Also, $\mathcal{R}_{d}$ is
clopen in the sense that we have the relative clopenness in
$F(2^{\mathbb{Z}^{n}})$ of the set $C$ of $x\in F(2^{\mathbb{Z}^{n}})$ such
that $[x]_{\mathcal{R}_{d}}=R\cdot x$ for some $R$ of the form
$R=\prod_{i}[0,c_{i}]$. Intuitively, elements of the set $C$ are the “bottom-
left” corners of all rectangles in the partition given by $\mathcal{R}_{d}$.
We will, with a slight abuse of terminolgy, refer to $\mathcal{R}_{d}$ as a
“clopen partition” or “clopen finite subequivalence relation” though
$\mathcal{R}_{d}$ is not relatively clopen as a subset of
$F(2^{\mathbb{Z}^{n}})\times F(2^{\mathbb{Z}^{n}})$.

In [9] a clopen rectangular partition $\mathcal{R}_{d}$ with side lengths in
$\\{d,d+1\\}$ is constructed by first starting with a $d^{\prime}$-marker set
$M_{d^{\prime}}$ with $d^{\prime}\gg d$. About each point $x\in
M_{d^{\prime}}$ we consider the “cube” $C=C_{x}$ in $[x]$ centered at $x$ with
side lengths $d^{\prime}$. These cubes clearly cover $F(2^{\mathbb{Z}^{n}})$
by property (2) of Definition 2.1. We refer to this collection of cubes as a
clopen covering of $F(2^{\mathbb{Z}^{n}})$. For each of these cubes $C$ we
“adjust” it by moving each of its faces outward with a distance bounded by a
small fraction of $d^{\prime}$ (say no more than $\frac{1}{10}d^{\prime}$).
When doing the adjustment we ensure that each of the faces $f$ of $C$ stays a
certain distance, bounded below by a fixed fraction $\epsilon d^{\prime}$ of
$d^{\prime}$ (where $\epsilon$ is a fixed constant depending only on $n$),
away from any parallel face $f^{\prime}$ of a cube $C^{\prime}$ within a
Hausdorff distance of $5d^{\prime}$ from $C$. To do these adjustments we use a
big-marker-little-marker procedure. More precisely, we use an auxiliary
distance $d^{\prime\prime}\gg d^{\prime}$ and a $d^{\prime\prime}$-marker set
$M_{d^{\prime\prime}}\subseteq M_{d}$ (actually, to make
$M_{d^{\prime\prime}}\subseteq M_{d^{\prime}}$ we must relax slightly the
inequalities in Definition 2.1 by replacing $d$ with $(1-\eta)d$ for property
(1) and $(1+\eta)d$ for property (2) for some small $\eta$). We use
$M_{d^{\prime\prime}}$ to organize the adjustment process, first adjusting the
points of $M_{d^{\prime\prime}}$, then at step $i$ adjusting the cubes
centered at points in $g_{i}\cdot M_{d^{\prime}}$ not already considered,
where $\\{g_{i}\\}$ is an enumeration of all $g\in\mathbb{Z}^{n}$ within
distance $d^{\prime\prime}/2$ to the origin. As $d^{\prime\prime}\gg
d^{\prime}$, the cubes being adjusted at any given step do not interfere with
each other. After finitely many steps (roughly $(d^{\prime\prime})^{n}$ many)
we will have adjusted all of the cubes. This results in a clopen partition
$\mathcal{R}_{d^{\prime}}$ of $F(2^{\mathbb{Z}^{n}})$ into regions each of
which is the disjoint union of finitely many rectangles $R$ of side lengths
between $\epsilon d^{\prime}$ and $\frac{6}{5}d^{\prime}$. If $d^{\prime}$ is
large enough so that $\epsilon d^{\prime}>d^{2}$, then we proceed with a
finite subdivision algorithm to further subdivide the
$\mathcal{R}_{d^{\prime}}$ regions into rectangles with side lengths in
$\\{d,d+1\\}$. This produces the desired clopen rectangular partition
$\mathcal{R}_{d}$. The full details of this construction can be found in [9].

In summary, the key steps of the clopen rectangular partition construction for
a marker distance $d$ are the following:

  1. (1)

Find a clopen covering of $F(2^{\mathbb{Z}^{n}})$ by rectangles of side
lengths $d^{\prime}\gg d$;

  2. (2)

Using a big-marker-little-marker procedure, adjust the rectangles in the
clopen covering so that any parallel faces of rectangles are at least
$\epsilon d^{\prime}$ apart, for some constant $\epsilon$ depending only on
$n$; the adjusted clopen covering gives rise to a clopen partition of
$F(2^{\mathbb{Z}^{n}})$ into rectangular polygonal regions;

  3. (3)

Use a finite subdivision algorithm to divide each of the rectangular polygonal
regions in the clopen partition into rectangles of side lengths $d$ or $d+1$.

In the following we give a variant of the finite subdivision algorithm in
dimension $n=2$ so that in the final clopen rectangular partition, no points
will be close to 4 different rectangles.

######  Lemma 2.2.

Let $0<\epsilon\leq 1/2$ and $d>0$ be a sufficiently large integer. Let $R$ be
a rectangular polygonal region in $\mathbb{Z}^{2}$ such that any parallel
sides of $R$ have a perpendicular distance at least $12d$. Let $S$ be a subset
of the boundary of $R$ such that each point in $S$ is at least
$\frac{1}{60}\epsilon d$ apart from any corner of $R$ and any two points of
$S$ are at least $\epsilon d$ apart. Then there is a partition $\mathcal{R}$
of $R$ into rectangles such that

  1. (i)

any rectangle in $\mathcal{R}$ has side lengths between $\frac{1}{2}d$ and
$d$;

  2. (ii)

for any rectangle $\tilde{R}$ in $\mathcal{R}$, any corner of $\tilde{R}$ is
at least $\frac{1}{60}\epsilon d$ apart from any point in $S$;

  3. (iii)

no point of $R$ is within $\frac{1}{60}\epsilon d$ of four different
rectangles in $\mathcal{R}$.

###### Proof.

We first note that if $p$ is any point on the boundary of $R$ then within
$\frac{1}{10}\epsilon d$ of $p$ there is a point $q$ on the boundary of $R$
such that $q$ is at least $\frac{1}{60}\epsilon d$ apart from any corner of
$R$ or any point of $S$. In fact, if $p$ is at least $\frac{1}{60}\epsilon d$
apart from any corner of $R$ or any point of $S$, then we let $q=p$.
Otherwise, some corner of $R$ or point of $S$ is within $\frac{1}{60}\epsilon
d$ of $p$. Consider all the points on the boundary of $R$ that are within
$\frac{1}{20}\epsilon d$ of $p$. If there are no other corner of $R$ or point
of $S$ in this set, then some point $q$ can be selected from this set to
satisfy the requirement. Otherwise, it must be the case that both a corner of
$R$ and a point of $S$ are within $\frac{1}{20}\epsilon d$ of $p$. Now
consider the set of all points on the boundary of $R$ that are within
$\frac{1}{10}\epsilon d$ of $p$. By our assumption about $R$ and $S$, there
are no other points in this set that is either a corner of $R$ or a point of
$S$. A point $q$ can be selected from this set to satisfy the requirement.

It is worth noting that the point $q$ can be chosen from either side of $p$ on
the boundary of $R$ as long as its choice is not blocked by the existence of a
corner on one side. This observation will be useful in our argument below.

Next, we claim that if $p$ is any point on the boundary of $R$ that is not
itself a corner and $l$ is the unique line of the boundary of $R$ that
contains $p$, then there is a point $q$ on $l$ within $\frac{1}{5}\epsilon d$
of $p$ such that $q$ is at least $\frac{1}{60}\epsilon d$ apart from any
corner of $R$ or any point of $S$, and, letting $s$ be the ray starting from
$q$ that is perpendicular to $l$ and pointing to the interior of $R$, then the
very first intersection of $s$ with another part of the boundary of $R$ is a
point $r$ that is also at least $\frac{1}{60}\epsilon d$ apart from any corner
of $R$ or any point of $S$.

To prove this claim we need to consider a number of cases. However, the
argument for all these cases are similar. We only give the argument for one
case. Suppose $p$ is within $\frac{1}{60}\epsilon d$ of a corner of $R$ and
within $\frac{1}{30}\epsilon d$ of a point in $S$. This is illustrated in
Figure 1.

$p$$R$$S$$q^{\prime}$$q$$l$$m$$r$$r^{\prime}$$s^{\prime}$$s$ Figure 1.
Avoiding corners of $R$ and points of $S$

The above mentioned corner of $R$ and the point in $S$ must be on two opposite
sides of $p$ on $l$. In this case we still can pick a point $q^{\prime}$ on
$l$ within $\frac{1}{10}\epsilon d$ of $p$ such that $q^{\prime}$ is at least
$\frac{1}{60}\epsilon d$ apart from any point of $S$. Obviously $q^{\prime}$
is on the opposite side of $p$ as the corner of $R$ is. Note that by our
assumptions the next point of $S$ is at least $\epsilon d$ apart from $p$, and
therefore at least $\frac{9}{10}\epsilon d$ apart from $q^{\prime}$. Now let
$s^{\prime}$ be the ray through $q^{\prime}$ that is perpendicular to $l$ and
pointing to the interior of $R$. Let $r^{\prime}$ be the first intersection of
$s^{\prime}$ with a boundary part of $R$, which we denote by $m$. $m$ and $l$
are parallel. Draw a ray through $p$ that is perpendicular to $l$ and pointing
to the interior of $R$. Then on $m$, on the opposite side of $r^{\prime}$,
there is not a corner of $R$ that is within $\epsilon d$ of $r^{\prime}$. This
is because, otherwise, by comparing the corner close to $p$ and such a corner,
we obtain two parallel sides of $R$ that are within perpendicular distance $d$
of each other, contradicting our assumption. Thus, on this side of
$r^{\prime}$ of $m$ there is a point $r$ within $\frac{1}{10}\epsilon d$ of
$r^{\prime}$ such that $r$ is at least $\frac{1}{60}\epsilon d$ apart from any
point of $S$. Now let $q$ be on $l$ and $s$ be the ray to give $r$ as the
intersection of $s$ with $m$. Then $p$ and $q$ are on opposite sides of
$q^{\prime}$ on $l$, and $q$ is within $\frac{1}{10}\epsilon d$ of
$q^{\prime}$. Thus $q$ is within $\frac{1}{5}\epsilon d$ of $p$ and is as
required.

We use the above claim tacitly in the following finite subdivision algorithm.
The algorithm consists of four steps. In the first step, for each horizontal
boundary side $l$ of $R$ draw a horizontal line $l^{\prime}$ within $R$ so
that the distance between $l$ and $l^{\prime}$ is in between $3d$ and $4d$,
and that the two intersections of $l^{\prime}$ with the boundary of $R$ are at
least $\frac{1}{60}\epsilon d$ away from any corner of $R$ or point of $S$. In
the second step, for each vertical boundary line $l$ of $R$ whose extension
intersects the interior of $R$, extend $l$ until it intersects the first
horizontal line that is created in the first step of the algorithm. The first
two steps of the algorithm is illustrated in Figure 2.

Figure 2. The first two steps of the subdivision algorithm

The first two steps give a subdivision of $R$ into rectangles of side lengths
at least $3d$. Also, no point is within $4d$ of four distinct rectangles. For
each of these rectangles, say $R^{\prime}$, let $S^{\prime}$ be the set of its
non-corner boundary points that are either in $S$ or next to a corner of
another rectangle created in the first two steps. Then any point of
$S^{\prime}$ is at least $\frac{1}{60}\epsilon d$ apart from a corner of
$R^{\prime}$ and any two points of $S^{\prime}$ are at least $\epsilon d$
apart if their distance is $>1$. Now in the third step of the algorithm, we
introduce vertical lines to each rectangle $R^{\prime}$ to subdivide it into
smaller rectangles. For each $R^{\prime}$, the distances between any two
vertical lines will be between $\frac{1}{2}d$ and $d$, and the intersections
of these new lines with the boundary of $R^{\prime}$ will be at least
$\frac{1}{60}\epsilon d$ apart from any point of $S^{\prime}$. This can
clearly be done to any $R^{\prime}$ with the assumed property of $S^{\prime}$,
using the fact that the edges of $R^{\prime}$ have lengths at least $3d$. It
takes a moment of reflection to see that after this is done to each rectangle,
we add to the $S^{\prime}$ for a neighboring rectangle, but we still maintain
the property that any two points of $S^{\prime}$ is at least $\epsilon d$
apart if their distance is $>1$. Thus this can be done to all rectangles one
by one. Moreover, after all these divisions by vertical lines are completed,
each of the resulting rectangles also satisfies the property that any two
points of the new $S^{\prime}$ is at least $\epsilon d$ apart if their
distance is $>1$ and at least $\frac{1}{60}\epsilon d$ apart from a corner. In
addition, the resulting rectangles from the third step all have width between
$\frac{1}{2}d$ and $d$. Finally, in the fourth step of the algorithm we
introduce only horizontal lines to further subdivide the rectangles resulting
from the third step. The final resulting rectangles will have side lengths
between $\frac{1}{2}d$ and $d$, and all of their corners will be at least
$\frac{1}{60}\epsilon d$ apart from other corners from neighboring rectangles
or from a point of $S$. Thus the proof of the lemma is complete. ∎

We can apply Lemma 2.2 to obtain clopen rectangular partitions of
$F(2^{\mathbb{Z}^{2}})$ in which no four rectangles come together. We state
this in the next lemma.

######  Lemma 2.3.

For all sufficiently large $d$ there is a clopen rectangular partition on
$F(2^{\mathbb{Z}^{2}})$ having the following properties:

  1. (1)

All of the rectangles in the partition have side lengths between
$\frac{1}{2}d$ and $d$.

  2. (2)

No point is within distance $\frac{1}{120}d$ of four distinct rectangles of
the partition.

###### Proof.

In order to get this we only need to modify step (3) of the standard
construction as sketched before Lemma 2.2. We also assume that $d^{\prime}>d$
is sufficiently large so that $\epsilon d^{\prime}>12d$, where $\epsilon$ is
as in $(2)$ of the sketch before Lemma 2.2. Using the big-marker-little-marker
procedure one produces a clopen covering of $F(2^{\mathbb{Z}^{2}})$ by
rectangles of side lengths at least $d^{\prime}$, and such that distinct
parallel edges are at least $\epsilon d^{\prime}$ apart. At each stage $i$ (as
determined by the big-marker-little-marker procedure) we subtract from each
stage $i$ rectangle the rectangles that intersect it from earlier stages. This
produces a rectangular polyhedral region $R$ with the property that parallel
edges at least $\epsilon d^{\prime}>12d$ apart. We simultaneously subdivide
the rectangular polyhedron $R$ into smaller rectangular regions using Lemma
2.2. We apply the lemma using $\epsilon=\frac{1}{2}$ and the set $S$ being the
points on the boundary of $R$ of distance $1$ from a perpendicular edge of a
(smaller) rectangle produced at an earlier stage together with the points on
the boundary of $R$ which are on the edge of a (larger, not yet subdivided)
rectangle corresponding to a later stage $j>i$ in the big-marker-little-marker
procedure. The resulting rectangular partition produced at the end has the
desired property. ∎

###  2.2. Review of orthogonal marker region construction

In [9] we also gave a construction of the so-called orthogonal marker regions
on $F(2^{\mathbb{Z}^{n}})$. For the orthogonal marker region construction we
have a sequence $d_{0}<d_{1}<\cdots$ of marker distances. We refer to $d_{k}$
as the $k$-th marker distance. For our arguments we need the sequence of
marker distances to grow reasonably fast. We will implicitly assume in the
following that there is a fixed constant $K=K(n)$ (depending on the dimension
$n$) such that $d_{k+1}>Kd_{k}$ for all $k$.

The orthogonal marker regions will be a sequence $\mathcal{R}_{m}$ of clopen
partitions of $F(2^{\mathbb{Z}^{n}})$ into polygonal regions each of which is
a union of rectangles. We inductively define the $m$th clopen partition
$\mathcal{R}_{m}$. To begin, we let $\mathcal{R}^{m}_{m}$ be a clopen
rectangular partition of $F(2^{\mathbb{Z}^{n}})$ with side lengths in
$\\{d_{m},d_{m}+1\\}$. We may construct this partition so that parallel edges
which are distance $>1$ apart are distance $>\epsilon_{0}d_{m}$ apart, for
some fixed $\epsilon_{0}>0$ (this was implicit in the argument of Lemma 2.3
except here we do not need Lemma 2.2 but rather can use a simpler subdivision
algorithm obtained by just extending the faces of the earlier regions which
intersect a rectangular region at some stage of the construction).

We successively modify the regions to produce clopen partitions
$\mathcal{R}^{m}_{m-1},\dots,\mathcal{R}^{m}_{1}$, and we will let
$\mathcal{R}_{m}=\mathcal{R}^{m}_{1}$. Suppose we have defined
$\mathcal{R}^{m}_{k+1}$. We again use a big-marker-little-marker construction
by working with $d^{\prime\prime}\gg d^{\prime}\gg d_{k}$ to produce
rectangular marker regions $\tilde{\mathcal{R}}$ of side lengths between
$\frac{1}{2}d_{k}$ and $d_{k}$. More specifically, let $\mathcal{R}$ be a
clopen covering of $F(2^{\mathbb{Z}^{n}})$ by rectangles with side lengths
approximately $d^{\prime}$. We then adjust the faces of rectangles in
$\mathcal{R}$ to produce another clopen covering $\mathcal{R}^{\prime}$ such
that parallel faces of distinct regions in the covering are at least
$3\epsilon^{\prime}d^{\prime}$ apart, for some fixed $\epsilon^{\prime}>0$. We
may assume $\epsilon^{\prime}d^{\prime}>12d_{k}$. We then do a secondary
adjustment to produce $\mathcal{R}^{\prime\prime}$ by moving the faces of the
regions in $\mathcal{R}^{\prime}$ no more than $\epsilon^{\prime}d^{\prime}$
so that the perpendicular distance between parallel faces of a region in
$\mathcal{R}^{\prime\prime}$ and a nearby region of $\mathcal{R}^{j}_{k}$ for
all $k\leq j<m$ are at least $\epsilon_{1}d_{k}$ apart, for some fixed
$\epsilon_{1}>0$ which also depends only on $n$. We still have that parallel
faces of distinct regions in $\mathcal{R}^{\prime\prime}$ are at least
$\epsilon^{\prime}d^{\prime}>12d_{k}$ apart. We then do a subdivision
algorithm to produce a clopen partition $\tilde{\mathcal{R}}$ so that each
rectangular region in the partition has side lengths between
$\frac{1}{2}d_{k}$ and $d_{k}$, and each face of a region in
$\tilde{\mathcal{R}}$ is at least $\epsilon_{2}d_{k}$ from any parallel face
of a nearby region in $\mathcal{R}^{j}_{k}$ for $k\leq j<m$, and at least
$\epsilon_{2}d_{k}$ from a parallel face of a region in $\tilde{\mathcal{R}}$
if it has distance $>1$ from that face.

We then get a clopen assignment to each region $\tilde{R}$ of
$\tilde{\mathcal{R}}$ one of the regions of $\mathcal{R}^{m}_{k+1}$ which
intersect it. We then replace each region $R$ of $\mathcal{R}^{m}_{k+1}$ with
the union of the $\tilde{R}$ which are assigned to $R$. Thus we have obtained
$\mathcal{R}^{m}_{k}$. Note that each region $R$ of the partition
$\mathcal{R}^{m}_{k}$ is a finite union of rectangular regions from the
$\tilde{\mathcal{R}}$ partition.

If we let $\epsilon=\epsilon(n)=\min\\{\epsilon_{1},\epsilon_{2}\\}$, then we
have the following properties of the $\mathcal{R}^{m}_{k}$.

######  Definition 2.4.

The orthogonality properties of the $\mathcal{R}^{m}_{k}$ are the following.

  1. (1)

(bounded geometry) $\mathcal{R}^{m}_{k}$ is a clopen partition of
$F(2^{\mathbb{Z}^{n}})$, and each region $R$ in $\mathcal{R}^{m}_{k}$ is a
finite disjoint union of rectangles in $\tilde{R}$ with side lengths between
$\frac{1}{2}d_{k}$ and $d_{k}$.

  2. (2)

(orthogonality to previous regions) Any face $F$ of a region in
$\mathcal{R}^{m}_{k}$ is at least $\epsilon d_{k}$ away from any parallel face
$F^{\prime}$ of a nearby region in $\mathcal{R}^{j}_{k}$ for any $k\leq j<m$.

  3. (3)

(orthogonality to same regions) Any face $F$ of a region in
$\mathcal{R}^{m}_{k}$ is at least $\epsilon d_{k}$ away from any parallel face
$F^{\prime}$ of a nearby region in $\mathcal{R}^{m}_{k}$ unless
$\rho(F,F^{\prime})\leq 1$.

As we said above, we set $\mathcal{R}_{m}=\mathcal{R}^{m}_{1}$. This completes
the review of the construction of the basic orthogonal marker regions, for a
given set of distances $d_{0}<d_{1}\cdots$. We note explicitly for later
purposes that for each dimension $n$, there is a fixed constant $K=K(n)$ such
that if $d_{k+1}>Kd_{k}$ for all $k$, then the orthogonal marker construction
can be carried out.

It is not clear that the orthogonal marker regions that we constructed above
are connected and have connected boundaries. These connectedness properties
will be useful later, so we note below that they can be arranged with a
refinement or a variation of the above construction.

A subset $S\subseteq\mathbb{Z}^{n}$ is connected if it is connected in the
Cayley graph of $\mathbb{Z}^{n}$ with the standard generators. For any set
$S\subseteq\mathbb{Z}^{n}$ we define the boundary of $S$, denoted by $\partial
S$, to be the set of points $x\in S$ such that $e\cdot x\not\in S$ for one of
the standard generators $e$. Since the regions we consider will be finite
unions of rectangles with reasonably big side lengths, we will regard such
$S\subseteq\mathbb{Z}^{n}$ as a subset of $\mathbb{R}^{n}$ in the obvious way
and speak of their connectedness, simple connectedness, and their boundaries
as subsets of $\mathbb{R}^{n-1}$. This convention will make our discussion
easier.

######  Theorem 2.5.

For some fixed $\epsilon=\epsilon_{n}>0$ there are clopen partitions
$\mathcal{R}_{m}$ of $F(2^{\mathbb{Z}^{n}})$ satisfying the orthogonality
properties so that each region $R$ of an $\mathcal{R}_{m}$ partition is
connected and also its boundary $\partial R$ is connected. In fact each region
$R$ is homeomorphic to the closed unit ball in $\mathbb{R}^{n}$.

The rest of this subsection is devoted to a proof of Lemma 2.5 for the
dimension $n=2$ case. A different proof for the general case will be given in
the next subsection. We first give a proof for the dimension $n=2$ case as the
argument in this case requires less modification of the construction, and the
$n=2$ case suffices for the applications we will have later in the paper.

We follow the general outline of the standard construction of orthogonal
marker regions but make several modifications. First, in constructing
$\mathcal{R}^{m}_{m}$ we use Lemma 2.3 and ensure that no point is close to 4
rectangular marker regions. In the subsequent steps, we will maintain this
property at each step of the construction. Suppose we have defined
$\mathcal{R}^{m}_{k+1}$ and for each region $R$ of $\mathcal{R}^{m}_{k+1}$ we
have that $R$ and $\partial R$ are connected. In fact, we will inductively
assume that the $\mathcal{R}^{m}_{k+1}$ regions are homeomorphic to the closed
unit disk via a homeomorphism which maps the boundary to the unit circle (and
so induces a homeomorphism between the boundary and the unit circle). As in
the standard orthogonal marker regions construction, we define an auxiliary
clopen rectangular partition $\tilde{\mathcal{R}}$ in the step of the
construction of $\mathcal{R}^{m}_{k}$ from $\mathcal{R}^{m}_{k+1}$. In
defining the $\tilde{\mathcal{R}}$ partition, we use scale $d_{k}$ and Lemma
2.3 to get the partition $\tilde{\mathcal{R}}$. Thus, every point $x$ of
$F(2^{\mathbb{Z}^{2}})$ is close to at most $3$ distinct regions of
$\tilde{\mathcal{R}}$ (i.e., no $4$ regions of $\tilde{\mathcal{R}}$ come
together).

The next step is to assign the regions $\tilde{R}$ of $\tilde{\mathcal{R}}$ to
the regions $R$ of $\mathcal{R}^{m}_{k+1}$. Instead of doing the assignment
arbitrarily as in the standard construction, we make the following
modification. Call a region $\tilde{R}$ exceptional if it intersects $3$
distinct regions of $\tilde{\mathcal{R}}^{m}_{k+1}$. First, we assign the
exceptional regions $\tilde{R}$ to regions $R$ of $\mathcal{R}^{m}_{k+1}$ as
follows. Let $R_{1},R_{2},R_{3}$ be the three regions of
$\mathcal{R}^{m}_{k+1}$ which intersect $\tilde{R}$. Label them so that
$R_{3}$ is the region which contains an entire face of $\tilde{R}$ (see Figure
3). Assign $\tilde{R}$ to $R_{1}$. Then, for the regions $\tilde{R}^{\prime}$
in $\tilde{\mathcal{R}}$ that are within $2d_{k}$ distance of the exceptional
$\tilde{R}$, assign $\tilde{R}^{\prime}$ to $R_{1}$ if $\tilde{R}^{\prime}$
intersects $R_{1}$. Next, for those regions $\tilde{R}^{\prime}$ in
$\tilde{\mathcal{R}}$ that are within $2d_{k}$ distance to $\tilde{R}$, if
they have not been assigned, assign them to $R_{2}$. Figure 3 illustrates this
assignment process near the exceptional rectangles of $\tilde{R}$.

$R_{1}$$R_{2}$$R_{3}$ Figure 3. The assignment algorithm in dimension 2. The
red rectangles are assigned to $R_{1}$, and the blue ones to $R_{2}$.

The rectangles $\tilde{R}^{\prime}$ of $\tilde{\mathcal{R}}$ which are not
within $2d_{k}$ of an exceptional rectangle are assigned arbitrarily as
before. The regions of $\mathcal{R}^{m}_{k}$ are obtained from this assignment
as in the standard construction. It is clear that the orthogonality properties
are satisfied as before. We only verify that the regions are homemorphic to
the unit disk (with boundaries mapping to the unit circle).

A region $R^{\prime\prime}$ of $\mathcal{R}^{m}_{k}$ is obtained from a region
$R$ of $\mathcal{R}^{m}_{k+1}$ in two steps. First, for each exceptional
rectangle $\tilde{R}$ which intersects $R$, we add or subtract from $R$ the
rectangles of $\tilde{\mathcal{R}}$ within $2d_{k}$ of $\tilde{R}$ according
to the above algorithm (the region $R$ corresponds to one of the regions
$R_{1}$, $R_{2}$, $R_{3}$ in the above description, and which one may depend
on $\tilde{R}$). Let $R^{\prime}$ be the region obtained from $R$ in this
first step. In the second step we produce $R^{\prime\prime}$ from $R^{\prime}$
by adding or subtracting from $R^{\prime}$ all of the rectangles $\tilde{R}$
in $\tilde{\mathcal{R}}$ which intersect $R$ (or equivalently $R^{\prime}$)
not within $2d_{k}$ of an exceptional rectangle intersecting $R$. We first
show that $R^{\prime}$ is homeomorphic to $R$ (and thus by induction to the
unit ball). Consider a single exceptional rectangle $\tilde{R}$ of
$\tilde{\mathcal{R}}$ which intersects $R$. With respect to $\tilde{R}$, that
is, in considereing the rectangles of $\tilde{\mathcal{R}}$ within $2d_{k}$ of
$\tilde{R}$, $R$ may be considered as $R_{1}$, $R_{2}$, or $R_{3}$ in the
algorithm. If $R$ is considered as $R_{1}$, then all of the rectangles of
$\tilde{\mathcal{R}}$ within $2d_{k}$ of $\tilde{R}$ which intersect $R$ are
added to $R$ in forming $R^{\prime}$. There is clearly a homeomophism of this
new region with $R$ which preserves boundaries, and is obtained by contracting
each of these rectangles in $\tilde{\mathcal{R}}$ back to the boundary of $R$.
These homeomorphism can be taken to be the identity outside of
$B(\tilde{R},3d_{k})$, the $3d_{k}$ neighborhood of $\tilde{R}$. Suppose $R$
is considered as an $R_{2}$ region with respect to $\tilde{R}$. In this case
we obtain $R^{\prime}$ within a $3d_{k}$ neighborhood of $\tilde{R}$ by first
removing the rectangles within $2d_{k}$ of $\tilde{R}$ which intersect both
$R_{1}$ and $R_{2}$, and then adding the rectangles which intersect $R_{2}$
but not $R_{1}$. After removing the first set of rectangles the result is
homeomorphic to $R_{2}$ by the same contraction argument used in the $R_{1}$
case. There is also a homeomorphism which contracts the added rectangles back
to the boundary of $R$. Both of these homeomorphisms will be the identity
outside of $B(\tilde{R},3d_{k})$. Combining these two homeomorphisms gives a
homeomorphism between $R^{\prime}\cap B(\tilde{R},2d_{k})$ with $R\cap
B(\tilde{R},2d_{k})$ which is the identity outside of $B(\tilde{R},3d_{k})$.
In the third case where $R$ is considered as the $R_{3}$ region, we remove all
of the rectangles which intersect $R$ within $2d_{k}$ of $\tilde{R}$ in
forming $R^{\prime}$. Clearly a simple contraction of these rectangles to the
boundary of $R$ gives the homeomorphism in this case as well. Since the
different exceptional rectangles which intersect $R$ are at least $\epsilon
d_{k+1}\gg 3d_{k}$ apart, we can combine these homeomorphisms from these
exceptional rectangles meeting $R$ to produce a (boundary preserving)
homeomorphism from $R^{\prime}$ to $R$.

We next show $R^{\prime\prime}$ is homeomorphic to $R^{\prime}$ by a boundary
preserving homeomorphism. For each edge $l$ of $R$, say $l$ is horizontal, let
$M_{l}$ be the the set of rectangles in $\tilde{\mathcal{R}}$ which intersects
$l$ and are not within $2d_{k}$ of an exceptional rectangle $\tilde{R}$. Let
$S_{l}$ be the rectangle whose horizontal edges have distance $d_{k}+\epsilon$
from $l$, for some small $\epsilon>0$, and whose left edge has $x$-coordinate
$a-\epsilon$ where the leftmost rectangle $A$ in $M_{l}$ has $x$-coordinate
$a$.

$R$$B(\tilde{R},2d_{k})$$l$$S_{l}$$M_{l}$ Figure 4. The construction of
$R^{\prime\prime}$ from $R^{\prime}$. The blue rectangles are to be added and
the red ones to be removed.

Likewise, the right edge of $S_{l}$ has $x$-coordinate $b+\epsilon$ where $b$
is the $x$-coordinate of the right edge of the rightmost rectangle $B$ in
$M_{l}$. If $l$ is vertical the rectangle $S_{l}$ is similarly defined. Figure
4 illustrates these definitions. Note that none of the rectangles in
$\tilde{\mathcal{R}}$ which intersect a different edge $l^{\prime}$ of $R$
will intersect $S_{l}$. In fact, if $S_{l^{\prime}}$ denotes the corresponding
rectangle for the edge $l^{\prime}$, then $S_{l}\cap S_{l^{\prime}}=\emptyset$
(if $\epsilon<\frac{1}{2}d_{k}$). It is easy to see that there is
homeomorphism of $S_{l}$ with itself which is the identity on the boundary of
$S_{l}$ and which maps $S_{l}\cap R^{\prime}$ to $S_{l}\cap R^{\prime\prime}$.
Combining these homeomorphisms for the different edges of $R$ gives a
homeomorphism from $R^{\prime}$ to $R^{\prime\prime}$.

This finishes a proof of Theorem 2.5 for the $n=2$ case.

###  2.3. Connected orthogonal marker regions

In this subsection we give a proof of the general case of Theorem 2.5 that
requires more substantial modifications of the standard construction of
orthogonal marker regions.

We still follow the general outline of the standard construction.
Specifically, we will construct an auxiliary clopen rectangular partition
$\tilde{\mathcal{R}}$ in the construction of $\mathcal{R}^{m}_{k}$ from
$\mathcal{R}^{m}_{k+1}$. However, in constructing $\tilde{\mathcal{R}}$, we
will use $n+1$ many scale values
$\epsilon_{0}d^{\prime}_{k}<\epsilon_{1}d^{\prime}_{k}<\cdots<\epsilon_{n}d^{\prime}_{k}$
instead of the single value $d_{k}$ as before. At the end we will take
$d_{k}=\epsilon_{0}d^{\prime}_{k}$. By subdividing the rectangles in
$\tilde{\mathcal{R}}$ we will produce a clopen partition $\tilde{S}$ with side
lengths between $\frac{1}{2}d_{k}$ and $d_{k}$ and an assignment map which
assigns to each $S\in\tilde{S}$ a region of $\mathcal{R}^{m}_{k+1}$ so that
the resulting regions define the partition $\mathcal{R}^{m}_{k}$ which satisfy
Theorem 2.5 for some $\epsilon>0$.

We first let $\mathcal{R}$ be a clopen partition of $F(2^{\mathbb{Z}^{n}})$
into rectangles of side lengths between $\frac{1}{2}d^{\prime}_{k}$ and
$d^{\prime}_{k}$. We may assume that for some $\eta>0$ (which depends only on
$n$) that (2) and (3) of the orthogonality properties hold using the constant
$\eta$. Furthermore, we may assume that every face of a rectangle in
$\mathcal{R}$ is also at least $\eta d^{\prime}_{k}$ away from any parallel
face of a nearby rectangle in $\mathcal{R}^{m}_{k+1}$. Fix
$\epsilon_{0}<\epsilon_{1}<\cdots<\epsilon_{n}$ with
$\epsilon_{n}<\frac{1}{3}\eta$ and $\epsilon_{j}<\frac{1}{12}\epsilon_{j+1}$
for all $j<n$.

Say a rectangle $R$ in $\mathcal{R}$ is of type $j$ (where $0\leq j\leq n$) if
there are exactly $j$ distinct basic unit vectors $e$ such that $R$ intersects
a face of some $\mathcal{R}^{m}_{k+1}$ region which is perpendicular to $e$.
In particular, $R$ is of type 0 if it does not intersect any face of an
$\mathcal{R}^{m}_{k+1}$ region, and it is of type $n$ if intersects a corner
of an $\mathcal{R}^{m}_{k+1}$ region.

To construct the partition $\tilde{\mathcal{R}}$, we further subdivide the
rectangles in $\mathcal{R}$. We begin with the rectangles $R$ in $\mathcal{R}$
of type $n$. Note that $R$ is a rectangle of side lengths between
$\frac{1}{2}d_{k}^{\prime}$ and $d_{k}^{\prime}$, whereas any region in
$\mathcal{R}^{m}_{k+1}$ is a disjoint union of finitely many rectangles each
of which has side lengths at least $\frac{1}{2}d_{k+1}$, with $d_{k+1}\gg
d_{k}^{\prime}$. Also by our assumption, $R$ intersects $n$ many mutually
perpendicular faces of a $\mathcal{R}^{m}_{k+1}$ region. Since
$\epsilon_{n}<\frac{1}{3}\eta\ll\frac{1}{2}$, we may subdivide $R$ into
rectangles $S$ with side lengths between
$\frac{2}{3}\epsilon_{n}d^{\prime}_{k}$ and $\epsilon_{n}d^{\prime}_{k}$ such
that the perpendicular distance between any face of $S$ and a parallel face of
an $\mathcal{R}^{m}_{k+1}$ region intersecting $R$ is at least
$\frac{1}{4}\epsilon_{n}d^{\prime}_{k}$. Let $\tilde{\mathcal{R}}_{n}$ be the
resulting partition. Let $\mathcal{S}_{n}$ be the collection of all rectangles
of type $n$ in $\tilde{\mathcal{R}}_{n}$. At the next step we consider the
rectangles $R$ in $\tilde{\mathcal{R}}_{n}$ of type $n-1$. These include both
the rectangles in $\mathcal{R}$ of type $n-1$ and the rectangles $S$ in a
subdivision from the first step which happen to be of type $n-1$. We subdivide
all of these rectangles into rectangles with side lenghs between
$\frac{2}{3}\epsilon_{n-1}d_{k}^{\prime}$ and $\epsilon_{n-1}d_{k}^{\prime}$
in such a way that the distance from any of their faces to a face of a region
in $\mathcal{R}^{m}_{k+1}$ is at least
$\frac{1}{4}\epsilon_{n-1}d_{k}^{\prime}$. Let the resulting partition be
$\tilde{\mathcal{R}}_{n-1}$. Let $\mathcal{S}_{n-1}$ be the collection of all
rectangles in these subdivisions which are still of type $n-1$. Continuing in
this manner we define the partitions
$\tilde{\mathcal{R}}_{n},\dots,\tilde{\mathcal{R}}_{1}=\tilde{\mathcal{R}}$
each of which is a refinement of the previous one in the sequence. We also
obtain collections $\mathcal{S}_{n},\dots,\mathcal{S}_{1}$, and
$\mathcal{S}_{j}$ is the collection of all rectangles of type $j$ in the
partition $\tilde{\mathcal{R}}$. In summary, each rectangle in
$\mathcal{S}_{j}$ has side lengths between
$\frac{2}{3}\epsilon_{j}d_{k}^{\prime}$ and $\epsilon_{j}d_{k}^{\prime}$, and
any face of a rectangle in $\mathcal{S}_{j}$ is at least
$\frac{1}{4}\epsilon_{j}d_{k}^{\prime}$ from a parallel face in
$\mathcal{R}^{m}_{k+1}$. Also, each rectangle in $\mathcal{S}_{j}$ is of type
$j$. We let $\tilde{\mathcal{R}}$ be the collection
$\bigcup_{j}\mathcal{S}_{j}$. The standard arguments show that we may assume
that there is an $\epsilon^{\prime}>0$ such that the orthogonality properties
2 and 3 holds for the faces of regions in $\tilde{\mathcal{R}}$ using constant
$\epsilon^{\prime}$.

We define $\mathcal{R}^{m}_{k}$ using $\tilde{\mathcal{R}}$ and an arbitrary
assignment of the rectangles in $\tilde{\mathcal{R}}$ to regions of
$\mathcal{R}^{m}_{k+1}$ which intersect them. Figure 5 illustrates this
construction in dimension 2.

$R_{1}$$R_{2}$$R_{3}$$S_{2}$$S_{1}$ Figure 5. The second construction in
dimension 2.

It is clear from our construction that the orthogonality properties hold for
$\mathcal{R}^{m}_{k}$. We verify that each region of $\mathcal{R}^{m}_{k}$ is
homeomorphic to the closed unit ball via a homemorphism which preserves the
boundaries. This suffices, as we may then take
$d_{k}=\epsilon_{0}d^{\prime}_{k}$ and subdivide the rectangles in
$\tilde{\mathcal{R}}$ to have dimensions between $\frac{1}{2}d_{k}$ and
$d_{k}$ and maintain the orthogonality properties 2, 3 for some constant
$\epsilon>0$.

Fix a region $R$ of $\mathcal{R}^{m}_{k+1}$. Let $A$ be the set of all
rectangles in $\tilde{\mathcal{R}}$ which intersect $\partial R$. Let $A=B\cup
C$ where $B$ are those rectangles in $A$ which are assigned to $R$ and
$C=A-B$. Let $R^{\prime}$ be the region of $\mathcal{R}^{m}_{k}$ corresponding
to $R$, that is, $R^{\prime}$ is the union of $R$ and all of the rectangles in
$B$, minus all of the rectangles in $C$. For $0\leq j\leq n+1$, let $B_{j}$,
$C_{j}$ be those rectangles in $B$, $C$ respectively of type $\geq j$. Let
$A_{j}=B_{j}\cup C_{j}$. Let $R_{j}=(R\cup(\cup B_{j}))-(\cup C_{j})$. Thus,
$R^{\prime}=R_{0}$ and $R=R_{n+1}$. We show for each $0\leq j\leq n$ that
$R_{j}$ is homeomorphic to $R_{j+1}$ by a boundary preserving homeomorphism.
Since $R_{n+1}=R$ is homeomorphic to the ball by induction, this suffices. Let
$T_{j+1}=\cup A_{j+1}$.

Consider a $j$-edge $E$ of $\partial R$. By a $j$-edge we mean a connected
component of the intersection of $j$ mutually perpendicular faces of $R$. Say
the faces determining $E$ have normal vectors $e_{k_{1}},\dots,e_{k_{j}}$. For
$i\in\\{k_{1},\dots,k_{j}\\}$, let $c_{i}$ be the common value of $\pi_{i}(x)$
for $x\in E$. So, $E$ is of the form $E=I_{1}\times I_{2}\times\cdots\times
I_{n}$ where $I_{i}$ is a proper interval for
$i\notin\\{k_{1},\dots,k_{j}\\}$, and for $i\in\\{k_{1},\dots,k_{j}\\}$ we
have $I_{i}=\\{c_{i}\\}$. Let $\pi_{E}$ denote the projection map to $E$, so
$\pi_{E}(t_{1},\dots,t_{n})=(s_{1},\dots,s_{n})$ where $s_{i}=t_{i}$ if
$i\notin\\{k_{1},\dots,k_{j}\\}$, and $s_{i}=c_{i}$ otherwise.

Fix $\epsilon>0$ with $\epsilon_{j}<\epsilon<\frac{1}{4}\epsilon_{j+1}$. Let
$E(\epsilon)=J_{1}\times J_{2}\times\cdots\times J_{n}$ where $J_{i}=I_{i}$
for $i\notin\\{k_{1},\dots,k_{j}\\}$, and $J_{i}=[c_{i}-\epsilon
d_{k}^{\prime},c_{i}+\epsilon d_{k}^{\prime}]$ for
$i\in\\{k_{1},\dots,k_{j}\\}$. Roughly speaking, $E(\epsilon)$ is the
$\epsilon d_{k}^{\prime}$-expansion of $E$ in the directions
$e_{k_{1}},\dots,e_{k_{j}}$.

Let $E^{\prime}(\epsilon)=E(\epsilon)\setminus T_{j+1}$. Let $F=E\setminus
T_{j+1}$. Let $F(\epsilon)$ be the set of all $x=(t_{1},\dots,t_{n})$ such
that $\pi_{E}(x)\in F$ and $t_{i}\in[c_{i}-\epsilon
d_{k}^{\prime},c_{i}+\epsilon d_{k}^{\prime}]$ for
$i\in\\{k_{1},\dots,k_{j}\\}$. So, $F(\epsilon)$ is the $\epsilon
d_{k}^{\prime}$-expansion of $F$ in the directions
$e_{k_{1}},\dots,e_{k_{j}}$. For each $x\in E$, let $x(\epsilon)$ denote the
set of $(t_{1},\dots,t_{n})$ such that $\pi_{E}(t_{1},\dots,t_{n})=x$ and
$t_{i}\in[c_{i}-\epsilon d_{k}^{\prime},c_{i}+\epsilon d_{k}^{\prime}]$ for
$i\in\\{k_{1},\dots,k_{j}\\}$.

######  Claim 2.6.

$E^{\prime}({\epsilon})=F(\epsilon)$.

###### Proof.

It is clear that $F(\epsilon)\subseteq E(\epsilon)$. We show that for every
point $x\in E$, if $x\in F$ then $x(\epsilon)\subseteq E^{\prime}(\epsilon)$,
and if $x\notin F$ then $x(\epsilon)\subseteq T_{j+1}$. The claim then
follows.

To see this, consider $x\in E$. First suppose $x\in T_{j+1}$. Then $x$ lies
both in $E$ and a rectangle $Q$ in $A_{j+1}$ which intersects $E$. Since all
faces determining $E$ are at least
$\frac{1}{4}\epsilon_{j+1}d^{\prime}_{k}>\epsilon d_{k}^{\prime}$ from any
parallel faces of $Q$, it follows that $x(\epsilon)\subseteq Q$. Thus if
$x\notin F$ we have $x(\epsilon)\subseteq T_{j+1}$. Suppose now that $x\in F$.
Suppose toward a contradiction that $y\in x(\epsilon)\cap T_{j+1}$ (that is,
this set is non-empty). Let $L_{k_{1}}$, $L_{k_{2}},\dots,L_{k_{j}}$ be the
natural sequence of line segments of length $\leq\epsilon d_{k}^{\prime}$
which together form a path $p=(u_{0}=x,u_{k_{1}},\dots,u_{k_{j}}=y)$ from $x$
to $y$. Here $L_{k_{r}}$ only involves changing the $k_{r}$ coordinate. More
precisely, $L_{k_{r}}$ is the set of points $z$ with
$\pi_{i}(z)=\pi_{i}(u_{k_{r-1}})$ for $i\neq k_{r}$, and $\pi_{k_{r}}(z)$ is
between $\pi_{k_{r}}(u_{k_{r-1}})=\pi_{k_{r}}(x)=c_{k_{r}}$ and
$\pi_{k_{r}}(u_{k_{r}})=\pi_{k_{r}}(y)$. Let $r$ be minimal such that
$u_{k_{r}}\in T_{j+1}$. Say $u_{k_{r}}\in Q$, where $Q$ is a rectangle in
$A_{j+1}$. Note that $u_{k_{r-1}}$ is on the boundary of $R$, in fact it lies
on a face of $\partial R$ with normal vector $e_{k_{r}}$. However, $u_{k_{r}}$
lies on a face of $Q$ which is perpendicular to $e_{k_{r}}$. This contradicts
the fact that any face of $Q$ is at least
$\frac{1}{4}\epsilon_{j+1}d_{k}^{\prime}>\epsilon d_{k}^{\prime}$ from a
parallel face of $R$. ∎

Figure 6 illustrates the set $E^{\prime}(\epsilon)$ in $3$-dimensions where
$E$ is the $j=1$ “edge” corresponding to the $x,y$ plane. The rectangles in
green form the set $T_{2}$ (those in $T_{1}\setminus T_{2}$ are not shown).
The region in blue is $E^{\prime}(\epsilon)$ (only the top half of it is
shown).

Figure 6. The set $E^{\prime}(\epsilon)$.

Note that by Claim 2.6, $E^{\prime}(\epsilon)\cap R_{j+1}$ is the set of
points $x$ such that $\pi_{E}(x)\in F$ and for $i\in\\{k_{1},\dots,k_{j}\\}$,
$\pi_{i}(x)\in I^{\prime}_{i}$ where $I^{\prime}_{i}$ is an interval of the
form $[c_{i},c_{i}+\epsilon d_{k}^{\prime}]$ or of the form $[c_{i}-\epsilon
d_{k}^{\prime},c_{i}]$. Now, for each such $j$-edge $E$ of $R$ and
corresponding $E^{\prime}(\epsilon)$ there is a boundary preserving
homeomorphism between $E^{\prime}(\epsilon)\cap R_{j}$ and
$E^{\prime}(\epsilon)\cap R_{j+1}$. This is because, by Claim 2.6,
$E^{\prime}(\epsilon)\cap R_{j}$ is obtained from $E^{\prime}(\epsilon)\cap
R_{j+1}$ by adding the rectangles of type $j$ of $B_{j}$ which intersect $F$,
and deleting those of $C_{j}$ which intersect $F$. Each of these rectangles
$T$ is of the form $(T\cap F)\times C$ where $C$ is a $j$-dimensional
rectangle with side lengths $<\epsilon d_{k}^{\prime}$. The homeomorphism is
induced by continuously contracting the edge lengths of $C$ to $0$.

For each $j$-edge $E$ of $R$, let $\varphi_{E}$ be a boundary preserving
homeomorphism of $E^{\prime}(\epsilon)\cap R_{j}$ with
$E^{\prime}(\epsilon)\cap R_{j+1}$. we can take $\varphi_{E}$ to be the
identity on the boundary of $E^{\prime}(\epsilon)$. To finish the proof of
Theorem 2.5 it suffices to show the following claim, which shows that we can
take the union of the $\varphi_{E}$ (and the identity on
$R_{j}\setminus\bigcup_{E}E^{\prime}(\epsilon)$, where the union ranges over
all the $j$-edges $E$ of $R$).

######  Claim 2.7.

Let $E_{1}$, $E_{2}$ be distinct $j$-edges of $R$. Then the corresponding
$E^{\prime}_{1}(\epsilon)$, $E^{\prime}_{2}(\epsilon)$ are disjoint.

###### Proof.

Let $z\in E^{\prime}_{1}(\epsilon)\cap E^{\prime}_{2}(\epsilon)$. Say $E_{1}$
is defined by faces with normal vectors $\\{e_{k_{1}},\dots,e_{k_{j}}\\}$ and
values $c_{i}$ for $i\in\\{k_{1},\dots,k_{j}\\}$ as above. Let
$D_{1}=\\{k_{1},\dots,k_{j}\\}$ (so for $x\in E_{1}$, $\pi_{i}(x)=c_{i}$ for
$i\in D_{1}$). Similarly, let $E_{2}$ be defined by
$\\{e_{\ell_{1}},\dots,e_{\ell_{j}}\\}$ and values $c^{\prime}_{i}$. Let
$D_{2}=\\{\ell_{1},\dots,\ell_{j}\\}$. Since $E_{1}\neq E_{2}$, and $E_{1}$,
$E_{2}$ are both within distance $\epsilon d_{k}^{\prime}$ of $z$, and hence
they are of distance $2\epsilon d_{k}^{\prime}$ of each other, we must have
that $D_{1}\neq D_{2}$.

Let $z_{1}=\pi_{E_{1}}(z)\in E_{1}$, so $z_{1}$ is obtained from $z$ by
changing all of the values $\pi_{i}(z)$, for $i\in D_{1}$, to the value
$c_{i}$. Similarly, let $z_{2}=\pi_{E_{2}}(z)$. Let $w$ be such that
$\pi_{i}(w)=\pi_{i}(z)$ for $i\notin D_{1}\cup D_{2}$, $\pi_{i}(w)=c_{i}$ for
$i\in D_{1}$ and $\pi_{i}(w)=c^{\prime}_{i}$ for $i\in D_{2}-D_{1}$. That is,
$w$ is the result of changing the values $\pi_{i}(z)$ for $i\in D_{1}\cup
D_{2}$. Since $D_{1}\neq D_{2}$, $w$ lies on a $j^{\prime}$-edge of $R$ for
$j^{\prime}\geq j+1$. Also $w$ and $z$ are within $\epsilon d_{k}^{\prime}$ of
each other. This is a contradiction as $w$ lies in a rectangle $Q\in T_{j+1}$,
and all faces of $Q$ which are perpendicular to a direction in $D_{1}\cup
D_{2}$ have distance at least
$\frac{1}{4}\epsilon_{j+1}d_{k}^{\prime}>\epsilon d_{k}^{\prime}$ from $w$. ∎

##  3\. Orthogonal Decompositions in $F(2^{\mathbb{Z}^{n}})$

In §2 we recalled the construction of the orthogonal marker regions
$\mathcal{R}_{k}=\mathcal{R}^{k}_{1}$ for $F(2^{\mathbb{Z}^{n}})$
corresponding to a set of marker distances $d_{1}<d_{2}<\cdots$ (which satisfy
$d_{k+1}/d_{k}\geq K$ for some constant $K=K(n)$ depending only on the
dimension $n$). A slightly different point of view results in what we call an
orthogonal decomposition for $F(2^{\mathbb{Z}^{n}})$. In §4 we will present a
more general form of the definition in the context of a Borel graphing of a
countable Borel equivalence relation. The basic idea is to consider the sets
$X_{k}=\partial\mathcal{R}_{k}=\bigcup\\{\partial R:R\in\mathcal{R}_{k}\\}$,
the set of boundary points for the regions in the Borel partition
$\mathcal{R}_{k}$. These sets are not pairwise disjoint, but they intersect in
a controlled fashion which we make precise below. We record here the strongest
forms of these intersection properties, while in §4 we abstract a weaker
version on these properties which nonetheless suffices for some applications
(e.g., the existence of toast structures and the Borel proper $3$-coloring of
the Schreier graph on $F(2^{\mathbb{Z}^{n}})$).

For each $k$ we consider all the partitions $\mathcal{R}_{m}$ for $m\geq k$
and let $\mathcal{A}_{k}$ be the coarsest common refinement of all of them. We
call the elements of $\mathcal{A}_{k}$ the $k$-atoms of the orthogonal
decomposition. In contrast, we write $X_{k}^{\infty}$ for
$\bigcup_{m=k}^{\infty}X_{m}=\bigcup_{m=k}^{\infty}\partial\mathcal{R}_{m}$
and let $\mathcal{R}(k)$ denote the collection of connected components of
$X-X_{k}^{\infty}$ (where $X=F(2^{\mathbb{Z}^{n}})$). We call these connected
components of $X-X_{k}^{\infty}$ the $k$-nuclei of the orthogonal
decomposition. In §5 we will show that we may maintain certain topological
regularity for the $k$-atoms and the $k$-nuclei, as shown possible in Theorem
2.5 for the marker regions $R\in\mathcal{R}_{k}$ themselves. This will
guarantee that the $k$-atoms and $k$-nuclei are in one-one correspondence, and
that each $k$-nucleus is exactly the interior of a $k$-atom. In the rest of
this section we describe the basic orthogonality properties of the $k$-nuclei.

The following theorem summarizes the properties of the orthogonal
decomposition.

######  Theorem 3.1.

Let $\mathcal{R}_{m}$ be a sequence of marker regions for
$X=F(2^{\mathbb{Z}^{n}})$ satisfying the orthogonal properties for distances
$d_{1}<d_{2}<\cdots$ as contructed in the proof of Theorem 2.5. Let
$X_{k}=\partial\mathcal{R}_{k}$, and
$X_{k}^{\infty}=\bigcup_{m=k}^{\infty}X_{m}$. Then the following hold.

  1. (1)

$\bigcap_{k}X_{k}^{\infty}=\emptyset$, and for each $k$ the connected
components of $X-X_{k}^{\infty}$ are finite.

  2. (2)

(strong orthogonality) There is a constant $\epsilon=\epsilon(n)>0$ and a
function $\delta\colon X\times\mathbb{N}\times\mathbb{N}\to n$ such that
$\delta(x,k,\ell)=0$ unless $x\in X_{k}^{\infty}$ and $\ell\leq k$, and
satisfying: if $k<k^{\prime}$, $x\in X_{k}$, $x^{\prime}\in X_{k^{\prime}}$,
then for any $\ell\leq k$ if we have
$\delta(x,k,\ell)=\delta(x^{\prime},k^{\prime},\ell)$, then
$\rho(x,x^{\prime})>\epsilon d_{\ell}$.

###### Proof.

Each connected component of $X-X_{k}^{\infty}$ is contained in a connected
component of $X-X_{k}$, which is contained in a set of the form $R-\partial R$
for some $R\in\mathcal{R}_{k}=\mathcal{R}^{k}_{1}$. Since each
$R\in\mathcal{R}^{k}_{1}$ is finite, (1) holds.

For (2), let $\delta$ be the function defined as follows. If $x\notin X_{k}$,
set $\delta(x,k,\ell)=0$ for all $\ell$. Suppose now $x\in X_{k}$ and
$\ell\leq k$. Let $B^{k}_{\ell}=\bigcup\\{\partial
R^{\prime}:R^{\prime}\in\mathcal{R}^{k}_{\ell}\\}$. So, $B^{k}_{\ell}$ is the
union of the $\ell$th level boundaries of the regions used in the construction
of $\mathcal{R}_{k}$. Let $y\in B^{k}_{\ell}$ be the point of $B^{k}_{\ell}$
closest to $x$ in the $\rho$-metric on $[x]$ (with ties broken in an arbitrary
Borel manner). Let $\tilde{\mathcal{R}}^{k}_{\ell}$ be the set of auxiliary
rectangles used in defining $\mathcal{R}^{k}_{\ell}$ from
$\mathcal{R}^{k}_{\ell+1}$. Then for some
$\tilde{R}\in\tilde{\mathcal{R}}^{k}_{\ell}$ we have $y\in\partial\tilde{R}$.
We set $\delta(x,k,\ell)=i$ if $y$ is on a face of $\tilde{R}$ which is
perpendicular to $e_{i}$ (if there is more than one such $i$, take the least
one).

We note that there is a constant $N=N(n)$ such that for the points $x$ and $y$
in the above definition, $\rho(x,y)\leq N(d_{1}+\cdots+d_{\ell-1})$. This is
because, in the construction of $\mathcal{R}^{k}_{j}$ from
$\mathcal{R}^{k}_{j+1}$, we started with auxiliary rectangles of side lengths
as large as $\epsilon_{n}d_{j}^{\prime}$, while
$d_{j}=\epsilon_{0}d_{j}^{\prime}$. Thus, any point of $B^{k}_{j}$ has
distance at most $Nd_{j}$ to $B^{k}_{j+1}$, where
$N=\frac{\epsilon_{n}}{\epsilon_{0}}$.

Suppose now $k<k^{\prime}$, $x\in X_{k}$, $x^{\prime}\in X_{k}$, and for some
$\ell<k$ we have that $\delta(x,k,\ell)=\delta(x^{\prime},k^{\prime},\ell)$.
Let $y,y^{\prime}$ be the points defined as above corresponding to $x$ and
$x^{\prime}$, respectively. Now we have
$\rho(x,y),\rho(x^{\prime},y^{\prime})\leq N(d_{1}+\cdots+d_{\ell-1})$.
Because $\delta(x,k,\ell)=\delta(x^{\prime},k^{\prime},\ell)$, $y$ and
$y^{\prime}$ are on parallel faces of rectangles $R$ and $R^{\prime}$, where
$R\in\tilde{\mathcal{R}}^{k}_{\ell}$ and
$R^{\prime}\in\tilde{\mathcal{R}}^{k^{\prime}}_{\ell}$. By construction, every
face of a rectangle in $\tilde{\mathcal{R}}^{k^{\prime}}_{\ell}$ is at least
$\epsilon d_{\ell}$ from a parallel face of any rectangle in
$\tilde{\mathcal{R}}^{k}_{\ell}$, where $\epsilon>0$ is a constant depending
only on $n$. So,

$\rho(x,x^{\prime})>\epsilon
d_{\ell}-2N(d_{1}+\cdots+d_{\ell-1})>\frac{\epsilon}{2}d_{\ell}$

provided $\frac{2N}{K-1}<\frac{\epsilon}{2}$ (recall $K$ is a constant so that
$d_{j+1}>Kd_{j}$ for all $j$). This establishes (2), with constant
$\frac{\epsilon}{2}$. ∎

We refer to sets $\\{X_{k}\\}_{k\in\mathbb{N}}$ satisfying (1) and (2) of
Theorem 3.1 as a _strong orthogonal decomposition_ , and the constant
$\epsilon>0$ in (2) as the orthogonality constant for the decomposition.

The following corollary is a consequence of Theorem 3.1 which we refer to as
_bounded geometry weak orthogonality_ (we will generalize and formalize this
definition in the next section).

######  Corollary 3.2.

Let $\\{X_{k}\\}_{k\in\mathbb{N}}$ be a strong orthogonal decomposition for
$F(2^{\mathbb{Z}^{n}})$ with orthogonality constant $\epsilon>0$. Then the
following hold.

  1. (1)

For every $k\geq 1$ and every connected component $R$ of $X-X_{k}^{\infty}$ we
have for all $\ell\geq k$ that

$\rho(R,X_{\ell})\leq\frac{\epsilon}{2}d_{1}\Longrightarrow\rho(R,X_{\ell})\leq
1.$

  2. (2)

For every $k\geq 1$ and every connected component $R$ of $X-X_{k}^{\infty}$ we
have

$|\\{\ell\geq k\colon\rho(R,X_{\ell})=1\\}|\leq n+1.$

###### Proof.

Let $R$ be a connected component of $X-X_{k}^{\infty}$. We first show (2). Let
$\ell_{1}<\ell_{2}<\cdots<\ell_{m}$ enumerate the $\ell>k$ such that
$\rho(X_{\ell},R)=1$. Suppose $m>n$. For each $1\leq j\leq m$ let $x_{j}\in
X_{\ell_{j}}$ be such that $\rho(x_{j},R)=1$. There must be $j_{1}\neq j_{2}$
such that
$\delta(x_{j_{1}},\ell_{j_{1}},k+1)=\delta(x_{j_{2}},\ell_{j_{2}},k+1)$.
However, we then have that $\rho(x_{j_{1}},x_{j_{2}})>\epsilon d_{k+1}>2d_{k}$
(we assume $K$ is large enough so that $\epsilon d_{i+1}>2d_{i}$, that is,
$K>\frac{2}{\epsilon}$). However, since $\rho(x_{j_{1}},R)=1$,
$\rho(x_{j_{2}},R)=1$, we have that $\rho(x_{j_{1}},x_{j_{2}})\leq d_{k}+2$, a
contradiction.

Next we show (1). Let $R$ be a connected component of $X-X_{k}^{\infty}$, let
$x\in R$, and let $y\in X_{\ell}$ with $\ell\geq k$ and
$\rho(x,y)\leq\frac{\epsilon}{2}d_{1}$. Consider the path $p$ from $x$ to $y$
such that $\rho(z,y)\leq\rho(x,y)$ for all $z\in p$. Let $x^{\prime}\in p$ be
the first point on the path not in $R$. Say $x^{\prime}\in X_{\ell^{\prime}}$.
If $\ell=\ell^{\prime}$, then let $x^{\prime\prime}$ be the point of $p$
immediately before $x^{\prime}$, and we have that $x^{\prime\prime}\in R$ and
$\rho(x^{\prime\prime},X_{\ell})=1$.

So, assume $\ell^{\prime}\neq\ell$. We thus have points $x^{\prime}\in
X_{\ell^{\prime}}$, $y\in X_{\ell}$ with $\rho(x^{\prime},R)=1$ and
$\rho(x^{\prime},y)\leq\frac{\epsilon}{2}d_{1}$. Recall $e_{1},\dots,e_{n}$
are the coordinate vectors in $\mathbb{Z}^{n}$. Let $x_{0}=x^{\prime}$,
$y_{0}=y$, and assume $(\alpha_{1}e_{1}+\cdots+\alpha_{n}e_{n})\cdot
x_{0}=y_{0}$ for $\alpha_{1},\dots,\alpha_{n}\in\mathbb{Z}$. We claim that
either $\rho(R,X_{\ell})=1$ (and thus the corollary is proved) or there are
$\beta_{1},\gamma_{1}\in\mathbb{Z}$ with $\alpha_{1}\beta_{1}\geq 0$,
$\beta_{1}\gamma_{1}\leq 0$, and $\alpha_{1}=\beta_{1}-\gamma_{1}$ such that,
letting $x_{1}=(\beta_{1}e_{1})\cdot x_{0}$ and $y_{1}=(\gamma_{1}e_{1})\cdot
y_{0}$, we have $x_{1}\in X_{\ell^{\prime}}$, $y_{1}\in X_{\ell}$,
$\rho(x_{1},R)=1$, and $\rho(x_{1},y_{1})\leq\frac{\epsilon}{2}d_{1}$.

If $\alpha_{1}=0$ then let $\beta_{1}=\gamma_{1}=0$ and we have $x_{1}=x_{0}$
and $y_{1}=y_{0}$. Suppose $\alpha_{1}\neq 0$. Let $\beta\geq 0$ be the
largest such that $\beta\leq|\alpha_{1}|$ and $\mbox{sgn}(\alpha_{1})\beta
e_{1}\cdot x_{0}$ is an element of $X_{\ell^{\prime}}$ and is of distance $1$
to $R$. Also let $\gamma\geq 0$ be the largest such that
$\gamma\leq|\alpha_{1}|$ and $-\mbox{sgn}(\alpha_{1})\gamma e_{1}\cdot y_{0}$
is an element of $X_{\ell}$. If $\beta+\gamma\geq|\alpha_{1}|$, then the claim
holds by letting $\beta_{1}=\mbox{sgn}(\alpha_{1})\beta$ and
$\gamma_{1}=\beta_{1}-\alpha_{1}$. Suppose $\beta+\gamma<|\alpha_{1}|$. Then
$-\mbox{sgn}(\alpha_{1})\gamma e_{1}\cdot y_{0}$ is on a face $S$ of
$X_{\ell}$ that is perpendicular to $e_{1}$. On the other hand, we have two
possible cases for the reason $\beta$ is the largest with
$\mbox{sgn}(\alpha_{1})\beta e_{1}\cdot x_{0}$ being an element of
$X_{\ell^{\prime}}$ and of distance 1 to $R$. Case 1 is
$\mbox{sgn}(\alpha_{1})\beta e_{1}\cdot x_{0}$ is on a face $T$ of
$X_{\ell^{\prime}}$ that is perpendicular to $e_{1}$. In this case, $S$ and
$T$ are parallel, and $\rho(S,T)\leq\frac{\epsilon}{2}d_{1}$, contradicting
the strong orthogonality condition of Theorem 3.1. Case 2 is
$\mbox{sgn}(\alpha_{1})\beta e_{1}\cdot x_{0}$ is of distance 1 to an element
$x^{\prime\prime}\in R$, and $x^{\prime\prime}$ is of distance $1$ to a face
$T$ of some $X_{\ell^{\prime\prime}}$ which is perpendicular to $e_{1}$. In
this case, if $\ell^{\prime\prime}=\ell$, we have
$\rho(x^{\prime\prime},X_{\ell})=1$ and the corollary is proved; otherwise
$\ell^{\prime\prime}\neq\ell$ and again $S$ and $T$ are parallel faces of
distance $\leq\frac{\epsilon}{2}d_{1}$, contradicting the strong orthogonality
condition of Theorem 3.1.

Applying the claim, we either have verified the corollary, or we will get
$x_{1}\in X_{\ell^{\prime}}$, $y_{1}\in X_{\ell}$ with $\rho(x_{1},R)=1$ and
$\rho(x_{1},y_{1})\leq\frac{\epsilon}{2}{d_{1}}$. Now
$(\alpha_{2}e_{2}+\dots+\alpha_{n}e_{n})\cdot x_{1}=y_{1}$. By similar
arguments, we obtain $x_{2},\dots,x_{n}$ and $y_{2},\dots,y_{n}$ (unless we
finish the proof of the corollary early) where $x_{n}=y_{n}\in
X_{\ell^{\prime}}\cap X_{\ell}$. Since $\rho(x_{n},R)=1$, we have
$\rho(R,X_{\ell})=1$ as promised. ∎

##  4\. Weakly Orthogonal Decompositions

In this section we present some applications of the weakly orthogonal
decompositions. One of the applications is to the computation of Borel
chromatic numbers. Our results will imply that for all $n\geq 2$, the Schreier
graph of $F(2^{\mathbb{Z}^{n}})$ has Borel chromatic number $3$. This is in
contrast with the result in [11] that their continuous chromatic numbers are
$4$. These are the first known results where the Borel characteristics and the
continuous characteristics of countabe group actions behave differently.
Another application is to the existence of the so-called Borel unlayered toast
structures on $F(2^{\mathbb{Z}^{n}})$. The significance of this notion is that
it implies hyperfiniteness for the orbit equivalence relation. In contrast
with other known results, we have shown in [11] that continuous toast
structures do not exist, and in [10] that Borel layered toast structures do
not exist.

Fix a standard Borel space $X$ and a Borel graph $\Gamma\subseteq X\times X$
on $X$. Let $\rho_{\Gamma}$ denote the shortest-path-length metric on the
connected components of $\Gamma$.

######  Definition 4.1.

A _weakly orthogonal decomposition of $X$_ is a collection $(X_{k})_{k\geq 1}$
of Borel subsets of $X$ satisfying the following two conditions. Below we
write $X_{k}^{\infty}$ for $\bigcup_{n=k}^{\infty}X_{n}$.

  1. (i)

(decomposition) Every connected component of $\Gamma\restriction(X\setminus
X_{k}^{\infty})$ is finite, and $\bigcap_{k\geq 1}X_{k}^{\infty}=\varnothing$.

  2. (ii)

(weakly orthogonal) There exists a constant $Q$ such that for every $k\geq 1$
and every connected component $R$ of $\Gamma\restriction(X\setminus
X_{k}^{\infty})$ we have for all $n\geq k$

$\rho_{\Gamma}(R,X_{n}^{\infty})\leq
Q\Longrightarrow\rho_{\Gamma}(R,X_{n}^{\infty})=1.$

We furthermore say that $(X_{k})_{k\geq 1}$ has _bounded geometry_ if in
addition to the above properties it satisfies the following.

  1. (iii)

(bounded geometry) There exists a constant $P$ such that for every $k\geq 1$
and every connected component $R$ of $\Gamma\restriction(X\setminus
X_{k}^{\infty})$ we have

$|\\{n\geq k:\rho_{\Gamma}(R,X_{n})=1\\}|\leq P.$

We call the smallest $P$ satisfying (iii) the _polygonal bound_ for
$(X_{k})_{k\geq 1}$, and we call the smallest $Q$ satisfying (ii) the
_orthogonality constant_ for $(X_{k})_{k\geq 1}$.

As we have shown in Corollary 3.2, in $F(2^{\mathbb{Z}^{n}})$ bounded geomtry
weakly orthogonal decompositions exist with polygonal bound $P=n+1$ and
orthogonality constant $Q=\frac{\epsilon}{2}d_{1}$. Here the constant
$\epsilon$ depends on $n$ but $d_{1}$ does not. In particular, we can pick
$d_{1}$ to be arbitrarily large.

We observe that the existence of a weakly orthogonal decomposition of $X$
necessitates hyperfiniteness.

######  Lemma 4.2.

Let $X$ be a standard Borel space and let $\Gamma\subseteq X\times X$ be a
Borel graph on $X$. Let $E_{\Gamma}$ be the equivalence relation on $X$ given
by the connected components of $\Gamma$. If there exists a weakly orthogonal
decomposition of $X$ then $E_{\Gamma}$ is hyperfinite.

###### Proof.

Fix a weakly orthogonal decomposition $(X_{k})_{k\geq 1}$ of $X$. For $k\geq
1$ let $E_{k}$ be the equivalence relation which is trivial (consists of
singletons) when restricted to $X_{k}^{\infty}$ and which when restricted to
$X\setminus X_{k}^{\infty}$ is given by the connected components of
$\Gamma\restriction(X\setminus X_{k}^{\infty})$. The sequence $(E_{k})_{k\geq
1}$ witnesses the hyperfiniteness of $E_{\Gamma}$. ∎

We also observe that if a Borel graph $\Gamma$ admits a weakly orthogonal
decomposition with bounded geometry, then necessarily $\Gamma$ is locally
finite. For if $x\in X$, then by bounded geometry, there are only finitely
many $n$ such that $\rho(x,X_{n})=1$. Let $m$ be large enough so that if
$\rho(x,X_{n})=1$, then $n<m$, and $x\notin X^{\infty}_{m}$. But then
$X\setminus X_{m}^{\infty}$ contains $x$ and all the neighbors of $x$, and so
the connected component of $X\setminus X_{m}^{\infty}$ which contains $x$
contains all of its neighbors. Since this component is finite, $x$ has only
finitely many neighbors in $\Gamma$.

For the remainder of this section we fix a bounded geometry weakly orthogonal
decomposition $(X_{k})_{k\geq 1}$ of $X$ with polygonal bound $P$ and
orthogonality constant $Q$. We set
$X_{k}^{\infty}=\bigcup_{n=k}^{\infty}X_{n}$.

######  Definition 4.3.

A set $R\subseteq X$ is a _$k$ -nucleus_ if $R$ is a connected component of
$\Gamma\restriction(X\setminus X_{k}^{\infty})$. We say that $R$ is an
_nucleus_ if $R$ is a $k$-nucleus for some $k\geq 1$.

######  Definition 4.4.

Let $R$ be a nucleus.

  * •

We define the _stage_ of $R$, denoted $s(R)$, to be the maximum $k$ such that
$R$ is a $k$-nucleus.

  * •

For $m\geq 1$, we define the $m$-boundary index of $R$ to be

$B_{R}(m)=\\{n\geq m:\rho_{\Gamma}(R,X_{n})=1\\}.$

  * •

We define the _amplitude_ of $R$ to be $a(R)=\max B_{R}(s(R))$.

  * •

For $d\geq 1$, the _$d$ -fundamental interior_ of $R$ is

$f_{d}(R)=\\{r\in R:\forall n\geq s(R)\ \ \rho_{\Gamma}(r,X_{n}^{\infty})\geq
P\cdot d-|B_{R}(n+1)|\cdot d\\}.$

######  Lemma 4.5.

Let $R$ and $R^{\prime}$ be nuclei.

  1. (i)

If $R\cap R^{\prime}\neq\varnothing$ and $s(R)\leq s(R^{\prime})$ then
$R\subseteq R^{\prime}$.

  2. (ii)

If $R\subseteq R^{\prime}$ and $R\neq R^{\prime}$ then $s(R)<s(R^{\prime})$.

  3. (iii)

If $R\subseteq R^{\prime}$ then $B_{R}(n)\subseteq B_{R^{\prime}}(n)$ for all
$n\geq s(R^{\prime})$.

  4. (iv)

$|B_{R}(n+1)|\leq P-1$ for all $n\geq s(R)$.

  5. (v)

If $R\subseteq R^{\prime}$ then $a(R)\leq a(R^{\prime})$.

###### Proof.

(i). By definition $R$ is connected in $\Gamma\restriction(X\setminus
X_{s(R)}^{\infty})$ and therefore connected in the larger graph
$\Gamma\restriction(X\setminus X_{s(R^{\prime})}^{\infty})$. The set
$R^{\prime}$ is a connected component of the latter graph, so as $R\cap
R^{\prime}\neq\varnothing$ we must have $R\subseteq R^{\prime}$.

(ii). For every $k\geq s(R^{\prime})$, $R$ is strictly contained in
$R^{\prime}$ which is connected in the graph $\Gamma\restriction(X\setminus
X_{k}^{\infty})$. So $R$ is not a connected component of
$\Gamma\restriction(X\setminus X_{k}^{\infty})$. Therefore
$s(R)<s(R^{\prime})$.

(iii). Fix $n\geq s(R^{\prime})$. Suppose that $m\in B_{R}(n)$. Then
$\rho_{\Gamma}(R,X_{m})=1$. Since $R^{\prime}$ is a connected component of
$\Gamma\restriction(X\setminus X_{s(R^{\prime})}^{\infty})$ and $m\geq n\geq
s(R^{\prime})$, we must have $R^{\prime}\cap X_{m}=\varnothing$. Using
$R\subseteq R^{\prime}$ we obtain
$0<\rho_{\Gamma}(R^{\prime},X_{m})\leq\rho_{\Gamma}(R,X_{m})=1$. Therefore
$m\in B_{R^{\prime}}(n)$.

(iv). This follows immediately from the bounded geometry property in
Definition 4.1 and the fact that by definition $s(R)\not\in B_{R}(n+1)$ for
$n\geq s(R)$.

(v). It is immediate from the definitions that $s(R)\leq a(R)$ and
$s(R^{\prime})\leq a(R^{\prime})$. If $a(R)\leq s(R^{\prime})$ then we are
done. Otherwise $a(R)\in B_{R}(s(R^{\prime}))\subseteq
B_{R^{\prime}}(s(R^{\prime}))$ by (iii) and hence

$a(R^{\prime})=\max B_{R^{\prime}}(s(R^{\prime}))\geq\max
B_{R}(s(R^{\prime}))=\max B_{R}(s(R))=a(R).\qed$

######  Lemma 4.6.

Let $R$ and $R^{\prime}$ be nuclei and fix $d\geq 1$. Assume that $P\cdot
d\leq Q$.

  1. (i)

$\rho_{\Gamma}(f_{d}(R),X\setminus R)\geq d$.

  2. (ii)

If $R\cap R^{\prime}=\varnothing$ then
$\rho_{\Gamma}(f_{d}(R),f_{d}(R^{\prime}))\geq 2d$.

  3. (iii)

If $R\subseteq R^{\prime}$ then $f_{d}(R)\subseteq f_{d}(R^{\prime})$.

  4. (iv)

If $f_{d}(R)\subseteq f_{d}(R^{\prime})$ and $a(R)<a(R^{\prime})$ then
$\rho_{\Gamma}(f_{d}(R),X\setminus f_{d}(R^{\prime}))\geq d$.

###### Proof.

(i). $R$ is a connected component of $\Gamma\restriction(X\setminus
X_{s(R)}^{\infty})$, so from Lemma 4.5.(iv) we obtain

$\rho_{\Gamma}(f_{d}(R),X\setminus
R)=\rho_{\Gamma}(f_{d}(R),X_{s(R)}^{\infty})\geq P\cdot d-|B_{R}(s(R)+1)|\cdot
d\geq d.$

(ii). By swapping $R$ and $R^{\prime}$ if necessary, we may assume that
$s(R)\leq s(R^{\prime})$. Since $R^{\prime}$ is a finite connected component
of $\Gamma\restriction(X\setminus X_{s(R^{\prime})}^{\infty})$ and $R\cap
X_{s(R^{\prime})}^{\infty}=\varnothing$, we have that
$\rho_{\Gamma}(R,R^{\prime})\geq 2$. So from (i) we obtain

$\rho_{\Gamma}(f_{d}(R),f_{d}(R^{\prime}))\geq\rho_{\Gamma}(f_{d}(R),X\setminus
R)+\rho_{\Gamma}(R,R^{\prime})-1+\rho_{\Gamma}(X\setminus
R^{\prime},f_{d}(R^{\prime}))-1\geq 2d.$

(iii). By Lemma 4.5.(iii) we have for all $n\geq s(R^{\prime})$

$\rho_{\Gamma}(f_{d}(R),X_{n}^{\infty})\geq P\cdot d-|B_{R}(n+1)|\cdot d\geq
P\cdot d-|B_{R^{\prime}}(n+1)|\cdot d.$

It follows from the definitions that $f_{d}(R)\subseteq f_{d}(R^{\prime})$.

(iv). Fix $y$ with $\rho_{\Gamma}(y,f_{d}(R))<d$. We will argue that $y\in
f_{d}(R^{\prime})$. By (i) we have that $y\in R\subseteq R^{\prime}$. Consider
$s(R^{\prime})\leq n<a(R^{\prime})$. By Lemma 4.5.(iii) we have
$B_{R}(n+1)\subseteq B_{R^{\prime}}(n+1)$. The assumption $a(R)<a(R^{\prime})$
further gives $a(R^{\prime})\in B_{R^{\prime}}(n+1)\setminus B_{R}(n+1)$ so
that $|B_{R}(n+1)|+1\leq|B_{R^{\prime}}(n+1)|$. Therefore for
$s(R^{\prime})\leq n<a(R^{\prime})$ we have

$\rho_{\Gamma}(y,X_{n}^{\infty})>\rho_{\Gamma}(f_{d}(R),X_{n}^{\infty})-d\geq
P\cdot d-|B_{R}(n+1)|\cdot d-d\geq P\cdot d-|B_{R^{\prime}}(n+1)|\cdot d.$

For $n\geq a(R^{\prime})$ we have $n\not\in B_{R}(s(R))$ since
$a(R)<a(R^{\prime})$. So $\rho_{\Gamma}(R,X_{n}^{\infty})>1$ and thus by the
weakly orthogonal property and (i) we have

$\displaystyle\rho_{\Gamma}(y,X_{n}^{\infty})$
$\displaystyle>\rho_{\Gamma}(f_{d}(R),X_{n}^{\infty})-d\geq\rho_{\Gamma}(f_{d}(R),X\setminus
R)+\rho_{\Gamma}(R,X_{n}^{\infty})-1-d$ $\displaystyle\geq Q+1-1=Q\geq P\cdot
d=P\cdot d-|B_{R^{\prime}}(n+1)|\cdot d.$

We conclude that $y\in f_{d}(R^{\prime})$. ∎

######  Remark 4.7.

The weakly orthogonal property has only been used thus far in proving clause
(iv) of Lemma 4.6.

For a graph $\Gamma$ on $X$ and $n\geq 1$ define

$\Gamma^{(n)}=\\{(x,y):x\neq y\text{ and }\rho_{\Gamma}(x,y)\leq n\\}.$

######  Theorem 4.8.

Let $X$ be a standard Borel space and let $\Gamma\subseteq X\times X$ be a
Borel graph on $X$. Let $(X_{k})_{k\geq 1}$ be a bounded geometry weakly
orthogonal decomposition of $X$ with polygonal bound $P$ and orthogonality
constant $Q$. If $d\geq 1$ and $(2d+1)\cdot P\leq Q$, then there is a Borel
set $Y\subseteq X$ such that both of the graphs $\Gamma^{(d)}\restriction Y$
and $\Gamma^{(d)}\restriction(X\setminus Y)$ have finite connected components.

###### Proof.

Call a nucleus $R$ maximal if $a(R)<a(R^{\prime})$ for every nucleus
$R^{\prime}$ with $R^{\prime}\supsetneq R$. For a set $A\subseteq X$ set

$\partial_{d}A=\\{a\in A:\rho_{\Gamma}(a,X\setminus A)\leq d\\}.$

Define

$Y=\bigcup\Big{\\{}\partial_{d}f_{2d+1}(R):R\text{ is a maximal
nucleus}\Big{\\}}.$

Let $R$ and $R^{\prime}$ be maximal nuclei with

$\rho_{\Gamma}(\partial_{d}f_{2d+1}(R),\partial_{d}f_{2d+1}(R^{\prime}))\leq
d.$

By Lemma 4.6.(i) we must have that $R\cap R^{\prime}\neq\varnothing$. By
swapping $R$ and $R^{\prime}$, we may suppose that $s(R)\leq s(R^{\prime})$ so
that $R\subseteq R^{\prime}$. It follows from Lemma 4.6.(iii) that
$f_{2d+1}(R)\subseteq f_{2d+1}(R^{\prime})$. We have

$\rho_{\Gamma}(f_{2d+1}(R),X\setminus f_{2d+1}(R^{\prime}))\leq
d+\rho_{\Gamma}(\partial_{d}f_{2d+1}(R),\partial_{d}f_{2d+1}(R^{\prime}))\leq
2d<2d+1,$

so from Lemma 4.6.(iv) we conclude that $a(R)=a(R^{\prime})$. By maximality it
follows that $R=R^{\prime}$. We conclude that every connected component of
$\Gamma^{(d)}\restriction Y$ is contained in $\partial_{d}f_{2d+1}(R)$ for
some maximal nucleus $R$ and hence is finite.

Now fix $x\in X\setminus Y$. By Definition 4.1.(i) there is $k\geq 1$ with
$\rho_{\Gamma}(x,X_{k}^{\infty})>P\cdot(2d+1)$. Let $R$ be the unique
$k$-nucleus containing $x$. Notice that $x\in f_{2d+1}(R)$. Any nucleus
$R^{\prime}\supseteq R$ with $a(R^{\prime})=a(R)$ must be contained in the
same connected component of $\Gamma\restriction(X\setminus X_{a(R)}^{\infty})$
as $R$. Since the connected components of $\Gamma\restriction(X\setminus
X_{a(R)}^{\infty})$ are finite, there must exist a maximal
$R^{\prime}\supseteq R$ with $a(R^{\prime})=a(R)$. By Lemma 4.6.(iii) we have
$x\in f_{2d+1}(R)\subseteq f_{2d+1}(R^{\prime})$. Since
$\partial_{d}f_{2d+1}(R^{\prime})\subseteq Y$ and $x\in
f_{2d+1}(R^{\prime})\setminus Y$, the connected component of $x$ in
$\Gamma^{(d)}\restriction(X\setminus Y)$ is contained in
$f_{2d+1}(R^{\prime})$ and is therefore finite. ∎

The following corollary is based off an argument due to Conley and Miller [7].

######  Corollary 4.9.

Let $X$ be a standard Borel space and let $\Gamma\subseteq X\times X$ be a
Borel graph on $X$ with $\chi(\Gamma)<\aleph_{0}$. Suppose that there is a
bounded geometry weakly orthogonal decomposition of $X$ with polygonal bound
$P$ and orthogonality constant $Q$ satisfying $5\cdot P\leq Q$. Then

$\chi_{B}(\Gamma)\leq 2\cdot\chi(\Gamma)-1.$

###### Proof.

By Theorem 4.8, there is a Borel set $Y\subseteq X$ such that both of the
graphs $\Gamma^{(2)}\restriction Y$ and $\Gamma^{(2)}\restriction(X\setminus
Y)$ have finite connected components. In particular, the connected components
of $\Gamma\restriction Y$ are finite and therefore we can find a Borel
chromatic coloring

$c_{Y}:Y\rightarrow\\{1,2,\ldots,\chi(\Gamma)\\}$

of $\Gamma\restriction Y$. Set $Y^{\prime}=Y\setminus
c_{Y}^{-1}(\chi(\Gamma))$ and set $c=c_{Y}\restriction Y^{\prime}$. Since we
removed a single color from $Y$, we did not remove any pair of adjacent points
in $Y$. It follows that for every connected component $C^{\prime}$ of
$\Gamma\restriction(X\setminus Y^{\prime})$, there is a connected component
$C$ of $\Gamma^{(2)}\restriction(X\setminus Y)$ such that $C^{\prime}$ is
contained in the union of $C$ and the set of neighbors of $C$. Since $C$ is
finite and $\Gamma$ is locally finite, it follows that $C^{\prime}$ is finite.
Therefore there is a Borel chromatic coloring

$d\colon X\setminus
Y^{\prime}\rightarrow\\{\chi(\Gamma),\chi(\Gamma)+1,\ldots,2\cdot\chi(\Gamma)-1\\}$

of $\Gamma\restriction(X\setminus Y^{\prime})$. The functions $c$ and $d$ use
disjoint colors, so $c\cup d$ is a Borel chromatic
$(2\cdot\chi(\Gamma)-1)$-coloring of $\Gamma$. ∎

######  Corollary 4.10.

For every $n\geq 1$, $\chi_{B}(F(2^{\mathbb{Z}^{n}})=3$.

###### Proof.

We observe that $\chi(F(2^{\mathbb{Z}^{n}}))=2$ and that Corollary 3.2 holds
with $P=n+1$ and $Q=\frac{\epsilon}{2}d_{1}$, where we can take $d_{1}$ to be
arbitrarily large. Then the conclusion holds by Corollary 4.9. ∎

We recall the definition of toast structures (c.f. [10] and [11]).

######  Definition 4.11.

Let $X$ be a standard Borel space and $\Gamma\subseteq X\times X$ be a Borel
graph on $X$. Let $\rho_{\Gamma}$ be the shortest-path-length metric on the
connected components of $\Gamma$. Let $E_{\Gamma}$ be the equivalence relation
on $X$ given by the connected components of $\Gamma$. Let $\\{T_{n}\\}$ be a
sequence of subequivalence relations of $E_{\Gamma}$, i.e., each
$T_{n}\subseteq E_{\Gamma}$ is an equivalence relation on a subset of $X$,
called the domain of $T_{n}$, denoted $\mbox{dom}(T_{n})$. We call
$\\{T_{n}\\}$ a (unlayered) toast if

  1. (1)

Each $T_{n}$-equivalence class is finite.

  2. (2)

$\bigcup_{n}\mbox{dom}(T_{n})=X$.

  3. (3)

For each $T_{n}$-equivalence class $C$, and each $T_{m}$-equivalence class
$C^{\prime}$ where $m>n$, if $C\cap C^{\prime}\neq\varnothing$ then
$C\subseteq C^{\prime}$.

  4. (4)

For each $T_{n}$-equivalence class $C$ there is $m>n$ and a
$T_{m}$-equivalence class $C^{\prime}$ such that $C\subseteq
C^{\prime}\setminus\partial C^{\prime}$, where $\partial C^{\prime}=\\{x\in
C^{\prime}\colon\rho_{\Gamma}(x,X\setminus C^{\prime})=1\\}$.

We call $\\{T_{n}\\}$ a layered toast if instead of (4) above, we have

  1. (4’)

For each $T_{n}$-equivalence class $C$ there is a $T_{n+1}$-equivalence class
$C^{\prime}$ such that $C\subseteq C^{\prime}\setminus\partial C^{\prime}$.

If $\\{T_{n}\\}$ is an unlayered or layered toast, we call $\\{T_{n}\\}$ Borel
if for each $n$, $\mbox{dom}(T_{n})\subseteq X$ is Borel and $T_{n}$ is a
Borel equivalence relation on $\mbox{dom}(T_{n})$. If $X$ is a zero-
dimensional Polish space and $\\{T_{n}\\}$ an unlayered or layered toast on
$X$, we call $\\{T_{n}\\}$ continuous if for every $n$,
$\mbox{dom}(T_{n})\subseteq X$ is clopen in $X$ and $T_{n}$ is a clopen
equivalence relation on $\mathrm{dom}(T_{n})$.

With an argument similar to Lemma 4.2, we can see that the existence of a
Borel unlayered toast implies hyperfiniteness of $E_{\Gamma}$.

######  Theorem 4.12.

Let $X$ be a standard Borel space and let $\Gamma$ be a Borel graph on $X$.
Let $d\geq 2$. Suppose that there is a bounded geometry weakly orthogonal
decomposition of $X$ with polygonal bound $P$ and orthogonality constant $Q$
satisfying $d\cdot P\leq Q$. Then there is a Borel unlayered toast on $X$.

###### Proof.

As in the proof of Theorem 4.8 we consider maximal nuclei, i.e., nuclei $R$
for which $a(R)<a(R^{\prime})$ for every nucleus $R^{\prime}$ with
$R^{\prime}\supsetneq R$. As in the proof of Theorem 4.8, every nucleus is
contained in some maximal nucleus.

For each $n$, define

$\mbox{dom}(T_{n})=\bigcup\\{f_{d}(R)\colon s(R)=n\text{ and }R\text{ is
maximal}\\}$

and $T_{n}$ by the partition of $\mbox{dom}(T_{n})$ given by
$\\{f_{d}(R)\colon s(R)=n\\}$. Definition 4.11 (1) and (2) follow immediately
from Definition 4.1 (i) (decomposition). For Definition 4.11 (3), let $m>n$.
Consider a $T_{n}$-equivalence class $C=f_{d}(R)$ and a $T_{m}$-equivalence
class $C^{\prime}=f_{d}(R^{\prime})$. Assume $C\cap
C^{\prime}\neq\varnothing$. It follows that $R\cap R^{\prime}\neq\varnothing$.
Hence by Lemma 4.5 (i), $R\subseteq R^{\prime}$. By Lemma 4.6 (iii),
$C=f_{d}(R)\subseteq f_{d}(R^{\prime})=C^{\prime}$.

Finally, for Definition 4.11 (4), let $C=f_{d}(R)$ be a $T_{n}$-equivalence
class. Let $R^{\prime}$ be any maximal nucleus with $R^{\prime}\supsetneq R$.
Then $R\subseteq R^{\prime}$ and $a(R^{\prime})>a(R)$. By Lemma 4.6 (iii) and
(iv), we have $\rho_{\Gamma}(C,X\setminus C^{\prime})\geq d\geq 2$. Hence
$C\subseteq C^{\prime}\setminus\partial C^{\prime}$. ∎

######  Corollary 4.13.

For each $n\geq 1$, there exists a Borel unlayered toast on
$F(2^{\mathbb{Z}^{n}})$.

###### Proof.

This follows from Corollary 3.2 and Theorem 4.12, again noting that the
condition $d\cdot P\leq Q$ can be satisfied in Corollary 3.2 by choosing a
large enough $d_{1}$. ∎

In contrast, in [10] we showed that there is no Borel layered toast on
$F(2^{\mathbb{Z}^{n}})$ for any $n\geq 1$, and in [11] we showed that there is
no continuous unlayered toast on $F(2^{\mathbb{Z}^{n}})$ for any $n\geq 1$.

##  5\. Topological regularity

The orthogonality results of Theorem 3.1 and Corollary 3.2 establish a certain
“geometric regularity” for the connected components $R$ of $X-X_{k}^{\infty}$.
We prove here a result which shows that we may strengthen the conclusion to
get a “topological regularity” for these components as well. In fact, we can
control (in a sense to be made precise) the possible shapes and configurations
for these components. Since we only need these arguments for dimension $2$, we
will restrict to this case. The main point is that we can produce an
orthogonal decomposition with components homeomorphic to the unit ball of
$\mathbb{R}^{2}$.

We continue to let $e_{1},e_{2}$ denote the standard generators of
$\mathbb{Z}^{2}$, or equivalently the standard unit vectors of
$\mathbb{R}^{2}$.

We first give an informal description of our construction in this section,
which will be a variation of the basic orthogonal marker construction that is
a refinement of the construction used in §2.3 to prove Theorem 2.5. As in that
proof we will use marker distances $d_{1}\ll d_{2}\ll\cdots\ll d_{n}\ll
d_{n+1}\cdots$ along with different scale values on each level $n$. The scale
values will be of the form $\delta d_{k}$, where $d_{k}$ is a marker distance
the use of which depends on the stage of the construction, and $\delta$ is a
multiplier which is a fixed parameter not depending on $k$. We will use
several such fixed parameters $0<\alpha<\epsilon_{2}<\eta<\epsilon_{1}<1$, and
they do not depend on the stage of the construction in which they are used. In
fact we will have

$\alpha<\frac{1}{10}\epsilon_{2}<\epsilon_{2}<\eta^{2}<\eta<2\eta<\epsilon_{1}<\frac{1}{2}$

to serve various purposes. Their exact values will be determined later in the
construction.

As before, we will construct orthogonal marker decompositions
$\mathcal{R}^{m}_{k}$ for all $m\geq 1$ and $1\leq k\leq m$. If
$(m_{1},k_{1})$, $(m_{2},k_{2})$ are pairs of positive integers with
$k_{1}\leq m_{1}$ and $k_{2}\leq m_{2}$, we let
$(m_{1},k_{1})\prec(m_{2},k_{2})$ if $m_{1}<m_{2}$ or $(m_{1}=m_{2}\mbox{ and
}k_{1}>k_{2})$. This ordering has order-type $\omega$ and corresponds to the
order in which we construct the $\mathcal{R}^{m}_{k}$ regions. Thus, we
construct $\mathcal{R}^{1}_{1}$, $\mathcal{R}^{2}_{2}$, $\mathcal{R}^{2}_{1}$,
$\mathcal{R}^{3}_{3}$, $\mathcal{R}^{3}_{2}$, $\mathcal{R}^{3}_{1},\cdots$. In
particular, for each $m$, we will start with a clopen rectangular
decomposition $\mathcal{R}^{m}_{m}$ and then successively fractilize each
region in $\mathcal{R}^{m}_{k+1}$ to obtain the clopen decomposition
$\mathcal{R}^{m}_{k}$. We thus eventually define the clopen decomposition
$\mathcal{R}^{m}_{1}$.

The rectangles in $\mathcal{R}^{m}_{m}$ (the “diagonal” steps of the
construction) will have side lengths roughly $\alpha d_{m}$, whereas the
rectangles used in modifying the regions in $\mathcal{R}^{m}_{k+1}$ to obtain
the regions in $\mathcal{R}^{m}_{k}$ will have side lengths between
$\eta^{2}d_{k}$ and $d_{k}$. Since $\alpha d_{k}<\frac{1}{10}\eta^{2}d_{k}$,
each rectangle $R$ in $\mathcal{R}^{k}_{k}$ will be at least $10$ times
smaller than any rectangle used to get an $\mathcal{R}^{m}_{k}$ region from an
$\mathcal{R}^{m}_{k+1}$ region. Similar to previous constructions, we will
first define an auxiliary clopen rectangular partial decomposition
$\tilde{\mathcal{Q}}^{m}_{k}$ which will cover the boundaries of the
$\mathcal{R}^{m}_{k+1}$ regions. We will then define a rectangular partial
decomposition $\tilde{\mathcal{R}}^{m}_{k}$ which refines the
$\tilde{\mathcal{Q}}^{m}_{k}$ in that every $R\in\tilde{\mathcal{R}}^{m}_{k}$
is a subset of a $Q\in\tilde{\mathcal{Q}}^{m}_{k}$. The
$\tilde{\mathcal{R}}^{m}_{k}$ regions will also cover the boundaries of the
$\mathcal{R}^{m}_{k+1}$ regions. Finally, we use a continuous (but otherwise
arbitrary) assignment of the $\tilde{\mathcal{R}}^{m}_{k}$ regions to one of
the $\mathcal{R}^{m}_{k+1}$ regions it intersects. This will define the
$\mathcal{R}^{m}_{k}$ regions.

We next describe the construction in more, formal details. Asssume inductively
that the $\mathcal{R}^{m_{1}}_{k_{1}}$ have been constructed for all
$(m_{1},k_{1})\prec(m,k)$ and that the following inductive hypotheses are
satisfied.

Inductive Hypotheses

  1. (H1)

Each $R\in\mathcal{R}^{m_{1}}_{m_{1}}$ is a rectangle with side lengths
between $\frac{1}{2}\alpha d_{m_{1}}$ and $\alpha d_{m_{1}}$.

  2. (H2)

$\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$ is defined if $k_{1}<m_{1}$, and is a
clopen rectangular partial decomposition which covers the boundaries of the
regions in $\mathcal{R}^{m_{1}}_{k_{1}+1}$. Each rectangle
$Q\in\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$ has side lengths between
$\frac{1}{2}d_{k_{1}}$ and $d_{k_{1}}$.

  3. (H3)

(orthogonality of the $\tilde{\mathcal{Q}}$) If $k_{1}<m_{1}$ and $F$ is a
side of a rectangle in $\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$, then $F$ is at
least $\epsilon_{1}d_{k_{1}}$ from any parallel side $F^{\prime}$ of a
rectangle in one of the following decompositions:

     * •

$\mathcal{R}^{k_{1}+1}_{k_{1}+1}$,

     * •

$\tilde{\mathcal{R}}^{m_{2}}_{k_{1}+1}$ for $m_{2}\in(k_{1}+1,m_{1}]$,

     * •

$\tilde{\mathcal{Q}}^{\ell}_{k_{1}}$ for $\ell\in(k_{1},m_{1})$,

     * •

$\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$ if $\rho(F,F^{\prime})>1$;

Also, $F$ is at least $\alpha\epsilon_{1}d_{k_{1}}$ from a parallel side of a
rectangle in $\mathcal{R}^{k_{1}}_{k_{1}}$.

  4. (H4)

$\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is defined if $k_{1}<m_{1}$ and
$\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is a clopen rectangular refinement of
$\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$ which still covers the boundaries of the
regions in $\mathcal{R}^{m_{1}}_{k_{1}+1}$. In particular, each
$R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is a subrectangle of a
$Q\in\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$. Each rectangle
$R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ has side lengths between
$\eta^{2}d_{k_{1}}$ and $d_{k_{1}}$.

  5. (H5)

(short directions for the $\tilde{\mathcal{R}}$) If
$R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ and $R$ intersects $2$ non-parallel
sides of regions in $\tilde{\mathcal{R}}^{m_{1}}_{k_{1}+1}$, then $R$ has side
lengths $\eta d_{k_{1}}$. In this case, we say that $R$ has type $2$.
Otherwise, $R$ intersects exactly one side $F$ of a region in
$\tilde{\mathcal{R}}^{m_{1}}_{k_{1}+1}$. Then the length of $R$ in the
direction perpendicular to $F$ is $\eta^{2}d_{k_{1}}$. In this case we say
that $R$ has type $1$, and call the direction perpendicular to $F$ the short
direction for $R$.

  6. (H6)

(coherence of $\tilde{\mathcal{Q}}$ and $\tilde{\mathcal{R}}$) If $F$ is a
side of a rectangle $R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$, then either $F$
is part of a side of a rectangle $Q\in\tilde{\mathcal{Q}}^{m_{1}}_{k_{1}}$ or
$F$ is within $\eta d_{k_{1}}$ of a parallel boundary side of a region in
$\mathcal{R}^{m_{1}}_{k_{1}+1}$. In fact, if $R$ is of type-$1$ and not
adjacent to a rectangle of type-$2$, then $F$ is within $\eta^{2}d_{k_{1}}$ of
a parallel boundary side of a region in $\mathcal{R}^{m_{1}}_{k_{1}+1}$.

  7. (H7)

(orthogonality of the $\tilde{\mathcal{R}}$) Any side $F$ of a rectangle
$R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is at least $\epsilon_{2}d_{k_{1}}$
from any parallel side $F^{\prime}$ of a rectangle
$R^{\prime}\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ if $\rho(F,F^{\prime})>1$.

  8. (H8)

(orthogonality of the $\tilde{\mathcal{R}}$) Any side $F$ of a rectangle
$R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is at least $\epsilon_{2}d_{k_{1}}$
from any parallel side of a rectangle
$R^{\prime}\in\tilde{\mathcal{R}}^{m_{2}}_{k_{1}}$ for
$m_{2}\in(k_{1},m_{1})$. Also, $F$ is at least $\alpha\epsilon_{2}d_{k_{1}}$
from any parallel side of a rectangle in $\mathcal{R}^{k_{1}}_{k_{1}}$.

######  Remark 5.1.

Although the constants $\epsilon_{1},\eta,\epsilon_{2}$ and $\alpha$ are pre-
fixed, absolute constants not depending on the stages of the construction, we
will determine their exact values through describing the construction in
detail at the inductive step. The constant $\epsilon_{1}$ will be a
preliminary orthogonality constant used in constructing the
$\tilde{\mathcal{Q}}$ (to maintain the orthogonality in the inductive
hypothesis (H3)). We will then pick constant $\eta$ with
$\eta^{2}<\eta<2\eta<\epsilon_{1}$ which is used in construction the
$\tilde{\mathcal{R}}$ rectangles as a control of the side lengths. The
$\tilde{\mathcal{R}}$ rectangles will be adjusted to satisfy orthogonality
(items (H7) and (H8) of the induction hypothesis), which determines the
orthogonality constant $\epsilon_{2}<\eta^{2}$. Throughout this construction
the diagonal decompositions $\mathcal{R}^{m}_{m}$ will be specially defined to
have a multiplier $\alpha$ for their side lengths compared to the non-diagonal
decompositions. A key observation is that the orthogonality estimates
involving the diagonal decompositions hold with the same multiplier $\alpha$
no matter what the value of $\alpha$ is. In other words, none of the constants
$\epsilon_{1},\eta$ and $\epsilon_{2}$ depend on the value of $\alpha$. We
finally pick $\alpha<\frac{1}{10}\epsilon_{2}$. In the end, the constant
$\epsilon=\alpha\epsilon_{2}$ will be the final resulting orthogonality
constant for the $\tilde{\mathcal{R}}$.

######  Remark 5.2.

If $R\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ is of type $2$, then $R$ has edge
lengths $\eta d_{k_{1}}$ from (H6). If $R$ is of type $1$ and not adjacent to
a type $2$ rectangle $R^{\prime}\in\tilde{\mathcal{R}}^{m_{1}}_{k_{1}}$ then
$R$ has short dimension $\eta^{2}d_{k_{1}}$ and has other side length between
$\frac{1}{2}d_{k_{1}}$ and $d_{k_{1}}$ from (H3) and (H6). If $R$ is of type
$1$ and is adjacent to an $R$ of type-$2$ then $R$ still has short dimension
$\eta^{2}d_{k_{1}}$ and has other side length between
$(\epsilon_{1}-\eta)d_{k_{1}}$ and $d_{k_{1}}$. This follows from (H4) and
(H5).

We now turn to the construction of the $\mathcal{R}^{m}_{k}$ regions. For
$k=m$, let $\mathcal{R}^{m}_{m}$ be a rectangular clopen decomposition of
$F(2^{\mathbb{Z}^{2}})$ with each rectangle $R\in\mathcal{R}^{m}_{m}$ having
side lengths between $\frac{1}{2}\alpha d_{m}$ and $\alpha d_{m}$. Then the
inductive hypothesis (H1) is maintained. Assume now the clopen partition
$\mathcal{R}^{m}_{k+1}$ has been defined, and we define $\mathcal{R}^{m}_{k}$.

Let $\tilde{\mathcal{P}}^{m}_{k}$ be a clopen rectangular partition of
$F(2^{\mathbb{Z}^{2}})$ satisfying the following:

  1. (1)

Each rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ has side lengths between
$\frac{1}{2}d_{k}$ and $d_{k}$.

  2. (2)

Each side of a rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ is at least
$\epsilon_{1}d_{k}$ from a parallel side of a rectangle
$R\in\mathcal{R}^{k+1}_{k+1}$.

  3. (3)

Each side of a rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ is at least
$\epsilon_{1}d_{k}$ from a parallel side of a rectangle
$R\in\tilde{\mathcal{R}}^{m_{2}}_{k+1}$ for any $m_{2}\in(k+1,m]$.

  4. (4)

Each side of a rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ is at least
$\epsilon_{1}d_{k}$ from a parallel side of a rectangle
$Q^{\prime}\in\tilde{\mathcal{Q}}^{\ell}_{k}$ for any $\ell\in(k,m)$.

  5. (5)

Each side $F$ of a rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ is at least
$\epsilon_{1}d_{k}$ from a parallel side $F^{\prime}$ of a rectangle
$Q^{\prime}\in\tilde{\mathcal{P}}^{m}_{k}$ if $\rho(F,F^{\prime})>1$.

  6. (6)

Each side $F$ of a rectangle $Q\in\tilde{\mathcal{P}}^{m}_{k}$ is at least
$\alpha\epsilon_{1}d_{k}$ from a parallel side $F^{\prime}$ of a rectangle
$Q^{\prime}\in\mathcal{R}^{k}_{k}$.

The construction of the $\tilde{\mathcal{P}}^{m}_{k}$ is by the standard
orthogonal marker region construction using the inductive hypotheses. The
orthogonality condition in (2) is guaranteed by (H1) and the fact that $\alpha
d_{k+1}>d_{k}$ since $d_{k+1}\gg d_{k}$. The condition in (3) is guaranteed by
(H7) and (H8), together with the fact that $\alpha\epsilon_{2}d_{k+1}>10d_{k}$
because $d_{k+1}\gg d_{k}$. For the condition in (4), we note that by (H2)
each rectangle in $\tilde{\mathcal{Q}}^{\ell}_{k}$ for $\ell\in(k,m)$ is
within distance $d_{k}$ to the boundaries of a rectangle in
$\tilde{\mathcal{R}}^{\ell}_{k+1}$. Again by (H7) and (H8), together with the
fact that $\alpha\epsilon_{2}d_{k+1}>10d_{k}$, we conclude that there is an
absolute upper bound (independent from $m,k$) for the number of such
$\tilde{\mathcal{Q}}^{\ell}_{k}$ rectangles $Q^{\prime}$ to consider. The
condition in (5) can be guaranteed by the standard construction. Finally, the
factor of $\alpha$ in (6) comes from the fact that the rectangles in
$\mathcal{R}^{k}_{k}$ have smaller side lengths of size roughly $\alpha
d_{k}$, as opposed to $d_{k}$. Again, this orthogonality condition can be
guranteed for any value of $\alpha$ as long as the $\mathcal{R}^{k}_{k}$
rectangles have side lengths between $\frac{1}{2}\alpha d_{k}$ and $\alpha
d_{k}$, which is given by (H1).

The consideration of (1)–(5) gives an absolute upper bound for the number of
rectangle sides to avoid. This upper bound, which does not depend on $m$ and
$k$, determines the constant $\epsilon_{1}$. Then the consideration of (6)
follows for any constant value $\alpha$ which is independent from
$\epsilon_{1}$. The exact value of $\alpha$ will be determined later in the
construction.

Now we define $\tilde{\mathcal{Q}}^{m}_{k}$ to consist of those rectangles in
$\tilde{\mathcal{P}}^{m}_{k}$ which intersect the boundary of a
$\mathcal{R}^{m}_{k+1}$ region. Then it is straightforward to check that the
inductive hypotheses (H2) and (H3) are maintained.

We now define a clopen rectangular partial decomposition
$\tilde{\mathcal{R}}^{m}_{k}$ which still covers the boundaries of
$\mathcal{R}^{m}_{k+1}$. Each rectangle $R\in\tilde{\mathcal{R}}^{m}_{k}$ is a
subrectangle of some $Q\in\tilde{\mathcal{Q}}^{m}_{k}$. The construction of
$R$ from $Q$ will be done in a continuous manner. We will then let
$\mathcal{R}^{m}_{k}$ be obtained from $\mathcal{R}^{m}_{k+1}$ by using the
auxiliary partial decomposition $\tilde{\mathcal{R}}^{m}_{k}$ in the usual
way: we assign each region $R\in\tilde{\mathcal{R}}^{m}_{k}$ to one of the
regions in $\mathcal{R}^{m}_{k+1}$ which $R$ intersects. For each region
$D\in\mathcal{R}^{m}_{k+1}$, let $U$ be the union of all the rectangles
$R\in\tilde{\mathcal{R}}^{m}_{k}$ which are assigned to $D$, and let $V$ be
the union of all the rectangles $R^{\prime}\in\tilde{\mathcal{R}}^{m}_{k}$
which intersect the boundary of $D$ but are not assigned to $D$ (they are
assigned to some neighboring regions of $D$). Let $D^{\prime}=(D\cup U)-V$.
Then $\mathcal{R}^{m}_{k}$ is the collection of all such $D^{\prime}$ for
$D\in\mathcal{R}^{m}_{k+1}$.

Observe that from this construction we will have maintained inductively that
any boundary side of a region in $\mathcal{R}^{m}_{k}$ is part of a side of
some rectangle in $\tilde{\mathcal{R}}^{m}_{k}$. We will use this observation
tacitly in our proof below.

We will be using a constant $\eta$ that satisfies
$\eta^{2}<\eta<2\eta<\epsilon_{1}$. As we proceed to describe the rectangles
in $\tilde{\mathcal{R}}^{m}_{k}$, we use Figure 7 to illustrate the
construction.

Let $Q\in\tilde{\mathcal{Q}}^{m}_{k}$. As in (H5), we say $Q$ has type $1$ if
$Q$ intersects exactly one side of a rectangle in $\mathcal{R}^{m}_{k+1}$, and
say $Q$ is of type $2$ if it intersects $2$ such sides.

First suppose that $Q$ has type $2$. Let $S_{0}\subseteq Q$ be a rectangle
centered at a corner point of an $\mathcal{R}^{m}_{k+1}$ region, and such that
$S_{0}$ has side lengths $\eta d_{k}$. This is possible by (3) above and the
fact that $2\eta<\epsilon_{1}$. The basic orthogonality arguments give that we
may translate $S_{0}$ in each direction by a small amount (say by an amount
$<\frac{1}{10}\eta^{2}d_{k}$) such that any side of the translated $S_{0}$ is
at least $\epsilon_{2}d_{k}$ from a parallel side of a rectangle in
$\tilde{\mathcal{R}}^{\ell}_{k}$ for any $\ell\in(k,m)$, and also at least
$\alpha\epsilon_{2}d_{k}$ from a parallel side of a rectangle in
$\mathcal{R}^{k}_{k}$. We may also assume the translation is small enough so
that any side of the translated $S_{0}$ is at least $\frac{\eta}{2}d_{k}$ from
a parallel side of a region in $\mathcal{R}^{m}_{k+1}$. In doing this
construction we use the inductive hypotheses (H2), (H4) and (H8). This
orthogonality argument is the first of several that will determine the value
of $\epsilon_{2}$. One may think of a current value of $\epsilon_{2}$, noting
that we may have to shrink the value later. In any case, $\epsilon_{2}$ will
depend on $\eta$ (but not on $m,k$), and we assume that
$\epsilon_{2}<\eta^{2}$. Similar to the situation of (6) above, this
construction works with any value $\alpha$.

$S_{0}$$S_{1}$$S_{2}$$\mathcal{R}^{m}_{k+1}$$\tilde{\mathcal{Q}}^{m}_{k}$$\tilde{\mathcal{R}}^{m}_{k}$
Figure 7. Construction of the $\tilde{\mathcal{R}}^{m}_{k}$

We continue to construct other subrectangles of $Q$ which will be in
$\tilde{\mathcal{R}}^{m}_{k}$. Let $S_{0}$ denote the translated rectangle
constructed above. For each of the $2$, $3$, or $4$ sides $s$ of an
$\mathcal{R}^{m}_{k+1}$ region which are incident to the corner point, we let
$S_{1}$, $S_{2}$ (and possibly $S_{3}$, $S_{4}$) be rectangles contained in
$Q\setminus S_{0}$ which contain the the portion of the boundary sides of an
$\mathcal{R}^{m}_{k+1}$ region intersecting $Q$ which lie outside of $S_{0}$,
and each of these rectangles has width $\eta^{2}d_{k}$. (In Figure 7 only
$S_{1}$ and $S_{2}$ are shown.) Note that we only need to specify two sides of
the $S_{i}$ since the other two sides are parts of the sides of $Q$ and
$S_{0}$, respectively. We then translate the $S_{i}$ rectangles by no more
than $\frac{1}{10}\eta^{2}d_{k}$ so that the two sides of $S_{i}$ which are
perpendicular to their adjacent side of $Q$ are at least $\epsilon_{2}d_{k}$
from a parallel side of a rectangle in $\tilde{\mathcal{R}}^{\ell}_{k}$ for
$\ell\in(k,m)$, and at least $\alpha\epsilon_{2}d_{k}$ from a parallel side of
a rectangle in $\mathcal{R}^{k}_{k}$. In doing this construction we use the
inductive hypotheses (H2), (H4), (H7) and (H8). Also, we may have to shrink
the value of $\epsilon_{2}$ obtained from the first step where we constructed
$S_{0}$. But the construction works with any value of $\alpha$.

Next we consider a rectangle $Q$ of type $1$. In this case, there is only one
boundary side $F$ of an $\mathcal{R}^{m}_{k+1}$ region which intersects $Q$.
We let $S_{5}\subseteq Q$ be a rectangle containing $F\cap Q$, with the two
sides parallel to $F$ having distance $\eta^{2}d_{k}$ and the other two sides
being parts of sides of $Q$. We then translate $S_{5}$ perpendicular to $F$ so
that the long sides of $S_{5}$ (the sides parallel to $F$) are:

  * •

at least $\epsilon_{2}d_{k}$ away from parallel sides of a rectangle in
$\tilde{\mathcal{R}}^{\ell}_{k}$ for $\ell\in(k,m)$,

  * •

at least $\epsilon_{2}d_{k}$ away from parallel sides of rectangles of the
form $S_{1},S_{2},S_{3}$ and $S_{4}$, and

  * •

at least $\alpha\epsilon_{2}d_{k}$ away from parallel sides of a rectangle in
$\mathcal{R}^{k}_{k}$.

As above, this uses the inductive hypotheses (H2), (H4), (H7) and (H8) and may
require shrinking the constant $\epsilon_{2}$ again, but the construction
works with any value of $\alpha$.

This finishes the construction of $\tilde{\mathcal{R}}^{m}_{k}$, and the value
of $\epsilon_{2}$ is determined from the above orthogonality arguments. At
this point, we fix the consatnt $\alpha<\frac{1}{10}\epsilon_{2}$.

We now verify the inductive hypotheses for the $\tilde{\mathcal{R}}^{m}_{k}$
rectangles. Assume $k<m$. The inductive hypotheses (H4), (H5) and (H6)) are
immediate from the construction of the rectangles in
$\tilde{\mathcal{R}}^{m}_{k}$. The inductive hypothesis (H7) is implicit from
the above construction; just note that the sides of rectangles of the form
$S_{0}$–$S_{5}$ are designed to be sufficiently far apart.

The next lemma verifes induction hypothesis (H8).

######  Lemma 5.3.

(orthogonality of the $\tilde{\mathcal{R}}$) The $\tilde{\mathcal{Q}}$,
$\tilde{\mathcal{R}}$ rectangles satisfy inductive hypothesis (H8).

###### Proof.

Let $F$ be a side of a rectangle $R\in\tilde{\mathcal{R}}^{m}_{k}$. Then by
our construction, $F$ is either part of a side of a rectangle
$Q\in\tilde{\mathcal{Q}}^{m}_{k}$ or is within $\eta d_{k}$ of a parallel side
on the boundary of a region in $\mathcal{R}^{m}_{k+1}$. In the latter case,
$F$ is within $\eta d_{k}$ of a parallel side of a rectangle in
$K\in\tilde{\mathcal{R}}^{m}_{k+1}$.

Suppose $F^{\prime}$ be a side of a rectangle
$R^{\prime}\in\tilde{\mathcal{R}}^{\ell}_{k}$ where $\ell\in(k,m)$. Since
$(\ell,k)\prec(m,k)$, by (H4), (H5) and (H6) for
$\tilde{\mathcal{R}}^{\ell}_{k}$, $F^{\prime}$ is either part of a side of a
rectangle $Q^{\prime}\in\tilde{\mathcal{Q}}^{\ell}_{k}$ or is within $\eta
d_{k}$ of a parallel side of a rectangle
$K^{\prime}\in\tilde{\mathcal{R}}^{m_{2}}_{k+1}$ (or
$K^{\prime}\in\mathcal{R}^{m_{2}}_{k+1}$ if $m_{2}=k+1$).

If $F$ is in the $K$ case, then the result follows from the above
constructions of the $S_{0}$–$S_{5}$ regions. If both $F$, $F^{\prime}$ are in
the $Q$, $Q^{\prime}$ case respectively, then the result follows from (4)
above. If $F$ is in the $Q$ case and $F^{\prime}$ is in the $K^{\prime}$ case,
then by (2) and (3) above, $F$ is $\epsilon_{1}d_{k}$ away from any parallel
side of $K^{\prime}$. Since $F^{\prime}$ is within $\eta d_{k}$ of such a
parallel side, we conclude that $F$ and $F^{\prime}$ are at least
$(\epsilon_{1}-\eta)d_{k}>\eta d_{k}>\epsilon_{2}d_{k}$ apart.

Now suppose $F^{\prime}$ is a side of a rectangle
$R^{\prime}\in\mathcal{R}^{k}_{k}$. If $F$ is in the $Q$ case the result
follows from (6). If $F$ is in the $K$ case the result follows from the above
constructions of the $S_{0}$–$S_{5}$. ∎

For convenience, we summarize the sizes of the $\tilde{\mathcal{R}}^{m}_{k}$
rectangles in the following.

######  Fact 5.4.

The rectangles in $\tilde{\mathcal{R}}^{m}_{k}$ form a clopen assignment and
the rectangles in $\tilde{\mathcal{R}}^{m}_{k}$ cover the boundaries of the
regions in $\mathcal{R}^{m}_{k+1}$. We furthermore have the following.

  1. (1)

Each rectangle in $\tilde{\mathcal{R}}^{m}_{k}$ has side lengths between
$\eta^{2}d_{k}$ and $d_{k}$, and is of type-$1$ or type-$2$ with respect to
the regions in $\mathcal{R}^{m}_{k+1}$.

  2. (2)

A type-$2$ rectangle in $\tilde{\mathcal{R}}^{m}_{k}$ has side lengths $\eta
d_{k}$.

  3. (3)

A type-$1$ rectangle in $\tilde{\mathcal{R}}^{m}_{k}$ has smaller side length
$\eta^{2}d_{k}$ in the short direction.

  4. (4)

A type-$1$ rectangle $R$ in $\tilde{\mathcal{R}}^{m}_{k}$ has smaller sides
which are part of the boundaries of a region in $\tilde{\mathcal{Q}}^{m}_{k}$
if $R$ is not adjacent to a type-$2$ rectangle in
$\tilde{\mathcal{R}}^{m}_{k}$. In particular, such an $R$ has longer side
lengths between $\frac{1}{2}d_{k}$ and $d_{k}$.

We let $\epsilon=\alpha\epsilon_{2}$, which is the smallest of the constants
appearing in the induction hypotheses. In most of the arguments we can use the
single constant $\epsilon$ in our estimates. An exception occurs in the
following Claim 5.7.

######  Theorem 5.5.

For each $\ell$, the connected components of
$F(2^{\mathbb{Z}^{2}})\setminus\bigcup_{m=\ell}^{\infty}\partial\mathcal{R}^{m}_{1}$
are homeomorphic to disks.

###### Proof.

We fix $\ell$ and show by reverse induction on $k$, starting from $k=\ell$,
that the connected components of $\mathcal{N}^{\ell}_{k}$ are homeomorphic to
disks, where
$\mathcal{N}^{\ell}_{k}=F(2^{\mathbb{Z}^{2}})\setminus\bigcup_{m=\ell}^{\infty}\partial\mathcal{R}^{m}_{k}$.
The result for $k=1$ then finishes the proof.

Consider first the case $k=\ell$. The connected components of
$\mathcal{N}^{\ell}_{\ell}$ are contained within a single
$\mathcal{R}^{\ell}_{\ell}$ rectangle $R$.

######  Claim 5.6.

For each of the two directions $e_{1}$, $e_{2}$, there is at most one value of
$m>\ell$ such that a boundary side of an $\mathcal{R}^{m}_{\ell}$ region that
is parallel to $e_{i}$ intersects $R$.

###### Proof.

Fix $e\in\\{e_{1},e_{2}\\}$, and suppose there is a boundary side $F_{1}$ of a
region in $\mathcal{R}^{m_{1}}_{\ell}$ and a parallel coundary side $F_{2}$ of
a region in $\mathcal{R}^{m_{2}}_{\ell}$ such that $F_{1}$ and $F_{2}$ both
intersect the rectangle $R\in\mathcal{R}^{\ell}_{\ell}$. Since $\ell$ is not
equal to $m_{1}$ or $m_{2}$, from (H7) and (H8) of the induction hypotheses we
have that $\rho(F_{1},F_{2})>\epsilon_{2}d_{\ell}>10\alpha d_{\ell}$. Since
$R$ has side lengths $\alpha d_{\ell}$, both $F_{1}$ and $F_{2}$ cannot
intersect $R$. ∎

Claim 5.6 says that each rectangle $R$ in $\mathcal{R}^{\ell}_{\ell}$ is
divided into connected components of $\mathcal{N}^{\ell}_{\ell}$ in one of a
small number of possible ways; these are illustrated in Figure 8. Thus the
theorem holds in the case $k=\ell$.

$\ell$$\ell$$\ell$$\ell$

$\ell$$\ell$$\ell$$\ell$$m$

$\ell$$\ell$$\ell$$\ell$$m$

$\ell$$\ell$$\ell$$m$$\ell$$m$

$\ell$$\ell$$\ell$$m_{1}$$\ell$$m_{2}$

Figure 8. Possible ways in which an $\mathcal{R}^{\ell}_{\ell}$ rectangle is
divided by higher level $\mathcal{R}^{m}_{\ell}$ regions.

We now assume the connected components of $\mathcal{N}^{\ell}_{k+1}$ are
homeomorphic to disks, and show the result for $\mathcal{N}^{\ell}_{k}$.

######  Claim 5.7.

Let $R_{0}\in R^{\ell}_{\ell}$, $R_{1}\in\mathcal{R}^{m_{1}}_{\ell}$, and
possibly $R_{2}\in\mathcal{R}^{m_{2}}_{\ell}$ be such that $\partial
R_{i}\cap\partial R_{0}\neq\emptyset$ for $i=1,2$. Let
$R_{0}(k)\in\mathcal{R}^{\ell}_{k}$, $R_{1}(k)\in\mathcal{R}^{m_{1}}_{k}$,
$R_{2}(k)\in\mathcal{R}^{m_{2}}_{k}$ be the regions corresponding to $R_{0}$,
$R_{1}$ and $R_{2}$, respectively. Then any member of $\mathcal{N}^{\ell}_{k}$
contained in $R_{0}(k)$ has boundary contained in $\partial
R_{0}(k)\cup\partial R_{1}(k)\cup\partial R_{2}(k)$.

###### Proof.

Figure 8 illustrates the possible ways in which this situation can happen. To
be specific, let us consider the case where
$R_{1}\in\mathcal{R}^{m_{1}}_{\ell}$ exists but $R_{2}$ does not and we are in
the second case of Figure 8 (the other cases are similar). From (H8) we have
that the boundary of $R_{1}$ is at least $\epsilon_{2}\alpha d_{\ell}$ from a
parallel boundary of $R_{0}$. Since $d_{k}\ll\cdots\ll d_{\ell-1}\ll
d_{\ell}$, we have $\sum_{i=k}^{\ell-1}d_{i}<\frac{1}{2}\epsilon_{2}\alpha
d_{\ell}$, and it follows that $\partial R_{1}(k)\cap R_{0}(k)\neq\emptyset$.
Similarly, if $R^{\prime}\neq R_{1}(k)$ is another regon in
$\bigcup_{m=\ell}^{\infty}\mathcal{R}^{m}_{k}$, then $\partial R^{\prime}\cap
R_{0}(k)=\emptyset$ and so $\partial R_{1}(k)$ is the only $k$-level boundary
which intersects $R_{0}(k)$. Thus, any element of $\mathcal{N}^{\ell}_{k}$
contained in $R_{0}(k)$ is formed from $\partial R_{1}(k)$, and its boundary
is contained in $\partial R_{0}(k)\cup\partial R_{1}(k)$.

∎

In view of Claim 5.7 we only need to consider at most three regions
$R_{0}\in\mathcal{R}^{\ell}_{\ell}$, $R_{1}\in\mathcal{R}^{m_{1}}_{\ell}$,
$R_{2}\in\mathcal{R}^{m_{2}}_{\ell}$ in the situation illustrated in Figure 8
and show that the members of $\mathcal{N}^{\ell}_{k}$ contained in $R_{0}(k)$
are homeomorphic to disks. In the following argument we continue to use the
notation established in Claim 5.7.

Clearly $R_{1}=R_{1}(\ell)$ divides $R_{0}=R_{0}(\ell)$ into two connected
components, each of which (a rectangle) is homeomorphic to a disk. Suppose
inductively that $R_{1}(k+1)$ divides $R_{0}(k+1)$ into two components, each
of which is homeomorphic to a disk. Assume inductively that the following
hold.

  1. (I1)

$\partial R_{1}(k+1)$ intersects $\partial R_{0}(k+1)$ in exactly two points
$x=x(k+1)$, $y=y(k+1)$.

  2. (I2)

At the points $x$, $y$, a vertical (horizontal) edge of $\partial R_{1}(k+1)$
intersects a horizontal (vertical) edge of $\partial R_{0}(k+1)$.

Note that by (H8), any boundary side of $\partial R_{1}(k+1)$ is at least
$\epsilon d_{k+1}$ from a parallel coundary side of $\partial R_{0}(k+1)$. Let
us call $L_{1}$ the boundary side of $\partial R_{1}(k+1)$ containing $x$, and
$L_{0}$ the boundary side of $\partial R_{0}(k+1)$ containing $x$ (the
argument at the point $y$ is similar). We use Figure 9 to illustrate the
situation as we proceed with the argument.

$E_{1}$$L_{1}$$L_{0}$$x$$x^{\prime}$$S_{0}$$S_{1}$ Figure 9. Proof of Theorem
5.5. The green shaded rectangle is $S_{1}$. The boundary of $R_{1}(k)$ is
shown in blue, and the boundary of $R_{0}(k)$ in green.

The segment $L_{1}$ must extend vertically above and below $L_{0}$ at least
$\epsilon d_{k+1}\gg d_{k}$, which follows from (H8). Similarly, $L_{0}$
extends horizontally past $x$ at least $\epsilon d_{k+1}\gg d_{k}$. Also,
outside of the balls of radius $\epsilon d_{k+1}$ around $x$ and $y$, every
point of $\partial R_{1}(k+1)$ between $x$ and $y$ is at least $\epsilon
d_{k+1}$ from any point of $\partial R_{0}(k+1)$. This follows from (H8) and
assumption (I1) above. It is therefore immediate that outside of these balls
we also have that $\partial R_{1}(k)$ and $\partial R_{0}(k)$ are disjoint.
Let us consider the ball $B$ of radius $\epsilon d_{k+1}$ aound $x$. Let
$S_{1}\in\tilde{\mathcal{R}}^{m}_{k}$ containing $x$. This is one of the
rectangles used in forming $R_{1}(k)$ from $R_{1}(k+1)$ (by either adding or
removing it from $R_{1}(k+1)$). Let $E_{1}$ be the vertical edge of $S_{1}$
which forms part of the boundary of $R_{1}(k)$. Note that $E_{1}$ crosses
$L_{0}$. From (H6) we have that the short sides of $S_{1}$ (those parallel to
$L_{0}$) are part of the sides of a rectangle
$Q_{1}\in\tilde{\mathcal{Q}}^{m}_{k}$. From (H3) we have that these short
sides of $S_{1}$ are at least $\epsilon_{1}d_{k}$ away from $L_{0}$. Thus,
$E_{1}$ extends vertically at least $\epsilon_{1}d_{k}$ above and below
$L_{0}$.

On the other hand, let $S_{0}\in\tilde{\mathcal{R}}^{\ell}_{k}$ be the
rectangle used in forming $R_{0}(k)$ from $R_{0}(k+1)$ such that $E_{1}$
intersects $S_{0}$ (or equivalently $S_{0}$ contains $x$). From (H5) we have
that the sides of $S_{0}$ parallel to $L_{0}$ are within
$\eta^{2}d_{k}<\epsilon_{1}d_{k}$ of $L_{0}$. Thus, the part of $\partial
R_{1}(k)$ formed by the short sides of $S_{1}$ and $E_{1}$ only intersects
$\partial R_{0}(k)$ in a single point $x^{\prime}$ on a long side of $S_{0}$.
It likewise follows from (H5) that inside the ball $B$, $x^{\prime}$ is the
only point of intersection of $\partial R_{1}(k)$ and $\partial R_{0}(k)$.
This establishes the above assumptions (I1) and (I2) for $R_{1}(k)$ and
$R_{0}(k)$.

The above argument applies verbatim to pairs $R_{0},R_{1}$ and $R_{1},R_{2}$,
giving that any element of $\mathcal{N}^{\ell}_{k}$ is homeomorphic to a disk.

Finally, the completed induction for $k=1$ finishes the proof of Theorem 5.5.
∎

From Theorem 5.5 it is clear that in a orthogonal decomposition with
topological regularity, a $k$-nucleus, namely a connected component of
$F(2^{\mathbb{Z}^{2}})\setminus\bigcup_{m\geq k}\partial\mathcal{R}^{m}_{1}$,
is exactly $A-\partial A$ for an $k$-atom. It thus follows that all $k$-atoms
are also homeomorphic to disks.

######  Corollary 5.8.

There is an orthogonal decomposition of $F(2^{\mathbb{Z}^{2}})$ in which, for
any $k$, all $k$-atoms are homeomorphic to disks.

We do not yet know how to generalize Corollary 5.8 to higher dimensions. One
possible approach is to prove a version of Lemma 2.2 in higher dimensions so
that, from a local point of view, an arbitrary assignment of the
$\tilde{R}^{m}_{k}$ regions to one of the $\mathcal{R}^{m}_{k+1}$ regions will
result in the marker regions obtained homeomorphic to disks, as in the
2-dimensional construction in this section. This boils down to a finitary
problem of whether such preliminary decompositions always exist in dimension
$3$ and above (e.g. whether one can decompose an arbitrary finite
$n$-dimensional rectangular polygon so that no point is close to $n+2$
different regions). It seems that if this preliminary decomposition is
possible, then the rest of the method used in this section can be applied to
obtain a generalization for higher dimensions. Of course, Corollary 5.8
suffices for our results in the rest of this paper.

##  6\. Borel Perfect Matchings in $F(2^{\mathbb{Z}^{n}})$

In this section we use the method of orthogonal decompositions to show that
there is a Borel perfect matching for $F(2^{\mathbb{Z}^{n}})$ for $n\geq 2$.
By a Borel perfect matching we mean a Borel complete section $B\subseteq
F(2^{\mathbb{Z}^{n}})$ and a Borel function $f\colon B\to\\{0,\dots,n-1\\}$
such that the pairs $(x,e_{f(x)}\cdot x)$ for $x\in B$ partition the space
$F(2^{\mathbb{Z}^{n}})$.

More generally we consider an free Borel action of $\mathbb{Z}^{n}$ on a
Polish space $X$ and its (undirected) Schreier graph associated with the
standard generating set $\\{e_{0},\dots,e_{n-1}\\}$ of $\mathbb{Z}^{n}$. A
Borel perfect matching is similarly defined. We show the following theorem.

######  Theorem 6.1.

For any $n\geq 2$ and any free Borel action of $\mathbb{Z}^{n}$ on a Polish
space $X$, there is a Borel perfect matching for the Schreier graph on $X$.

In order to prove Theorem 6.1 it is clearly enough to consider the case $n=2$.
The proof for a general free action of $\mathbb{Z}^{2}$ is identical to the
proof for the shift action of $\mathbb{Z}^{2}$ on $X=F(2^{\mathbb{Z}^{2}})$,
so we consider this case.

###  6.1. Charges, corner functions, and finite Stokes theorems

We first prove a combinatorial result for $\mathbb{Z}^{2}$ itself. In fact,
this result can be extended to $\mathbb{Z}^{n}$, which we give, though we only
need the case $n=2$. The result is a sort of “finite version” of Stokes
theorem. We first present the $n=2$ case.

For $x=(i,j)\in\mathbb{Z}^{2}$, let $q(x)=(-1)^{i+j}$ and call it the charge
of $x$. For $x=(i,j),y=(i^{\prime},j^{\prime})\in\mathbb{Z}^{2}$, let
$\rho(x,y)=\max\\{|i-i^{\prime}|,|j-j^{\prime}|\\}$ denote the $\ell^{\infty}$
distance between $x$ and $y$. If $F\subseteq\mathbb{Z}^{2}$, let $\partial
F=\\{x\in F\colon\rho(x,\mathbb{Z}^{2}-F)=1\\}$.

For $F\subseteq\mathbb{Z}^{2}$ we define a corner function $c\colon
F\to\mathbb{Z}$ as follows (the name derives from the fact that for a
rectangular polygon in $\mathbb{Z}^{2}$ the function $c(x)$ is $0$ except when
$x$ is a corner point of the boundary). For $x\in F$ we set

$c(x)=4-2e(x)+s(x),$

where $e(x)$ is the number of horizontal and vertical edges that connect $x$
to a point of $F$, that is, $e(x)=|\\{p\in\\{(\pm 1,0),(0,\pm 1)\\}\colon
x+p\in F\\}|$. Also $s(x)$ is the number of points $y$ of the form $x+(\pm
1,\pm 1)$ which are in $F$ and are such that the two points of
$\mathbb{Z}^{2}$ which are adjacent to both $x$ and $y$ are also in $F$.

The following is our “finite Stokes theorem” for finite
$F\subseteq\mathbb{Z}^{2}$.

######  Theorem 6.2 (Finite Stokes).

Let $F\subseteq\mathbb{Z}^{2}$ be finite. Then we have

$\sum_{x\in F}q(x)=\frac{1}{4}\sum_{x\in\partial F}q(x)c(x).$

###### Proof.

For $x\in F-\partial F$, we have that $c(x)=0$, and so

$\sum_{x\in\partial F}q(x)c(x)=\sum_{x\in F}q(x)c(x).$

So, it suffices to show that $\sum_{x\in F}(4q(x)-q(x)c(x))=0$. From the
definition of $c(x)$ we have that $\sum_{x\in F}(4q(x)-q(x)c(x))=\sum_{x\in
F}(2q(x)e(x)-q(x)s(x))$. It suffices to show that each of the sums $\sum_{x\in
F}q(x)e(x)$ and $\sum_{x\in F}q(x)s(x)$ is equal to $0$.

Let $E$ be the set of pairs of points (“edges”) $(x,y)$ with $x,y\in F$ and
$x,y$ differing by $(\pm 1,0)$ or $(0,\pm 1)$. Then $\sum_{x\in
F}q(x)e(x)=\sum_{(x,y)\in E}(q(x)+q(y))=0$ as $q(x)+q(y)=0$ for all $(x,y)\in
E$.

Let $S$ be the set of “squares” in $F$, that is, $S$ is the set of all
$4$-element subsets of $F$ of the form
$R=\\{(i,j),(i+1,j),(i,j+1),(i+1,j+1)\\}$ for some $i,j$. Then we have
$\sum_{x\in F}q(x)s(x)=\sum_{R\in S}\sum_{(a,b)\in R}(-1)^{a+b}=0$ as for each
square $R$ in $F$ we have that $\sum_{(a,b)\in R}(-1)^{a+b}=0$.

This completes the proof of Theorem 6.2. ∎

Although Theorem 6.2 is all we need for the results of this paper, we state
the natural generalization to $\mathbb{Z}^{n}$ for any $n\geq 2$. If $k\leq
n$, by a $k$-dimensional $1$-cube in $\mathbb{Z}^{n}$ we mean a set of the
form

$C=\\{x=(x_{1},\dots,x_{n})\in\mathbb{Z}^{n}\,:\,x_{i}=\pm 1\mbox{ for $i\in
I$ and }x_{i}=0\mbox{ for $i\not\in I$}\\}$

for some $I\subseteq\\{1,\dots,n\\}$ with $|I|=k$, i.e., $C$ is a set with
$2^{k}$ many elements $x=(x_{1},\dots,x_{n})\in\mathbb{Z}^{n}$ such that any
non-zero coordinate of $x$ must occur in one of the coordinates
$i_{1},\dots,i_{k}$ where $1\leq i_{1}<\cdots<i_{k}\leq n$, and any non-zero
coordinate of $x$ must be $\pm 1$. There are $2^{k}\binom{n}{k}$ many distinct
$k$-dimensional $1$-cubes in $\mathbb{Z}^{n}$.

######  Theorem 6.3.

Let $F\subseteq\mathbb{Z}^{n}$ be finite. Then

$\sum_{x\in F}q(x)=\frac{1}{2^{n}}\sum_{x\in\partial F}q(x)c(x)$

where $q(x)=\sum_{i=1}^{n}(-1)^{x_{i}}$ and
$c(x)=\sum_{i=0}^{n}(-1)^{i}2^{n-i}c_{i}(x)$ where $c_{0}(x)=1$, and for
$i>0$, $c_{i}(x)$ is the number of $i$-dimensional $1$-cubes $C$ such that
$C+x\subseteq F$.

The proof of Theorem 6.3 is an immediate generalization of that of Theorem
6.2.

Returning to $\mathbb{Z}^{2}$, we will need the following simple lemma about
the $\sum q(x)c(x)$ expression of Theorem 6.2.

$p$$p^{\prime}$ Figure 10. Adjacent paths $p,p^{\prime}$ as in Lemma 6.4

######  Lemma 6.4.

Let $p$ be a simple (i.e. non-self-intersecting) path consisting of a
concatenation of horizontal and vertical segments of points in
$\mathbb{Z}^{2}$. Assume each segment has length at least $5$. Let
$p^{\prime}$ be a path disjoint from $p$ which is contained in
$B_{\rho_{\infty}}(p,1)$ (the set of points of distance $1$ from $p$ in the
$\rho_{\infty}$ metric), and which is adjacent to $p$ as shown in Figure 10.
Fix an orientation for $p$ so that $p^{\prime}$ lies to the left of $p$. Let
$s=\sum_{x\in p}q(x)c(x)$, where the values of $c(x)$ are computed for the
region $R=\mathbb{Z}^{2}\setminus p^{\prime}$ and let $s^{\prime}=\sum_{x\in