2 Voronoi partitions and other forests

In this section, we define some $\mathsf {FIID}$ subgraphs which will always be forests since we are working on ${\mathbb T}_3$ . We have already defined the forest $\mathsf {clust}(L)$ corresponding to a labeling L.

We now define Voronoi partitions. If S is a vertex set, we want to partition all the other vertices into classes according to the closest element of S. We have to deal with the potential ambiguity if a vertex v is at an equal distance from several elements of S, moreover, we want to make the partition classes connected.

The role of the $\alpha $ is to handle the ambiguity if $|S_v|>1$ and in this way, the partition classes are indeed connected. Note that one can break the tie in many other ways, but it is not automatically true that the partition classes are connected. For example, if each vertex v chose to be equivalent with a uniform random element from $S_v$ and different vertices did it independently of each other, then the partition classes do not have to be connected.

When we use Voronoi partitions, the forest will be in the form of $\mathsf {clust}(L)$ or something closely related, the S will be an $\mathsf {FIID}$ set and the $\alpha $ will be extracted from the source. We will suppress $\alpha $ in the notation and just denote the partition by ${\mathsf {Vor}}(S)$ . We always assume that the hidden $\alpha $ is independent of any other steps of the construction. We will refer to partition classes as cells and we will use this terminology in general where we have a forest where every component is finite almost surely. We will see that our Voronoi partitions have this property. When we consider a Voronoi partition as a forest, we mean that we delete edges between vertices of different cells and forget the distinguished vertex; in this way, they are $\mathsf {FIID}$ forests.

If we want to produce an $\mathsf {FIID}$ labeling with a $\mathsf {un} [0,1]$ marginal whose clusters are finite but arbitrarily large, that is easy. We can even sample an arbitrary random forest whose components are almost surely finite, and label the vertices independently afterward.

The finiteness of the components above was crucial; when we construct the infinite clusters with uniform labels, then the labels and the clusters will be built together step-by-step and not by selecting the infinite clusters first and labeling them afterward.

We will call a random forest whose components are almost surely finite a cell-partition and the components will be called cells or $\Pi $ -cells where the forest is denoted by $\Pi $ . If $\Pi $ is an $\mathsf {FIID}$ cell-partition, then let $\mathsf {Ber}(\Pi )$ be the $\mathsf {FIID} \{0,1\}$ -labeling $\unicode{x3bb} $ of the vertex set with the properties that: its marginals are fair bits ( $\textbf P(\unicode{x3bb} (v)=1)=\textbf P(\unicode{x3bb} (v)=0)=\tfrac {1}{2}$ ), the labels are constant over a $\Pi $ -cell ( $\Pi (v_1)=\Pi (v_2)$ implies $\unicode{x3bb} (v_1)=\unicode{x3bb} (v_2)$ ), and the labels over different cells are independent. By the notation $\unicode{x3bb} \sim \mathsf {Ber}(\Pi )$ , we will mean that first $\Pi $ is sampled, and then we sample $\unicode{x3bb} $ given $\Pi $ . We will use $\mathsf {Ber}(\Pi )$ to imitate a Bernoulli percolation on a graph whose vertices are the cells of $\Pi $ . The fact that a labeling with this distribution can be realized as an $\mathsf {FIID}$ labeling is a consequence of the previous lemma: the fair bits needed for $\mathsf {Ber}(\Pi )$ can be obtained from the $\mathsf {un} [0,1] \theta $ -label guaranteed by the lemma, for example, by defining the bit to be $1$ if $\theta>\tfrac {1}{2}$ and $0$ if $\theta \leq \tfrac {1}{2}$ .

One may notice that for a Voronoi-type partition ${\mathsf {Vor}}(S)$ , we do not need to know the finiteness of the cells to label them as claimed in the lemma, since each cell already comes with a single distinguished vertex (the one from S), and the whole cell can copy labels from this distinguished vertex just as in the proof.

So, if a Voronoi partition had non-zero chance of producing infinite clusters, then that already would witness the truth of our Theorem 1.1. However, a simple application of the mass-transport principle shows that every Voronoi cell must be finite. See [Reference Lyons and PeresLP16, Ch. 8] for more on the mass-transport principle and note that the application we need here is also covered there directly as Example 8.6. For completeness, we also explain this here.

We will show that an invariant process on a Cayley graph cannot determine infinite components with a single distinguished vertex; the precise statement is Lemma 2.3 below. Note that this immediately implies that this is also true if the word ‘single’ is replaced by ‘finitely many’, as from the finitely many vertices we can select a uniform one and this still will be an invariant process if the original one was.

