$H_{\ast}=(T_{1}^{l},T_{2}^{l},\ldots,T_{{\ell_{\operatorname{pump}}}}^{l},T_{\ast}^{m},T_{1}^{r},T_{2}^{r},\ldots,T_{{\ell_{\operatorname{pump}}}}^{r})\in
Y_{f}(W),$

add
$(T_{1}^{l},T_{2}^{l},\ldots,T_{{\ell_{\operatorname{pump}}}}^{l},T_{\ast}^{m})$
to $Z_{f}(W)$, where we set the root of $T_{1}^{l}$ as the root, and add
$(T_{\ast}^{m},T_{1}^{r},T_{2}^{r},\ldots,T_{{\ell_{\operatorname{pump}}}}^{r})$
to $Z_{f}(W)$, where we set the root of
${T_{{\ell_{\operatorname{pump}}}}^{r}}$ as the root.

We write $\textsf{Class}_{1}(S)=\bigcup_{T\in S}\\{\textsf{Class}_{1}(T)\\}$
and $\textsf{Class}_{2}(S)=\bigcup_{H\in S}\\{\textsf{Class}_{2}(H)\\}$, and
we make the following observation.

######  Lemma 4.10 (Property of $X_{f}(W)$, $Y_{f}(W)$, and $Z_{f}(W)$).

The three sets of equivalence classes $\textsf{Class}_{1}(X_{f}(W))$,
$\textsf{Class}_{2}(Y_{f}(W))$, and $\textsf{Class}_{1}(Z_{f}(W))$ depend only
on $\textsf{Class}_{1}(W)$ and the labeling function $f$.

###### Proof.

This is a simple consequence of Lemmas 4.7 and 4.9. ∎

##### A Fixed Point $W^{\ast}$

Given a fixed labeling function $f$, we want to find a set of rooted trees
$W^{\ast}$ that is a _fixed point_ for the procedure $Z_{f}$ in the sense that

$\textsf{Class}_{1}(Z_{f}(W^{\ast}))=\textsf{Class}_{1}(W^{\ast}).$

To find such a set $W^{\ast}$, we construct a two-dimensional array of rooted
trees $\\{W_{i,j}\\}$, as follows.

  * •

For the base case, $W_{1,1}$ consists of only the one-vertex rooted tree.

  * •

Given that $W_{i,j}$ as been constructed, we define
$W_{i,j+1}=Z_{f}(W_{i,j})$.

  * •

Given that $W_{i,j}$ for all positive integers $j$ have been constructed,
$W_{i+1,1}$ is defined as follows. Pick $b_{i}$ as the smallest index such
that $\textsf{Class}_{1}(W_{i,b_{i}})=\textsf{Class}_{1}(W_{i,a_{i}})$ for
some $1\leq a_{i}<b_{i}$. By the pigeon hole principle, the index $b_{i}$
exists, and it is upper bounded by $2^{C}$, where $C$ is the number of
equivalence classes for rooted trees. We set

$W_{i+1,1}=W_{i,a_{i}}\cup W_{i,a_{i}+1}\cup\cdots\cup W_{i,b_{i}-1}.$

We show that the sequence
$\textsf{Class}_{1}(W_{i,a_{i}}),\textsf{Class}_{1}(W_{i,a_{i}+1}),\textsf{Class}_{1}(W_{i,a_{i}+2}),\ldots$
is periodic with a period $c_{i}=b_{i}-a_{i}$.

######  Lemma 4.11.

For any $i\geq 1$ and for any $j\geq a_{i}$, we have
$\textsf{Class}_{1}(W_{i,j})=\textsf{Class}_{1}(W_{i,j+c_{i}})$, where
$c_{i}=b_{i}-a_{i}$.

###### Proof.

By Lemma 4.10, $\textsf{Class}_{1}(W_{i,j})$ depends only on
$\textsf{Class}_{1}(W_{i,j-1})$. Hence the lemma follows from the fact that
$\textsf{Class}_{1}(W_{i,b_{i}})=\textsf{Class}_{1}(W_{i,a_{i}})$. ∎

Next, we show that
$\textsf{Class}_{1}(W_{2,1})\subseteq\textsf{Class}_{1}(W_{3,1})\subseteq\textsf{Class}_{1}(W_{4,1})\subseteq\cdots$.

######  Lemma 4.12.

For any $i\geq 2$, we have
$\textsf{Class}_{1}(W_{i,1})\subseteq\textsf{Class}_{1}(W_{i,j})$ for each
$j>1$, and so
$\textsf{Class}_{1}(W_{i,1})\subseteq\textsf{Class}_{1}(W_{i+1,1})$.

###### Proof.

Since $W_{i,1}=\bigcup_{a_{i-1}\leq l\leq b_{i-1}-1}W_{i-1,l}$, we have

$\bigcup_{a_{i-1}+j-1\leq l\leq b_{i-1}+j}W_{i-1,l}\subseteq W_{i,j}$

according to the procedure of constructing $W_{i,j}$. By Lemma 4.11,

$\textsf{Class}_{1}\left(\bigcup_{a_{i-1}\leq l\leq
b_{i-1}-1}W_{i-1,l}\right)=\textsf{Class}_{1}\left(\bigcup_{a_{i-1}+j-1\leq
l\leq b_{i-1}+j}W_{i-1,l}\right)$

for all $j\geq 1$, and so we have
$\textsf{Class}_{1}(W_{i,1})\subseteq\textsf{Class}_{1}(W_{i,j})$ for each
$j>1$. The claim
$\textsf{Class}_{1}(W_{i,1})\subseteq\textsf{Class}_{1}(W_{i+1,1})$ follows
from the fact that $W_{i+1,1}=\bigcup_{a_{i}\leq l\leq b_{i}-1}W_{i,l}$. ∎

Set $i^{\ast}$ to be the smallest index $i\geq 2$ such that
$\textsf{Class}_{1}(W_{i,1})=\textsf{Class}_{1}(W_{i+1,1})$. By the pigeon
hole principle and Lemma 4.12, the index $i^{\ast}$ exists, and it is upper
bounded by $C$, the number of equivalence classes for rooted trees. We set

$W^{\ast}=W_{i^{\ast},1}.$

The following lemma shows that
$\textsf{Class}_{1}(Z_{f}(W^{\ast}))=\textsf{Class}_{1}(W^{\ast})$, as needed.

######  Lemma 4.13.

For any $i\geq 2$, if
$\textsf{Class}_{1}(W_{i,1})=\textsf{Class}_{1}(W_{i+1,1})$, then
$\textsf{Class}_{1}(W_{i,j})$ is the same for all $j\geq 1$.

###### Proof.

By Lemma 4.11 and the way we construct $W_{i+1,1}$, we have

$\textsf{Class}_{1}(W_{i,j})\subseteq\textsf{Class}_{1}(W_{i+1,1})\ \
\text{for each}\ \ j\geq a_{i}.$

By Lemma 4.12, we have

$\textsf{Class}_{1}(W_{i,1})\subseteq\textsf{Class}_{1}(W_{i,j})\ \ \text{for
each}\ \ j>1.$

Therefore, $\textsf{Class}_{1}(W_{i,1})=\textsf{Class}_{1}(W_{i+1,1})$ implies
that $\textsf{Class}_{1}(W_{i,j})=\textsf{Class}_{1}(W_{i,1})$ for each $j\geq
a_{i}$. Hence we must have
$\textsf{Class}_{1}(Z_{f}(W_{i,1}))=\textsf{Class}_{1}(W_{i,1})$, and so
$\textsf{Class}_{1}(W_{i,j})$ is the same for all $j\geq 1$. ∎