Let G be a Cayley graph of a countable group $\Gamma $ , we will use $\Omega :=\{0,1\}^{V(G)\cup E(G)}$ to represent various vertex and edge configurations of G. Note that $\Gamma $ acts on $\Omega $ . We interpret the edges with label zero as deleted, the edges with label $1$ as kept, and vertices with label $1$ as distinguished (and the vertices of label $0$ are not), and thus when we talk about a component, we mean that the underlying graph has all the original vertices (distinguished or not), but only the edges which are kept. Thus, we can represent the event that ‘in every component, there is at most one distinguished vertex and there is an infinite component which does contain a distinguished vertex’ as a measurable subset ${\mathcal E}\subset \Omega $ .

We have not specified a probability measure on $\Omega $ , but now we will say something about all $\Gamma $ -invariant ones.

Lemma 2.3. If $\mathcal {P}$ is any $\Gamma $ -invariant probability measure on $\Omega $ , then the event ${\mathcal E}$ cannot happen, that is

$$ \begin{align*}\mathcal{P}({\mathcal E})=0.\end{align*} $$

To prove this, we will need the mass-transport principle for countable groups, which is the following.

Proposition 2.4. Let $\Gamma $ be a countable group and o be its identity. If $f:\Gamma \times \Gamma \longrightarrow [0,1]$ is diagonally invariant (meaning that $f(\gamma x, \gamma y)=f(x,y)$ for all $\gamma ,x,y \in \Gamma )$ , then

$$ \begin{align*}\sum_{x\in \Gamma}f(o,x)=\sum_{x\in \Gamma}f(x,o).\end{align*} $$

Recall that if $\Pi $ is a forest, then for a vertex v, we denoted by $\Pi (v)$ the component of v. If two forests $P,F$ are related in a way that $P(v)\subset F(v)$ for all v, then we denote this relationship by $P\prec F$ or $F\succ P$ . To such a pair, we associate a new forest.

When we use this large scale forest construction, the P-components will be finite (so P is a cell-partition). If there is a further cell-partition $\Pi $ on $F/P$ , then there is a natural corresponding cell-partition $\texttt {glue}_{\Pi }(P)$ on F so that $P \prec \texttt {glue}_{\Pi }(P) \prec F$ . We just glue together the cells of P according to $\Pi $ , meaning that if $\mathcal {C}$ is a $\Pi $ -cell consisting of the P-cells $C_1,\ldots ,C_l$ , then $\bigcup \{C_i:C_i\in \mathcal {C}\}$ will be a $\texttt {glue}_{\Pi }(P)$ -cell and, as these cells already partition all the vertices of F, defines $\texttt {glue}_{\Pi }(P)$ .

When $F,P$ are ${\mathsf {FIID}}$ subforests of ${\mathbb T}_3$ and $P\prec F$ and P is a cell-partition, then by Lemma 2.2, we can assume that the vertices of $F/P$ are equipped with a family of i.i.d. random variables $x(v)_{v\in V(F/P)}\buildrel {d}\over \sim {\mathsf {un}} [0,1]$ which we can use to build Voronoi-type partitions on $F/P$ as an ${\mathsf {FIID}}$ -forest on the original ${\mathbb T}_3$ (corresponding to each other via our glue operation).

3 High level overview

We will use the basic theory of Bernoulli percolation on trees, see [Reference Lyons and PeresLP16] or [Reference PeteP19]. In fact, we will only need some very basic result from which we can directly obtain everything that we need so we made some effort to stay self-contained. In addition to this, we will need at the end the fact that an $\mathsf {FIID}$ is ergodic, thus, when we prove that a vertex is contained in an infinite cluster with positive probability, we can conclude that there are infinite clusters with probability one.

A Bernoulli- ${p}$ site percolation on a graph is the $\{0,1\}$ -labeling where a vertex gets label $1$ with probability p and $0$ with probability $1-p$ , independently of the others. We will denote this labeling by ${\mathsf {Ber}}({p})$ .

We will need the following proposition.

Although we will work on more general trees, the above will be sufficient, through the fact that if a tree T has minimal degree $\delta :=d_{\textrm {min}}(T)$ , then T contains ${\mathbb T}_{\delta }$ as a subgraph.

The above result has the easy consequence, which we will prove as Lemma 4.4, that for any $\epsilon>0$ , there exists a $D(\epsilon )\in {\mathbb N}$ such that if a tree T with a distinguished root $r\in V(T)$ has minimal degree at least $D(\epsilon )$ , then a ${\mathsf {Ber}}(\tfrac {1}{2})$ labeling on T will have an infinite cluster containing r with probability at least $(1-\epsilon )$ . In fact, we will need a property which is stronger than being infinite: we need forking clusters. In the process that we are going to define, the infinite clusters will automatically be forking; however, we will not prove this, since for our construction to work, it will be enough to know that forking clusters exists with positive probability, and thus some of the infinite clusters will be forking by ergodicity. We will prove forking clusters exists with positive probability through Lemma 4.5 directly from Proposition 3.2.

To highlight the ideas of the construction, we first show the modest claim that for any positive integer n, there is an $\mathsf {FIID}$ labeling $\theta _n$ on ${\mathbb T}_3$ whose marginal is uniform on the label set $\{0,1\}^n$ and $\mathsf {clust}(\theta _n)$ contains infinite clusters.

On the d-regular tree ${\mathbb T}_d$ , a ${\mathsf {Ber}}(p)$ labeling almost surely has infinite clusters spanned by vertices of label $1$ exactly when $p>1/(d-1)$ . This implies that if a tree T has minimal degree at least $\delta $ and if $p({\delta }-1)>1$ , then the clusters of a ${\mathsf {Ber}}(p)$ -labeling on T will contain infinite ones labeled with $1$ .

If $L_0,\ldots , L_{n-1}$ are independent $\mathsf {Ber}(\tfrac {1}{2})$ -labelings, and we concatenate them to get the $\{0,1\}^n$ -labeling $\mathcal {L}_n:=(L_0,\ldots ,L_{n-1})$ , then for any $s\in \{0,1\}^n$ , the distribution of vertices whose $\mathcal {L}_n$ -label is s will be the same as the distribution of vertices whose label is $1$ in a single $\mathsf {Ber}({1/ {2^n}})$ -labeling. In particular, there will be infinite clusters in $\mathsf {clust}(\mathcal {L}_n)$ on ${\mathbb T}_d$ if $d>2^n+1$ .

This is not yet the $\theta _n$ we promised, as we want to label ${\mathbb T}_3$ instead of ${\mathbb T}_d$ where d depends on n. However, we can imitate a tree whose minimal degree is at least d within ${\mathbb T}_3$ using Voronoi partitions and the large scale tree construction. As in Example 1.4, let S be an $\mathsf {FIID}$ vertex set in ${\mathbb T}_3$ for which any two $v_1,v_2\in S$ have distance at least $2r+1$ , then let $\Pi _0:=\mathsf {Vor}(S)$ . Each $\Pi _0$ -cell $\mathcal {C}$ contains the ball $B_{{\mathbb T}_3}(v,r)$ around $v\in S\cap \mathcal {C}$ . This implies that the large-scale tree ${\mathbb T}_3/\Pi _0$ has minimal degree at least $|B_{{\mathbb T}_3}(v,r)|+2$ .

For large enough r, the random tree ${\mathbb T}_3/\Pi _0$ has minimal degree at least $2^n+2$ , so using the $\mathsf {FIID}$ labeling $\mathsf {Ber}(\Pi _0)$ guaranteed by Lemma 2.2 and concatenating n independent versions $\unicode{x3bb} _i\sim \mathsf {Ber}(\Pi _0)$ to form $\theta _n$ , we get an $\mathsf {FIID} \{0,1\}^n$ -labeling which has infinite clusters and marginals uniform on $\{0,1\}^n$ .

This proves the claim, but how do we get a labeling which has uniform marginals on $[0,1]$ but still with infinite clusters?

Instead of the ‘static’ sequence $\Pi _0,\ldots ,\Pi _0,\ldots ,$ with the i.i.d. labels $\unicode{x3bb} _i\sim \mathsf {Ber}(\Pi _0)$ , we use a dynamically changing sequence of cell-partitions $\Pi _0\prec \cdots \prec \Pi _n\prec \cdots $ , and the corresponding sequence of labelings $\Lambda _0\sim \mathsf {Ber}(\Pi _0),\ldots ,\Lambda _n\sim \mathsf {Ber}(\Pi _n),\ldots $ . This way, we will be able to use infinitely many bits and thus get $\mathsf {un}[0,1]$ marginals, while also having infinite clusters. The essence of how this sequence is constructed and what issues need to be taken care of is already visible in the step from $\Pi _0$ to $\Pi _1$ .

There will be ‘target degrees’ $D_0$ and $D_1$ which, for now, are just large integers.

A target degree was also present in the previous $\theta _n$ construction in the fact that ${\mathbb T}_3/\Pi _0$ had minimal degree at least $2^n+2$ and $\Pi _0$ in the final construction is defined just as before; this time, we want ${\mathbb T}_3/\Pi _0$ to have minimal degree at least $D_0$ . To $\Pi _0$ , we associate the labeling $\Lambda _0\sim \mathsf {Ber}(\Pi _0)$ and we get the random forest $\mathcal {F}_0:=\mathsf {clust}(\Lambda _0)$ , where of course $\Pi _0\prec \mathcal {F}_0$ .

We want to build $\Pi _1$ in such a way that $\Pi _0\prec \Pi _1\prec \mathcal {F}_0$ and, ‘whenever possible’, the components of the large-scale forest $\mathcal {F}_0/\Pi _1$ should have minimal degree at least $D_1$ . So the goal in this second step is similar to that in the first step, when we wanted ${\mathbb T}_3/\Pi _0$ to have minimal degree at least $D_0$ .