We remark that simply selecting $W^{\ast}$ to be any set such that
$\textsf{Class}_{1}(Z_{f}(W^{\ast}))=\textsf{Class}_{1}(W^{\ast})$ is not
enough for our purpose. As we will later see, it is crucial that the set
$W^{\ast}$ is constructed by iteratively applying the function $Z_{f}$ and
taking the union of previously constructed sets.

##### A Sequence of Sets of Trees

We define $W_{1}^{\ast}=W^{\ast}$ and $W_{i}^{\ast}=Z_{f}(W_{i-1}^{\ast})$ for
each $1<i\leq L$, where $L$ is some sufficiently large number to be
determined.

The way we choose $W^{\ast}$ guarantees that
$\textsf{Class}_{1}(W_{i}^{\ast})=\textsf{Class}_{1}(W^{\ast})$ for all $1\leq
i\leq L$. For convenience, we write $X_{i}^{\ast}=X_{f}(W_{i}^{\ast})$ and
$Y_{i}^{\ast}=Y_{f}(W_{i}^{\ast})$. Similarly,
$\textsf{Class}_{1}(X_{i}^{\ast})$ is the same for all $1\leq i\leq L$ and
$\textsf{Class}_{2}(Y_{i}^{\ast})$ is the same for all $1\leq i\leq L$.

Our analysis will rely on the assumption that all rooted trees in $W^{\ast}$
admit correct labelings. Whether this is true depends only on
$\textsf{Class}_{1}(W^{\ast})$, which depends only on the labeling function
$f$. We say that $f$ is _feasible_ if it leads to a set $W^{\ast}$ where all
the rooted trees therein admit correct labelings. The proof that a feasible
labeling function $f$ exists is deferred.

The assumption that $f$ is feasible implies that all trees in $W_{i}^{\ast}$,
$X_{i}^{\ast}$, and $Y_{i}^{\ast}$, for all $1\leq i\leq L$, admit correct
labelings. All rooted trees in $X_{i}^{\ast}$ admit correct labelings because
they are subtrees of the rooted trees in $W_{i+1}^{\ast}$. A correct labeling
of any bipolar tree $H\in Y_{i}^{\ast}$ can be obtained by combining any
correct labelings of the two rooted trees in $W_{i+1}^{\ast}$ resulting from
$H$.

##### Layers of Vertices

We assign a layer number $\lambda(v)$ to each vertex $v$ in a tree based on
the step that $v$ is introduced in the construction

$W_{1}^{\ast}\rightarrow W_{2}^{\ast}\rightarrow\cdots\rightarrow
W_{L}^{\ast}.$

If a vertex $v$ is introduced as the root vertex of a tree in
$X_{i}^{\ast}=X_{f}(W_{i}^{\ast})$, then we say that the layer number of $v$
is $\lambda(v)=i\in\\{1,2,\ldots,L\\}$. A vertex $v$ has $\lambda(v)=0$ if it
belongs to a tree in $W_{1}^{\ast}$.

For any vertex $v$ with $\lambda(v)=i$ in a tree $T\in X_{j}^{\ast}$ with
$i\leq j$, we write $T_{v}$ to denote the subtree of $T$ such that $T_{v}\in
X_{i}^{\ast}$ where $v$ is the root of $T_{v}$.

We construct a sequence of sets $R_{1},R_{2},\ldots,R_{L}$ as follows. We go
over all rooted trees $T\in X_{L}^{\ast}$, all possible correct labeling
$\mathcal{L}$ of $T$, and all vertices $v$ in $T$ with
$\lambda(v)=i\in\\{1,2,\ldots,L\\}$. Suppose that the $\Delta-2$ rooted trees
in the construction of $T_{v}\in X_{i}^{\ast}=X_{f}(W_{i}^{\ast})$ are
$T_{1}$, $T_{2}$, $\ldots$, $T_{\Delta-2}$, and let $r_{i}$ be the root of
$T_{i}$. Consider the following parameters.

  * •

$c_{i}=\textsf{Class}_{1}(T_{i})$.

  * •

$\mathtt{a}_{i}$ is the real half-edge label of $v$ in $T_{v}$ for the edge
$\\{v,r_{i}\\}$, under the correct labeling $\mathcal{L}$ of $T$ restricted to
$T_{v}$.

  * •

$\mathcal{I}$ is the size-$2$ multiset of virtual half-edge labels of $v$ in
$T_{v}$, under the correct labeling $\mathcal{L}$ of $T$ restricted to
$T_{v}$.

Then we add
$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})$
to $R_{i}$.

######  Lemma 4.14.

For each $1\leq i<L$, $R_{i}$ is determined by $R_{i+1}$.

###### Proof.

We consider the following alternative way of constructing $R_{i}$ from
$R_{i+1}$. Each rooted tree $T^{\prime}$ in
$W_{i+1}^{\ast}=Z_{f}(W_{i}^{\ast})$ can be described as follows.

  * •

Start with a path $(r_{1},r_{2},\ldots,r_{{\ell_{\operatorname{pump}}}+1})$,
where $r_{1}$ is the root of $T^{\prime}$.

  * •

For each $1\leq j\leq{\ell_{\operatorname{pump}}}+1$, append $\Delta-2$ rooted
trees $T_{j,1},T_{j,2},\ldots,T_{j,\Delta-2}\in W_{i}^{\ast}$ to $r_{j}$.

  * •

Assign the labels to the half-edges surrounding
$r_{{\ell_{\operatorname{pump}}}+1}$ according to the labeling function $f$.

Now, consider the function $\phi$ that maps each equivalence class $c$ for
rooted trees to a subset of $\Sigma$ defined as follows:
$\mathtt{a}\in\phi(c)$ if there exist

$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})\in
R_{i+1}$

and $1\leq j\leq\Delta-2$ such that $c=c_{j}$ and $\mathtt{a}=\mathtt{a}_{j}$.

We go over all possible $T^{\prime}\in W_{i+1}^{\ast}=Z_{f}(W_{i}^{\ast})$.
Note that the root $r$ of $T^{\prime}$ has exactly one virtual half-edge. For
each $\mathtt{b}\in\Sigma$ such that
$\\{\mathtt{a},\mathtt{b}\\}\in\mathcal{E}$ for some
$\mathtt{a}\in\phi(\textsf{Class}_{1}(T^{\prime}))$, we go over all possible
correct labelings $\mathcal{L}$ of $T^{\prime}$ where the virtual half-edge of
$r$ is labeled $\mathtt{b}$. For each $1\leq
j\leq{\ell_{\operatorname{pump}}}+1$, consider the following parameters.

  * •

$c_{l}=\textsf{Class}_{1}(T_{j,l})$.

  * •

$\mathtt{a}_{l}$ is the half-edge label of $r_{j}$ for the edge
$\\{r_{j},r_{j,l}\\}$.

  * •

$\mathcal{I}$ is the size-$2$ multiset of the remaining two half-edge labels
of $v$.

Then we add
$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})$
to $R_{i}$.