A key difference is that in the first step, we worked with the deterministic tree ${\mathbb T}_3$ , while now we have to deal with the random forest $\mathcal {F}_0$ . We can immediately see that the target degree goal cannot be reached for all components of $\mathcal {F}_0/\Pi _1$ , as $\mathcal {F}_0/\Pi _1$ contains finite clusters, whose minimal degree is always $1$ , because a finite tree always has leaves. What about the infinite clusters? If there was a bi-infinite path among them, then for that component, the target degree goal cannot be achieved for $D_1>2$ .

A key concept is a furcation vertex discussed in more detail in the next section. These are the vertices whose removal splits their component into a forest containing at least three infinite components. For example, a bi-infinite path contains no furcations at all. We will see that simply because $\mathcal {F}_0$ is defined by an invariant random process, as soon as a component contains a furcation at all, it contains enough to reach our target degree goal. Invariance alone does not guarantee that the infinite clusters have furcations, as an invariant process could split ${\mathbb T}_3$ into bi-infinite paths. Our process imitates Bernoulli percolations, and we will see that the existence of furcations is guaranteed. These concerns will be taken care of in the next section.

Now we can clarify for which components of the $\mathcal {F}_0/\Pi _1$ we can achieve the target degree goal: those containing furcations, which will be called forking components. We sketch what we do within a forking component. Of course, we need to do something with the other components as well, but that is rather arbitrary.

If v is a furcation of $\mathcal {F}_0(v)$ , then by the finiteness of the $\Pi _0$ cells, $\Pi _0(v)$ will also be a furcation of $\mathcal {F}_0/\Pi _0(v)$ . Conversely, if $\Pi _0(v)$ is a furcation of $\mathcal {F}_0/\Pi _0(v)$ , then there is a vertex $v_0\in \Pi _0(v)$ which is a furcation of $\mathcal {F}_0 (v)$ . Let S be the collection of furcations of $\mathcal {F}_0/\Pi _0$ and take the associated Voronoi partition $\mathsf {Vor}(S)$ . This partition lives on the large-scale forest $\mathcal {F}_0/\Pi _0$ , but it gives a natural way to glue together the corresponding $\Pi _0$ cells into $\Pi ^{\text { there exists } \texttt {furc}}:=\texttt {glue}_{\mathsf {Vor}(S)}(\Pi _0)$ . In $\Pi ^{\text { there exists } \texttt {furc}}$ , every cell within a forking component contains some furcation, and the cells of $\Pi ^{\text { there exists } \texttt {furc}}$ remain finite by the mass-transport principle. See Figure 1. This finiteness implies that in the component $\mathcal {F}_0/\Pi ^{\text { there exists } \texttt {furc}}(v)$ , every degree will be at least $3$ (see what could go wrong if the cells were not finite in Example 4.2). Now that all the degrees are at least $3$ , we can repeat the same idea that we used in ${\mathbb T}_3$ to achieve an arbitrarily high target degree, and this is how we get the new partition $\Pi _1$ with the properties that $\Pi _0\prec \Pi _1\prec \mathcal {F}_0$ and that the forking components of the large-scale forest $\mathcal {F}_0/\Pi _1$ have minimal degree at least $D_1$ . After this, we can proceed to the labeling $\Lambda _1\sim \mathsf {Ber}(\Pi _1)$ , define $\mathcal {F}_1=\mathsf {clust}(\Lambda _0,\Lambda _1)$ , and continue in the same way. The sequence of labelings $\Lambda _0,\ldots , \Lambda _n,\ldots $ has the property that when we take their concatenation as the binary representation of a real $\Theta $ from $[0,1]$ , then $\Theta $ has $\mathsf {un} [0,1]$ marginal.

Figure 1

First, a forking tree $\mathscr {F}(v)$ , together with a cell-partition $\Pi $ . Arrows represent infinite parts of the tree, furcation vertices are denoted by solid dots. Furcation $\Pi $ -cells are shaded. Second, the partition $\Pi ^{\text { there exists } \texttt {furc}}\succ ~\Pi $ is also shown. Third, the large-scale tree $\mathscr {F}(v)/\Pi ^{\text { there exists } \texttt {furc}}$ .

To show that this labeling has infinite clusters, we need to prove that for any given vertex r, the probability that r is in an infinite cluster is positive, say at least $c>0$ . To do so, we will use Lemma 4.4 mentioned in the beginning of this section. Choose a sequence $\epsilon _0,\epsilon _1,\ldots , \epsilon _n,\ldots $ such that $\prod _{i\in {\mathbb N}}(1-\epsilon _i)>c$ , and choose the target degree sequence as $D_0:=D(\epsilon _0),D_1:=D(\epsilon _1), \ldots $ and so on. Then in the first step, we imitate a $\mathsf {Ber}(\tfrac {1}{2})$ labeling on a tree whose minimal degree is at least $D(\epsilon _0)$ , so the probability that the cell $\Pi _0(r)$ of r will end up within a forking cluster is at least $(1-\epsilon _0)$ and if that happens, we can achieve our next target degree of $D(\epsilon _1)$ for the component $\mathscr {F}_0(r)$ . Then for this component, we will imitate a ${\mathsf {Ber}}(\tfrac {1}{2})$ labeling on the tree $\mathscr {F}_0/\Pi _1(r)$ whose minimal degree is at least $D(\epsilon _1)$ so the cell $\Pi _1(r)$ of r will stay within a forking cluster with probability at least $(1-\epsilon _1)$ conditioned on the event that it stayed within an forking cluster after the first labeling. Thus, the probability that r is within a forking cluster after the first two labelings is at least $(1-\epsilon _0)(1-\epsilon _1)$ . Continuing in this way, the probability that r is within an infinite cluster in each stage will be at least c and since the cells will increase, it implies that r will be within an infinite cluster even when each label is taken into account.