This construction of $R_{i}$ is equivalent to the original construction of
$R_{i}$ because a correct labeling of $T^{\prime}\in W_{i}^{\ast}$ can be
extended to a correct labeling of a tree $T\in X_{L}^{\ast}$ that contains
$T^{\prime}$ as a subtree if and only if the virtual half-edge label of the
root $r$ of $T^{\prime}$ is $\mathtt{b}\in\Sigma$ such that
$\\{\mathtt{a},\mathtt{b}\\}\in\mathcal{E}$ for some
$\mathtt{a}\in\phi(\textsf{Class}_{1}(T^{\prime}))$.

It is clear that this construction of $R_{i}$ only depends on
$\textsf{Class}_{1}(W_{i}^{\ast})$, the labeling function $f$, and the
function $\phi$, which depends only on $R_{i+1}$. Since the labeling function
$f$ is fixed and $\textsf{Class}_{1}(W_{i}^{\ast})$ is the same for all $i$,
we conclude that $R_{i}$ depends only on $R_{i+1}$. ∎

######  Lemma 4.15.

We have $R_{1}\subseteq R_{2}\subseteq\cdots\subseteq R_{L}$.

###### Proof.

For the base case, we show that $R_{L-1}\subseteq R_{L}$. In fact, our proof
will show that $R_{i}\subseteq R_{L}$ for each $1\leq i<L$. Consider any

$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})\in
R_{i}.$

Then there is a rooted tree $T\in X_{i}^{\ast}$ that is formed by attaching
$\Delta-2$ rooted trees of equivalence classes
$c_{1},c_{2},\ldots,c_{\Delta-2}$ to the root vertex so that if we label the
half-edges surrounding the root vertex according to
$\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2}$, and
$\mathcal{I}$, then this partial labeling can be completed into a correct
labeling of $T$.

Because $\textsf{Class}_{1}(W_{i}^{\ast})=\textsf{Class}_{1}(W_{L}^{\ast})$,
there is also a rooted tree $T^{\prime}\in X_{L}^{\ast}$ that is formed by
attaching $\Delta-2$ rooted trees of equivalence classes
$c_{1},c_{2},\ldots,c_{\Delta-2}$ to the root vertex. Therefore, if we label
the root vertex of $T^{\prime}$ in the same way as we do for $T$, then this
partial labeling can also be completed into a correct labeling of
$T^{\prime}$. Hence we must have

$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})\in
R_{L}.$

Now, suppose that we already have $R_{i}\subseteq R_{i+1}$ for some $1<i<L$.
We will show that $R_{i-1}\subseteq R_{i}$. Denote by $\phi_{i}$ and
$\phi_{i+1}$ the function $\phi$ in Lemma 4.14 constructed from $R_{i}$ and
$R_{i+1}$. We have $\phi_{i}(c)\subseteq\phi_{i+1}(c)$ for each equivalence
class $c$, because $R_{i}\subseteq R_{i+1}$. Therefore, in view of the
alternative construction described in the proof of Lemma 4.14, we have
$R_{i-1}\subseteq R_{i}$. ∎

##### The Set of Vertex Configurations $\mathcal{V}^{\prime}$

By Lemmas 4.14 and 4.15, if we pick $L$ to be sufficient large, we can have
$R_{1}=R_{2}=R_{3}$. More specifically, if we pick

$L\geq C^{\Delta-2}\cdot\binom{|\Sigma|+1}{|\Sigma|-1}+3,$

then there exists an index $3\leq i\leq L$ such that $R_{i}=R_{i-1}$, implying
that $R_{1}=R_{2}=R_{3}$. Here $C$ is the number of equivalence classes for
rooted trees and $\binom{|\Sigma|+1}{|\Sigma|-1}$ is the number of size-$2$
multisets of elements from $\Sigma$.

The set $\mathcal{V}^{\prime}$ is defined by including all size-$\Delta$
multisets
$\\{\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2}\\}\cup\mathcal{I}$
such that

$(c_{1},c_{2},\ldots,c_{\Delta-2},\mathtt{a}_{1},\mathtt{a}_{2},\ldots,\mathtt{a}_{\Delta-2},\mathcal{I})\in
R_{1}$

for some $c_{1},c_{2},\ldots,c_{\Delta-2}$.

##### The Set $\mathcal{V}^{\prime}$ is $\ell$-full

To show that the set $\mathcal{V}^{\prime}$ is $\ell$-full, we consider the
subset $\mathcal{V}^{\ast}\subseteq\mathcal{V}^{\prime}$ defined by the set of
vertex configurations used by the labeling function $f$ in the construction of
$Y_{f}(W_{i}^{\ast})$. The definition of $\mathcal{V}^{\ast}$ is invariant of
$i$ as $\textsf{Class}_{1}(W_{i}^{\ast})$ is the same for all $i$. Clearly,
for each $x\in\mathcal{V}^{\ast}$, there is a rooted tree $T\in W_{2}^{\ast}$
where the root of a subtree $T^{\prime}\in X_{1}^{\ast}$ of $T$ has its
size-$\Delta$ multiset of half-edge labels fixed to be $x$ by $f$, and so
$\mathcal{V}^{\ast}\subseteq\mathcal{V}^{\prime}$.

For notational simplicity, we write $x\overset{k}{\leftrightarrow}x^{\prime}$
if there is a correct labeling of a $k$-vertex path
$(v_{1},v_{2},\ldots,v_{k})$ using only vertex configurations in
$\mathcal{V}^{\prime}$ so that the vertex configuration of $v_{1}$ is $x$ and
the vertex configuration of $v_{k}$ is $x^{\prime}$. If it is further required
that the half-edge label of $v_{1}$ for the edge $\\{v_{1},v_{2}\\}$ is
$\mathtt{a}\in x$, then we write
$(x,\mathtt{a})\overset{k}{\leftrightarrow}x^{\prime}$. The notation
$(x,\mathtt{a})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{a}^{\prime})$
is defined similarly.

######  Lemma 4.16.

For any $x\in\mathcal{V}^{\prime}\setminus\mathcal{V}^{\ast}$ and
$\mathtt{a}\in x$, there exist a vertex configuration
$x^{\prime}\in\mathcal{V}^{\ast}$ and a number $2\leq k\leq
2{\ell_{\operatorname{pump}}}+1$ such that
$(x,\mathtt{a})\overset{k}{\leftrightarrow}x^{\prime}$.

###### Proof.

Let $T\in W_{L}^{\ast}$ be chosen so that there is a correct labeling
$\mathcal{L}$ where $x$ is a vertex configuration of some vertex $v$ with
$\lambda(v)=2$.

To prove the lemma, it suffices to show that for each of the $\Delta$
neighbors $u$ of $v$, it is possible to find a path $P=(v,u,\ldots,w)$ meeting
the following conditions.

  * •

$w$ is a vertex whose half-edge labels have been fixed by $f$. This ensures
that the vertex configuration of $w$ is in $\mathcal{V}^{\ast}$.

  * •

All vertices in $P$ are within layers 1,2, and 3. This ensures that the vertex
configuration of all vertices in $P$ are in $\mathcal{V}^{\prime}$.

  * •

The number of vertices $k$ in $P$ satisfies $2\leq k\leq
2{\ell_{\operatorname{pump}}}+1$.

We divide the proof into three cases. Refer to Fig. 4 for an illustration,
where squares are vertices whose half-edge labels have been fixed by $f$.

##### Case 1

Consider the subtree $T_{v}\in X_{2}^{\ast}$ of $T$ whose root is $v$. In view
of the construction of the set $X_{f}(W_{2}^{\ast})$, $v$ has $\Delta-2$
children $u_{1},u_{2},\ldots,u_{\Delta-2}$ in $T_{v}$, where the subtree
$T_{i}$ rooted at $u_{i}$ is a rooted tree in $W_{2}^{\ast}$.

For each $1\leq i\leq\Delta-2$, according to the structure of the trees in the
set $W_{2}^{\ast}=Z_{f}(W_{1}^{\ast})$, there is a path
$(u_{i}=w_{1},w_{2},\ldots,w_{{\ell_{\operatorname{pump}}}+1})$ in $T_{i}$
containing only layer-1 vertices, where the half-edge labels of
$w_{{\ell_{\operatorname{pump}}}+1}$ have been fixed by $f$. Hence
$P=(v,u_{i}=w_{1},w_{2},\ldots,w_{{\ell_{\operatorname{pump}}}+1})$ is a
desired path with $k={\ell_{\operatorname{pump}}}+2$ vertices.

##### Case 2

Consider the subtree $T^{\prime}\in W_{3}^{\ast}=Z_{f}(W_{2}^{\ast})$ that
contains $v$ in $T$. Similarly, according to the structure of the trees in the
set $W_{3}^{\ast}=Z_{f}(W_{2}^{\ast})$, there is a path
$(r=w_{1}^{\prime},w_{2}^{\prime},\ldots,w_{{\ell_{\operatorname{pump}}}+1}^{\prime})$
in $T^{\prime}$ containing only layer-2 vertices so that $r$ is the root of
$T^{\prime}$, $v=w_{i}^{\prime}$ for some $1\leq
i^{\prime}\leq{\ell_{\operatorname{pump}}}+1$, and the half-edge labels of
$w_{{\ell_{\operatorname{pump}}}+1}^{\prime}$ have been fixed by $f$. Since
$x\in\mathcal{V}^{\prime}\setminus\mathcal{V}^{\ast}$, we have $v\neq
w_{{\ell_{\operatorname{pump}}}+1}^{\prime}$. Hence
$P=(v=w_{i}^{\prime},w_{i+1}^{\prime},\ldots,w_{{\ell_{\operatorname{pump}}}+1}^{\prime})$
is a desired path with $2\leq k\leq{\ell_{\operatorname{pump}}}+1$ vertices.

##### Case 3

There is only one remaining neighbor of $v$ to consider. In view of the
construction of $X_{f}(W_{3}^{\ast})$, there is a layer-3 vertex $v^{\prime}$
adjacent to the vertex $r$, the root of the tree $T^{\prime}\in W_{3}^{\ast}$
considered in the previous case. If the half-edge labels of $v^{\prime}$ have
been fixed by $f$, then
$P=(v=w_{i}^{\prime},w_{i-1}^{\prime},\ldots,w_{1}^{\prime}=r,v^{\prime})$ is
a desired path. Otherwise, similar to the analysis in the previous case, we
can find a path $P^{\prime}=(v^{\prime},\ldots,w)$ connecting $v^{\prime}$ to
a vertex $w$ whose half-edge labels have been fixed by $f$. All vertices in
$P^{\prime}$ are of layer-3, and the number of vertices in $P^{\prime}$ is
within $[2,{\ell_{\operatorname{pump}}}+1]$. Combining $P^{\prime}$ with the
path $(v=w_{i}^{\prime},w_{i-1}^{\prime},\ldots,w_{1}^{\prime}=r,v^{\prime})$,
we obtain the desired path $P$ whose number of vertices satisfies $2\leq k\leq
2{\ell_{\operatorname{pump}}}+1$. ∎

Figure 4: An illustration for the proof of Lemma 4.16.

For Lemma 4.17, note that if $\mathtt{a}$ appears more than once in the
multiset $x$, then we still have $\mathtt{a}\in x\setminus\\{\mathtt{a}\\}$.

######  Lemma 4.17.

For any $\mathtt{a}\in x\in\mathcal{V}^{\ast}$, $\mathtt{a}^{\prime}\in
x^{\prime}\in\mathcal{V}^{\ast}$, and $0\leq
t\leq{\ell_{\operatorname{pump}}}-1$, we have
$(x,\mathtt{b})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
for some $\mathtt{b}\in x\setminus\\{\mathtt{a}\\}$ and
$\mathtt{b}^{\prime}\in x^{\prime}\setminus\\{\mathtt{a}^{\prime}\\}$ with
$k=2{\ell_{\operatorname{pump}}}+4+t$.

###### Proof.

For any $\mathtt{a}\in x\in\mathcal{V}^{\ast}$, we can find a rooted tree
$T_{x,\mathtt{a}}\in W_{2}^{\ast}$ such that the path $(v_{1}$, $v_{2}$,
$\ldots$, $v_{{\ell_{\operatorname{pump}}}+1})$ of the layer-1 vertices in
$T_{x,\mathtt{a}}$ where $v_{1}=r$ is the root of $T_{x,\mathtt{a}}$ satisfies
the property that the half-edge labels of $v_{{\ell_{\operatorname{pump}}}+1}$
have been fixed to $x$ by $f$ where the half-edge label for
$\\{v_{{\ell_{\operatorname{pump}}}},v_{{\ell_{\operatorname{pump}}}+1}\\}$ is
in $x\setminus\\{\mathtt{a}\\}$.

Now, observe that for any choice of
$(\Delta-2)({\ell_{\operatorname{pump}}}+1)$ rooted trees

$\\{T_{i,j}\\}_{1\leq i\leq{\ell_{\operatorname{pump}}}+1,1\leq
j\leq\Delta-2}$

in $W_{2}^{\ast}$, there is a rooted tree $T^{\prime}\in
W_{3}^{\ast}=Z_{f}(W_{2}^{\ast})$ formed by appending $T_{i,1}$, $T_{i,2}$,
$\ldots$, $T_{i,\Delta-2}$ to $u_{i}$ in the path $(u_{1}$, $u_{2}$, $\ldots$,
$u_{{\ell_{\operatorname{pump}}}+1})$ and fixing the half-edge labeling of
$u_{{\ell_{\operatorname{pump}}}+1}$ by $f$. All vertices in
$(u_{1},u_{2},\ldots,u_{{\ell_{\operatorname{pump}}}+1})$ are of layer-2.

We choose any $T^{\prime}\in W_{2}^{\ast}$ with $T_{i,j}=T_{x,\mathtt{a}}$ and
$T_{i^{\prime},j^{\prime}}=T_{x^{\prime},\mathtt{a}^{\prime}}$ such that
$i^{\prime}-i=t+1$. The possible range of $t$ is
$[0,{\ell_{\operatorname{pump}}}-1]$. Consider any $T\in W_{L}^{\ast}$ that
contains $T^{\prime}$ as its subtree, and consider any correct labeling of
$T$. Then the path $P$ resulting from concatenating the path
$(v_{{\ell_{\operatorname{pump}}}+1},v_{{\ell_{\operatorname{pump}}}},\ldots,v_{1})$
in $T_{x,\mathtt{a}}$, the path $(u_{i},u_{i+1},\ldots,u_{i^{\prime}})$, and
the path
$(v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{{\ell_{\operatorname{pump}}}+1}^{\prime})$
in $T_{x^{\prime},\mathtt{a}^{\prime}}$ shows that
$(x,\mathtt{b})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
for
$k=({\ell_{\operatorname{pump}}}+1)+(t+2)+({\ell_{\operatorname{pump}}}+1)=2{\ell_{\operatorname{pump}}}+4+t$.
See Fig. 5 for an illustration.