Why is this construction an $\mathsf {FIID}$ ? By Lemma 2.2, if the forest $\Pi _i$ is $\mathsf {FIID}$ , then the labeling $\Lambda _i\sim \mathsf {Ber}(\Pi _i)$ is $\mathsf {FIID}$ as well. Moreover, as soon as a labeling L is $\mathsf {FIID}$ , the indicator function whether or not a vertex v is a furcation of its component in $\mathsf {clust}(L)$ is $\mathsf {FIID}$ itself (see the note on measurability related to furcations in the next section right after Definition 4.1). Because of this, when we glue together some of the ‘old’ cells of $\Pi _i$ to build new cells so that each new cell will contain furcation. This gluing process again can be realized as an $\mathsf {FIID}$ . The way we described the process, we need fresh randomness at every stage, but as we already explained at the end of §1, the bits of a single real number can be reorganized to obtain an infinite collection of infinitely many independent bits. So, in fact, the measurable map corresponding to the intuitive description we give can be constructed by using the i.i.d. labels provided originally.

4 Furcations

Furcation vertices will let us reach our target degree goal through Lemma 4.3, and we will find trees containing them in Bernoulli clusters through Lemma 4.5.

This terminology follows [Reference Lyons and PeresLP16] and is similar but not identical to the encounter points of the landmark Burton–Keane argument which are known as trifurcations since.

Note that in a bounded degree tree, a vertex v is a furcation if and only if for any $n\in {\mathbb N}$ there exist three paths, $\mathcal {P}_1, \mathcal {P}_2$ , and $\mathcal {P}_3$ , of length at least n which are all emanating from v and are edge and (except for v) vertex disjoint. Thus, the indicator of a vertex being a furcation is measurable, being the infimum of countably many measurable functions.

An infinite example for a tree without furcation is the bi-infinite path. The next example shows trees whose furcations are arranged in an adversarial fashion and if S is the set of their furcations, then the cells of ${\mathsf {Vor}}(S)$ are not finite. These examples are also worth keeping in mind, as they would be obstacles to our target degree goals. However, they simply cannot occur in an invariant process on a Cayley graph (as we have seen in the application of the mass-transport principle).

The following lemma can be proven by induction on r.

Recall Theorem 3.2 which said that a $\mathsf {Ber}(\tfrac {1}{2})$ labeling of ${\mathbb T}_4$ has infinite clusters. This implies that for a specific vertex v of ${\mathbb T}_4$ , the probability that v will be in an infinite cluster in a $\mathsf {Ber}(\tfrac {1}{2})$ -labeling is positive. We, however, need forking clusters. We can get their existence from Theorem 3.2 as follows.

To see this, consider first the rooted tree $(T,r)$ built from rooted copies $(T_1,r_1),\ldots , (T_D,r_D)$ of ${\mathbb T}_4$ (so $T_i$ is a $4$ -regular tree and $r_i$ is one of its vertices and D will be fixed later) by adding a new vertex r to this collection and make it into a tree by connecting r to $r_i$ for all i (no other edges are added). For r to be in a forking cluster in a $\mathsf {Ber}(\tfrac {1}{2})$ -labeling of T, it is enough if there are at least three such $(T_i,r_i)$ so that $r_i$ in an infinite cluster of the labeling restricted to $T_i$ and r is connected to $r_i$ . The probability of this clearly goes to $1$ as $D\rightarrow \infty $ . If $D:=D(\epsilon )$ is chosen so that this probability is at least $1-\epsilon $ , then in a tree whose minimal degree is at least D, we can take any vertex to be the root and embed this $(T,r)$ graph into it.

Choose a sequence $\epsilon _0,\epsilon _1, \ldots , \epsilon _n,\ldots \subset (0,1) $ tending to $0$ fast enough so that $\prod _{n=1}^{\infty } (1-\epsilon _n)>0$ . Define $D_n:=D(\epsilon _n)$ and use this sequence as the target degree in our construction. We got immediately from Lemma 4.4 the following lemma.

We add a more process-oriented corollary to this, which involves random rooted trees $(\mathcal {T}_n, r_n)$ which contains the previous $(T_n, r_n)$ trees as subgraphs by the constraint on their minimal degree. At this point, the distribution of these random trees can be arbitrary as soon as they satisfy the degree constraints. Assume that we start with a random rooted tree $(\mathcal {T}_0,r_0)$ which has minimal degree at least $D_0$ , and we run the following process. Label the vertices of $\mathcal {T}_0$ by a $\mathsf {Ber}(\tfrac {1}{2})$ -labeling $\mathcal {L}_0$ , and if the cluster of $r_0$ in $\mathsf {clust}(\mathcal {L}_0)$ is not forking, then stop; otherwise, generate a new random rooted tree $(\mathcal {T}_1,r_1)$ whose minimal degree is at least $D_1$ , take a $\mathsf {Ber}(1/2)$ -labeling $\mathcal {L}_1$ of its vertices, and so on. Then, with positive probability, the above process never stops and the generated sequence of bits $\mathcal {L}_0(r_0),\ldots ,\mathcal {L}_n(r_n),\ldots $ will be i.i.d., so the random real number whose bits are this sequence has distribution $\mathsf {un}[0,1]$ .

In our construction, Bernoulli processes on large-scale forests (from Definition 2.5) will be used, and with the aid of Lemma 4.5, we will find forking ones among its clusters. We will put those clusters into use through the following lemma.

An important property of the cell partition $\texttt {furc}_D(\Pi )$ follows from Lemma 4.3 and from the finiteness of the $\texttt {furc}_D(\Pi )$ -cells: the minimal degree of any forking component of $\mathscr {F}/\texttt {furc}_D(\Pi )$ is at least $D+2$ . So Lemma 4.7 is a natural tool to achieve the previously described target degree goals.

5 The main construction

This section is largely devoted to the proof of our main theorem.

First we define the $\mathsf {FIID}$ labeling $\Theta $ witnessing the truth of our theorem. We define the sequence of cell-partitions $\Pi _0\prec \Pi _1\prec \cdots \prec \Pi _n\prec \cdots $ ; this will give us also the sequence of $\Lambda _i\sim \mathsf {Ber}(\Pi _i)$ labels, where, conditioned on $\Pi _i$ , the label $\Lambda _i$ will be independent from the previous labels. Of course, $\Pi _i$ itself depends on $\{(\Pi _j,\Lambda _j)\}_{j<i}$ .

Here, $\Pi _0$ and $\Lambda _0$ are as defined before in §3. Assume that $\Pi _0\prec \cdots \prec \Pi _n$ and $\Lambda _0,\ldots ,\Lambda _n$ are defined. Let $\mathcal {F}_n:=\mathsf {clust}(\Lambda _0,\ldots ,\Lambda _n)$ , where $(\Lambda _0,\ldots ,\Lambda _n)$ is the $\{0,1\}^{n+1}$ -label obtained by concatenating the $\Lambda _i$ terms.

We want to define $\Pi _{n+1}$ in such a way that $\Pi _n\prec \Pi _{n+1} \prec \mathcal {F}_n$ , and if for a vertex v the tree $\mathcal {F}_n(v)$ is forking, then the $\Pi _{n+1}(v)$ -cell should contain at least $D_{n+1}$ furcations of $\mathcal {F}_n$ . We use Lemma 4.7 for the pair $\Pi _n\prec \mathcal {F}_n$ and define $\Pi _{n+1}:=\texttt {furc}_{D_{n+1}}(\Pi _n)$ . As we mentioned at end of the previous section, we know by Lemma 4.3 that the minimal degree of a forking component of $\mathscr {F}_{n+1}/\Pi _{n+1}$ is at least $D_{n+1}+2$ .

This concludes the construction of $\Pi _0\prec \cdots \prec \Pi _n\prec \cdots $ and thus also that of $\Lambda _i\sim \mathsf {Ber}(\Pi _i)$ , with the specification that, conditioned on $\Pi _i$ , the $\Lambda _i$ must be independent of the previous steps. This implies that for a any vertex o fixed in advance, the sequence $\Lambda _0(o),\Lambda _1(o),\ldots $ of fair bits is i.i.d., and thus if we define $\Theta (o)$ to be the real number from $[0,1]$ whose consecutive bits are $\Lambda _0,\ldots ,\Lambda _n,\ldots $ , then $\Theta (o)$ has distribution $\mathsf {un}[0,1]$ . Thus, $\Theta $ has $\mathsf {un}[0,1]$ marginals.

Now we turn to the proof of our main theorem.

We mentioned in §1 that [Reference Chifan and IoanaChI10, Theorem 1.1] implies that the clusters in $\Theta $ and $\Theta ^{\infty }$ must be hyperfinite. Here we show their hyperfiniteness directly.