For the rest of the proof, we show that the desired rooted tree
$T_{x,\mathtt{a}}\in W_{2}^{\ast}$ exists for any $\mathtt{a}\in
x\in\mathcal{V}^{\ast}$. For any $x\in\mathcal{V}^{\ast}$, we can find a
bipolar tree

$H_{\ast}=(T_{1}^{l},T_{2}^{l},\ldots,T_{{\ell_{\operatorname{pump}}}}^{l},T_{\ast}^{m},T_{1}^{r},T_{2}^{r},\ldots,T_{{\ell_{\operatorname{pump}}}}^{r})\in
Y_{1}^{\ast}=Y_{f}(W_{1}^{\ast})$

such that the vertex configuration of the root $r^{m}$ of $T_{\ast}^{m}$ is
fixed to be $x$ by the labeling function $f$. Then, for any $\mathtt{a}\in x$,
at least one of the two rooted trees in $W_{2}^{\ast}=Z_{f}(W_{1}^{\ast})$
resulting from cutting $H_{\ast}$ satisfies the desired requirement. ∎

Figure 5: An illustration for the proof of Lemma 4.17.

In the subsequent discussion, the length of a path refers to the number of
edges in a path. In particular, the length of a $k$-vertex path is $k-1$.

The following lemma is proved by iteratively applying Lemma 4.17 via
intermediate vertex configurations $\tilde{x}\in\mathcal{V}^{\ast}$.

######  Lemma 4.18.

For any $\mathtt{a}\in x\in\mathcal{V}^{\ast}$ and $\mathtt{a}^{\prime}\in
x^{\prime}\in\mathcal{V}^{\ast}$, we have
$(x,\mathtt{b})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
for some $\mathtt{b}\in x\setminus\\{\mathtt{a}\\}$ and
$\mathtt{b}^{\prime}\in x^{\prime}\setminus\\{\mathtt{a}^{\prime}\\}$ for all
$k\geq 6{\ell_{\operatorname{pump}}}+10$.

###### Proof.

By applying Lemma 4.17 for three times, we infer that Lemma 4.17 also works
for any path length $k-1=(k_{1}-1)+(k_{2}-1)+(k_{3}-1)$, where
$k_{i}-1=2{\ell_{\operatorname{pump}}}+3+t_{i}$ for $0\leq
t_{i}\leq{\ell_{\operatorname{pump}}}-1$.

Specifically, we first apply Lemma 4.17 to find a path realizing
$(x,\mathtt{b})\overset{k_{1}}{\leftrightarrow}\tilde{x}$ for some
$\tilde{x}\in\mathcal{V}^{\ast}$, and for some $\mathtt{b}\in
x\setminus\\{\mathtt{a}\\}$. Let $\tilde{\mathtt{a}}\in\tilde{x}$ be the real
half-edge label used in the last vertex of the path. We extend the length of
this path by $k_{2}-1$ by attaching to it the path realizing
$(\tilde{x},\tilde{\mathtt{b}})\overset{k_{2}}{\leftrightarrow}\tilde{x}$, for
some $\tilde{\mathtt{b}}\in\tilde{x}\setminus\\{\tilde{\mathtt{a}}\\}$.
Finally, let $\tilde{\mathtt{c}}\in\tilde{x}$ be the real half-edge label used
in the last vertex of the current path. We extend the length of the current
path by $k_{3}$ by attaching to it the path realizing
$(\tilde{x},\tilde{\mathtt{d}})\overset{k_{3}}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$,
for some $\tilde{\mathtt{d}}\in\tilde{x}\setminus\\{\tilde{\mathtt{x}}\\}$,
and for some $\mathtt{b}^{\prime}\in
x^{\prime}\setminus\\{\mathtt{a}^{\prime}\\}$. The resulting path realizes
$(x,\mathtt{b})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
for some $\mathtt{b}\in x\setminus\\{\mathtt{a}\\}$ and
$\mathtt{b}^{\prime}\in x^{\prime}\setminus\\{\mathtt{a}^{\prime}\\}$.

Therefore, Lemma 4.17 also works with path length of the form
$k-1=6{\ell_{\operatorname{pump}}}+9+t$, for any
$t\in[0,3{\ell_{\operatorname{pump}}}-3]$.

Any $k-1\geq 6{\ell_{\operatorname{pump}}}+9$ can be written as
$k-1=b(2{\ell_{\operatorname{pump}}}+3)+(6{\ell_{\operatorname{pump}}}+9+t)$,
for some $t\in[0,3{\ell_{\operatorname{pump}}}-3]$ and some integer $b\geq 0$.
Therefore, similar to the above, we can find a path showing
$(x,\mathtt{b})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
by first applying Lemma 4.17 with path length
$2{\ell_{\operatorname{pump}}}+3$ for $b$ times, and then applying the above
variant of Lemma 4.17 to extend the path length by
$6{\ell_{\operatorname{pump}}}+9+t$. ∎

We show that Lemmas 4.16 and 4.18 imply that $\mathcal{V}^{\prime}$ is
$\ell$-full for some $\ell$.

######  Lemma 4.19 ($\mathcal{V}^{\prime}$ is $\ell$-full).

The set $\mathcal{V}^{\prime}$ is $\ell$-full for
$\ell=10{\ell_{\operatorname{pump}}}+10$.

###### Proof.

We show that for any target path length $k-1\geq
10{\ell_{\operatorname{pump}}}+9$, and for any $\mathtt{a}\in
x\in\mathcal{V}^{\ast}$ and $\mathtt{a}^{\prime}\in
x^{\prime}\in\mathcal{V}^{\ast}$, we have
$(x,\mathtt{a})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{a}^{\prime})$.

By Lemma 4.16, there exists a vertex configuration
$\tilde{x}\in\mathcal{V}^{\ast}$ so that we can find a path $P$ realizing
$(x,\mathtt{a})\overset{\ell_{1}}{\leftrightarrow}\tilde{x}$ for some path
length $1\leq(\ell_{1}-1)\leq 2{\ell_{\operatorname{pump}}}$. Similarly, there
exists a vertex configuration $\tilde{x}^{\prime}\in\mathcal{V}^{\ast}$ so
that we can find a path $P^{\prime}$ realizing
$(x^{\prime},\mathtt{a}^{\prime})\overset{\ell_{2}}{\leftrightarrow}\tilde{x}^{\prime}$
for some path length $1\leq(\ell_{2}-1)\leq 2{\ell_{\operatorname{pump}}}$.

Let $\tilde{\mathtt{a}}$ be the real half-edge label for $\tilde{x}$ in $P$,
and let $\tilde{\mathtt{a}}^{\prime}$ be the real half-edge label for
$\tilde{x}^{\prime}$ in $P^{\prime}$. We apply Lemma 4.18 to find a path
$\tilde{P}$ realizing
$(x,\mathtt{b})\overset{\tilde{\ell}}{\leftrightarrow}(x^{\prime},\mathtt{b}^{\prime})$
for some $\mathtt{b}\in\tilde{x}\setminus\\{\tilde{\mathtt{a}}\\}$ and
$\mathtt{b}^{\prime}\in\tilde{x}^{\prime}\setminus\\{\tilde{\mathtt{a}}^{\prime}\\}$
with path length

$\tilde{\ell}-1=(k-1)-(\ell_{1}-1)-(\ell_{2}-1)\geq
6{\ell_{\operatorname{pump}}}+9.$