To see this for the $\Theta $ -clusters, notice that not only $\Pi _{\infty }(o)\subset \mathsf {clust}(\Theta )$ for any o, which already means $\Pi _{\infty }\prec {\mathsf {clust}}(\Theta )$ , but actually $\Pi _{\infty }={\mathsf {clust}}(\Theta )$ and $\Pi _{\infty }(o)$ is an increasing union of the finite $\Pi _n(o)$ s. To see this, consider an edge e connecting a vertex $v_{\texttt {in}}\in \Pi _{\infty }(o)$ with $v_{\texttt {out}}\not \in \Pi _{\infty }(o)$ . Notice that for any i, the labels $\Lambda _i(v_{\texttt {in}})$ and $\Lambda _i(v_{\texttt {out}})$ are independent, so they cannot be all equal. So e is deleted from $\mathsf {clust}(\Theta )$ .

To see the hyperfiniteness of the $\Theta ^{\infty }$ -clusters, we reorganize the way we build them using some new sequence of cell-partitions $\Pi _n^{\bullet }$ . For a finite $\Theta $ -cluster K, it is well defined which is the infinite $\Theta $ -cluster $\texttt {goal}(K)$ to which it finally will be attached, by $\Theta ^{\infty }(K)=\Theta ^{\infty }(\texttt {goal}(K))=\Theta (\texttt {goal}(K))$ ; by being inside a tree, it is also well defined what is the vertex $\texttt {m}(K)$ of $\texttt {goal}(K)$ which is closest to K. Moreover, K will be attached to an infinite cluster at a certain stage indexed by the smallest $i=:I(K)$ for which $\Theta ^i(K)=\Theta ^{\infty }(K)$ .

We will reorganize the original $\Pi _n$ partitions into a new one using these two parameters $I(K)$ and $\texttt {m}(K)$ . Extend these parameters to vertices in a natural way: for a vertex v within a finite $\Theta $ -cluster K, let $I(v):=I(K), \texttt {m}(v):=\texttt {m}(K)$ , while if v is within an infinite $\Theta $ -cluster, then let $I(v):=0, \texttt {m}(v):=v$ . The I index has the following property: if P is a one-sided infinite path which stays completely within an infinite $\Theta ^{\infty }$ -cluster and starts at a vertex v whose $\Theta $ -cluster is already infinite, then I can only increase along P as we start from its starting point and move away from it. Moreover, if $u_1,u_2$ are vertices of P with $I(u_1)=I(u_2)$ , then $u_1$ and $u_2$ are in the same $\Theta $ -cluster.

The cells of the new partition $\Pi _n^{\bullet }$ are built as follows: the vertices of an infinite $\Theta $ -cluster $\mathcal {K}$ are partitioned into $\Pi _n$ -cells. For a given $\Pi _n$ -cell C within $\mathcal {K}$ , we collect together those finite $\Theta $ -clusters K whose $\texttt {m}(K)$ is in C and whose index $I(K)$ is at most n to form a single $\Pi _n^{\bullet }$ -cell. The finite $\Theta $ -clusters K for which $I(K)>n$ will be individual $\Pi ^{\bullet }_n$ -cells.

To define $\Pi _n^{\bullet }$ formally, introduce an auxiliary partitioning $\Pi ^{\circ }_n$ so that for a vertex $\Pi ^{\circ }_n(o):=\Pi _n(o)$ if $\Pi _{\infty }(o)$ is infinite and $\Pi ^{\circ }_n(o):=\Pi _{\infty }(o)$ if $\Pi _{\infty }(o)$ is finite. Finally, let us define

$$ \begin{align*} \Pi^{\bullet}_n(v):=\begin{cases} \Pi_n^{\circ}(v) & \mbox{if } I(v)>n,\\ \bigcup \{{\Pi_n^{\circ}(x)}| I(x)\leq n, \Pi^{\circ}_n(\texttt{m}(x))=\Pi^{\circ}_n(\texttt{m}(v))\} & \mbox{if } I(v)\leq n. \end{cases} \end{align*} $$

Then every $\Pi _m^{\bullet }(v)$ -class is finite because if it was infinite, then by Kőnig’s lemma, we could find an infinite path P within $\Pi _m^{\bullet }(v)$ for which $\texttt {m}(u)=:u_0$ would be the same for every vertex u of P and this $u_0$ would be the starting point of P. By definition of the $\texttt {m}(u)$ parameter, as we walk away from $u_0$ , we get out from the infinite $\Theta $ -cluster of $u_0$ immediately, so $I(u)>0$ for any vertex $u\not = u_0$ of P. However, by the definition of $\Pi _m^{\bullet }(v)$ , the index $I(u)$ is at most m within it, so from one vertex w on, I is constant on P. However, that would mean that the full infinite part of P after w is contained in a single $\Theta $ -cluster, so that cluster would be infinite in the first place.