The path formed by concatenating $P_{1}$, $\tilde{P}$, and $P_{2}$ shows that
$(x,\mathtt{a})\overset{k}{\leftrightarrow}(x^{\prime},\mathtt{a}^{\prime})$.
∎

##### A Feasible Labeling Function $f$ exists

We show that a feasible labeling function $f$ exists given that $\Pi$ can be
solved in $\mathsf{LOCAL}(n^{o(1)})$ rounds. We will construct a labeling
function $f$ in such a way each equivalence class in
$\textsf{Class}_{1}(W^{\ast})$ contains only rooted trees that admit legal
labeling. That is, for each $c\in\textsf{Class}_{1}(W^{\ast})$, the mapping
$h$ associated with $c$ satisfies $h(X)=\textsf{YES}$ for some $X$.

We will consider a series of modifications in the construction

$W\rightarrow X_{f}(W)\rightarrow Y_{f}(W)\rightarrow Z_{f}(W)$

that do not alter the sets of equivalence classes in these sets, conditioning
on the assumption that all trees that we have processed admit correct
labelings. That is, whether $f$ is feasible is invariant of the modifications.

##### Applying the Pumping Lemma

Let $w>0$ be some target length for the pumping lemma. In the construction of
$Y_{f}(W)$, when we process a bipolar tree

$H=(T_{1}^{l},T_{2}^{l},\ldots,T_{{\ell_{\operatorname{pump}}}}^{l},T^{m},T_{1}^{r},T_{2}^{r},\ldots,T_{{\ell_{\operatorname{pump}}}}^{r}),$

we apply Lemma 4.8 to the two subtrees
$H^{l}=(T_{1}^{l},T_{2}^{l},\ldots,T_{{\ell_{\operatorname{pump}}}}^{l})$ and
$H^{r}=(T_{1}^{r},T_{2}^{r},\ldots,T_{{\ell_{\operatorname{pump}}}}^{r})$ to
obtain two new bipolar trees $H_{+}^{l}$ and $H_{+}^{r}$. The $s$-$t$ path in
the new trees $H_{+}^{l}$ and $H_{+}^{r}$ contains $w+x$ vertices, for some
$0\leq x<{\ell_{\operatorname{pump}}}$. The equivalence classes do not change,
that is, $\textsf{Class}_{2}(H^{l})=\textsf{Class}_{2}(H_{+}^{l})$ and
$\textsf{Class}_{2}(H^{r})=\textsf{Class}_{2}(H_{+}^{r})$.

We replace $H^{l}$ by $H_{+}^{l}$ and replace $H^{r}$ by $H_{+}^{r}$ in the
bipolar tree $H$. Recall that the outcome of applying the labeling function
$f$ to the root $r$ of the rooted tree $T_{{\ell_{\operatorname{pump}}}+1}$
depends only on

$\textsf{Class}_{2}(H^{l}),\textsf{Class}_{1}(T_{1}^{m}),\textsf{Class}_{1}(T_{2}^{m}),\ldots,\textsf{Class}_{1}(T_{\Delta-2}^{m}),\textsf{Class}_{2}(H^{r}),$

so applying the pumping lemma to $H^{l}$ and $H^{r}$ during the construction
of $Y_{f}(W)$ does not alter $\textsf{Class}_{1}(T_{\ast}^{m})$ and
$\textsf{Class}_{2}(H^{\ast})$ for the resulting bipolar tree $H^{\ast}$ and
its middle rooted tree $T_{\ast}^{m}$, by Lemma 4.9.

##### Reusing Previous Trees

During the construction of the fixed point $W^{\ast}$, we remember all bipolar
trees to which we have applied the feasible function $f$.

During the construction of $Y_{f}(W)$. Suppose that we are about to process a
bipolar tree $H$, and there is already some other bipolar tree $\tilde{H}$ to
which we have applied $f$ before so that
$\textsf{Class}_{2}(H^{l})=\textsf{Class}_{2}(\tilde{H}^{l})$,
$\textsf{Class}_{1}(T_{i}^{m})=\textsf{Class}_{1}(\tilde{T}_{i}^{m})$ for each
$1\leq i\leq\Delta-2$, and
$\textsf{Class}_{2}(H^{r})=\textsf{Class}_{2}(\tilde{H}^{r})$. Then we replace
$H$ by $\tilde{H}$, and then we process $\tilde{H}$ instead.

By Lemma 4.9, this modification does not alter
$\textsf{Class}_{1}(T_{\ast}^{m})$ and $\textsf{Class}_{2}(H^{\ast})$ for the
resulting bipolar tree $H^{\ast}$.

##### Not Cutting Bipolar Trees

We consider the following different construction of $Z_{f}(W)$ from
$Y_{f}(W)$. For each $H^{\ast}\in Y_{f}(W)$, we simply add two copies of
$H^{\ast}$ to $Z_{f}(W)$, one of them has $r=s$ and the other one has $r=t$.
That is, we do not cut the bipolar tree $H^{\ast}$, as in the original
construction of $Z_{f}(W)$.

In general, this modification might alter $\textsf{Class}_{1}(Z_{f}(W))$.
However, it is not hard to see that if all trees in $Y_{f}(W)$ already admit
correct labelings, then $\textsf{Class}_{1}(Z_{f}(W))$ does not alter after
the modification.

Specifically, let $T$ be a rooted tree in $Z_{f}(W)$ with the above
modification. Then $T$ is identical to a bipolar tree
$H^{\ast}=(T_{1},T_{2},\ldots,T_{k})\in Y_{f}(W)$, where there exists some
$1<i<k$ such that the root $r_{i}$ of $T_{i}$ has its half-edge labels fixed
by $f$. Suppose that the root of $T$ is the root $r_{1}$ of $T_{1}$. If we do
not have the above modification, then the rooted tree $T^{\prime}$ added to
$Z_{f}(W)$ corresponding to $T$ is $(T_{1},T_{2},\ldots,T_{i})$, where the
root of $T^{\prime}$ is also $r_{1}$.

Given the assumption that all bipolar trees in $Y_{f}(W)$ admit correct
labelings, it is not hard to see that
$\textsf{Class}_{1}(T^{\prime})=\textsf{Class}_{1}(T)$. For any correct
labeling $\mathcal{L}^{\prime}$ of $T^{\prime}$, we can extend the labeling to
a correct labeling $\mathcal{L}$ of $T$ by labeling the remaining vertices
according to any arbitrary correct labeling of $H^{\ast}$. This is possible
because the labeling of $r_{i}$ has been fixed. For any correct labeling
$\mathcal{L}$ of $T$, we can obtain a correct labeling $\mathcal{L}^{\prime}$
of $T^{\prime}$ by restricting $\mathcal{L}$ to $T^{\prime}$.

##### Simulating a $\mathsf{LOCAL}$ Algorithm

We will show that there is a labeling function $f$ that makes all the rooted
trees in $W^{\ast}$ to admit correct solutions, where we apply the above three
modifications in the construction of $W^{\ast}$. In view of the above
discussion, such a function $f$ is feasible.

The construction of $W^{\ast}$ involves only a finite number $k$ of iterations
of $Z_{f}$ applied to some previously constructed rooted trees. If we view the
target length $w$ of the pumping lemma as a variable, then the size of a tree
in $W^{\ast}$ can be upper bounded by $O(w^{k})$.