However, the increasing union of $\bigcup _{m\in {\mathbb N}}\Pi _m^{\bullet }(v)$ is exactly the $\Theta ^{\infty }$ -cluster of v. To see this, note that if u is in the $\Theta ^{\infty }$ -cluster of v, then there will be some n such that $\Pi _n(\texttt {m }(u))=\Pi _n(\texttt {m}(v))$ , so if $j\geq \texttt {max}\{n,I(u),I(v)\}$ , then $u\in \Pi ^{\bullet }_j(v)$ .

6 The case of finitary $\mathsf {FIID}$ s

An $\mathsf {FIID}$ process is finitary if it can be defined with a code $f: [0,1]^V\rightarrow [0,1]^V$ which determines the label of any vertex based on the source in a finite neighborhood of that vertex. That is, for almost all $\omega \in [0,1]^V$ and each vertex v, there exists a random radius $r=r(\omega , v)\in {\mathbb N}$ , such that if $\omega _1$ has the same restriction to $B_r(v)$ as $\omega $ , then the label of v is the same using either sources of randomness, that is, $f(\omega )(v)=f(\omega _1)(v)$ . We will call the smallest such $r(\omega , v)$ the level of v, and denote it by $\texttt {lev}_f(v)$ . If f has this property, then we will call it finitary as well. To show that a given $\mathsf {FIID}$ is not finitary, it is not enough to point out that a particular code used in its definition is not finitary as different codes could determine the same process.

We will show that an $\mathsf {FIID}$ process which witnesses the truth of Theorem 1.1 cannot be finitary. It was raised as an open question if there exists an $\mathsf {FIID}$ process on a non-amenable group which is not finitary during the discussion of a talk by Ray and Spinka (to access the talk, see [Reference Ray and SpinkaRS22], the talk is based on the paper [Reference Angel, Ray and SpinkaARS21]), and our construction thus gives an affirmative answer to this question. The label set in our process is the interval $[0,1]$ , and to our knowledge, the question if there exists a non-finitary $\mathsf {FIID}$ with a finite label set on a non-amenable group is still open.

Let L be a finitary $\mathsf {FIID}$ labeling with $\mathsf {un}[0,1]$ marginals. We will show that every cluster of L is finite almost surely.

Let us fix a finitary code f for L and assume that L is obtained using this f. If C is a cluster of L, then we will call the set of its vertices whose level is minimal the base of C. Let $\mathsf {clust}_1(L)$ be the collection of those infinite clusters whose base is finite, and $\mathsf {clust}_{\infty }(L)$ be the collection of those infinite clusters whose base is infinite. We will show that both $\mathsf {clust}_1(L)$ and $\mathsf {clust}_{\infty }(L)$ must be empty almost surely.

If $\mathsf {clust}_1(L)$ was not empty, then we would get a contradiction with Lemma 2.3, since the clusters of $\mathsf {clust}_1(L)$ are infinite with finitely many distinguished vertices, from which a single distinguished vertex can be picked uniformly.

To show that $\mathsf {clust}_{\infty }(L)$ is empty almost surely, let us partition it further, and for $m\in {\mathbb N}$ , let $\mathsf {clust}_{\infty }^m(L)$ be the collection of those clusters within $\mathsf {clust}_{\infty }(L)$ whose base consists of vertices of level exactly m. Since this is a countable partition, it is enough to show that $\mathsf {clust}_{\infty }^m(L)$ is empty almost surely for any fixed m. If $\mathsf {clust}_{\infty }^m(L)$ was not empty, then infinitely many vertices had level m and the same label (the base of any cluster in $\mathsf {clust}_{\infty }^m(L)$ would be such a collection of vertices). In particular, there existed a pair of vertices whose distance is at least $2m+1$ , their level is m, and they had the same label. Since the possible pairs of vertices form a countable set, it is enough to show that this has zero probability for any fixed pair. Pick two vertices $v_1$ and $v_2$ whose distance is at least $2m+1$ , conditioned on $\texttt {lev}_f(v_1)=\texttt {lev}_f(v_2)=m$ , their labels are independent, since $B_m(v_1)$ and $B_m(v_2)$ are disjoint. If the event $\texttt {lev}_f(v)=m$ has positive probability, then conditioned on it, the distribution of the label of v still must be atomless, otherwise the unconditional distribution could not be $\mathsf {un}[0,1]$ . However, independent samples from an atomless distribution are different almost surely.

Being finitary is a locality condition, and for other natural notions of locality, we refer the reader to [Reference Meyerovitch and SpinkaMS22] (in their more refined framework, what we called finitary above is called stop-finitary). Note also that the classic example of isomporhism between Bernoulli shifts by Meshalkin ([Reference MeshalkinM59]) is also a finitary one and that in [Reference Keane and SmorodinskyKS79], Keane and Smorodinsky proved the existence of finitary isomorphisms between Bernoulli shifts of the same entropy over ${\mathbb Z}$ , and thus strengthening Ornstein’s landmark theorem (for a survey of finitary codings in this direction, see [Reference Serafin, Denteneer, den Hollander and VerbitskiyS06]).