Suppose that we are given an arbitrary $n^{o(1)}$-round $\mathsf{LOCAL}$
algorithm $\mathcal{A}$ that solves $\Pi$. It is known [CP19, Cha20] that
randomness does not help for LCL problems on bounded-degree trees with lound
complexity $\Omega(\log n)$, so we assume that $\mathcal{A}$ is deterministic.

The runtime of $\mathcal{A}$ on a tree of size $O(w^{k})$ can be made to be at
most $t=w/10$ if $w$ is chosen to be sufficiently large.

We pick the labeling function $f$ as follows. Whenever we encounter a new
bipolar tree $H$ to which we need to apply $f$, we simulate $\mathcal{A}$
locally at the root $r^{m}$ of the middle rooted tree $T^{m}$ in $H$. Here we
assume that the pumping lemma was applied before simulating $\mathcal{A}$.
Moreover, when we do the simulation, we assume that the number of vertices is
$n=O(w^{k})$.

To make the simulation possible, we just locally generate arbitrary distinct
identifiers in the radius-$t$ neighborhood $S$ of $r^{m}$. This is possible
because $t=w/10$ is so small that for any vertex $v$ in any tree $T$
constructed by recursively applying $Z_{f}$ for at most $k$ iterations, the
radius-$(t+1)$ neighborhood of $v$ intersects at most one such $S$-set.
Therefore, it is possible to complete the identifier assignment to the rest of
the vertices in $T$ so that for any edge $\\{u,v\\}$, the set of identifiers
seen by $u$ and $v$ are distinct in an execution of a $t$-round algorithm.

Thus, by the correctness of $\mathcal{A}$, the labeling of all edges
$\\{u,v\\}$ are configurations in $\mathcal{E}$ and the labeling of all
vertices $v$ are configurations in $\mathcal{V}$. Our choice of $f$ implies
that all trees in $W^{\ast}$ admit correct labeling, and so $f$ is feasible.
Combined with Lemma 4.19, we have proved that $\mathsf{LOCAL}(n^{o(1)})$
$\Rightarrow$ $\ell$-full.

### Acknowledgements

We would like to thank Anton Bernshteyn, Endre Csóka, Mohsen Ghaffari, Jan
Hladký, Steve Jackson, Alexander Kechris, Edward Krohne, Oleg Pikhurko,
Brandon Seward, Jukka Suomela, and Yufan Zheng for insightful discussions.

YC was supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by
the ETH Zürich Foundation. JG was supported by Leverhulme Research Project
Grant RPG-2018-424. CG and VR were supported by the European Research Council
(ERC) under the European Unions Horizon 2020 research and innovation programme
(grant agreement No. 853109). ZV was partially supported by the National
Research, Development and Innovation Office – NKFIH, grants no. 113047, no.
129211 and FWF Grant M2779.

## References

  * [BBC+22] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studenỳ, and Jukka Suomela.  Efficient classification of local problems in regular trees.  arXiv preprint arXiv:2202.08544, 2022.
  * [BBE+20] Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela.  Classification of distributed binary labeling problems.  In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:17, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [BBH+19] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela.  Lower bounds for maximal matchings and maximal independent sets.  In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 481–497, 2019.
  * [BBKO21] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti.  Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), 2021.
  * [BBKO22] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti.  Distributed $\Delta$-coloring plays hide-and-seek.  In 54th ACM Symposium on Theory of Computing (STOC), 2022.
  * [BBO20] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti.  Distributed lower bounds for ruling sets.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 365–376, 2020\.
  * [BBO+21] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko.  Locally checkable problems in rooted trees.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 2021.
  * [BBOS20] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela.  Almost global problems in the local model.  Distributed Computing, pages 1–23, 2020.
  * [BCG+21a] Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Vaclav Rozhoň, and Zoltán Vidnyánszky.  Complexity classes of local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics.  in preparation, 2021.
  * [BCG+21b] Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Vaclav Rozhoň, and Zoltán Vidnyánszky.  Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics.  arXiv preprint arXiv:2106.02066, 2021.  A short version of the paper was presented at the _13th Innovations in Theoretical Computer Science conference (ITCS 2022)_.
  * [BCG+21c] Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky.  On homomorphism graphs, 2021.
  * [BEPS16] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider.  The locality of distributed symmetry breaking.  Journal of the ACM, 63(3):20, 2016.
  * [Ber] Anton Bernshteyn.  Work in progress.
  * [Ber20a] Anton Bernshteyn.  Distributed algorithms, the Lovász Local Lemma, and descriptive combinatorics.  arXiv preprint arXiv:2004.04905, 2020.
  * [Ber20b] Anton Bernshteyn.  A fast distributed algorithm for ($\Delta$+1)-edge-coloring.  preprint, 2020.
  * [Ber21] Anton Bernshteyn.  Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms.  arXiv preprint arXiv:2102.08797, 2021.
  * [BFH+16] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto.  A lower bound for the distributed Lovász local lemma.  In Proc. 48th ACM Symp. on Theory of Computing (STOC), pages 479–488, 2016.
  * [BGH19] Ágnes Backhausz, Balázs Gerencsér, and Viktor Harangi.  Entropy inequalities for factors of IID.  Groups Geom. Dyn., 13(2):389–414, 2019.
  * [BGR20] Sebastian Brandt, Christoph Grunau, and Václav Rozhoň.  Generalizing the sharp threshold phenomenon for the distributed complexity of the lovász local lemma.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 329–338, 2020.
  * [BHK+17] Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański.  LCL problems on grids.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), page 101–110, New York, NY, USA, 2017. Association for Computing Machinery.
  * [BHK+18] Alkida Balliu, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela.  New classes of distributed time complexity.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1307–1318, 2018.
  * [BHOS19] Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela.  Hardness of minimal symmetry breaking in distributed computing.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 369–378, 2019.
  * [BO20] Sebastian Brandt and Dennis Olivetti.  Truly tight-in-$\Delta$ bounds for bipartite maximal matching and variants.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, page 69–78, New York, NY, USA, 2020. Association for Computing Machinery.
  * [Bow10a] Lewis Bowen.  The ergodic theory of free group actions: entropy and the f -invariant.  Groups Geom. Dyn., 4(3):419–432, 2010.
  * [Bow10b] Lewis Bowen.  A measure-conjugacy invariant for free group actions.  Ann. of Math., 171(2):1387–1400, 2010.
  * [Bra19] Sebastian Brandt.  An automatic speedup theorem for distributed problems.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 379–388, 2019.
  * [BSV15] Ágnes Backhausz, Balázs Szegedy, and Bálint Virág.  Ramanujan graphings and correlation decay in local algorithms.  Random Structures Algorithms, 47(3):424–435, 2015.
  * [CGA+16] Endre Csóka, Łukas Grabowski, Máthé András, Oleg Pikhurko, and Konstantin Tyros.  Borel version of the local lemma.  arXiv preprint arXiv:1605.04877, 2016.
  * [CGM+17] Endre Csóka, Łukasz Grabowski, András Máthé, Oleg Pikhurko, and Konstantinos Tyros.  Borel version of the Local Lemma.  arXiv:1605.04877, 2017.
  * [Cha20] Yi-Jun Chang.  The Complexity Landscape of Distributed Locally Checkable Problems on Trees.  In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:17, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [CHL+20] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto.  Distributed edge coloring and a special case of the constructive Lovász local lemma.  ACM Trans. Algorithms, 16(1):8:1–8:51, 2020.
  * [CJM+20] Clinton T. Conley, Steve Jackson, Andrew S. Marks, Brandon Seward, and Robin Tucker-Drob.  Borel asymptotic dimension and hyperfinite equivalence relations.  arXiv:2009.06721, 2020.
  * [CKP19] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie.  An exponential separation between randomized and deterministic complexity in the local model.  SIAM Journal on Computing, 48(1):122–143, 2019.
  * [CM16] Clinton T. Conley and Benjamin D. Miller.  A bound on measurable chromatic numbers of locally finite Borel graphs.  Math. Res. Lett., 23(6):1633–1644, 2016.
  * [CM17] Clinton T. Conley and Benjamin D. Miller.  Measure reducibility of countable Borel equivalence relations.  Ann. of Math. (2), 185(2):347–402, 2017.
  * [CMTD16] Clinton T Conley, Andrew S Marks, and Robin D Tucker-Drob.  Brooks’theorem for measurable colorings.  In Forum of Mathematics, Sigma, volume 4. Cambridge University Press, 2016.
  * [CP19] Yi-Jun Chang and Seth Pettie.  A time hierarchy theorem for the local model.  SIAM Journal on Computing, 48(1):33–69, 2019.
  * [CSS20] Yi-Jun Chang, Jan Studený, and Jukka Suomela.  Distributed graph problems through an automata-theoretic lens.  arXiv:2002.07659, 2020.
  * [CV86] Richard Cole and Uzi Vishkin.  Deterministic coin tossing with applications to optimal parallel list ranking.  Information and Control, 70(1):32–53, 1986.
  * [DF92] Randall Dougherty and Matthew Foreman.  Banach-Tarski paradox using pieces with the property of Baire.  Proc. Nat. Acad. Sci. U.S.A., 89(22):10726–10728, 1992.
  * [DJK94] Randall Dougherty, Steve Jackson, and Alexander S. Kechris.  The structure of hyperfinite Borel equivalence relations.  Trans. Amer. Math. Soc., 341(1):193–225, 1994.
  * [Ele18] Gábor Elek.  Qualitative graph limit theory. cantor dynamical systems and constant-time distributed algorithms.  arXiv preprint arXiv:1812.07511, 2018.
  * [Gab00] Damien Gaboriau.  Coût des relations d’équivalence et des groupes.  Invent. Math., 139(1):41–98, 2000.
  * [Gao08] Su Gao.  Invariant descriptive set theory.  Chapman and Hall/CRC, 2008.
  * [GHS14] Mika Göös, Juho Hirvonen, and Jukka Suomela.  Linear-in-$\Delta$ lower bounds in the LOCAL model.  In Proc. 33rd ACM Symp. on Principles of Distributed Computing (PODC), pages 86–95, 2014.
  * [GJ15] Su Gao and Steve Jackson.  Countable abelian group actions and hyperfinite equivalence relations.  Inventiones Math., 201(1):309–383, 2015.
  * [GJKS] S. Gao, S. Jackson, E. Krohne, and B. Seward.  Borel combinatorics of countable group actions.  in prep.
  * [GJKS15] Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward.  Forcing constructions and countable borel equivalence relations.  arXiv:1503.07822, 2015.
  * [GJKS18] Su Gao, Steve Jackson, Edward Krohne, and Brandon Seward.  Continuous combinatorics of abelian group actions., 2018.
  * [GJS09] S. Gao, S. Jackson, and B. Seward.  A coloring property for countable groups.  Mathematical Proceedings of the Cambridge Philosophical Society, 147(3):579–592, 2009.
  * [GKM17] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus.  On the complexity of local distributed graph problems.  In Proc. 49th ACM Symp. on Theory of Computing (STOC), pages 784–797, 2017.
  * [GMP17] Łukasz Grabowski, András Máthé, and Oleg Pikhurko.  Measurable circle squaring.  Ann. of Math. (2), 185(2):671–710, 2017.
  * [GR21a] Jan Grebík and Václav Rozhoň.  Classification of local problems on paths from the perspective of descriptive combinatorics.  arXiv preprint arXiv:2103.14112, 2021.
  * [GR21b] Jan Grebík and Václav Rozhoň.  Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics.  arXiv preprint arXiv:2103.08394, 2021.
  * [GRB22] Christoph Grunau, Václav Rozhoň, and Sebastian Brandt.  The landscape of distributed complexities on trees and beyond.  ArXiv, abs/2202.04724, 2022.
  * [HK96] Greg Hjorth and Alexander S. Kechris.  Borel equivalence relations and classifications of countable models.  Annals of pure and applied logic, 82(3):221–272, 1996.
  * [HSW17] Alexander E. Holroyd, Oded Schramm, and David B. Wilson.  Finitary coloring.  Ann. Probab., 45(5):2867–2898, 2017.
  * [JKL02] Steve Jackson, Alexander S. Kechris, and Alain Louveau.  Countable Borel equivalence relations.  J. Math. Logic, 2(01):1–80, 2002.
  * [Kec95] Alexander S. Kechris.  Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.
  * [KM20] Alexander S. Kechris and Andrew S. Marks.  Descriptive graph combinatorics.
http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf, 2020\.

  * [KMW16] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.  Local computation: Lower and upper bounds.  Journal of the ACM, 63(2), 2016.
  * [KST99] Alexander S. Kechris, Sławomir Solecki, and Stevo Todorčević.  Borel chromatic numbers.  Adv. Math., 141(1):1–44, 1999.
  * [Lac90] Miklós Laczkovich.  Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem.  J. Reine Angew. Math., 404:77–117, 1990.
  * [Lin92] Nati Linial.  Locality in distributed graph algorithms.  SIAM Journal on Computing, 21(1):193–201, 1992.
  * [LN11] Russell Lyons and Fedor Nazarov.  Perfect matchings as iid factors on non-amenable groups.  European Journal of Combinatorics, 32(7):1115–1125, 2011.
  * [Mar16] Andrew S. Marks.  A determinacy approach to Borel combinatorics.  J. Amer. Math. Soc., 29(2):579–600, 2016.
  * [MNP22] András Máthé, Jonathan A. Noel, and Oleg Pikhurko.  Circle squaring with pieces of small boundary and low borel complexity.  arXiv:2202.01412, 2022.
  * [MR89] Gary L. Miller and John H. Reif.  Parallel tree contraction–Part I: fundamentals.  Advances in Computing Research, 5:47–72, 1989.
  * [MU16] Andrew Marks and Spencer Unger.  Baire measurable paradoxical decompositions via matchings.  Adv. Math., 289:397–410, 2016.
  * [MU17] Andrew S. Marks and Spencer T. Unger.  Borel circle squaring.  Ann. of Math. (2), 186(2):581–605, 2017.
  * [NS95] Moni Naor and Larry Stockmeyer.  What can be computed locally?  SIAM Journal on Computing, 24(6):1259–1277, 1995.
  * [Pik21] Oleg Pikhurko.  Borel combinatorics of locally finite graphs.  arXiv preprint arXiv:2009.09113, 2021.
  * [RG20] Václav Rozhoň and Mohsen Ghaffari.  Polylogarithmic-time deterministic network decomposition and distributed derandomization.  In Proc. Symposium on Theory of Computation (STOC), 2020.
  * [STD16] B. Seward and R. Tucker-Drob.  Borel structurability on the 2-shift of a countable group.  Annals of Pure and Applied Logic, 167(1):1–21, 2016.