# Representation theory of the group of automorphisms of a finite rooted tree.

Fabio Scarabotti

###### Abstract

We show that the ordinary irreducible representations of the group of
automorphisms of a finite, rooted tree may be obtained following one of the
classical method used for the irreducible representations of the symmetric
group, namely the approach in Chapter 2 of the classical book by James and
Kerber. To reach this goal, we introduce and study the combinatorics of tree
compositions, a natural generalization of set compositions but with new
features and more complexity due to the tree structure. This leads to a
natural parametrization of the conjugacy classes and of the irreducible
representations by means of the same combinatorial objects. Our trees are not
necessarily spherically homogeneous and our approach is coordinate free.
111AMS 2020 Math. Subj. Class.Primary: 20C15. Secondary: 05E10, 20B25, 20C30.
Keywords: Automorphisms of rooted trees, Symmetric groups, Representation
theory, Mackey’s theory.

###### Contents

  1. 1 Introduction
  2. 2 Finite rooted trees: automorphisms and compositions
  3. 3 The quotient of a tree composition
  4. 4 Trees of partitions
  5. 5 The conjugacy classes of $\mbox{\rm Aut}(\mathcal{T})$
  6. 6 Common refinements of tree compositions
  7. 7 Tree compositions with $0-1$ intersection and transposition
  8. 8 The irreducible representations of $\mbox{\rm Aut}(\mathcal{T})$

##  1 Introduction

The symmetric group $S_{n}$ may be seen as the group of automorphisms of a
rooted tree $\mathcal{T}$ with just one level, that is an $n$-star. Similarly,
the wreath product of two symmetric groups $S_{m}\wr S_{n}$ is the group of
automorphisms of a rooted tree with two levels: just add $m$ children to each
leaf of the $n$-star; we may continue: the iterated wreath product of $h$
symmetric groups is naturally the group of automorphisms of a spherically
homogeneous rooted tree $\mathcal{T}$ with $h$ levels. This observation was
the starting point of the joint paper with Tullio Ceccherini-Silberstein and
Filippo Tolli [6], where, in particular, we analyzed the permutation
representations on the varieties of spherically homogeneous subtrees, showing
that they decomposes without multiplicity. This is a clear analogy with the
$h=1$ case, where they correspond to the permutation representations
$M^{(n-k,k)}$ of the symmetric group.

In the present paper we push the analogy further and we show that all the
irreducible representations of the group of automorphisms of a finite, rooted
tree may be constructed following one of the classical approach to the
representation theory of $S_{n}$, namely that in [21, Chapter 2], which relies
on Mackey’s theory. Moreover, we show that it works for every kind of rooted
tree $\mathcal{T}$, that is in the present paper $\mathcal{T}$ is not
necessarily spherically homogeneous and $\mbox{\rm Aut}(\mathcal{T})$ is not
necessarily an iterated wreath product of symmetric groups. Actually, this
general point of view is also imposed by the theory itself: for instance, the
constructions in Section 3 require the application of the fundamental notion
to arbitrary trees. We get a parametrization of the conjugacy classes (Section
5) and of the irreducible representations (Section 8) by means of the same
objects: what we have called the equivalence classes of tree compositions
which in turn are parametrized by means of the set of trees of partitions. Our
approach uses iterations to construct combinatorial structures and just at the
end we employ Mackey’s theory. The permutation representations on sets of tree
compositions that we introduce are the natural generalization of the
permutation representations $M^{\lambda}$ usually introduced for the symmetric
group; see [9, 21, 27].

Our method avoids the use of Clifford theory (but see Example 2.8 and Open
Problem 8.13) and it concentrates to the direct study of the action of
$\mbox{\rm Aut}(\mathcal{T})$ on the tree $\mathcal{T}$ itself and on the many
combinatorial and algebraic structures associated to this action that are
naturally involved in the representation theory. As a matter of fact, the
representation of the symmetric group is not used in our paper but it is
obtained at the end as a consequence of our more general theory. As already
pointed out, our main goal is to reveal the great analogies between $S_{n}$
and $\mbox{\rm Aut}(\mathcal{T})$ and what really comes out as new
difficulties or new tools when we face the second group.

Throughout the paper we use the case height=1 to illustrate the basic facts in
the most elementary case; to introduce our coordinate free and arrow style
approach; as a basis for most of the inductive proofs; to manage the case in
which the tree has leaves not only at the last level.

This is the plan of the paper.

In Section 2 we introduce the first level decomposition of a rooted tree. It
is a quite useful device to describe tree homomorphisms, to construct proofs
by induction on the height of the tree and to avoid the use of coordinates.
Then we define the fundamental notion of tree composition. It is a natural
generalization of the composition of a set but it has two peculiarities. First
of all, it is presented in a coordinate free fashion, by means of surjective
maps between rooted trees. Moreover, these maps must satisfy a regularity
condition imposed by the representation theory but also from the
parametrization of the conjugacy classes. We introduce the notion of
equivalence, strict equivalence and isomorphism of tree compositions and we
give several examples.

In Section 3 we define the quotient of a tree composition. Its name derives
from its construction: we start by introducing a suitable equivalence relation
and its quotient yields the desired composition. We introduce two systems of
pseudogroups of partial isomorphisms that will be used in subsequent sections
in many technical computations with tree compositions and automorphisms.

In Section 4 we introduce the type of a tree composition: it is a
generalization, in our setting, of the usual notion of numerical composition.
Then we introduce the notion of tree of partitions: it is the generalization,
in our setting, of the notion of numerical partition and we show that tree of
partitions parametrizes the equivalence classes of tree compositions. We give
an algorithm to construct all the trees of partitions associated to a rooted
tree and we end the section by introducing a total order between tree of
partitions that generalizes the lexicographic order for numerical partitions.

In Section 5 we describe and parametrize the conjugacy classes of $\mbox{\rm
Aut}(\mathcal{T})$ by means equivalence classes of tree compositions which in
turn are parametrized by the tree of partitions associated to $\mathcal{T}$.

In Section 6 we construct a theory of common refinements of two tree
compositions. It is the key ingredient to parametrize diagonal actions of
$\mbox{\rm Aut}(\mathcal{T})$ on products of spaces of tree compositions and
therefore to apply Mackey’s theory.

In Section 7 we generalizes, in our setting, two basic combinatorial and
algebraic facts which are the key ingredient in the representation theory of
the symmetric group, namely the existence and uniqueness of the $0-1$ matrix
in [21, 2.1.1] and the easier implication of the Gale-Ryser Theorem [21,
1.4.17], with the dominance order replaced with the total order. These results
are quite easy for set compositions but in the context of tree compositions
they require more technical proofs.

In Section 8 we finally describe the ordinary irreducible representations of
$\mbox{\rm Aut}(\mathcal{T})$, exactly as in [21, Theorem 2.1.11]. We also
describe several open problems suggested by the theory developed in the
present paper.

Other references on the approach to the representation theory of the symmetric
group that we follow are [8, 23]; it is also sketched in [30, Section 3.11].
James and Kerber attributed it to A. J. Coleman [13]. In [22] the basic
property on which it is based is extended to the wreath product of two
symmetric groups. The standard reference on the representation theory of
wreath products is [21, Chapter 4]; a more recent account is [7]. The
representation theory of groups of the form $G\wr S_{n}$ is an active area of
research; see [1, 24]. General references on groups acting on (infinite)
rooted trees are [3, 17]. In [16] the authors describe the conjugacy classes
of the groups of automorphisms of infinite trees. In [25] and [15, Chapter 3]
the irreducible representations of the groups of automorphisms of certain
finite trees are used to describe the irreducible representations of the group
of automorphisms of an infinite, homogeneous tree.

##  2 Finite rooted trees: automorphisms and compositions

Let $\mathcal{T}$ be a finite rooted tree [14, Section 1.5]; we identify
$\mathcal{T}$ we the set of its vertices. As in [6, Section 3.1], the root is
denoted by $\\{\emptyset\\}$. A path in $\mathcal{T}$ of lenght $k$ is a
finite sequence of vertices $v_{0},v_{1},v_{2},\dotsc,v_{k}\in\mathcal{T}$
such that $v_{j}$ is adjacent to $v_{j+1}$, $j=0,1,2,\dotsc,k-1$. If $v_{0}$
is the root we say that $v_{k}$ is at level $k$; the $k$-_th level_ of the
tree is the set of all vertices at level $k$. If $v,w\in\mathcal{T}$ are
adjacent, $v$ at level $k$ and $w$ at level $k+1$ we say that $v$ is the
_parent_ of $w$ and that $w$ is a _child_ of $v$. A _leaf_ of $\mathcal{T}$ is
a vertex without children; a vertex with at least one child is internal. If
$u\in\mathcal{T}$ is not a leaf then $\text{\rm Ch}(u)$ will denote the set of
its children. If $u,w$ have the same parent $v$ we say that $u$ and $w$ are
siblings. The _height_ of the tree $\mathcal{T}$ is the level of the lowest
leaf; equivalently, the lenght of the longest path starting from the root. We
denote by $H(\mathcal{T})$ the height of $\mathcal{T}$. If
$v,w\in\mathcal{T}$, $v$ at level $j$, $w$ at level $k$, $j<k$ and there is a
path from $v$ to $w$ we say that $v$ is an ancestor of $w$ and that $w$ is a
descendant of $v$.

We denote by $\mbox{\rm Aut}(\mathcal{T})$ the group of all bijective maps
$\alpha\colon\mathcal{T}\to\mathcal{T}$ which preserve the adjacency relation
and that, in addition, fix the root $\emptyset$. That is, $\mbox{\rm
Aut}(\mathcal{T})$ is the group of all automorphisms of $\mathcal{T}$ as a
rooted tree. Clearly, every $\alpha\in\mbox{\rm Aut}(\mathcal{T})$ stabilizes
all levels of the tree. For each internal vertex $u\in\mathcal{T}$ we denote
by $\mathcal{T}_{u}$ the subtree made up of $u$ and of all its descendants; if
$\mathcal{P}$ is another rooted tree and
$\varphi\colon\mathcal{T}\rightarrow\mathcal{P}$ is a rooted tree homomorphism
(that is, a graph homomorphism [14, Section 1.1] that sends the root of
$\mathcal{T}$ to the root of $\mathcal{P}$) we denote by

$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ (2.1)

the restriction of $\varphi$ to $\mathcal{T}_{u}$.

If $h=H(\mathcal{T})$ and $\lvert\text{Ch}(u)\rvert=r_{k}$, for every vertex
$u$ at level $k-1$, $k=1,2,\dotsc,h$, we say that $\mathcal{T}$ is a
_spherically homogeneous rooted tree of branching type_ ${\bf
r}\coloneqq(r_{1},r_{2},\ldots,r_{h})$. If this is the case, then

$\mbox{\rm Aut}(\mathcal{T})\cong S_{r_{h}}\wr S_{r_{h-1}}\wr\cdots\wr
S_{r_{2}}\wr S_{r_{1}},$ (2.2)

where $S_{n}$ is the symmetric group on $n$ objects and $\wr$ denotes the
wreath product; see [10, Theorem 2.1.15]. If $r_{1}=r_{2}=\dotsb=r_{h}=1$ then
we say that $\mathcal{T}$ is a path of lenght $h$.

The first tree in Figure 1 is of height 3, the second tree in Figure 1 is
spherically homogeneous and the tree in Figure 2 is not spherically
homogeneous but have all the leaves at the lowest level.

${\scriptstyle\emptyset}$

${\scriptstyle\emptyset}$

Fig. 1

It is possible to introduce a system of coordinate on a rooted tree
$\mathcal{T}$ just by numbering the first level vertices by $1,2,\dotsc,n$,
then the children of the vertex $j$ are numbered by $j1,j2,\dotsc,jm$ and so
on. This is an example:

${\scriptstyle\emptyset}$

${\scriptstyle 1}$${\scriptstyle 2}$${\scriptstyle 3}$

${\scriptstyle 11}$${\scriptstyle 12}$

${\scriptstyle 21}$${\scriptstyle 22}$

${\scriptstyle 31}$${\scriptstyle 32}$${\scriptstyle 33}$

${\scriptstyle 111}$${\scriptstyle 112}$${\scriptstyle 113}$

${\scriptstyle 121}$

${\scriptstyle 211}$${\scriptstyle 212}$

${\scriptstyle 221}$${\scriptstyle 222}$

${\scriptstyle 311}$${\scriptstyle 321}$${\scriptstyle 331}$

Fig. 2

We prefer to introduce a coordinate free description of a rooted tree in the
following way: we denote by $V_{\mathcal{T}}$ the vertices at the first level
and by $W_{\mathcal{T}}$ the vertices in $V_{\mathcal{T}}$ which are leaves.
Then the first level decomposition is given by:

$\mathcal{T}=\\{\emptyset\\}\sqcup V_{\mathcal{T}}\sqcup\left[\bigsqcup_{u\in
V_{\mathcal{T}}\setminus
W_{\mathcal{T}}}\left(\\{u\\}\times\widetilde{\mathcal{T}_{u}}\right);\right],$
(2.3)

where $\widetilde{\mathcal{T}_{u}}\coloneqq\mathcal{T}_{u}\setminus\\{u\\}$.
That is, we think that to each $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$
is attached the tree $\mathcal{T}_{u}$ and we call it a first level subtree.
The edges at the first level join the root $\emptyset$ to the vertices in
$V_{\mathcal{T}}$ while the edges at the second level join each $u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ to the vertices at first level of
$\mathcal{T}_{u}$. When we use (2.3) we often represent the vertices of
$\mathcal{T}$ below the first level as couples of the form

$(u,w)\quad\text{ where }\;u\in V_{\mathcal{T}}\setminus
W_{\mathcal{T}}\;\text{ and }\;w\in\widetilde{\mathcal{T}_{u}}.$ (2.4)

That is, we use $(u,w)$ in place of the coordinates $j_{1}j_{2}\dotsb j_{h}$
($u$ takes the place of $j_{1}$ and $w$ of $j_{2}j_{3}\dotsb j_{h}$). Clearly,
if $H(\mathcal{T})=1$ then $V_{\mathcal{T}}=W_{\mathcal{T}}$ while if
$H(\mathcal{T})\geq 2$ then $V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ is not
empty while $W_{\mathcal{T}}$ might be empty.

If $\mathcal{T}$ and $\mathcal{P}$ are rooted trees,
$\varphi\colon\mathcal{T}\rightarrow\mathcal{P}$ is a rooted tree homomorphism
and

$\mathcal{P}=\\{\emptyset\\}\sqcup V_{\mathcal{P}}\sqcup\left[\bigsqcup_{x\in
V_{\mathcal{P}}\setminus
W_{\mathcal{P}}}\left(\\{x\\}\times\widetilde{\mathcal{P}}_{x}\right)\right]$
(2.5)

is the first level decomposition of $\mathcal{P}$ (cf. (2.3)) then we
represent $\varphi$ by means of (2.1) and (2.4) in the following form: a map
between sets $\varphi\rvert_{W_{\mathcal{T}}}\colon W_{\mathcal{T}}\rightarrow
W_{\mathcal{P}}$ and then

$\varphi(u,w)=(\varphi(u),\varphi_{u}(w)),\qquad\text{ for all }u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}},w\in\widetilde{\mathcal{T}_{u}}.$
(2.6)

If $\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$ is another tree
homomorphism and $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ then
$(\alpha\circ\varphi)(u,w)=\alpha(\varphi(u),\varphi_{u}(w))=\bigl{(}(\alpha\circ\varphi)(u),\left(\alpha_{\varphi(u)}\circ\varphi_{u}\right)(w)\bigr{)}$,
that is

$(\alpha\circ\varphi)_{u}=\alpha_{\varphi(u)}\circ\varphi_{u}.$ (2.7)

We will use (2.6) also to express isomorphisms and automorphisms. In
particular, if $g\in\mbox{\rm Aut}(\mathcal{T})$ then from (2.7) we deduce
that

$(u,w)=(g\circ g^{-1})(u,w)=\bigl{(}g\circ
g^{-1}(u),\left(g_{g^{-1}(u)}\circ(g^{-1})_{u}\right)(w)\bigr{)}$

so that

$(g^{-1})_{u}=\left(g_{g^{-1}(u)}\right)^{-1}.$ (2.8)

Note that in this expression we need to use the parentheses: for instance,
$g^{-1}_{u}$ is ambiguous because it might denote the inverse of $g_{u}$ or
the restriction of $g^{-1}$ to $\mathcal{T}_{u}$!

######  Definition 2.1.

If $\mathcal{T},\mathcal{P}$ are rooted trees a $\mathcal{P}$-composition of
$\mathcal{T}$ is a surjective rooted tree homorphism
$\varphi\colon\mathcal{T}\rightarrow\mathcal{P}$, such that:

  1. 1.

for every internal vertex $u\in\mathcal{T}$ the map
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ is
surjective;

  2. 2.

if $u,v\in\mathcal{T}$ are internal, $u\neq v$ and
$\varphi(u)=\varphi(v)\eqqcolon x$ then there exists an isomorphism
$\tau_{v,u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{v}$ such that
$\varphi_{u}=\varphi_{v}\circ\tau_{v,u}$, that is the following diagram is
commutative:

$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\tau_{v,u}}$$\textstyle{\mathcal{P}_{x}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{v}}$
(2.9)

We also say that $\varphi$ is a tree composition of $\mathcal{T}$ and that 2.
is the regularity condition.

$u$$\mathcal{T}_{u}$

$v$$\mathcal{T}_{v}$

$x$$\mathcal{P}_{x}$

$\tau_{v,u}$

$\varphi_{v}$

$\varphi_{u}$

In particular, all the maps $\varphi_{u}$, $u\in\mathcal{T}$ internal, are
tree compositions and if $\varphi(u)=\varphi(v)$ then $\mathcal{T}_{u}$ and
$\mathcal{T}_{v}$ are necessarily isomorphic. If there exists a $\varphi$ as
above then we say that $\mathcal{P}$ is a compositional tree for
$\mathcal{T}$. The identity composition of $\mathcal{T}$ is given by the
identity automorphism: $\mbox{\rm
id}_{\mathcal{T}}\colon\mathcal{T}\rightarrow\mathcal{T}$.

We denote by $\mathsf{C}(\mathcal{T},\mathcal{P})$ the set of all
$\mathcal{P}$-compositions of $\mathcal{T}$. The group $\mbox{\rm
Aut}(\mathcal{T})\times\mbox{\rm Aut}(\mathcal{P})$ acts on
$\mathsf{C}(\mathcal{T},\mathcal{P})$ in a natural way: if
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$, $g\in\mbox{\rm
Aut}(\mathcal{T})$ and $k\in\mbox{\rm Aut}(\mathcal{P})$ we set

$(g,k)\varphi\coloneqq k\circ\varphi\circ g^{-1}.$ (2.10)

######  Example 2.2.

We illustrate the notion of tree composition with a very important example,
that will be used in Section 5 to parametrize the conjugacy classes of
$\mbox{\rm Aut}(\mathcal{T})$; see also [18, Section 9.3] for a similar
construction but with quite different applications. If $g\in\mbox{\rm
Aut}(\mathcal{T})$, $u,v\in\mathcal{T}$, $\\{v,g(v),\dotsc,g^{\ell-1}(v)\\}$
is a $g$-orbit at level $k-1$ and $\\{u,g(u),\dotsc,g^{r-1}(u)\\}$ is a
$g$-orbit at level $k$ then we have only two possibilities:

  1. 1.

for all $0\leq j\leq\ell-1$, $0\leq i\leq r-1$, $g^{i}(u)$ is not a child of
$g^{j}(v)$;

  2. 2.

for all $0\leq i\leq r-1$ there exists $0\leq j\leq\ell-1$ such that
$g^{i}(u)$ is a child of $g^{j}(v)$.

Note that, in the second case, $j$ is unique but a $j$ may have more than one
child in the orbit of $u$ because $r$ may be greater than $\ell$: just
consider the case $\ell=1$, that is $g$ fixes $v$ and it is transitive on the
children of $v$. A more elaborated example is the so called adding machine [5,
Exercise 6.59], which yields an automorphism of the $q$-ary tree which is
transitive at each level. Now to each $g\in\mbox{\rm Aut}(\mathcal{T})$ we
associate a tree composition
$\varphi^{g}\in\mathsf{C}\left(\mathcal{T},\mathcal{P}^{g}\right)$ in the
following way. The vertices of $\mathcal{P}^{g}$ at level $k$,
$k=1,2,\dotsc,h$, are the $g$-orbits of the elements of $\mathcal{T}$ at level
$k$. Two vertices $x,y\in\mathcal{P}^{g}$, $x$ at level $k-1$ and $y$ at level
$k$, are joined if the $g$-orbit corresponding to $y$ is made up of children
of the vertices in the $g$-orbit corresponding to $x$ (cf, 2. above);
$\mathcal{P}^{g}$ is a tree because every vertex as exactly one parent.
Finally, for all $u\in\mathcal{T}$ we set

$\varphi^{g}(u)\coloneqq\text{ the }g\text{-orbit of }u.$ (2.11)

Clearly, $\varphi^{g}$ is a surjective rooted trees homomorphism and
$(\varphi^{g})_{u}$ is surjective for every $u\in\mathcal{T}$ which is
internal. Moreover, if $u,v\in\mathcal{T}$, $u\neq v$, are internal and
$\varphi^{g}(u)=\varphi^{g}(v)\eqqcolon x$ then there exists a positive
integer $k$ such that:

$(\varphi^{g})_{u}=(\varphi^{g})_{v}\circ(g^{k})_{u}.$ (2.12)

Indeed, $u$ and $v$ belong to the same $g$-orbit (corresponding to $x$) so
that then there exists $k$ such that $v=g^{k}(u)$. Therefore $(g^{k})_{u}$ is
an isomorphism form $\mathcal{T}_{u}$ and $\mathcal{T}_{v}$. Moreover, if
$u^{\prime}\in\mathcal{T}_{u}$ and
$\varphi^{g}(u^{\prime})=x^{\prime}\in\left(\mathcal{P}^{g}\right)_{x}$ then
$\varphi^{g}(g^{k}(u^{\prime}))=x^{\prime}$ because $x^{\prime}$ corresponds
to the $g$-orbit of $u^{\prime}$ which clearly contains also
$g^{k}(u^{\prime})$. Then we have
$\varphi^{g}(g^{k}(u^{\prime}))=\varphi^{g}(u^{\prime})$ and this proves
(2.12); in particular the regularity condition in Definition 2.1.2 is verified
and $\varphi^{g}$ is indeed a tree composition.

######  Remark 2.3.

If $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{P},\mathcal{S})$ then not necessarily also
$\psi\circ\varphi\colon\mathcal{T}\rightarrow\mathcal{S}$ is a tree
composition. Indeed, suppose that $H(\mathcal{T})=2$,
$V_{\mathcal{T}}=\\{u,v\\}$, $V_{\mathcal{P}}=\\{x,y\\}$,
$V_{\mathcal{S}}=\\{a\\}$, $u$ has two children, while each of the vertices
$v,x,y,a$ has just one child. Set $\varphi(u)=x,\varphi(v)=y$ and
$\alpha(x)=\alpha(y)=a$, and the children are sent accordingly. Then $\varphi$
and $\alpha$ are tree compositions but $\alpha\circ\varphi$ is not a tree
composition because $\alpha\circ\varphi(u)=\alpha\circ\varphi(v)$ but
$\mathcal{T}_{u}$ and $\mathcal{T}_{v}$ are not isomorphic.

######  Definition 2.4.

  1. 1.

If $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$,
$\psi\in\mathsf{C}(\mathcal{P},\mathcal{S})$ and also
$\psi\circ\varphi\colon\mathcal{T}\rightarrow\mathcal{S}$ is a tree
composition then we say that $\psi\circ\varphi$ is coarser than $\varphi$, or
that $\varphi$ is finer than $\psi\circ\varphi$, equivalently that $\varphi$
is a refinement of $\psi\circ\varphi$.

  2. 2.

If $\varphi_{j}\in\mathsf{C}(\mathcal{T}_{j},\mathcal{P}_{j})$, $j=1,2$, are
two tree compositions an equivalence between them is given by a couple of
rooted trees isomorphisms
$\tau\colon\mathcal{T}_{1}\rightarrow\mathcal{T}_{2}$,
$\omega\colon\mathcal{P}_{1}\rightarrow\mathcal{P}_{2}$ such that
$\omega\circ\varphi_{1}=\varphi_{2}\circ\tau$. If
$\mathcal{P}_{1}=\mathcal{P}_{2}\eqqcolon\mathcal{P}$ and $\omega=\mbox{\rm
id}_{\mathcal{P}}$ we say that $\varphi_{1}$ and $\varphi_{2}$ are strictly
equivalent. If $\mathcal{T}_{1}=\mathcal{T}_{2}\eqqcolon\mathcal{T}$ and
$\alpha=\mbox{\rm id}_{\mathcal{T}}$ we say that $\varphi_{1}$ and
$\varphi_{2}$ are isomorphic.

Definition 2.4.2 may be illustrated by means of the following commutative
diagrams:

$\textstyle{\mathcal{T}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{1}}$$\scriptstyle{\tau}$$\textstyle{\mathcal{P}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\omega}$$\textstyle{\mathcal{T}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{1}}$$\scriptstyle{\tau}$$\textstyle{\mathcal{P}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\omega}$$\textstyle{\mathcal{T}_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{2}}$
equivalence
---
$\textstyle{\mathcal{P}_{2}}$$\textstyle{\mathcal{T}_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{2}}$
stict equivalence
---
$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{1}}$$\scriptstyle{\varphi_{2}}$
isomorphism
---
$\textstyle{\mathcal{P}_{2}}$ (2.13)

Clearly both strict equivalence and isomorphism imply equivalence. Moreover,
the regularity condition in Definition 2.1 is a strict equivalence: if
$x\in\mathcal{P}$ is internal, then all the tree compositions
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{x}$,
$u\in\varphi^{-1}(x)$, are strictly equivalent and $\mathcal{P}_{x}$
determines a precise way to “decompose” the subtrees that map to it.

######  Remark 2.5.

The distinction between equivalence, strict equivalence and isomorphism is a
key point of the theory of tree compositions. Just consider the following
particular case: the orbits of $\mbox{\rm Aut}(\mathcal{T})\times\mbox{\rm
Aut}(\mathcal{P})$ on $\mathsf{C}(\mathcal{T},\mathcal{P})$ with respect to
the action (2.10) coincide with the equivalence classes of
$\mathcal{P}$-compositions of $\mathcal{T}$; the orbits of $\mbox{\rm
Aut}(\mathcal{T})$ coincide with the strict equivalence classes; the obits of
$\mbox{\rm Aut}(\mathcal{P})$ coincide with the isomorphism classes. See also
Example 2.7 and Remark 4.6. Finally, note that the strict equivalence class of
the identity composition $\mbox{\rm id}_{\mathcal{T}}$ is made up of all
$g\colon\mathcal{T}\rightarrow\mathcal{T}$, $g\in\mbox{\rm Aut}(\mathcal{T})$.

######  Remark 2.6.

The fact that the equivalence of tree compositions is transitive is obvious,
but we state it explicitly for future reference, together with some similar
facts. Suppose that $\varphi_{1},\varphi_{2}$ are equivalent as in (2.13). If
$\varphi_{3}\in\mathsf{C}(\mathcal{T}_{3},\mathcal{P}_{3})$ is equivalent to
$\varphi_{2}$ then also $\varphi_{1}$ and $\varphi_{3}$ are equivalent. If
$\alpha\in\mathsf{C}(\mathcal{P}_{2},\mathcal{Q})$ and
$\alpha\circ\varphi_{2}\colon\mathcal{T}_{2}\rightarrow\mathcal{Q}$ is a tree
composition then also
$\alpha\circ\omega\circ\varphi_{1}\colon\mathcal{T}_{1}\rightarrow\mathcal{Q}$
is a tree composition. Another case: if $\varphi^{\prime}_{j}$ is strictly
equivalent to $\varphi_{j}$ , $j=1,2$, then $\varphi_{1}^{\prime}$ and
$\varphi_{2}^{\prime}$ are equivalent. Finally, note that if
$\beta\in\mbox{\rm Aut}(\mathcal{P}_{1})$ then $\varphi_{1}$ and
$\beta\circ\varphi_{1}$ are isomorphic.

Now we examine the notion of tree composition in the cases $H(\mathcal{T})=1$
and $H(\mathcal{T})=2$. We begin by recalling some basic definitions and
notions that will be used throughout the paper. If $n$ is a positive integer,
a numerical composition of $n$ into $k$-parts is a $k$-tuple of positive
integers $(a_{1},a_{2},\dotsc,a_{k})$ such that $a_{1}+a_{2}+\dotsc+a_{k}=n$;
a numerical partition of $n$ into $k$ parts is a $k$-tuple of positive
integers $(\lambda_{1},\lambda_{2},\dotsc,\lambda_{k})$ such that
$\lambda_{1}+\lambda_{2}+\dotsc+\lambda_{k}=n$ but also
$\lambda_{1}\geq\lambda_{2}\geq\dotsb\geq\lambda_{k}$; see [28, Chapter 1]).
The lenght of $\lambda$ is the number $k$ of its parts and it will be denoted
by $\ell(\lambda)\coloneqq k$. Moreover,
$\lvert\lambda\rvert\coloneqq\lambda_{1}+\lambda_{2}+\dotsb+\lambda_{k}$
denotes the sum of its parts. That is,

$\lambda\text{ is a partition of }\lvert\lambda\rvert\text{ into
}\ell(\lambda)\text{ parts.}$ (2.14)

If $Y$ is a finite set, we denote by $\mbox{\rm Sym}(Y)$ the group of all
permutations of $Y$; cf. [18, p. 4], [20, p. 31].

######  Example 2.7.

Suppose that $H(\mathcal{T})=1$, identify $\mathcal{T}$ with $V\coloneqq
V_{\mathcal{T}}$ and $\mathcal{P}$ with $X\coloneqq V_{\mathcal{P}}$. Then a
$\mathcal{P}$-composition of $\mathcal{T}$ is just a surjective map
$\varphi\colon V\rightarrow X$. It determines a partition of $V$ into $\lvert
X\rvert$ parts:

$V=\bigsqcup\limits_{x\in X}\varphi^{-1}(x).$ (2.15)

But note that the elements of $X$ are distinguishable so (2.15) is a set
composition (=an ordered partition: [28, Section 2.2]), that is if the
elements of $X$ are linearly ordered, say $X=\\{x_{1},x_{2},\dotsc,x_{k}\\}$,
then we have an ordered sequence of non empty, pairwise disjoint subsets of
$V$:

$\left(\varphi^{-1}(x_{1}),\varphi^{-1}(x_{2}),\dotsc,\varphi^{-1}(x_{k})\right)$
(2.16)

whose union is the whole $V$. See entry 3 of the Twelvefold way in [29,
Section 1.4] and [28, Sections 1.4]. If we set
$a_{k}=\left\lvert\varphi^{-1}(x_{k})\right\rvert$ then the numerical
composition $(a_{1},a_{2},\dotsc,a_{k})$ is the type of the set composition
(2.16). In most cases, we will avoid the numbering in (2.16) and we will use
(2.15) to indicate a set composition. Moreover, in our terminology, another
composition $\varphi^{\prime}\colon V\rightarrow X^{\prime}$ of $V$ is
equivalent to $\varphi$ if and only if $\lvert X\rvert=\lvert
X^{\prime}\rvert$ and there is a bijection $\beta\colon X\rightarrow
X^{\prime}$ such that
$\lvert\varphi^{-1}(x)\rvert=\lvert\varphi^{-1}(\beta(x))\rvert$, for all
$x\in X$; equivalently if and only if there exists a permutation $\pi$ of $V$
such that

$\left\\{\varphi^{\prime-1}(x^{\prime})\colon x^{\prime}\in
X^{\prime}\right\\}=\left\\{\pi\left(\varphi^{-1}(x)\right)\colon x\in
X\right\\}.$

We define the quotient  of $\varphi:V\rightarrow X$ by taking a singleton
$\\{a\\}$ and setting $\alpha:X\rightarrow\\{a\\}$, that is $\alpha(x)=a$ for
all $x\in X$. This a trivial case of a more general construction in Section 3.

$\emptyset$${\scriptstyle\dotsc}$3015${\scriptstyle\varphi^{-1}(x)}$${\scriptstyle\dotsc}$${\scriptstyle\dotsc}$$V$

$\emptyset$${\scriptstyle x}$${\scriptstyle\dotsc}$$X$

$\emptyset$${\scriptstyle a}$

Denote by $\mathsf{C}(V,X)$ the set of all surjective maps $\varphi\colon
V\rightarrow X$ and consider the natural action of $\mbox{\rm
Sym}(V)\times\mbox{\rm Sym}(X)$ on $\mathsf{C}(V,X)$ which is a particular
case of (2.10): if $(\pi,\beta)\in\mbox{\rm Sym}(V)\times\mbox{\rm Sym}(X)$
and $\varphi\in\mathsf{C}(V,X)$ we set

$(\pi,\beta)\varphi\coloneqq\beta\circ\varphi\circ\pi^{-1};$ (2.17)

see [2, Chapter 1, Section 2]. Then, as a particular case of Remark 2.5, we
get

  * •

the orbits of $\mbox{\rm Sym}(V)$ coincide with the strict equivalence classes
and their set may be parametrized by the numerical compositions of $\lvert
V\rvert$ into $\lvert X\rvert$ parts;

  * •

the orbits of $\mbox{\rm Sym}(X)$ coincide with the isomorphism classes and
also with the (unordered!) partitions of $V$ into $\lvert X\rvert$ parts;

  * •

the orbits of the whole $\mbox{\rm Sym}(V)\times\mbox{\rm Sym}(X)$ are the
equivalence classes and they may be parametrized by the numerical partitions
of $\lvert V\rvert$ into $\lvert X\rvert$ parts.

For instance, suppose that $\varphi\in\mathcal{C}(V,X)$ and that
$x_{1},x_{2},\dotsc,x_{k}$ are the elements of $X$ numbered in such a way that

$\left\lvert\varphi^{-1}(x_{1})\right\rvert\geq\left\lvert\varphi^{-1}(x_{2})\right\rvert\geq\dotsb\geq\left\lvert\varphi^{-1}(x_{k})\right\rvert.$

Then we can define
$\lambda_{i}\coloneqq\left\lvert\varphi^{-1}(x_{i})\right\rvert$ and
$\lambda=(\lambda_{1},\lambda_{2},\dotsc,\lambda_{k})$ is the numerical
partition of $n\coloneqq\lvert V\rvert$ associated to the $\left(\mbox{\rm
Sym}(V)\times\mbox{\rm Sym}(X)\right)$-orbit of $\varphi$. We also say that

$V=\\{\varphi^{-1}(x)\colon x\in X\\}$ (2.18)

is a partition of $V$ of type $\lambda$ and (2.18) will be the standard
notation to indicate an unordered partition of a set.

######  Example 2.8.

Suppose that $H(\mathcal{T})=2$ and, for the sake of simplicity, assume that
$W_{\mathcal{T}}=\emptyset$. Then

$\mathcal{T}=\\{\emptyset\\}\sqcup V_{\mathcal{T}}\sqcup\left[\bigsqcup_{u\in
V_{\mathcal{T}}}\left(\\{u\\}\times\widetilde{\mathcal{T}}_{u}\right)\right],$
(2.19)

and

$\mathcal{P}=\\{\emptyset\\}\sqcup V_{\mathcal{P}}\sqcup\left[\bigsqcup_{x\in
V_{\mathcal{P}}}\left(\\{x\\}\times\widetilde{\mathcal{P}}_{x}\right)\right];$
(2.20)

cf. (2.3). Now $\widetilde{\mathcal{T}}_{u}$ (respectively
$\widetilde{\mathcal{P}}_{x}$) is the set of leaves which are children of $u$
(respectively of $x$). A tree composition
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ is a surjective map such that
if $u,v\in V_{\mathcal{T}}$ and $\varphi(u)=\varphi(v)\eqqcolon x\in
V_{\mathcal{P}}$ then
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{x}$ and
$\varphi_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{P}_{x}$ are strictly
equivalent set compositions (cf. Example 2.7). We want to relate this
construction to the parametrization in [10, Corollary 2.6.2] of the
irreducible representations of the wreath prduct of two symmetric groups. We
define a coarser tree composition of $\mathcal{T}$ in the following way. We
introduce an equivalence relation in $V_{\mathcal{P}}$: for $x,x^{\prime}\in
V_{\mathcal{P}}$ we set $x\sim x^{\prime}$ if for all $u,v\in V_{\mathcal{T}}$
such that $\varphi(u)=x,\varphi(v)=x^{\prime}$ we have that
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{x}$ and
$\varphi_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{P}_{x^{\prime}}$ are
equivalent set compositions. Then we set $A=V_{\mathcal{P}}/\sim$ and denote
by $\pi\colon V_{\mathcal{P}}\rightarrow A$ the quotient map. If we suppose
that, for every $a\in A$, $B_{a}$ is a set of cardinality $1$ we may define
another tree by setting

$\mathcal{Q}=\\{\emptyset\\}\sqcup A\sqcup\left[\bigsqcup_{a\in
A}\left(\\{a\\}\times B_{a}\right)\right]$

and then a map $\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$ where, for each
$x\in V_{\mathcal{P}}$, $\alpha(x)=\pi(x)$ and $\alpha|_{\mathcal{P}_{x}}$
sends the whole $\widetilde{\mathcal{P}}_{x}$ to the singleton $B_{\pi(x)}$.
It is a tree composition because if $\pi(x)=\pi(x^{\prime})$ then
$\lvert\widetilde{\mathcal{P}}_{x}\rvert=\lvert\widetilde{\mathcal{P}}_{x^{\prime}}\rvert$.
Also the map $\alpha\circ\varphi\colon\mathcal{T}\rightarrow\mathcal{Q}$ is a
tree composition, because $u,v\in V_{\mathcal{T}}$ and
$\alpha(\varphi(u))=\alpha(\varphi(v))$ imply that $\varphi(u)\sim\varphi(v)$
and therefore
$\lvert\widetilde{\mathcal{T}}_{u}\rvert=\lvert\widetilde{\mathcal{T}}_{v}\rvert$.
Moreover, it has has the following property: if $u,v\in V$, $u\neq v$, then
the set compositions
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ and
$\varphi_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{P}_{\varphi(v)}$ are
equivalent if and only if $\alpha(\varphi(u))=\alpha(\varphi(v))$. Now
assuming that $\mathcal{T}$ is spherically homogeneous we may establish a
correspondence between the tree compositions in this example and the
parametrization of the irreducible representation of the wreath product of two
symmetric group in [10, Corollary 2.6.2]. It is given by:

  * •

the numerical composition $\nu=(n_{\mu})_{\mu\vdash v}$ in [10, Corollary
2.6.2] corresponds to the type of the set composition
$V_{\mathcal{T}}=\bigsqcup\limits_{a\in
A}\left(\alpha\circ\varphi\right)^{-1}(a)$;

  * •

for a part
$\left\lvert\left(\alpha\circ\varphi\right)^{-1}(a)\right\rvert\eqqcolon
n_{\mu}$, the numerical partition $\mu$ in [10, Corollary 2.6.2] corresponds
to the common type of the set partitions
$\widetilde{\mathcal{T}}_{v}=\\{\varphi^{-1}(z)\colon
z\in\widetilde{\mathcal{P}}_{x}\\}$, $x\in\alpha^{-1}(a)$,
$v\in\left(\alpha\circ\varphi\right)^{-1}(a)$;

  * •

the numerical partition $\lambda_{n_{\mu}}\vdash n_{\mu}$ in [10, Corollary
2.6.2] corresponds to the type of the set partition
$\left(\alpha\circ\varphi\right)^{-1}(a)=\\{\varphi^{-1}(x)\colon
x\in\alpha^{-1}(a)\\}$.

Now we illustrate the situation by means of three pictures, but we use
$\lambda^{(\mu)}$ to denote $\lambda_{n_{\mu}}$ of [10, Corollary 2.6.2].

  * •

In $\mathcal{T}$ the bigger ellipses represent the parts
$n_{\mu},n_{\mu^{\prime}},\dotsc,n_{\mu^{\prime\prime}}$ of the set
composition of $V_{\mathcal{T}}$ of type $\nu$; each part of this set
composition is in turn partitioned and the type of the relative partition is
$\lambda^{(\mu)},\lambda^{(\mu^{\prime})},\dotsc,\lambda^{(\mu)^{\prime\prime}}$.
The smaller ellipses represents the type
$\mu,\mu^{\prime},\dotsc,\mu^{\prime\prime}$ of the partitions of the vertices
at the second level, and the partition of the children of each vertex in the
first bigger ellipse is of type $\mu$, of the children of each vertex in the
second bigger ellipse is of type $\mu^{\prime},\dotsc,$ of the children of
each vertex in the last bigger ellipse is of type $\mu^{\prime\prime}$.

  * •

In $\mathcal{P}$ the first bigger ellipse contains the
$\ell\left(\lambda^{(\mu)}\right)$ vertices of $V_{\mathcal{P}}$ corresponding
to the parts of the partition of type $\lambda^{\mu}$ of the vertices in the
first bigger ellipse in $\mathcal{T}$. Similarly for the other bigger
ellipses. Then the first smaller ellipse contains $\ell(\mu)$ vertices
corresponding to the parts of the decomposition of type $\mu$ in the first
smaller ellipse of $\mathcal{T}$; similarly for the other smaller ellipses.

  * •

The vertices of the tree $\mathcal{Q}$ are labeled with the numerical
partitions
$\lambda^{(\mu)},\lambda^{(\mu^{\prime})},\dotsc,\lambda^{(\mu^{\prime\prime})}$
(first level) and $\mu,\mu^{\prime},\dotsc,\mu^{\prime\prime}$ (second level);
it is the quotient that will be introduced in Section 3, but we anticipate it
for future reference.

${\scriptstyle\emptyset}$$\mathcal{T}$

4522${\scriptstyle\lambda^{(\mu)}\vdash n_{\mu}}$

4522${\scriptstyle\lambda^{(\mu^{\prime})}\vdash n_{\mu^{\prime}}}$

4522${\scriptstyle\lambda^{(\mu^{\prime\prime})}\vdash
n_{\mu^{\prime\prime}}}$

2211${\scriptstyle\mu}$

2211${\scriptstyle\mu}$

2211${\scriptstyle\mu^{\prime}}$

2211${\scriptstyle\mu^{\prime}}$

2211${\scriptstyle\mu^{\prime\prime}}$

2211${\scriptstyle\mu^{\prime\prime}}$

${\scriptstyle\emptyset}$$\mathcal{P}$

4522${\scriptstyle\ell(\lambda^{(\mu)})}$

4522${\scriptstyle\ell(\lambda^{(\mu^{\prime})})}$

4522${\scriptstyle\ell(\lambda^{(\mu^{\prime\prime})})}$

2814${\scriptstyle\ell(\mu)}$

2814${\scriptstyle\ell(\mu)}$

2814${\scriptstyle\ell(\mu^{\prime})}$

2814${\scriptstyle\ell(\mu^{\prime})}$

2814${\scriptstyle\ell(\mu^{\prime\prime})}$

2814${\scriptstyle\ell(\mu^{\prime\prime})}$

${\scriptstyle\emptyset}$$\mathcal{Q}$

${\scriptstyle\lambda^{(\mu)}}$${\scriptstyle\mu}$

${\scriptstyle\lambda^{(\mu^{\prime})}}$${\scriptstyle\mu^{\prime}}$

${\scriptstyle\lambda^{(\mu^{\prime\prime})}}$${\scriptstyle\mu^{\prime\prime}}$

######  Example 2.9.

Suppose that $\mathcal{T}$ is a spherically homogeneous rooted tree of
branching type ${\bf r}=(r_{1},r_{2},\ldots,r_{h})$, choose integers $1\leq
s_{k}\leq r_{k}$, $k=1,2,\dotsc,h$, with $s_{k}<r_{k}$ for at least one $k$,
and set ${\bf s}=(s_{1},s_{2},\ldots,s_{h})$. Define $\mathsf{V}({\bf r},{\bf
s})$ as the variety of all subtrees $\mathcal{S}\subseteq\mathcal{T}$ which
are spherically homogeneous of branching type ${\bf s}$. In [8] and [10,
Section 3.2.6] is analyzed the permutation representation of $\mbox{\rm
Aut}(\mathcal{T})$ on $\mathsf{V}({\bf r},{\bf s})$, as an application of a
more general construction, the generalized Johnson scheme. In particular, this
permutation representation decomposes without multiplicity (i.e. gives rise to
a Gelfand pair) and it is a rooted tree analog of the permutation
representation of $S_{n}$ on $S_{n}/(S_{n-m}\times S_{m})$, also called
Johnson scheme; [7, Chapter 6]. Now we want to describe the trees in
$\mathsf{V}({\bf r},{\bf s})$ by means of trees compositions. First of all,
note that a tree $\mathcal{S}\in\mathsf{V}({\bf r},{\bf s})$ has the following
recursive description, where $\text{\rm Ch}_{\mathcal{T}}(u)$ respectively
$\text{\rm Ch}_{\mathcal{S}}(u)$ are the children of $u$ in $\mathcal{T}$,
respectively in $\mathcal{S}$ (if $u\in\mathcal{S}$).

  * •

$\emptyset\in\mathcal{S}$ and if $u$ is a vertex of $\mathcal{S}$ at level
$k-1$ then $\text{\rm Ch}_{\mathcal{S}}(u)$ is a subset of $\text{\rm
Ch}_{\mathcal{T}}(u)$ of cardinality $r_{k}$, $k=1,2,\dotsc,h$.

Then we define the rooted tree $\mathcal{P}$ of height $h$ inductively as
follows:

  * •

denote the root by $b_{0}$; for $k=1,2,\dotsc,h$, if $s_{k}<r_{k}$ then
$\text{\rm Ch}_{\mathcal{P}}(b_{k-1})=\\{a_{k},b_{k}\\}$ and
$\mathcal{P}_{a_{k}}$ is a path of lenght $h-k$; if $s_{k}=r_{k}$ then
$\text{\rm Ch}_{\mathcal{P}}(b_{k-1})=\\{b_{k}\\}$.

Clearly, the structure of $\mathcal{P}$ does not depend on ${\bf s}$: we have
just to draw $\mathcal{P}$ in the general case and then delete the vertices
$a_{k}$ such that $s_{k}=r_{k}$. Finally, to each
$\mathcal{S}\in\mathsf{V}({\bf r},{\bf s})$ we associate the tree composition
$\varphi^{\mathcal{S}}\in\mathsf{C}(\mathcal{T},\mathcal{P})$ defined
inductively in the following way:

  * •

if $u$ is a vertex of $\mathcal{S}$ at level $k-1$ then we set
$\varphi^{\mathcal{S}}\left(\text{\rm Ch}_{\mathcal{S}}(u)\right)\coloneqq
b_{k}$, while for all $v\in\text{\rm Ch}_{\mathcal{T}}(u)\setminus\text{\rm
Ch}_{\mathcal{S}}(u)$ (if it is not empty) we set
$\varphi^{\mathcal{S}}\left(T_{v}\right)\coloneqq\mathcal{P}_{a_{k}}$,
$k=1,2,\dotsc,h$.

In the following picture, ${\bf r}=(3,3,2)$, ${\bf s}=(2,2,1)$ and the subtree
$\mathcal{S}$ and its image in $\mathcal{P}$ are indicated by bolder lines and
vertices.

${\scriptstyle\emptyset}$${\scriptstyle\mathcal{T}}$

${\scriptstyle\emptyset}$${\scriptstyle\mathcal{P}}$

${\scriptstyle a_{1}}$${\scriptstyle b_{1}}$

${\scriptstyle a_{2}}$${\scriptstyle b_{2}}$

${\scriptstyle a_{3}}$${\scriptstyle b_{3}}$

In other words, $\varphi^{\mathcal{S}}(v)$ is a $b$-vertex if
$v\in\mathcal{S}$, otherwise it is a descendant of a suitable $a$-vertex. We
set $\Omega({\bf r},{\bf
s})\coloneqq\\{\varphi^{\mathcal{S}}\colon\mathcal{S}\in\mathsf{V}({\bf
r},{\bf s})\\}$ and clearly the map

$\mathsf{V}({\bf r},{\bf
s})\\}\ni\mathcal{S}\longmapsto\varphi^{\mathcal{S}}\in\Omega({\bf r},{\bf
s})$

is a bijection. Moreover, for all $g\in\mbox{\rm Aut}(\mathcal{T})$ and
$\mathcal{S}\in\mathsf{V}({\bf r},{\bf s})$, we have (cf. (2.10))

$\varphi^{g\mathcal{S}}=\varphi^{\mathcal{S}}\circ g^{-1}.$ (2.21)

Indeed, for all $u\in\mathcal{T}$

$\left(\varphi^{\mathcal{S}}\circ g^{-1}\right)(u)\text{ is a }b\text{-vertex
}\Longleftrightarrow g^{-1}(u)\in\mathcal{S}\;\Longleftrightarrow u\in
g\mathcal{S}\;\Longleftrightarrow\;\varphi^{g\mathcal{S}}(u)\text{ is a
}b\text{-vertex}.$

Therefore the bijection $\mathcal{S}\mapsto\varphi^{\mathcal{S}}$ is
equivariant, $\mathsf{V}({\bf r},{\bf s})$ and $\Omega({\bf r},{\bf s})$ are
isomorphic as homogeneous $\mbox{\rm Aut}(\mathcal{T})$-spaces and the
respective permutation representations are equivalent. Finally, from (2.21) we
deduce also that $\Omega({\bf r},{\bf s})$ is a strict equivalence class of
tree compositions.

######  Example 2.10.

Now suppose again that $\mathcal{T}$ is a spherically homogeneous rooted tree
of branching type ${\bf r}=(r_{1},r_{2},\ldots,r_{h})$ and also that

${\bf S}=\begin{bmatrix}s_{1}^{1}&s_{1}^{2}&\dotsb&s_{1}^{l}\\\
s_{2}^{1}&s_{2}^{2}&\dotsb&s_{2}^{l}\\\ \vdots&\vdots&&\vdots\\\
s_{h}^{1}&s_{h}^{2}&\dotsb&s_{h}^{l}\\\ \end{bmatrix}$

is an $h\times l$ matrix of positive integers such that $1\leq s_{k}^{l}\leq
s_{k}^{l-1}\leq\dotsb\leq s_{k}^{1}\leq s_{k}^{0}\coloneqq r_{k}$ for
$k=1,2,\dotsc,h$; we assume that for each $0\leq j\leq l-1$ there exists at
least one $k$ such that $s_{k}^{j+1}<s_{k}^{j}$. Then a flag $\mathcal{F}$ of
subtrees of $\mathcal{T}$ of type ${\bf S}$ is a sequence of nested subtrees

$\mathcal{F}\colon\;\mathcal{S}^{l+1}\coloneqq\\{\emptyset\\}\subseteq\mathcal{S}^{l}\subseteq\mathcal{S}^{l-1}\subseteq\dotsb\subseteq\mathcal{S}^{1}\subseteq\mathcal{S}^{0}\coloneqq\mathcal{T}$
(2.22)

such that $\mathcal{S}^{j}$ is spherically homogeneous of branching type
$\mathcal{\bf s}^{j}\coloneqq(s_{1}^{j},s_{2}^{j}\dotsc,s_{h}^{j})$,
$j=0,1,\dotsc,l-1,l$ (and $\mathcal{S}^{l+1}$ is just the root). We denote by
$\mathsf{V}({\bf r},{\bf S})$ the variety of all flags $\mathcal{F}$ as in
(2.22). The flag $\mathcal{F}$ has the following iterative description:

  * •

$V_{\mathcal{T}}=\bigsqcup\limits_{j=0}^{l}\left(V_{\mathcal{S}^{j}}\setminus
V_{\mathcal{S}^{j+1}}\right)\quad$ and $\quad\lvert
V_{\mathcal{S}^{j}}\rvert=s_{1}^{j}\;$, $j=0,1,\dotsc,l$.

  * •

For $k=2,3\dotsc,h$, if $u\in\mathcal{S}^{j}\setminus\mathcal{S}^{j+1}$ with
$0\leq j\leq l$ and $u$ is at level $k-1$ then

$\text{\rm Ch}_{\mathcal{T}}(u)=\text{\rm
Ch}_{\mathcal{S}^{j}}(u)\bigsqcup\left[\bigsqcup\limits_{i=0}^{j-1}\left(\text{\rm
Ch}_{\mathcal{S}^{i}}(u)\setminus\text{\rm
Ch}_{\mathcal{S}^{i+1}}(u)\right)\right]$

and $\lvert\text{\rm Ch}_{\mathcal{S}^{i}}(u)\rvert=s_{k}^{i}$,
$i=0,1,\dotsc,j$.

After that we define a rooted tree $\mathcal{P}$ of height $h$ as follows. The
vertices of $\mathcal{P}\setminus\\{\emptyset\\}$ are labeled with the
integers $0,1,\dotsc,l$, distinct siblings have different labels and the label
of $x\in\mathcal{P}$ is denoted by $\ell(x)$. Then inductively

  * •

$V_{\mathcal{P}}$ has $l+1$ vertices, labeled $0,1,\dotsc,l$;

  * •

for $k=2,3,\dotsc,h$, if we have constructed $\mathcal{P}$ up to level $k-1$,
$x$ is a vertices at level $k-1$ and $\ell(x)=j$ then $x$ has $j+1$ children,
labeled $0,1,2,\dotsc,j$;

  * •

if $s_{k}^{i-1}=s_{k}^{i}$, $1\leq k\leq h$, $1\leq i\leq l$, then we delete
all the subtrees $\mathcal{P}_{x}$ such that $x$ is at level $k$ and
$\ell(x)=i-1$.

The following is the tree $\mathcal{P}$ for $h=3$ and $l=2$.

\begin{picture}(400.0,70.0)\par\par\put(200.0,60.0){\circle*{4.0}}
\put(198.0,65.0){${\scriptstyle\emptyset}$}
\put(188.0,65.0){${\scriptstyle\mathcal{P}}$}
\par\put(200.0,60.0){\line(2,-1){120.0}}
\par\put(200.0,60.0){\line(-2,-1){120.0}} \put(200.0,60.0){\line(-1,-1){60.0}}
\par\put(160.0,40.0){\circle*{2.0}} \put(153.0,40.0){${\scriptstyle 0}$}
\put(180.0,40.0){\circle*{2.0}} \put(183.0,37.0){${\scriptstyle 1}$}
\put(180.0,40.0){\line(-2,-1){80.0}} \put(240.0,40.0){\circle*{2.0}}
\put(243.0,40.0){${\scriptstyle 2}$} \put(240.0,40.0){\line(-2,-1){80.0}}
\put(240.0,40.0){\line(-1,-1){40.0}} \put(120.0,20.0){\circle*{2.0}}
\put(113.0,20.0){${\scriptstyle 0}$} \put(140.0,20.0){\circle*{2.0}}
\put(135.0,22.0){${\scriptstyle 0}$} \put(160.0,20.0){\circle*{2.0}}
\put(163.0,17.0){${\scriptstyle 1}$} \put(160.0,20.0){\line(-2,-1){40.0}}
\put(200.0,20.0){\circle*{2.0}} \put(193.0,20.0){${\scriptstyle 0}$}
\put(220.0,20.0){\circle*{2.0}} \put(223.0,17.0){${\scriptstyle 1}$}
\put(220.0,20.0){\line(-2,-1){40.0}} \put(280.0,20.0){\circle*{2.0}}
\put(283.0,20.0){${\scriptstyle 2}$} \put(280.0,20.0){\line(-2,-1){40.0}}
\put(280.0,20.0){\line(-1,-1){20.0}} \par\put(80.0,0.0){\circle*{2.0}}
\put(73.0,0.0){${\scriptstyle 0}$} \put(100.0,0.0){\circle*{2.0}}
\put(93.0,0.0){${\scriptstyle 0}$} \put(120.0,0.0){\circle*{2.0}}
\put(113.0,0.0){${\scriptstyle 0}$} \put(140.0,0.0){\circle*{2.0}}
\put(133.0,0.0){${\scriptstyle 1}$} \put(160.0,0.0){\circle*{2.0}}
\put(153.0,0.0){${\scriptstyle 0}$} \put(180.0,0.0){\circle*{2.0}}
\put(173.0,0.0){${\scriptstyle 1}$} \put(200.0,0.0){\circle*{2.0}}
\put(193.0,0.0){${\scriptstyle 2}$} \put(240.0,0.0){\circle*{2.0}}
\put(233.0,0.0){${\scriptstyle 0}$} \put(260.0,0.0){\circle*{2.0}}
\put(253.0,0.0){${\scriptstyle 1}$} \put(320.0,0.0){\circle*{2.0}}
\put(323.0,0.0){${\scriptstyle 2}$} \par\end{picture}

${\scriptstyle\emptyset}$${\scriptstyle\mathcal{P}}$

${\scriptstyle 0}$${\scriptstyle 1}$${\scriptstyle 2}$${\scriptstyle
0}$${\scriptstyle 0}$${\scriptstyle 1}$${\scriptstyle 0}$${\scriptstyle
1}$${\scriptstyle 2}$

${\scriptstyle 0}$${\scriptstyle 0}$${\scriptstyle 0}$${\scriptstyle
1}$${\scriptstyle 0}$${\scriptstyle 1}$${\scriptstyle 2}$${\scriptstyle
0}$${\scriptstyle 1}$${\scriptstyle 2}$

To each flag $\mathcal{F}$ we associate a tree composition
$\varphi^{\mathcal{F}}\colon\mathcal{T}\rightarrow\mathcal{P}$ defined
recursively

  * •

for $j=0,1,\dotsc,l$, $\varphi^{\mathcal{F}}\left(V_{\mathcal{S}^{j}}\setminus
V_{\mathcal{S}^{j+1}}\right)\coloneqq$ the vertex of $V_{\mathcal{P}}$ with
label $j$;

  * •

for $k=2,3,\dotsc,h$, if we have defined $\varphi^{\mathcal{F}}$ up to level
$k-1$, $u$ is at level $k$ of $\mathcal{T}$, $v$ is the parent of $u$,
$\varphi^{\mathcal{F}}(v)=x$ and
$u\in\mathcal{S}^{j}\setminus\mathcal{S}^{j+1}$ then
$\varphi^{\mathcal{F}}(u)\coloneqq$ the child of $x$ with label $j$.

In other words, starting from the first level, the vertices in
$\mathcal{S}^{j}\setminus\mathcal{S}^{j+1}$ are sent to the vertices of
$\mathcal{P}$ with label $j$. It is easy to check that $\varphi^{\mathcal{F}}$
is a tree composition; if we set $\Omega({\bf r},{\bf
S})\coloneqq\left\\{\varphi^{\mathcal{F}}\colon\mathcal{F}\in\mathsf{V}({\bf
r},{\bf S})\right\\}$ then the map

$\mathsf{V}({\bf r},{\bf
S})\ni\mathcal{F}\longmapsto\varphi^{\mathcal{F}}\in\Omega({\bf r},{\bf S})$

is a bijection. Moreover, for all $g\in\mbox{\rm Aut}(\mathcal{T})$ and
$\mathcal{F}\in\mathsf{V}({\bf r},{\bf S})$, we have

$\varphi^{g\mathcal{F}}=\varphi^{\mathcal{F}}\circ g^{-1}.$ (2.23)

Indeed, for all $u\in\mathcal{T}$,

$\begin{split}\ell\left(\left(\varphi^{\mathcal{F}}\circ
g^{-1}\right)(u)\right)=j\quad&\Longleftrightarrow\quad
g^{-1}(u)\in\mathcal{S}^{j}\setminus\mathcal{S}^{j+1}\quad\Longleftrightarrow\quad
u\in\left(g\mathcal{S}^{j}\right)\setminus\left(g\mathcal{S}^{j+1}\right)\\\
&\Longleftrightarrow\quad\ell\left(\left(\varphi^{g\mathcal{F}}\right)(u)\right)=j\end{split}$

That is, the bijection $\mathcal{F}\mapsto\varphi^{\mathcal{F}}$ is
equivariant, $\mathsf{V}({\bf r},{\bf S})$ and $\Omega({\bf r},{\bf S})$ are
isomorphic as homogeneous $\mbox{\rm Aut}(\mathcal{T})$-spaces and the
respective permutation representations are equivalent. Finally, from (2.23) we
deduce also that $\Omega({\bf r},{\bf S})$ is a strict equivalence class of
tree compositions.

##  3 The quotient of a tree composition

In this section we introduce the fundamental construction of the quotient
partition. A particular case was just sketched in Example 2.8.

######  Theorem 3.1.

If $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ then there exist a tree
$\mathcal{Q}$ and a composition $\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$
(that we call the quotient of $\varphi$) such that

  1. (a)

if $x\in\mathcal{P}$ is internal and $Y$ is the set of all children of $x$
which are leaves then $\alpha_{x}$ sends the whole $Y$ to a singleton
$a\in\mathcal{Q}$, and $a$ is the unique child of $\alpha(x)$ which is a leaf.

  2. (b)

If $a,b\in\mathcal{Q}$ are distinct siblings which are are internal, then for
all pairs of siblings $u,v\in\mathcal{T}$ such that $\alpha(\varphi(u))=a$,
$\alpha(\varphi(v))=b$ the tree compositions
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ and
$\varphi_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{P}_{\varphi(v)}$ are not
equivalent.

  3. (c)

If $u,w\in\mathcal{T}$ are internal and
$\alpha(\varphi(u))=\alpha(\varphi(w))\eqqcolon a$ then there exist tree
isomorphisms $\tau_{w,u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{w}$ and
$\omega_{\varphi(w),\varphi(u)}\colon\mathcal{P}_{\varphi(u)}\rightarrow\mathcal{P}_{\varphi(w)}$
such that the following diagram is commutative:

$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\tau_{w,u}}$$\textstyle{\mathcal{P}_{\varphi(u)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi(u)}}$$\scriptstyle{\omega_{\varphi(w),\varphi(u)}}$$\textstyle{\mathcal{Q}_{a}}$$\textstyle{\mathcal{T}_{w}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{w}}$$\textstyle{\mathcal{P}_{\varphi(w)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi(w)}}$
(3.1)

In particular, the tree compositions
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ and
$\varphi_{w}\colon\mathcal{T}_{w}\rightarrow\mathcal{P}_{\varphi(w)}$ are
equivalent,
$\alpha_{\varphi(u)}\circ\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{Q}_{\alpha(\varphi(u))}$
and
$\alpha_{\varphi(w)}\circ\varphi_{w}\colon\mathcal{T}_{w}\rightarrow\mathcal{Q}_{\alpha(\varphi(w))}$
are strictly equivalent and
$\alpha\circ\varphi\colon\mathcal{T}\rightarrow\mathcal{Q}$ is a tree
composition.

  4. (d)

We may choose the isomorphisms $\tau$’s and $\omega$’s in (3.1), that is one
$\tau_{u,w}$ for all possible couples $u,w$ and one $\omega_{x,y}$ for all
possible couples $x,y$, in such a way that they satisfy the following
properties:

     * •

if $u,w\in\mathcal{T}$ are internal, $\alpha(\varphi(u))=\alpha(\varphi(w))$,
$u^{\prime}$ is a descendant of $u$ which is internal and
$w^{\prime}\coloneqq\tau_{w,u}(u^{\prime})$ then

$\tau_{w^{\prime},u^{\prime}}=\tau_{w,u}\rvert_{\mathcal{T}_{u^{\prime}}}\qquad(\text{\rm
restriction property for the }\tau^{\prime}s).$ (3.2)

     * •

If $a\in\mathcal{Q}$ is internal and $u,t,w\in(\alpha\circ\varphi)^{-1}(a)$
then

$\tau_{w,u}\circ\tau_{u,t}=\tau_{w,t}\quad\text{\rm and
}\quad\tau_{u,w}^{-1}=\tau_{w,u}\quad(\text{\rm composition property for the
}\tau^{\prime}s);$ (3.3)

moreover, $\tau_{u,u}=\mbox{\rm id}_{\mathcal{T}_{u}}$.

     * •

If $u,u^{\prime},w,w^{\prime}\in\mathcal{T}$ are internal then

$\varphi(u^{\prime})=\varphi(u)\;\text{ and
}\;\varphi(w^{\prime})=\varphi(w)\quad\Longrightarrow\quad\omega_{\varphi(w^{\prime}),\varphi(u^{\prime})}=\omega_{\varphi(w),\varphi(u)},$
(3.4)

that is, $\omega_{\varphi(w),\varphi(u)}$ depends only on the $\varphi$-images
of $u$ and $w$.

     * •

If $x,y\in\mathcal{P}$ are internal, $\alpha(x)=\alpha(y)$, $x^{\prime}$ is a
descendant of $x$ which is internal and
$y^{\prime}\coloneqq\omega_{y,x}(x^{\prime})$ then

$\omega_{y^{\prime},x^{\prime}}=\omega_{y,x}\rvert_{\mathcal{P}_{x^{\prime}}}\qquad(\text{\rm
restriction property for the }\omega^{\prime}s).$

     * •

If $a\in\mathcal{Q}$ is internal and $x,y,z\in\alpha^{-1}(a)$ then

$\omega_{z,y}\circ\omega_{y,x}=\omega_{z,x}\quad\text{\rm and
}\quad\omega_{x,y}^{-1}=\omega_{y,x}\quad(\text{\rm composition property for
the }\omega^{\prime}s);$ (3.5)

moreover,

$\omega_{x,x}=\mbox{\rm id}_{\mathcal{P}_{x}}.$ (3.6)

In particular,

$\text{ if }\varphi(u)=\varphi(w)\text{ then }\tau_{u,w}\text{ is a strict
equivalence as in }\eqref{diagTRSuv2}.$ (3.7)

  5. (e)

The quotient is unique up to isomorphisms: if
$\beta\colon\mathcal{P}\rightarrow\mathcal{B}$ is another quotient then there
exists a rooted tree isomorphism
$\gamma\colon\mathcal{Q}\rightarrow\mathcal{B}$ such that the following
diagram is commutative:

$\textstyle{\mathcal{Q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\textstyle{\mathcal{P}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha}$$\scriptstyle{\beta}$$\textstyle{\mathcal{B}}$

###### Proof.

By induction on $h\coloneqq H(\mathcal{T})$. For $h=1$ it is trivial:
condition (a) forces $\lvert V_{\mathcal{Q}}\rvert=1$, $\alpha$ sends the
whole $V_{\mathcal{P}}$ to the unique vertex in $V_{\mathcal{Q}}$ and the
$\tau$’s and the $\omega$’s do not exist; cf Example 2.7. For $h\geq 2$ again
(a) forces $\lvert W_{\mathcal{Q}}\rvert\leq 1$ and $\alpha$ sends the whole
$W_{\mathcal{P}}$ to the unique vertex in $W_{\mathcal{Q}}$ (if
$W_{\mathcal{T}}$ is not empty). Then we consider the set composition

$V_{\mathcal{T}}\setminus W_{\mathcal{T}}=\bigsqcup_{x\in
V_{\mathcal{P}}\setminus W_{\mathcal{P}}}\varphi^{-1}(x)$ (3.8)

and we introduce the following equivalence relation: for $x,x^{\prime}\in
V_{\mathcal{P}}\setminus W_{\mathcal{P}}$ we set $x\sim x^{\prime}$ if

$u,v\in V_{\mathcal{T}},\;\varphi(u)=x\text{ and
}\varphi(v)=x^{\prime}\;\Longrightarrow\;\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{x}\text{
and }\varphi_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{P}_{x^{\prime}}\text{
are equivalent; }$

clearly, by Remark 2.6, it suffices to verify this condition for just one
choice of $u\in\varphi^{-1}(x),v\in\varphi^{-1}(y)$, and $\sim$ is indeed an
equivalence relation. Set $A\coloneqq\left(V_{\mathcal{P}}\setminus
W_{\mathcal{P}}\right)/\sim$ and let $\pi\colon V_{\mathcal{P}}\setminus
W_{\mathcal{P}}\rightarrow A$ be the projection map, so that

$V_{\mathcal{T}}\setminus W_{\mathcal{T}}=\bigsqcup_{a\in
A}(\pi\circ\varphi)^{-1}(a)=\bigsqcup_{a\in
A}\left(\bigsqcup_{x\in\pi^{-1}(a)}\varphi^{-1}(x)\right).$ (3.9)

The first set composition in (3.9) is coarser than (3.8) while the second one
is a more structured form of (3.8).

We begin by defining the $\tau$’s, the $\omega$’s and $\alpha$ at the first
level. First of all, for each $a\in A$ fix an element $x_{a}\in\pi^{-1}(a)$
and then for all $y\in\pi^{-1}(a)$, fix an element $v_{y}\in\varphi^{-1}(y)$.
If we consider the tree compositions
$\varphi_{v_{x_{a}}}\colon\mathcal{T}_{v_{x_{a}}}\rightarrow\mathcal{P}_{\varphi(v_{x_{a}})}$,
$a\in A$, then, by the inductive hypothesis, there exist unique (up to
isomorphisms) tree compositions
$\alpha_{\varphi(v_{x_{a}})}\colon\mathcal{P}_{\varphi(v_{x_{a}})}\rightarrow\mathcal{Q}_{a}$
that satisfy the properties (a) and (b), with maps $\tau$’s and $\omega$’s,
defined within each $\mathcal{T}_{v_{x_{a}}}$ and
$\mathcal{P}_{\varphi(v_{x_{a}})}$, that satisfy the conditions in (c) and (d)
If $y\in\pi^{-1}(a)$ and $u\in\varphi^{-1}(y)$ then, by Definition 2.1.2,
$\varphi_{u}$ and $\varphi_{v_{y}}$ are strictly equivalent, so that we may
fix an isomorphism
$\tau_{v_{y},u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{v_{y}}$ such that

$\varphi_{u}=\varphi_{v_{y}}\circ\tau_{v_{y},u}$ (3.10)

and also set $\tau_{u,v_{y}}\coloneqq\tau_{v_{y},u}^{-1}$ and
$\tau_{v_{y},v_{y}}\coloneqq\mbox{\rm id}_{\mathcal{T}_{v_{y}}}$. Moreover, if
again $y\in\pi^{-1}(a)$, then $\varphi_{v_{y}}$ and $\varphi_{v_{x_{a}}}$ are
equivalent (by the definition of $\sim$) so that there we may fix isomorphisms
$\tau_{v_{y},v_{x_{a}}}\colon\mathcal{T}_{v_{x_{a}}}\rightarrow\mathcal{T}_{v_{y}}$
and $\omega_{y,x_{a}}\colon\mathcal{P}_{x_{a}}\rightarrow\mathcal{P}_{y}$ such
that (cf. (2.13))

$\varphi_{v_{y}}\circ\tau_{v_{y},v_{x_{a}}}=\omega_{y,x_{a}}\circ\varphi_{v_{x_{a}}}.$
(3.11)

We also set $\tau_{v_{x_{a}},v_{y}}\coloneqq\tau_{v_{y},v_{x_{a}}}^{-1}$,
$\omega_{x_{a},y}\coloneqq\omega_{y,x_{a}}^{-1}$ and
$\omega_{x_{a},x_{a}}\coloneqq\mbox{\rm id}_{\mathcal{P}_{x_{a}}}$.

If $u,w\in(\pi\circ\varphi)^{-1}(a)$, $y=\varphi(u)$, $z=\varphi(w)$, then
using the $\tau$’s and the $\omega$’s in (3.10) and (3.11) we set

$\tau_{w,u}\coloneqq\tau_{w,v_{z}}\circ\tau_{v_{z},v_{x_{a}}}\circ\tau_{v_{x_{a}},v_{y}}\circ\tau_{v_{y},u}\quad\text{
and
}\quad\omega_{\varphi(w),\varphi(u)}\coloneqq\omega_{z,x_{a}}\circ\omega_{x_{a},y}.$
(3.12)

See also the following diagram. Note that the triangles express strict
equivalences while the rectangles express equivalences.

$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{w,u}}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\tau_{v_{y},u}}$$\textstyle{\mathcal{T}_{v_{y}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{v_{y},v_{x_{a}}}}$$\scriptstyle{\varphi_{v_{y}}}$$\textstyle{\mathcal{P}_{y}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\omega_{x_{a},y}}$$\scriptstyle{\omega_{z,y}}$$\textstyle{\mathcal{T}_{v_{x_{a}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{v_{x_{a}}}}$$\scriptstyle{\tau_{v_{z},v_{x_{a}}}}$$\textstyle{\mathcal{P}_{x_{a}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\omega_{z,x_{a}}}$$\textstyle{\mathcal{T}_{v_{z}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{w,v_{z}}}$$\scriptstyle{\varphi_{v_{z}}}$$\textstyle{\mathcal{P}_{z}}$$\textstyle{\mathcal{T}_{w}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{w}}$
(3.13)

The conditions (3.4) and (3.6) are clearly verified. Also the composition
properties (3.3) and (3.5) are easy to check while from the particular cases
(3.10) and (3.11) it follows that

$\varphi_{w}\circ\tau_{w,u}=\omega_{\varphi(w),\varphi(u)}\circ\varphi_{u},$
(3.14)

that is the square in (3.1) is commutative at the first level and (3.14)
proves the full commutativity of (3.13). Note also that, if $h=2$, then the
construction of the $\tau$’s and the $\omega$’s stops here.

Now we can complete the definition of $\alpha$ and $\mathcal{Q}$: if $a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ then for all
$v\in(\alpha\circ\varphi)^{-1}(a)$ we define a surjective tree homomorphsm
$\alpha_{\varphi(v)}\colon\mathcal{P}_{\varphi(v)}\rightarrow\mathcal{Q}_{a}$
by setting:

$\alpha_{\varphi(v)}\coloneqq\alpha_{\varphi(v_{x_{a}})}\circ\omega_{\varphi(v_{x_{a}}),\varphi(v)}.$
(3.15)

The tree $\mathcal{Q}$ is defined by means of its first level decomposition
(2.3):

$\mathcal{Q}\coloneqq\\{\emptyset\\}\sqcup\left(A\sqcup
W_{\mathcal{Q}}\right)\sqcup\left[\bigsqcup_{a\in
A}\left(\\{a\\}\times\widetilde{\mathcal{Q}}_{a}\right)\right]$

and the surjective rooted tree homomorphism
$\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$ by means of (2.6), requiring
that $\alpha$ sends the whole $W_{\mathcal{P}}$ to the unique vertex in
$W_{\mathcal{Q}}$, $\alpha$ is equal to $\pi$ on $V_{\mathcal{P}}\setminus
W_{\mathcal{P}}$, $\alpha$ is equal to $\alpha_{x}$ on $\mathcal{P}_{x}$,
$x\in V_{\mathcal{P}}\setminus W_{\mathcal{P}}$. For the vertices in
$V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ and $V_{\mathcal{P}}\setminus
W_{\mathcal{P}}$ the maps $\omega$ and $\tau$ are those in (3.12) so that, by
(3.14) and (3.15), we get the commutative diagram (3.1) at the first level.
Moreover, (a) and (b) are verified at the first level by the definition of
$\sim$ and of $\alpha$ on $V_{\mathcal{T}}\setminus W_{\mathcal{T}}$. From
(3.14), (3.15), the inductive hypothesis applied to the
$\mathcal{T}_{v_{x_{a}}}$’s and Remark 2.6, it follows that (a) and (b) are
verified also at the lower levels.

We have already used induction to get a system of $\tau$’s and $\omega$’s
within the subtrees $\mathcal{T}_{v_{x_{a}}}$ and
$\mathcal{P}_{\varphi(v_{x_{a}})}$, $a\in V_{\mathcal{Q}}\setminus
W_{\mathcal{Q}}$, with the properties in (c) and (d). We combine them togheter
with those at the first level in order to complete the definition of the
$\tau$’s and the $\omega$’s.

Suppose that $\alpha(\varphi(w))=\alpha(\varphi(u))\eqqcolon b$, where
$w\in\mathcal{T}_{\widetilde{w}}$, $u\in\mathcal{T}_{\widetilde{u}}$, with
$\widetilde{w},\widetilde{u}\in V_{\mathcal{T}}$ (that is, $\widetilde{u}$ and
$\widetilde{w}$ are the ancestors of $u$ and $w$ at the first level).
Necessarily also
$\alpha(\varphi(\widetilde{w}))=\alpha(\varphi(\widetilde{u}))\eqqcolon a$,
for some $a\in V_{\mathcal{Q}}$. Set

$\overline{w}\coloneqq\tau_{v_{x_{a}},\widetilde{w}}(w)\qquad\text{and}\qquad\overline{u}\coloneqq\tau_{v_{x_{a}},\widetilde{u}}(u),$
(3.16)

so that $\overline{w},\overline{u}\in\mathcal{T}_{v_{x_{a}}}$ and

$\begin{split}\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\left(\varphi(\overline{w})\right)&=\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\circ\varphi_{v_{x_{a}}}\left(\overline{w}\right)\\\
(\text{by
}\eqref{tauomfl})\quad&=\varphi_{\widetilde{w}}\circ\tau_{\widetilde{w},v_{x_{a}}}\left(\overline{w}\right)\\\
(\text{by
}\eqref{defovzb})\quad&=\varphi_{\widetilde{w}}(w)=\varphi(w)\end{split}$
(3.17)

and similarly
$\omega_{\varphi(\widetilde{u}),\varphi(v_{x_{a}})}\left(\varphi(\overline{u})\right)=\varphi(u)$.
Moreover,

$\begin{split}\alpha(\varphi(\overline{w}))=&\left(\alpha_{\varphi(v_{x_{a}})}\circ\varphi_{v_{x_{a}}}\right)(\overline{w})\\\
(\text{by
}\eqref{defovzb})\quad=&\left(\alpha_{\varphi(v_{x_{a}})}\circ\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{w}}\right)(w)\\\
(\text{by
}\eqref{tauomfl})\quad=&\left(\alpha_{\varphi(v_{x_{a}})}\circ\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{w})}\circ\varphi_{\widetilde{w}}\right)(w)\\\
(\text{by
}\eqref{alphomfl})\quad=&\left(\alpha_{\varphi(\widetilde{w})}\circ\varphi_{\widetilde{w}}\right)(w)\\\
=&\alpha(\varphi(w))=b;\\\ \end{split}$

similarly $\alpha(\varphi(\overline{u}))=b$. Therefore we may invoke the
inductive hypothesis: we have already fixed the isomorphisms
$\tau_{\overline{w},\overline{u}}\colon\mathcal{T}_{\overline{u}}\rightarrow\mathcal{T}_{\overline{w}}$
and
$\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\colon\mathcal{P}_{\varphi(\overline{w})}\rightarrow\mathcal{P}_{\varphi(\overline{u})}$
so that we can define
$\tau_{w,u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{w}$ and
$\omega_{\varphi(w),\varphi(u)}\colon\mathcal{P}_{\varphi(u)}\rightarrow\mathcal{T}_{\varphi(w)}$
by setting:

$\begin{split}&\tau_{w,u}\coloneqq\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)\quad\text{
and }\\\
&\omega_{\varphi(w),\varphi(u)}\coloneqq\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right)\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ\left(\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\lvert_{\mathcal{P}_{\varphi(u)}}\right).\end{split}$
(3.18)

See also the following diagram, whose commutativity will be proved below.

---
$\textstyle{\mathcal{T}_{\widetilde{u}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{v_{x_{a}},\widetilde{u}}}$$\textstyle{\supseteq}$$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{w,u}}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}}$$\textstyle{\mathcal{P}_{\varphi(u)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi(u)}}$$\scriptstyle{\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u}})\lvert_{\mathcal{P}_{\varphi(u)}}}$$\scriptstyle{\omega_{\varphi(w),\varphi(u)}}$
$\textstyle{\mathcal{T}_{v_{x_{a}}}}$$\textstyle{\supseteq}$$\textstyle{\mathcal{T}_{\overline{u}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{\overline{u}}}$$\scriptstyle{\tau_{\overline{w},\overline{u}}}$$\textstyle{\mathcal{P}_{\varphi(\overline{u})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi(\overline{u})}}$$\scriptstyle{\omega_{\varphi(\overline{w}),\varphi(\overline{u})}}$$\textstyle{\mathcal{Q}_{b}}$$\textstyle{\mathcal{T}_{v_{x_{a}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{\widetilde{w},v_{x_{a}}}}$$\textstyle{\supseteq}$$\textstyle{\mathcal{T}_{\overline{w}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}}$$\scriptstyle{\varphi_{\overline{w}}}$$\textstyle{\mathcal{P}_{\varphi({\overline{w}})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi({\overline{w}})}}$$\scriptstyle{\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}}$
$\textstyle{\mathcal{T}_{\widetilde{w}}}$$\textstyle{\supseteq}$$\textstyle{\mathcal{T}_{w}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{w}}$$\textstyle{\mathcal{P}_{\varphi(w)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha_{\varphi(w)}}$
(3.19)

In the particular case $w=u$ we have $\widetilde{w}=\widetilde{u}$ and
$\overline{w}=\overline{u}$, so that
$\tau_{\overline{u},\overline{u}}=\mbox{\rm id}_{\mathcal{T}_{\overline{u}}}$
by the inductive hypothesis. Therefore (3.18) yields

$\displaystyle\tau_{u,u}=$
$\displaystyle\left(\tau_{\widetilde{u},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{u}}}\right)\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)$
$\displaystyle=$
$\displaystyle\tau_{\widetilde{u},\widetilde{u}}\lvert_{\mathcal{T}_{u}}=\left[\mbox{\rm
id}_{\mathcal{T}_{\widetilde{u}}}\right]_{\mathcal{T}_{u}}=\mbox{\rm
id}_{\mathcal{T}_{u}}.$ $\displaystyle(\text{by
}\eqref{defovzb},\;\eqref{proptau2b}\text{ level
}1,\;\mathcal{T}_{u}\subseteq\mathcal{T}_{\widetilde{u}})$

Now we prove (3.6): with the notation in (3.18), if $\varphi(w)=\varphi(u)$
then necessarily $\varphi(\widetilde{w})=\varphi(\widetilde{u})$ so that

$\displaystyle\varphi(\overline{u})=$
$\displaystyle\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{u}}(u)$
$\displaystyle(\text{by }\eqref{defovzb})$ $\displaystyle=$
$\displaystyle\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\left(\varphi_{\widetilde{u}}(u)\right)$
$\displaystyle(\text{by }\eqref{tauomfl})$ $\displaystyle=$
$\displaystyle\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{w})}\left(\varphi_{\widetilde{w}}(w)\right)=\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{w}}(w)=\varphi(\overline{w})$

and therefore $\omega_{\varphi(\overline{w}),\varphi(\overline{w})}=\mbox{\rm
id}_{\mathcal{P}_{\varphi(\overline{w})}}$, by the inductive hypothesis. Then,
from (3.12), (3.18) and the inclusion
$\mathcal{P}_{\varphi(\widetilde{w})}\subseteq\mathcal{P}_{\varphi(w)}$, it
follows that:

$\omega_{\varphi(w),\varphi(w)}=\omega_{\varphi(\widetilde{w}),\varphi(\widetilde{w})}\lvert_{\mathcal{P}_{\varphi(w)}}=\left[\mbox{\rm
id}_{\mathcal{P}_{\varphi(\widetilde{w})}}\right]_{\mathcal{P}_{\varphi(w)}}=\mbox{\rm
id}_{\mathcal{P}_{\varphi(w)}}.$

This implies that if $\varphi(u)=\varphi(v)$ then (3.1) becomes a strict
equivalence.

After that, by exploring the diagram (3.19) we get:

$\displaystyle\varphi_{w}\circ\tau_{w,u}=$
$\displaystyle\Bigl{[}\left(\varphi_{\widetilde{w}}\circ\tau_{\widetilde{w},v_{x_{a}}}\right)\lvert_{\mathcal{T}_{\overline{w}}}\Bigr{]}\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)$
$\displaystyle(\text{by }\eqref{defovzb},\eqref{deftauomega2b}\text{ and
}\mathcal{T}_{w}\subseteq\mathcal{T}_{\widetilde{w}})$ $\displaystyle=$
$\displaystyle\Bigl{[}\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\circ\varphi_{v_{x_{a}}}\right)\lvert_{\mathcal{T}_{\overline{w}}}\Bigr{]}\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)$
$\displaystyle(\text{by }\eqref{tauomfl})$ $\displaystyle=$
$\displaystyle\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right)\circ\varphi_{\overline{w}}\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)$
$\displaystyle(\mathcal{T}_{\overline{w}}\subseteq\mathcal{T}_{v_{x_{a}}})$
$\displaystyle=$
$\displaystyle\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right)\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ\varphi_{\overline{u}}\circ$
$\displaystyle\quad\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)$
$\displaystyle(\text{by }\eqref{diagTRSuv}\text{ within
}\mathcal{T}_{v_{x_{a}}})$ $\displaystyle=$
$\displaystyle\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right)\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ$
$\displaystyle\quad\circ\Bigl{[}\left(\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{u}}\right)\lvert_{\mathcal{T}_{u}}\Bigr{]}$
$\displaystyle(\text{by }\eqref{defovzb}\text{ and
}\mathcal{T}_{\overline{u}}\subseteq\mathcal{T}_{v_{x_{a}}})$ $\displaystyle=$
$\displaystyle\left(\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right)\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ$
$\displaystyle\quad\circ\Bigl{[}\left(\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\circ\varphi_{\widetilde{u}}\right)\lvert_{\mathcal{T}_{u}}\Bigr{]}$
$\displaystyle(\text{by }\eqref{tauomfl})$ $\displaystyle=$
$\displaystyle\omega_{\varphi(w),\varphi(u)}\circ\varphi_{u}.$
$\displaystyle(\text{by
}\mathcal{T}_{u}\subseteq\mathcal{T}_{\widetilde{u}}\text{ and
}\eqref{deftauomega2b})$

In other words, we have checked and used the commutativity of the bottom,
middle and top rectangles in (3.19). Similarly

$\begin{split}\alpha_{\varphi(w)}\circ\omega_{\varphi(w),\varphi(u)}=&\left[\left(\alpha_{\varphi(\widetilde{w})}\circ\omega_{\varphi(\widetilde{w}),\varphi(v_{x_{a}})}\right)\lvert_{\mathcal{P}_{\varphi(\overline{w})}}\right]\circ\\\
(\text{by }\eqref{squarep13},\eqref{deftauomega2b}\text{ and
}\mathcal{P}_{\varphi(w)}\subseteq\mathcal{P}_{\varphi(\widetilde{w}}))\qquad&\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ\left(\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\lvert_{\mathcal{P}_{\varphi(u)}}\right)\\\
(\text{by }\eqref{alphomfl}\text{ and
}\mathcal{P}_{\varphi(\overline{w})}\subseteq\mathcal{P}_{\varphi(v_{x_{a}})})\quad=&\alpha_{\varphi(\overline{w})}\circ\omega_{\varphi(\overline{w}),\varphi(\overline{u})}\circ\left(\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\lvert_{\mathcal{P}_{\varphi(u)}}\right)\\\
(\text{by }\eqref{diagTRSuv}\text{ within
}\mathcal{P}_{\varphi(v_{x_{a}})})\quad=&\alpha_{\varphi(\overline{u})}\circ\left(\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\lvert_{\mathcal{P}_{\varphi(u)}}\right)\\\
=&\left(\alpha_{\varphi(v_{x_{a}})}\circ\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{u})}\right)\lvert_{\mathcal{P}_{\varphi(u)}}\\\
=&\alpha_{\varphi(\widetilde{u})}\lvert_{\mathcal{P}_{\varphi(u)}}=\alpha_{\varphi(u)},\end{split}$

so that we have proved the commutativity of (3.1) in its full generality.
Again, we have checked and used the commutativity of the bottom, middle and
top triangles in (3.19). At the end, also (3.19) is fully commutative.

Now we prove the restriction property (3.2). Assume the notation in (3.18),
suppose that $u^{\prime}$ is a descendant of $u$ and set
$w^{\prime}\coloneqq\tau_{w,u}(u^{\prime})$,
$\overline{u^{\prime}}\coloneqq\tau_{v_{x_{a}},\widetilde{u}}(u^{\prime})$,
$\overline{w^{\prime}}\coloneqq\tau_{v_{x_{a}},\widetilde{w}}(w^{\prime})$, so
that, from the commutativity of (3.1), it follows that

$\alpha(\varphi(w^{\prime}))=(\alpha_{\varphi(w)}\circ\varphi_{w}\circ\tau_{w,u})(u^{\prime})=(\alpha_{\varphi(u)}\circ\varphi_{u})(u^{\prime})=\alpha(\varphi(u^{\prime})),$

so that $\tau_{w^{\prime},u^{\prime}}$ exists and it is defined by means of
(3.18). Moreover,

$\begin{split}\overline{w^{\prime}}=&\tau_{v_{x_{a}},\widetilde{w}}\left(\tau_{w,u}(u^{\prime})\right)=\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)(u^{\prime})\quad(\text{by
}\eqref{deftauomega2b})\\\
=&\tau_{\overline{w},\overline{u}}\left(\overline{u^{\prime}}\right).\end{split}$
(3.20)

By the inductive hypothesis, (3.2) holds true within $\mathcal{T}_{v_{x_{a}}}$
and therefore from (3.20) we deduce that
$\tau_{\overline{w^{\prime}},\overline{u^{\prime}}}=\tau_{\overline{w},\overline{u}}\lvert_{\mathcal{T}_{\overline{u^{\prime}}}}$.
It follows that

$\displaystyle\tau_{w^{\prime},u^{\prime}}=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w^{\prime}}}}\right)\circ\tau_{\overline{w^{\prime}},\overline{u^{\prime}}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u^{\prime}}}\right)$
$\displaystyle(\text{by }\eqref{deftauomega2b}\text{ for
}u^{\prime},w^{\prime})$ $\displaystyle=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w^{\prime}}}}\right)\circ\left(\tau_{\overline{w},\overline{u}}\lvert_{\mathcal{T}_{\overline{u^{\prime}}}}\right)\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u^{\prime}}}\right)$
$\displaystyle=$
$\displaystyle\Bigl{[}\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)\Bigr{]}_{\mathcal{T}_{u^{\prime}}}$
$\displaystyle(\text{by
}\mathcal{T}_{u^{\prime}}\subseteq\mathcal{T}_{u},\;\mathcal{T}_{\overline{w^{\prime}}}\subseteq\mathcal{T}_{\overline{w}}\text{
and }\eqref{starp17bb})$ $\displaystyle=$
$\displaystyle\tau_{w,u}\lvert_{\mathcal{T}_{u^{\prime}}}.$
$\displaystyle(\text{by }\eqref{deftauomega2b})$

Note also that the proof still works when $w$ and $u$ are first level
vertices, so that $w=\widetilde{w},u=\widetilde{u}$: in this case, (3.16)
yields $\overline{u}=\overline{w}=v_{x_{a}}$ so that
$\tau_{\overline{w},\overline{u}}=\mbox{\rm id}_{\mathcal{T}_{v_{x_{a}}}}$ and
(3.20) becomes $\overline{u^{\prime}}=\overline{w^{\prime}}$, which implies
that also $\tau_{\overline{u^{\prime}},\overline{w^{\prime}}}=\mbox{\rm
id}_{\mathcal{T}_{\overline{u^{\prime}}}}$. The proof of the restriction
property for the $\omega$’s is similar.

Now we prove (3.3). Assume again the notation in (3.18) but also that
$\alpha(\varphi(t))=\alpha(\varphi(u))=\alpha(\varphi(w))$,
$t\in\mathcal{T}_{\widetilde{t}}$, $\widetilde{t}\in V_{\mathcal{T}}$, so that
again $t\in(\alpha\circ\varphi)^{-1}(a)$, and set
$\overline{t}\coloneqq\tau_{v_{x_{a}},\widetilde{t}}(t)$, as in (3.16). Then

$\displaystyle\tau_{w,u}\circ\tau_{u,t}=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right)\circ\left(\tau_{\widetilde{u},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{u}}}\right)\circ\tau_{\overline{u},\overline{t}}\circ$
$\displaystyle\circ\left(\tau_{v_{x_{a}},\widetilde{t}}\lvert_{\mathcal{T}_{t}}\right)$
$\displaystyle(\text{by }\eqref{deftauomega2b})$ $\displaystyle=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\left[\tau_{v_{x_{a}},\widetilde{u}}\circ\tau_{\widetilde{u},v_{x_{a}}}\right]_{\mathcal{T}_{\overline{u}}}\circ\tau_{\overline{u},\overline{t}}\circ\left(\tau_{v_{x_{a}},\widetilde{t}}\lvert_{\mathcal{T}_{t}}\right)$
$\displaystyle(\text{by }\eqref{defovzb})$ $\displaystyle=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\tau_{\overline{u},\overline{t}}\circ\left(\tau_{v_{x_{a}},\widetilde{t}}\lvert_{\mathcal{T}_{t}}\right)$
$\displaystyle(\text{by }\eqref{proptau2b},\text{ level }1)$ $\displaystyle=$
$\displaystyle\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{t}}\circ\left(\tau_{v_{x_{a}},\widetilde{t}}\lvert_{\mathcal{T}_{t}}\right)$
$\displaystyle(\text{by }\eqref{proptau2b}\text{ within
}\mathcal{T}_{v_{x_{a}}})$ $\displaystyle=$ $\displaystyle\tau_{w,t}.$
$\displaystyle(\text{by }\eqref{deftauomega2b})$

Similarly, one can prove that $\tau_{w,u}\circ\tau_{u,w}=\tau_{w,w}=\mbox{\rm
id}_{\mathcal{T}_{w}}$. The proof of the composition properties for the
$\omega$’s is similar.

Now we prove (3.4): if $w^{\prime}\in\mathcal{T}_{\widetilde{w^{\prime}}}$,
$u^{\prime}\in\mathcal{T}_{\widetilde{u^{\prime}}}$ with
$\widetilde{w^{\prime}},\widetilde{u^{\prime}}\in V_{\mathcal{T}}$ and
$\varphi(w^{\prime})=\varphi(w),\;\varphi(u^{\prime})=\varphi(u)$ then also

$\varphi\left(\widetilde{w^{\prime}}\right)=\varphi(\widetilde{w}),\quad\varphi\left(\widetilde{u^{\prime}}\right)=\varphi(\widetilde{u})$
(3.21)

so that
$\widetilde{w^{\prime}},\widetilde{u^{\prime}}\in(\alpha\circ\varphi)^{-1}(a)$.
If we set
$\overline{w^{\prime}}\coloneqq\tau_{v_{x_{a}},\widetilde{w^{\prime}}}(w^{\prime})$
and
$\overline{u^{\prime}}\coloneqq\tau_{v_{x_{a}},\widetilde{u^{\prime}}}(u^{\prime})$
then

$\begin{split}\varphi(\overline{w^{\prime}})=&\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{w^{\prime}}}(w^{\prime})\\\
(\text{by
}\eqref{diagTRSuv})\quad=&\omega_{\varphi(v_{x_{a}}),\varphi\left(\widetilde{w^{\prime}}\right)}\circ\varphi_{\widetilde{w^{\prime}}}(w^{\prime})\\\
(\text{by
}\eqref{various1b})\quad=&\omega_{\varphi(v_{x_{a}}),\varphi(\widetilde{w})}\circ\varphi_{\widetilde{w}}(w)\\\
(\text{by
}\eqref{diagTRSuv})\quad=&\varphi_{v_{x_{a}}}\circ\tau_{v_{x_{a}},\widetilde{w}}(w)\\\
(\text{by }\eqref{defovzb})\quad=&\varphi(\overline{w}).\end{split}$ (3.22)

Similarly, $\varphi(\overline{u^{\prime}})=\varphi(\overline{u})$. By the
inductive hypothesis, it follows that
$\omega_{\varphi(\overline{w}),\varphi(\overline{u})}=\omega_{\varphi\left(\overline{w^{\prime}}\right),\varphi\left(\overline{u^{\prime}}\right)}$
and therefore (3.18) and (3.21) yield
$\omega_{\varphi(w^{\prime}),\varphi(u^{\prime})}=\omega_{\varphi(w),\varphi(u)}$,
that is (3.4).

Finally, from the existence of the maps $\tau$’s and $\omega$’s and the
commutativity of (3.1) we deduce that both $\alpha$ and $\alpha\circ\varphi$
are tree compositions while the uniqueness of $\alpha$ up to isomorphisms
follows from the uniqueness of $\pi$ and of each of the
$\alpha_{x}\colon\mathcal{P}_{x}\rightarrow\mathcal{Q}_{a}$,
$x\in\pi^{-1}(a)$, $a\in V_{\mathcal{Q}}$ (by induction). ∎

######  Remark 3.2.

The recursive definition of the $\tau$’s and of the $\omega$’s in (3.18) is
imposed by the restriction and the composition properties, that is if we have
a system of $\tau$’s that satisfy (3.2) and (3.3) assuming (3.16) then
necessarily:

$\tau_{w,u}=\tau_{w,\overline{w}}\circ\tau_{\overline{w},\overline{u}}\circ\tau_{\overline{u},u}=\left(\tau_{\widetilde{w},v_{x_{a}}}\lvert_{\mathcal{T}_{\overline{w}}}\right)\circ\tau_{\overline{w},\overline{u}}\circ\left(\tau_{v_{x_{a}},\widetilde{u}}\lvert_{\mathcal{T}_{u}}\right).$

The following definition is inspired by [19, Section 6C’].

######  Definition 3.3.

A system of $\tau$’s (respectively $\omega$’s) that satisfy the restriction
and composition properties in Theorem 3.1 will be called a pseudogroup of
equivalences (respectively pseudogroup of strict equivalences) associated to
the tree composition $\varphi$ and its quotient $\alpha$; we also say that the
two pseudogroups are coordinate.

######  Remark 3.4.

Let $\mathsf{G}$ (respectively $\mathsf{H}$) be the set of all $\tau_{u,v}$
(respectively, all $\omega_{\varphi(u),\varphi(v)}$) that satisfy (3.1), for
all couples $u,v$ as in Theorem 3.1(c); when $v=u$ then $\tau_{u,u}$ is an
automorphism of $\mathcal{T}_{u}$; $\omega_{x,x}$ an automorphism of
$\mathcal{P}_{x}$. Then $\mathsf{G}$ and $\mathsf{H}$ are a pseudogroups that
satisfy conditions similar those in Theorem 3.1, that is if
$\tau_{u,v},\tau_{v,w}\in\mathsf{G}$ then
$\tau_{u,v}\circ\tau_{v,w}\in\mathsf{G}$, $\tau_{u,v}^{-1}\in\mathsf{G}$ and
$\tau_{v,u}\rvert_{\mathcal{T}_{u^{\prime}}}\in\mathcal{G}$ if $u^{\prime}$ is
a descendant of $u$. But we need to fix a system of $\tau$’s and a coordinate
system of $\omega$’s as in Theorem 3.1, that is one $\tau_{u,v}$ and one
$\omega_{x,y}$ for all possible couples $u,v$, respectively $x,y$. They will
be used in the proof of many of the fundamental results in Section 5, Section
7 and Section 8.

######  Remark 3.5.

By means of the results in Remark 2.6 it is easy to check that if
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$,
$\psi\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P})$ are strictly equivalent
and $\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ is the quotient of
$\varphi$ then $\alpha$ is also the quotient of $\psi$. Similarly, suppose
that $\varphi$ and $\psi$ are equivalent and $\alpha$, $\beta$ are their
respective quotients, as in the following diagram, where $\tau$ and $\omega$
are isomorphisms, the left square is commutative and $\gamma$ is to be
defined.

$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau}$$\scriptstyle{\varphi}$$\textstyle{\mathcal{P}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\omega}$$\scriptstyle{\alpha}$$\textstyle{\mathcal{Q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\textstyle{\mathcal{T}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi}$$\textstyle{\mathcal{P}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta}$$\textstyle{\mathcal{Q}^{\prime}}$
(3.23)

Again by means of Remark 2.6, it easy easy to check that also
$\beta\circ\omega\colon\mathcal{P}\rightarrow\mathcal{Q}^{\prime}$ is a
quotient of $\varphi$. Then from Theorem 3.1(e) it follows that there exists
an isomorphism $\gamma$ such that the entire diagram is commutative.

######  Example 3.6.

In Example 2.7 and Example 2.8 we have already indicated the relative quotient
partitions. In Example 2.9 the quotient $\mathcal{Q}$ is obtained from
$\mathcal{P}$ by deleting $a_{h}$,
$\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$ sends $a_{h}$ to $b_{h}$ and
it fixes all the other vertices. In Example 2.10 the quotient $\mathcal{Q}$ is
equal to $\mathcal{P}$ up to level $h-1$; if $x\in\mathcal{P}$ is at level
$h-1$ and $\ell(x)=j\geq 1$ then the $j+1$ children of $x$ are replaced by
just one vertex which is the image of all the children of $x$.

######  Example 3.7.

If $\mathcal{T}=\mathcal{P}$ and $\varphi=\mbox{\rm id}_{\mathcal{T}}$ is the
identity composition then the relative quotient composition $\mbox{\rm
tv}_{\mathcal{T}}\colon\mathcal{T}\rightarrow\mathcal{C}$, that we call the
trivial composition of $\mathcal{T}$, has the following properties (which also
characterize it):

  * •

If $c,c^{\prime}\in\mathcal{C}$ are distinct siblings which are internal, then
for all pairs of siblings $u,v\in\mathcal{T}$ such that $\mbox{\rm
tv}_{\mathcal{T}}(\varphi(u))=c$, $\mbox{\rm
tv}_{\mathcal{T}}(\varphi(v))=c^{\prime}$ the trees $\mathcal{T}_{u}$ and
$\mathcal{T}_{v}$ are not isomorphic;

  * •

if $v\in\mathcal{T}$ and $Y\subseteq\mathcal{T}_{v}$ is the subsets of all
children of $v$ which are leaves then $\left(\mbox{\rm
tv}_{\mathcal{T}}\right)_{v}$ sends the whole $Y$ to a singleton
$c\in\mathcal{C}$, which is the unique child of $\mbox{\rm
tv}_{\mathcal{T}}(v)$ which is a leaf;

  * •

if $u,v\in\mathcal{T}$ are internal and $\mbox{\rm
tv}_{\mathcal{T}}(u)=\mbox{\rm tv}_{\mathcal{T}}(v)$ then $\mathcal{T}_{u}$
and $\mathcal{T}_{v}$ are isomorphic.

In particular, if $c\in\mathcal{C}$ then $\mathcal{C}_{c}$ is a path if and
only if $\mathcal{T}_{u}$ is spherically homogeneous for all $u\in\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)$. Moreover, we get the following iterative
description of $\mbox{\rm Aut}(\mathcal{T})$, which generalizes (2.2):

$\mbox{\rm Aut}(\mathcal{T})\cong\mbox{\rm
Sym}(W_{\mathcal{T}})\prod\left\\{\prod_{c\in V_{\mathcal{C}}\setminus
W_{\mathcal{C}}}\left[\mbox{\rm Sym}\left(\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\right)\wr\mbox{\rm
Aut}\left(\mathcal{T}_{u_{c}}\right)\right]\right\\},$ (3.24)

where $\prod$ indicates a direct product of groups and $u_{c}$ is the choice
of an element in $\mbox{\rm tv}_{\mathcal{T}}^{-1}(c)$.

In what follow, $\mbox{\rm Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}$ will
denote the set of all restrictions $g\rvert_{V_{\mathcal{T}}}$, $g\in\mbox{\rm
Aut}(\mathcal{T})$, so that from (3.24) we deduce that

$\mbox{\rm Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}\cong\mbox{\rm
Sym}(W_{\mathcal{T}})\prod\left\\{\prod_{c\in V_{\mathcal{C}}\setminus
W_{\mathcal{C}}}\mbox{\rm Sym}\left(\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\right)\right\\}.$ (3.25)

##  4 Trees of partitions

The type of a tree composition $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$
is the function
$\lvert\varphi^{-1}\rvert\colon\mathcal{P}\rightarrow\mathbb{N}$ defined by
setting $\lvert\varphi^{-1}\rvert(\emptyset)=0$ and for all
$y\in\mathcal{P}\setminus{\emptyset}$,

$\lvert\varphi^{-1}\rvert(y)\coloneqq\left\lvert\varphi^{-1}(y)\cap\text{Ch}(u)\right\rvert,$
(4.1)

where $u$ is any counterimage of the parent $x$ of $y$; by the regularity
condition in Definition 2.1, the cardinality of
$\varphi^{-1}(y)\cap\text{Ch}(u)$ does not depend on the choice of $u$. In
other words, if $x\in\mathcal{P}$ is internal and $u\in\varphi^{-1}(x)$, then

$\text{\rm Ch}(u)=\bigsqcup_{y\in\text{\rm
Ch}(x)}\left[\varphi^{-1}(y)\cap\text{\rm Ch}(u)\right]$ (4.2)

is a set composition (cf. (2.15)) and the map $\text{\rm Ch}(x)\ni
y\mapsto\lvert\varphi^{-1}(y)\cap\text{\rm Ch}(u)\rvert$, which determines the
type of this set composition, does not depend on the choice of $u$. Moreover,
if $u\in\mathcal{T}$ then the type of
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{\varphi(u)}$ is just
the restriction of $\lvert\varphi^{-1}\rvert$ to $\mathcal{P}_{\varphi(u)}$.
Clearly, strictly equivalent tree compositions have the same type; now we
prove the converse.

######  Theorem 4.1.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P})$ are of the same type.
Then they are strictly equivalent: there exists a tree isomorphism
$\tau\colon\mathcal{T}\rightarrow\mathcal{T}^{\prime}$ such that
$\varphi=\psi\circ\tau$.

$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\tau}$$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi}$

###### Proof.

By induction on $h$, the number of levels of these trees. If $h=1$ this is
trivial (cf. Example 2.7 and also the definition of
$\tau\rvert_{W_{\mathcal{T}}}$ below). Suppose $h>1$ and consider the first
level decomposition (2.3). There exists a bijection $\pi\colon
V_{\mathcal{T}}\rightarrow V_{\mathcal{T}^{\prime}}$ such that

$\pi\left(\varphi^{-1}(x)\right)=\psi^{-1}(x),\quad\text{ for all }x\in
V_{\mathcal{P}},$ (4.3)

because $\lvert\varphi^{-1}(x)\rvert=\lvert\psi^{-1}(x)\rvert$. In particular,
$\pi$ is a bijection between $W_{\mathcal{T}}$ and $W_{\mathcal{T}^{\prime}}$
(their images are $W_{\mathcal{P}}$) and we may set
$\tau\rvert_{W_{\mathcal{T}}}\coloneqq\pi\rvert_{W_{\mathcal{T}}}$, so that
(4.3) yields
$\varphi\rvert_{W_{\mathcal{T}}}=\psi\rvert_{W_{\mathcal{T}}}\circ\tau\rvert_{W_{\mathcal{T}}}$.
If $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ set
$\varphi(u)\equiv\psi(\pi(u))\eqqcolon x$, so that $x\in
V_{\mathcal{P}}\setminus W_{\mathcal{P}}$. Then
$\varphi_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{P}_{x}$ and
$\psi_{\pi(u)}\colon\mathcal{T}^{\prime}_{\pi(u)}\rightarrow\mathcal{P}_{x}$
have the same type as tree compositions of $\mathcal{T}_{u}$ and
$\mathcal{T}^{\prime}_{\pi(u)}$, respectively, so that, by the inductive
hypothesis, they are strictly equivalent: there exists an isomorphism
$\tau_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{\pi(u)}^{\prime}$ such
that

$\varphi_{u}=\psi_{\pi(u)}\circ\tau_{u}.$ (4.4)

This way we get an isomorphism as in (2.6) by setting
$\tau(u,w)\coloneqq(\pi(u),\tau_{u}(w))$ so that for all $u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, $w\in\widetilde{\mathcal{T}}_{u}$,
we have

$\displaystyle\left(\psi\circ\tau\right)(u,w)=$
$\displaystyle\left(\psi(\pi(u))),\psi_{\pi(u)}(\tau_{u}(w))\right)$
$\displaystyle(\text{by }\eqref{firstldell2})$ $\displaystyle=$
$\displaystyle\left(\varphi(u),\varphi_{u}(w)\right)=\varphi(u,w).$
$\displaystyle(\text{by }\eqref{formp13})$

∎

Now suppose that $\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ is the
quotient of $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$, cf. Theorem 3.1.
If $a\in\mathcal{Q}$ is internal, $x\in\alpha^{-1}(a)$ and
$u\in\varphi^{-1}(x)$, then

$\begin{split}\text{\rm Ch}(u)=&\bigsqcup_{b\in\text{\rm
Ch}(a)}\left[(\alpha\circ\varphi)^{-1}(b)\cap\text{\rm Ch}(u)\right]\\\
=&\bigsqcup_{b\in\text{\rm Ch}(a)}\;\bigsqcup_{y\in\left[\text{\rm
Ch}(x)\cap\alpha^{-1}(b)\right]}\left[\varphi^{-1}(y)\cap\text{\rm
Ch}(u)\right].\end{split}$ (4.5)

Clearly, (4.2) is a refinement of the first set composition in (4.5) while the
second set composition in (4.5) is a more structured form of (4.2). We
introduce the following notation: we denote by $\lambda^{b}$ the numerical
partition which is the type of the set partition

$(\alpha\circ\varphi)^{-1}(b)\cap\text{\rm
Ch}(u)=\left\\{\varphi^{-1}(y)\cap\text{\rm Ch}(u)\colon y\in\text{\rm
Ch}(x)\cap\alpha^{-1}(b)\right\\};$

cf. Example 2.7. That is, if $\text{\rm
Ch}(x)\cap\alpha^{-1}(b)=\\{y_{1},y_{2},\dotsc,y_{n}\\}$ then

$\lambda^{b}_{j}\coloneqq\left\lvert\varphi^{-1}(y_{j})\cap\text{\rm
Ch}(u)\right\rvert,\qquad j=1,2,\dotsc,n,$ (4.6)

assuming that $y_{1},y_{2},\dotsc,y_{n}$ are ordered in such a way that
$\lambda^{b}_{j}\geq\lambda^{b}_{j+1}$, $j=1,2,\dotsc,n-1$, so that
$\lambda^{b}$ is a partition of the number
$\left\lvert(\alpha\circ\varphi)^{-1}(b)\cap\text{\rm Ch}(u)\right\rvert$. In
other words, to each $b\in\mathcal{Q}$ we associate a partition $\lambda^{b}$
(by Theorem 3.1, it does not depend on the choice of $u$). In the following
picture the ellipse containing $\lambda^{b}$ represents the composition of
type $\lambda^{b}$ of the vertices in
($\alpha\circ\varphi)^{-1}(b)\cap\text{\rm Ch}(u)$.

${\scriptstyle
u}$2814${\scriptstyle\lambda^{b}}$${\scriptstyle(\alpha\circ\varphi)^{-1}(b)}$

${\scriptstyle x}$${\scriptstyle
y_{1}}$5025${\scriptstyle\alpha^{-1}(b)}$${\scriptstyle y_{n}}$

${\scriptstyle a}$${\scriptstyle b}$

In conclusion, for all $b\in\mathcal{Q}$,

$\ell(\lambda^{b})=\left\lvert\alpha^{-1}\right\rvert(b),\qquad\lvert\lambda^{b}\rvert=\left\lvert(\alpha\circ\varphi)^{-1}\right\rvert(b),$
(4.7)

(cf. (2.14) and (4.1)) and the parts of $\lambda^{b}$ are the numbers

$\lambda^{b}_{y}\coloneqq\left\lvert\varphi^{-1}\right\rvert(y),\quad
y\in\alpha^{-1}(b),$ (4.8)

listed in the weakly decreasing order.

######  Definition 4.2.

Let $\mathcal{Q}$ be a rooted tree. A tree of partitions on $\mathcal{Q}$ is a
function $\Lambda\colon a\mapsto\lambda^{a}$ that associates to each
$a\in\mathcal{Q}$ which is not the root a numerical partition $\lambda^{a}$
(we use $\Lambda$ to denote the function, so that $\lambda^{a}$ denotes the
value of $\Lambda(a)$). If $\Gamma\colon b\mapsto\mu^{b}$ is a tree of
partitions on another tree $\mathcal{Q}^{\prime}$ then it is isomorphic to
$\Lambda\colon a\mapsto\lambda^{a}$ if there exists a rooted tree isomorphism
$\gamma\colon\mathcal{Q}\rightarrow\mathcal{Q}^{\prime}$ such that
$\lambda^{a}=\mu^{\gamma(a)}$ for every $a\in\mathcal{Q}$. If
$a\mapsto\lambda^{a}$ is constructed as in (4.6), we say that it is determined
by (or associated to) the tree composition
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$.

######  Example 4.3.

In Example 2.7 and Example 2.8 we have already drawn the relative tree of
partitions. The tree of partitions of $\varphi^{\mathcal{S}}$ in Example 2.9
(see also Example 3.6) is the following (we assume $r_{h}-s_{h}\geq s_{h}$,
otherwise the last partition at the lower level is $(s_{h},r_{h}-s_{h})$):

\begin{picture}(400.0,150.0)\par\par\put(200.0,140.0){\circle*{4.0}}
\put(198.0,145.0){${\scriptstyle\emptyset}$}
\put(188.0,145.0){${\scriptstyle\mathcal{Q}}$}
\Thicklines\put(200.0,140.0){\line(1,-2){40.0}}
\put(200.0,140.0){\line(-1,-2){40.0}} \par\put(180.0,100.0){\circle*{2.0}}
\put(150.0,100.0){${\scriptstyle(r_{1}-s_{1})}$}
\put(220.0,100.0){\circle*{4.0}} \put(220.0,100.0){\line(-1,-2){20.0}}
\put(225.0,100.0){${\scriptstyle(s_{1})}$} \par\put(160.0,60.0){\circle*{2.0}}
\put(140.0,60.0){${\scriptstyle(r_{2})}$} \put(200.0,60.0){\circle*{2.0}}
\put(170.0,60.0){${\scriptstyle(r_{2}-s_{2})}$}
\put(240.0,60.0){\circle*{4.0}} \put(245.0,60.0){${\scriptstyle(s_{2})}$}
\dashline{2}(240,60)(225,30) \dashline{2}(160,60)(145,30)
\dashline{2}(240,60)(255,30) \put(145.0,30.0){\circle*{2.0}}
\put(145.0,30.0){\line(-1,-2){15.0}}
\put(115.0,30.0){${\scriptstyle(r_{h-1})}$} \put(225.0,30.0){\circle*{2.0}}
\put(225.0,30.0){\line(-1,-2){15.0}}
\put(175.0,30.0){${\scriptstyle(r_{h-1}-s_{h-1})}$}
\put(255.0,30.0){\circle*{4.0}} \Thicklines\put(255.0,30.0){\line(1,-2){15.0}}
\put(260.0,30.0){${\scriptstyle(s_{h-1})}$} \par\put(130.0,0.0){\circle*{2.0}}
\put(110.0,0.0){${\scriptstyle(r_{h})}$} \dashline{2}(180,20)(170,0)
\put(170.0,0.0){\circle*{2.0}} \put(150.0,0.0){${\scriptstyle(r_{h})}$}
\put(210.0,0.0){\circle*{2.0}} \put(190.0,0.0){${\scriptstyle(r_{h})}$}
\put(270.0,0.0){\circle*{4.0}}
\put(275.0,0.0){${\scriptstyle(r_{h}-s_{h},s_{h})}$} \par\end{picture}

${\scriptstyle\emptyset}$${\scriptstyle\mathcal{Q}}$

${\scriptstyle(r_{1}-s_{1})}$${\scriptstyle(s_{1})}$

${\scriptstyle(r_{2})}$${\scriptstyle(r_{2}-s_{2})}$${\scriptstyle(s_{2})}$2(240,60)(225,30)
2(160,60)(145,30) 2(240,60)(255,30)
${\scriptstyle(r_{h-1})}$${\scriptstyle(r_{h-1}-s_{h-1})}$${\scriptstyle(s_{h-1})}$

${\scriptstyle(r_{h})}$2(180,20)(170,0)
${\scriptstyle(r_{h})}$${\scriptstyle(r_{h})}$${\scriptstyle(r_{h}-s_{h},s_{h})}$

The tree of partitions of a tree composition as in Example 2.10 has the
following structure (the quotient $\mathcal{Q}$ is described in Example 3.6).
The tree $\mathcal{Q}$ coincides with $\mathcal{P}$ up to level $h-1$; if
$x\in\mathcal{Q}$ is at level $k\leq h-1$ and $\ell(x)=j$ then its associated
partition is $\lambda^{x}=(s_{k}^{j}-s_{k}^{j+1})$ (recall that
$s_{k}^{l+1}=0$). If $a$ is a vertex of $\mathcal{Q}$ at level $h$, $x$ is its
parent at level $h-1$ and $\ell(x)=j\geq 1$ then
$\lambda^{a}=(s_{h}^{0}-s_{h}^{1},s_{h}^{1}-s_{h}^{2},\dotsc,s_{h}^{j-1}-s_{h}^{j},s_{h}^{j})$
while if $\ell(x)=0$ then $\lambda^{a}=(s_{h}^{0})\equiv(r_{h})$.

######  Example 4.4.

It is easy to check that, if $\mathcal{T}$ is spherically homogeneous of
branching type $(r_{1},r_{2},\dotsc,r_{h})$, then the trees of partitions of
the trivial composition and of the identity composition (cf. Example 3.7) are,
respectively,

${\scriptstyle(r_{1})}$${\scriptstyle(r_{2})}$2(150,110)(150,80)
${\scriptstyle(r_{h-1})}$${\scriptstyle(r_{h})}$$\Lambda_{\text{\rm
tv}}$${\scriptstyle\left(1^{r_{1}}\right)}$${\scriptstyle\left(1^{r_{2}}\right)}$2(300,110)(300,80)
${\scriptstyle\left(1^{r_{h-1}}\right)}$${\scriptstyle\left(1^{r_{h}}\right)}$$\Lambda_{\text{\rm
id}}$

######  Theorem 4.5.

Two tree compositions $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ (with
quotient $\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ and tree of partitions
$a\mapsto\lambda^{a}$) and
$\psi\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P}^{\prime})$ (with quotient
$\beta\in\mathsf{C}(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ and tree of
partitions $b\mapsto\mu^{b}$) are equivalent if and only if they determine
isomorphic trees of partitions.

###### Proof.

If $\varphi$ and $\psi$ are equivalent and $\gamma$ is the isomorphism in
(3.23) then clearly $\lambda^{a}=\mu^{\gamma(a)}$.

For the converse, first of all we show how to construct $\omega$: more
precisely, starting from an isomorphism $\gamma$ such that
$\lambda^{a}=\mu^{\gamma(a)}$ we prove that there exists $\omega$ such that
the second square in (3.23) is commutative and also
$\lambda^{a}_{x}=\mu^{\gamma(a)}_{\omega(x)}$, for all $x\in\alpha^{-1}(a)$,
$a\in\mathcal{Q}$; cf. (4.8). By induction on $h$, the height of the trees;
for $h=1$ it is obvious: by Example 2.7 and Theorem 3.1(a), $V_{\mathcal{Q}}$
and $V_{\mathcal{Q}^{\prime}}$ are singletons and $\varphi$ and $\psi$ define
equivalent set compositions, because they are associated to the same numerical
partition. Suppose that $h>1$. By (4.7), for all $a\in V_{\mathcal{Q}}$ we
have

$\left\lvert\alpha^{-1}(a)\right\rvert=\ell\left(\lambda^{a}\right)=\ell\left(\mu^{\gamma(a)}\right)=\left\lvert\beta^{-1}(\gamma(a))\right\rvert.$

Therefore we can choose a bijection $\sigma\colon V_{\mathcal{P}}\rightarrow
V_{\mathcal{P}^{\prime}}$ in such a way that

$\sigma\left(\alpha^{-1}(a)\right)=\beta^{-1}(\gamma(a)),$ (4.9)

for all $a\in V_{\mathcal{Q}}$, and also
$\lambda^{a}_{x}=\mu^{\gamma(a)}_{\sigma(x)}$, for all $x\in\alpha^{-1}(a)$.
Again, $W_{\mathcal{Q}}$ and $W_{\mathcal{Q}^{\prime}}$ are both empty or both
singletons, and in the latter case may set
$\omega\rvert_{W_{\mathcal{P}}}=\sigma\rvert_{W_{\mathcal{P}}}$.

After that, for each $x\in V_{\mathcal{P}}\setminus W_{\mathcal{P}}$ consider
the tree compositions
$\alpha_{x}\colon\mathcal{P}_{x}\rightarrow\mathcal{Q}_{\alpha(x)}$ and
$\beta_{\sigma(x)}\colon\mathcal{P}^{\prime}_{\sigma(x)}\rightarrow\mathcal{Q}_{\gamma(\alpha(x))}^{\prime}\equiv\mathcal{Q}_{\beta(\sigma(x))}^{\prime}$
(cf. (4.9)). Since
$\gamma_{\alpha(x)}\colon\mathcal{Q}_{\alpha(x)}\rightarrow\mathcal{Q}_{\gamma(\alpha(x))}^{\prime}$
satisfies again the condition $\lambda^{a}=\mu^{\gamma(a)}$ for all
$a\in\mathcal{Q}_{\alpha(x)}$, by the inductive hypothesis there exists an
isomorphism
$\omega_{x}\colon\mathcal{P}_{x}\rightarrow\mathcal{P}^{\prime}_{\sigma(x)}$
such that

$\beta_{\sigma(x)}\circ\omega_{x}=\gamma_{\alpha(x)}\circ\alpha_{x}$ (4.10)

and

$\lambda^{a}_{z}=\mu^{\gamma(a)}_{\omega_{x}(z)},$ (4.11)

for all $z\in\alpha^{-1}(a)\cap\mathcal{P}_{x}$,
$a\in\mathcal{Q}_{\alpha(x)}$. Then we can define an isomorphism written as in
(2.6) by setting $\omega(x,z)=(\sigma(x),\omega_{x}(z))$ for all $x\in
V_{\mathcal{P}}\setminus W_{\mathcal{P}}$, $z\in\widetilde{\mathcal{P}}_{x}$,
so that

$\displaystyle\beta\circ\omega(x,z)=$
$\displaystyle\bigl{(}(\beta\circ\sigma)(x),(\beta_{\sigma(x)}\circ\omega_{x})(z))\bigr{)}$
$\displaystyle(\text{by }\eqref{firstldell2})$ $\displaystyle=$
$\displaystyle\bigl{(}(\gamma\circ\alpha)(x),(\gamma_{\alpha(x)}\circ\alpha_{x})(z)\bigr{)}$
$\displaystyle(\text{by }\eqref{gammaomeg}\text{ and }\eqref{betasig})$
$\displaystyle=$ $\displaystyle\gamma\circ\alpha(x,z).$
$\displaystyle(\text{by \eqref{firstldell2}})$

Finally, consider the tree compositions
$\omega\circ\varphi\colon\mathcal{T}\rightarrow\mathcal{P}^{\prime}$ and
$\psi\colon\mathcal{T}^{\prime}\rightarrow\mathcal{P}^{\prime}$ (cf. (3.23));
they have the same type because $x\in\alpha^{-1}(a)$, $a\in\mathcal{Q}$,
implies that

$\omega(x)\in\beta^{-1}(\gamma(a))$ (4.12)

and therefore

$\begin{split}\left\lvert\left(\omega\circ\varphi\right)^{-1}\right\rvert(\omega(x))=&\left\lvert\varphi^{-1}\right\rvert(x)=\lambda_{x}^{a}\\\
(\text{by }\eqref{betasig1})\quad=&\mu^{\gamma(a)}_{\omega(x)}\\\ (\text{by
}\eqref{betasig2})\quad=&\left\lvert\psi^{-1}\right\rvert(\omega(x));\end{split}$

cf. (4.8). Then the existence of $\tau$ is guaranteed by Theorem 4.1. ∎

We set
$\mathsf{C}_{T}(\mathcal{T},\mathcal{P})\coloneqq\left\\{\lvert\varphi^{-1}\rvert\colon\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})\right\\}$;
this is the set of all possible types of the $\mathcal{P}$-compositions of
$\mathcal{T}$. Then we denote by $\mathsf{C}_{P}(\mathcal{T},\mathcal{P})$ a
set of representatives for the isomorphism classes of trees of partitions
which are determined by the $\mathcal{P}$-compositions of $\mathcal{T}$.

######  Remark 4.6.

Consider the action (2.10). By Theorem 4.1, the orbits of $\mbox{\rm
Aut}(\mathcal{T})$ on $\mathsf{C}(\mathcal{T},\mathcal{P})$ (the strict
equivalent classes, cf. Remark 2.5) are parametrized by the elements of
$\mathsf{C}_{T}(\mathcal{T},\mathcal{P})$. Similarly, by Theorem 4.5, the
orbits of $\mbox{\rm Aut}(\mathcal{T})\times\mbox{\rm Aut}(\mathcal{P})$ on
$\mathsf{C}(\mathcal{T},\mathcal{P})$ (the equivalence classes, cf. Remark
2.5) are parametrized by the elements of
$\mathsf{C}_{P}(\mathcal{T},\mathcal{P})$.

######  Definition 4.7.

We set

$\mathsf{Par}(\mathcal{T})\coloneqq\bigsqcup_{\mathcal{P}}\mathsf{C}_{P}(\mathcal{T},\mathcal{P})$

where the union is over all (isomorphism classes of) compositional trees
$\mathcal{P}$ of $\mathcal{T}$.

In other words, $\mathsf{Par}(\mathcal{T})$ is a set of representatives for
the isomorphism classes of the set of all trees of partitions obtained from
all the possible tree compositions of $\mathcal{T}$. By Theorem 4.5,
$\mathsf{Par}(\mathcal{T})$ parametrizes the equivalence classes of tree
compositions of $\mathcal{T}$. We will usually indicate an element of
$\mathsf{Par}(\mathcal{T})$ as a couple $(\Lambda,\mathcal{Q})$; sometimes
only by $\Lambda$.

######  Algorithm 4.8.

Now we describe an iterative algorithm for the construction of all the
elements of $\mathsf{Par}(\mathcal{T})$. We will use the notation in Example
3.7 and also the $\tau$’s for the first level of the trivial composition
$\mbox{\rm tv}_{\mathcal{T}}\colon\mathcal{T}\rightarrow\mathcal{C}$ (cf.
Theorem 3.1(b)), which are just a set of isomorphisms between the subtrees
$\mathcal{T}_{u}$, $u\in\mbox{\rm tv}_{\mathcal{T}}^{-1}(c)$, for all $c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}$.

  1. 1.

If $h\coloneqq H(\mathcal{T})=1$ or if $W_{\mathcal{T}}$ is not empty use
Example 2.7.

  2. 2.

If $h>1$ then for each $c\in V_{\mathcal{C}}\setminus W_{\mathcal{C}}$ take a
set $A_{c}$ such that

$\lvert A_{c}\rvert\leq\min\left\\{\left\lvert\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\right\rvert,\left\lvert\mathsf{Par}(\mathcal{T}_{u_{c}})\right\rvert\right\\}$
(4.13)

and set $V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}\coloneqq\bigsqcup_{c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}}A_{c}$.

  3. 3.

Then for all $a\in A_{c}$, $c\in V_{\mathcal{C}}\setminus W_{\mathcal{C}}$,
choose $(\Lambda_{a},\mathcal{Q}_{a})\in\mathsf{Par}(\mathcal{T}_{u_{a}})$ in
such a way that if $a,a^{\prime}\in A_{c}$ and $a\neq a^{\prime}$ then
$(\Lambda_{a},\mathcal{Q}_{a})$ and
$(\Lambda_{a^{\prime}},\mathcal{Q}_{a^{\prime}})$ are not isomorphic; this
requires the preventive construction of the elements of
$\mathsf{Par}(\mathcal{T}_{u_{a}})$ and the condition $\lvert
A_{c}\rvert\leq\lvert\mathsf{Par}(\mathcal{T}_{u_{c}})\rvert$ in (4.13). Fix
also a tree composition
$\varphi_{a}\in\mathsf{C}(\mathcal{T}_{u_{c}},\mathcal{P}_{a})$ with quotient
$\alpha_{a}\in\mathsf{C}(\mathcal{P}_{a},\mathcal{Q}_{a})$ such that
$\Lambda_{a}$ is the tree of partitions of $\varphi_{a}$.

  4. 4.

Choose numerical partitions $\lambda^{a}$ in such a way that

$\sum_{a\in A_{c}}\lvert\lambda^{a}\rvert=\left\lvert\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\right\rvert,\quad\text{for all }c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}.$

This requires the condition $\lvert A_{c}\rvert\leq\lvert\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\rvert$ in (4.13). Then we may define $\mathcal{Q}$
by means of (2.3) and also $\Lambda$ is completely defined and we have the
tree of partitions.

  5. 5.

After that, suppose that $X_{a}$ is a finite set of cardinality
$\ell(\lambda^{a})$ and set

$V_{\mathcal{P}}\setminus
W_{\mathcal{P}}\coloneqq\bigsqcup_{\begin{subarray}{c}a\in A_{c},\\\ c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}\end{subarray}}X_{a},$

take $\mathcal{P}_{x}$, $x\in X_{a}$, isomorphic to $\mathcal{P}_{a}$ and
denote by $\omega_{a,x}\colon\mathcal{P}_{x}\rightarrow\mathcal{P}_{a}$ the
isomorphism. The map $\alpha$ at the first level may be defined by
$\alpha(X_{a})\coloneqq a$ and then
$\alpha_{x}\coloneqq\alpha_{a}\circ\omega_{a,x}$. This ends the definition of
$\mathcal{P}$ and of the tree composition
$\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$.

  6. 6.

Finally, define $\varphi$ at the first level in such a way that
$\varphi\bigl{(}\mbox{\rm
tv}_{\mathcal{T}}^{-1}(c)\bigr{)}=\bigsqcup\limits_{a\in A_{c}}X_{a}$ and each
of the set compositions $\bigsqcup\limits_{x\in X_{a}}\varphi^{-1}(x)$ is of
type $\lambda^{a}$. For $u\in\varphi^{-1}(x)$, $x\in X_{a}$, set
$\varphi_{u}\coloneqq\omega_{a,x}^{-1}\circ\varphi_{a}\circ\tau_{u_{c},u}$,
where $\varphi_{a}$ is as in 3. while $\omega_{a,x}$ is as in 5.

By means of Remark 2.6, Remark 3.5, Theorem 4.1 and Theorem 4.5 it is easy to
check that $\varphi$ is a tree composition, $\alpha$ is its quotient and
$\Lambda$ the corresponding tree of partitions. Moreover, choosing the
$(\Lambda_{a},\mathcal{Q}_{a})$’s in 3. and the $\lambda^{a}$’s in 4. in all
possible way we get all the tree of partitions associated to $\mathcal{T}$.

######  Example 4.9.

Suppose that $\mathcal{T}_{h}$ is the spherically homogeneous binary tree of
height $h$, that is set $r_{1}=r_{2}=\dotsb r_{h}=2$ in (2.2). Now we apply
Algorithm 4.8 to get a recursive formula for
$\left\lvert\mathsf{Par}\left(\mathcal{T}_{h}\right)\right\rvert$. First of
all, $\left\lvert\mathsf{Par}\left(\mathcal{T}_{1}\right)\right\rvert=2$ and
the tree $\mathcal{C}$ of the trivial composition is a path (cf. Example 4.4).
When we apply the algorithm we have three possibilities:

  1. (a)

take $A_{c}=\\{a\\}$, $\lambda^{a}=(2)$ and choose a tree of partitions in
$\mathsf{Par}\left(\mathcal{T}_{h-1}\right)$;

  2. (b)

take $A_{c}=\\{a\\}$, $\lambda^{a}=(1,1)$ and choose a tree of partitions in
$\mathsf{Par}\left(\mathcal{T}_{h-1}\right)$;

  3. (c)

take $A_{c}=\\{a,a^{\prime}\\}$, so that necessarily
$\lambda^{a}=(1)=\lambda^{a^{\prime}}$ and choose a couple of distinct trees
of partitions in $\mathsf{Par}\left(\mathcal{T}_{h-1}\right)$.

Then we have

$\left\lvert\mathsf{Par}\left(\mathcal{T}_{h}\right)\right\rvert=2\left\lvert\mathsf{Par}\left(\mathcal{T}_{h-1}\right)\right\rvert+\binom{\left\lvert\mathsf{Par}\left(\mathcal{T}_{h-1}\right)\right\rvert}{2},$

where the first term in the right hand side comes from (a) and (b) while the
second term from (c). The same formula is in [26, p. 539], where it is
obtained by iterating Clifford theory; cf. Open Problem 8.13.

Now we introduce a total order between tree of partitions. That is, if
$(\Lambda,\mathcal{Q})$ and $(\Gamma,\mathcal{N})$ are tree of partitions,
$(\Lambda,\mathcal{Q})$ associated to a tree composition
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$, with quotient
$\alpha\colon\mathcal{P}\rightarrow\mathcal{Q}$ and $(\Gamma,\mathcal{N})$
associated to $\varphi\in\mathsf{C}(\mathcal{S},\mathcal{M})$, with quotient
$\beta\colon\mathcal{M}\rightarrow\mathcal{N}$ ($\mathcal{T}$, $\mathcal{S}$
are not necessarily isomorphic, nor of the same height) we need to compare
them by means of a total order $<$. We will write simply $\Gamma<\Lambda$ and
the order $<$ will have the following property:

$\Lambda>\Gamma\;\text{ if the height of }\mathcal{Q}\text{ is greater than
the height of }\mathcal{N}.$ (4.14)

Moreover, $<$ will actually be an order between isomorphism classes of trees
of partitions (that is, it will be invariant with respect to isomorphisms) and
we will write $\Lambda\equiv\Gamma$ to indicate that $(\Lambda,\mathcal{Q})$
and $(\Gamma,\mathcal{N})$ are isomorphic.

We define the order by induction on $h$, the maximum height of the trees. If
$h=1$ a tree of partition is just one numerical partition as in Example 2.7
and we use the lexicographic order between numerical partitions. We specify it
because we need to compare also partitions of different integers: the standard
definitions usually involves partitions of the same integer; see [21, 1.4.5]
or [28, p. 222]. If $\lambda=(\lambda_{1},\lambda_{2}.\dotsc,\lambda_{k})$ and
$\mu=(\mu_{1},\mu_{2},\dotsc,\mu_{l})$ are distinct partitions then we write
$\lambda>\mu$ if one of the following cases is verified:

  * •

there exists and index $i$ such that
$\lambda_{1}=\mu_{1},\lambda_{2}=\mu_{2},\dotsc,\lambda_{i-1}=\mu_{i-1}$ and
$\lambda_{i}>\mu_{i}$;

  * •

$k>l$ and $\lambda_{i}=\mu_{i}$, $i=1,2,\dotsc,l$.

Assume now that $h\geq 2$ and that we have introduced a total order
$\geqq_{h-1}$ between trees of partitions of height $\leq h-1$. First of all,
we need to introduce an equivalence relation $\equiv^{\prime}$ and then a
total order $>^{\prime}$ between first level vertices of trees of partitions
of height $\leq h$. Suppose that $a\in V_{\mathcal{Q}}$, $b\in
V_{\mathcal{N}}$, where $(\Lambda,\mathcal{Q})$ and $(\Gamma,\mathcal{N})$ are
trees of partitions of height $\leq h$; note that we need to compare also two
vertices of the same tree, so that it is possible that $(\Lambda,\mathcal{Q})$
and $(\Gamma,\mathcal{N})$ are isomorphic. As usual, $\Lambda_{a}$ will denote
the restriction of $\Lambda$ to $\widetilde{\mathcal{Q}}_{a}$,
$a\in\mathcal{Q}$ internal (cf. (2.3)). That is, $\Lambda_{a}$ does not have a
value on $a$ because it is the root of $\mathcal{Q}_{a}$. Moreover, as
specified above, $\equiv_{h-1}$ will denote isomorphism of two tree of
partitions of height $\leq h-1$. This is the equivalence relation: we write
that

$a\equiv^{\prime}b$ (4.15)

when one of the following conditions is satisfied:

  * •

$a$ and $b$ are both leaves and $\lambda^{a}=\lambda^{b}$;

  * •

$a$ and $b$ are internal, $\Lambda_{a}\equiv_{h-1}\Gamma_{b}$ and
$\lambda^{a}=\lambda^{b}$.

In other words, $a=b$ means that we have an isomorphism between the tree of
partitions $\mathcal{Q}_{a}$ and $\mathcal{N}_{a}$ where also to the root is
associated a partition.

After that, we define the total order: if $a\not\equiv^{\prime}b$ we write
that

$a>^{\prime}b$ (4.16)

if one of the following conditions is verified:

  1. 1.

$a$ and $b$ are both leaves and $\lambda^{a}>\lambda^{b}$ with respect to the
total order (this is the case $h=1)$;

  2. 2.

$a$ is internal while $b$ is a leaf;

  3. 3.

$a$ and $b$ are internal and $\Lambda_{a}>_{h-1}\Gamma_{b}$;

  4. 4.

$\Lambda_{a}\equiv_{h-1}\Gamma_{b}$ but
$\left\lvert\lambda^{a}\right\rvert>\left\lvert\lambda^{b}\right\rvert$;

  5. 5.

$\Lambda_{a}\equiv_{h-1}\Gamma_{b}$,
$\left\lvert\lambda^{a}\right\rvert=\left\lvert\lambda^{b}\right\rvert$, but
$\lambda^{a}>\lambda^{b}$ in the lexicographic order for numerical partitions.

It is easy to check that $<^{\prime}$ is indeed a total order, more properly
it is an order between the equivalence classes of $\equiv^{\prime}$, but we
write it as in (4.16) in order to keep notation as simple as possible. Note
also that

  * •

by Theorem 4.5, $\Lambda_{a}\equiv_{h-1}\Gamma_{b}$ means that the tree
compositions $\varphi_{u}$, $u\in(\alpha\circ\varphi)^{-1}(a)$ and $\psi_{v}$,
$v\in(\beta\circ\psi)^{-1}(b)$ are equivalent;

  * •

$\Lambda_{a}\equiv_{h-1}\Gamma_{b}$ and
$\left\lvert\lambda^{a}\right\rvert=\left\lvert\lambda^{b}\right\rvert$ means
that the tree compositions $\varphi_{u}$, $u\in(\alpha\circ\varphi)^{-1}(a)$
and $\psi_{v}$, $v\in(\beta\circ\psi)^{-1}(b)$ are equivalent and that they
appear in the same number between the first level subtrees of $\mathcal{T}$
and $\mathcal{T}^{\prime}$;

  * •

$a\equiv^{\prime}b$ means that $\varphi_{u}$,
$u\in(\alpha\circ\varphi)^{-1}(a)$ and $\psi_{v}$,
$v\in(\beta\circ\psi)^{-1}(b)$ are equivalent, they apper in the same number
between the first level subtrees of $\mathcal{T}$ and $\mathcal{T}^{\prime}$
and are partitioned in the same way by the first level vertices respectively
in $\alpha^{-1}(a)$ and in $\beta^{-1}(b)$; cf. (4.8).

If $a,a^{\prime}\in V_{\mathcal{Q}}$, $a\neq a^{\prime}$, it is impossible
that $\Lambda_{a}\equiv_{h-1}\Lambda_{a^{\prime}}$, because, by Theorem
3.1(b), $a$ and $a^{\prime}$ corresponds to non equivalent tree compositions
$\varphi_{u}$, $u\in(\alpha\circ\varphi)^{-1}(a)$ and $\psi_{w}$,
$w\in(\alpha\circ\varphi)^{-1}(a^{\prime})$, so that, by Theorem 4.5, the tree
of partitions $\Lambda_{a}$ and $\Lambda_{a^{\prime}}$ are not isomorphic.
Therefore we may order the vertices of $V_{\mathcal{Q}}$ and $V_{\mathcal{N}}$
accordingly to $<^{\prime}$:

$V_{\mathcal{Q}}=\\{a_{1}>^{\prime}a_{2}>^{\prime}\dotsb>^{\prime}a_{l}\\}\quad\text{
and }\quad
V_{\mathcal{N}}=\\{b_{1}>^{\prime}b_{2}>^{\prime}\dotsb>^{\prime}b_{k}\\}.$

Finally, we set $\Lambda>_{h}\Gamma$

$\begin{split}&\bullet\text{ if }\;l>k,\;\text{ and
}a_{1}\equiv^{\prime}b_{1},a_{2}\equiv^{\prime}b_{2},\dotsc,a_{k}\equiv^{\prime}b_{k},\\\
&\bullet\text{ or if there exists }j\text{ such that
}a_{1}\equiv^{\prime}b_{1},a_{2}=^{\prime}b_{2},\dotsc,a_{j-1}\equiv^{\prime}b_{j-1}\text{
and }a_{j}>^{\prime}b_{j}.\end{split}$ (4.17)

Clearly, also $\geqq_{h}$ respect the condition in (4.14). Note also that if
$l=k$ and
$a_{1}\equiv^{\prime}b_{1},a_{2}\equiv^{\prime}b_{2},\dotsc,a_{l}\equiv^{\prime}b_{l}$
then $\Lambda\equiv\Gamma$ so that if $\Lambda\not\equiv\Gamma$ then
$\Lambda>\Gamma$ or $\lambda<\Gamma$.

Finally, note that, by Theorem 4.5, the order just introduced is actually an
order between equivalence classes of tree compositions. Therefore if $\varphi$
and $\psi$ are tree compositions and
$(\Lambda.\mathcal{Q}),(\Gamma,\mathcal{N})$ the respective tree of partitions
we will write

$\varphi\geqq\psi$ (4.18)

when $\Lambda\geqq\Gamma$, noting that in this case the equality in (4.18)
means that $\varphi$ and $\psi$ are equivalent and we write in
$\varphi\equiv\psi$ (again we are managing to keep notation as simple as
possible).

##  5 The conjugacy classes of $\mbox{\rm Aut}(\mathcal{T})$

This section is partially inspired to the classical theory of conjugacy
classes of wreath products; see [10, Section 2.3] and [21, Section 4.3]. But
now we need the new tool: the theory of tree compositions. In particular, the
construction of $\varphi^{g}$ in Example 2.2 will play a fundamental role.
Similar results for the automorphisms groups of infinite trees are in [16].

Let $g\in\mbox{\rm Aut}(\mathcal{T})$ and denote by $\pi$ its restriction to
$V_{\mathcal{T}}$. Suppose $\\{u,\pi(u),\dotsc,\pi^{\ell-1}(u)\\}$ is an orbit
of $\pi$ on $V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, with $\ell$ the
smallest positive integer such that $\pi^{\ell}(u)=u$. Set

$\left[g^{\ell}\right]_{u}\coloneqq g_{\pi^{\ell-1}(u)}\circ
g_{\pi^{\ell-2}(u)}\circ\dotsb\circ g_{\pi(u)}\circ g_{u}.$ (5.1)

By (2.7), $\left[g^{\ell}\right]_{u}\in\mbox{\rm Aut}(\mathcal{T}_{u})$; note
that (5.1) is just a particular notation for $g^{\ell}$ restricted to
$\mathcal{T}_{u}$, but when we use it we assume that $u$ is at the first level
and $\ell$ is the lenght of its $g$-orbit.

Now suppose that also $t\in\mbox{\rm Aut}(\mathcal{T})$ and denote by $\sigma$
the restriction of $t$ to $V_{\mathcal{T}}$. Then
$\sigma\circ\pi\circ\sigma^{-1}$ is the restriction of $tgt^{-1}$ to
$V_{\mathcal{T}}$ while from (2.7) and (2.8) we deduce that for $u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ we have:

$(tgt^{-1})_{u}=t_{\pi(\sigma^{-1}(u))}\circ
g_{\sigma^{-1}(u)}\circ\left(t_{\sigma^{-1}(u)}\right)^{-1}.$ (5.2)

######  Lemma 5.1.

With the notation above, for all $v\in V_{\mathcal{T}}\setminus
W_{\mathcal{T}}$ we have:

$\left[\left(tgt^{-1}\right)^{\ell}\right]_{\sigma(v)}=t_{v}\circ\left[g^{\ell}\right]_{v}\circ\left(t_{v}\right)^{-1}.$

###### Proof.

From (5.1) and (5.2) it follows that

$\begin{split}\left[\left(tgt^{-1}\right)^{\ell}\right]_{u}=&\left[t_{\pi^{\ell}(\sigma^{-1}(u))}\circ
g_{\pi^{\ell-1}(\sigma^{-1}(u))}\circ\left(t_{\pi^{\ell-1}(\sigma^{-1}(u))}\right)^{-1}\right]\circ\dotsb\circ\\\
&\circ\left[t_{\pi^{2}(\sigma^{-1}(u))}\circ
g_{\pi(\sigma^{-1}(u))}\circ\left(t_{\pi(\sigma^{-1}(u))}\right)^{-1}\right]\circ\left[t_{\pi(\sigma^{-1}(u))}\circ
g_{\sigma^{-1}(u)}\circ\left(t_{\sigma^{-1}(u)}\right)^{-1}\right]\\\
=&t_{\sigma^{-1}(u)}\circ\left[g^{\ell}\right]_{\sigma^{-1}(u)}\circ\left(t_{\sigma^{-1}(u)}\right)^{-1}.\end{split}$

Finally, set $v\coloneqq\sigma^{-1}(u)$. ∎

For $g\in\mbox{\rm Aut}(\mathcal{T})$ denote by $U_{g}$ a set of
representatives for the orbits of $g$ on $V_{\mathcal{T}}\setminus
W_{\mathcal{T}}$.

######  Lemma 5.2.

Let $g$ be as above and suppose that also $g^{\prime}\in\mbox{\rm
Aut}(\mathcal{T})$, with $\pi^{\prime}$ the restriction of $g^{\prime}$ to
$V_{\mathcal{T}}$. Then $g$ and $g^{\prime}$ are conjugate in $\mbox{\rm
Aut}(\mathcal{T})$ if and only if both the following conditions are verified

  1. (a)

$\pi,\pi^{\prime}$ are conjugate in $\mbox{\rm
Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}$:
$\pi^{\prime}=\sigma\circ\pi\circ\sigma^{-1}$ with $\sigma\in\mbox{\rm
Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}$ (cf. (3.25));

  2. (b)

for every $v\in U_{g}$ there exists an isomorphism
$t_{v}\colon\mathcal{T}_{v}\rightarrow\mathcal{T}_{\sigma(v)}$ ($\sigma$ as in
(a)) such that

$\left[\left(g^{\prime}\right)^{\ell}\right]_{\sigma(v)}=t_{v}\circ\left[g^{\ell}\right]_{v}\circ\left(t_{v}\right)^{-1}.$
(5.3)

###### Proof.

The only if part follows from Lemma 5.1. Now suppose that (5.3) is verified
for all $v\in U_{g}$. We define the isomorphisms
$t_{\pi^{k}(v)}\colon\mathcal{T}_{\pi^{k}(v)}\rightarrow\mathcal{T}_{\sigma(\pi^{k}(v))}$
by setting inductively

$t_{\pi^{k}(v)}\coloneqq g^{\prime}_{\sigma(\pi^{k-1}(v))}\circ
t_{\pi^{k-1}(v)}\circ\left(g_{\pi^{k-1}(v)}\right)^{-1},$ (5.4)

for $k=1,2,\dotsc,\ell-1$, where $\ell$ is the cardinality of the $\pi$-orbit
of $v$. Note that (5.4) is just (5.2) with $tgt^{-1}$ replaced by $g^{\prime}$
and $u=\sigma(\pi^{k-1}(v))$ so that we have just to verify (5.2) also in the
case $k=\ell$, which is the relation involving $g_{\pi^{\ell-1}(v)}$ and
$g^{\prime}_{\sigma(\pi^{\ell-1}(v))}$. This will be achieved by using (5.3)
as a compatibility condition:

$\displaystyle\left[g^{\ell}\right]_{v}=$ $\displaystyle
g_{\pi^{\ell-1}(v)}\circ g_{\pi^{\ell-2}(v)}\circ\dotsb\circ g_{\pi(v)}\circ
g_{v}$ $\displaystyle(\text{by }\eqref{defXi})$ $\displaystyle=$
$\displaystyle
g_{\pi^{\ell-1}(v)}\circ\left[\left(t_{\pi^{\ell-1}(v)}\right)^{-1}\circ
g^{\prime}_{\sigma(\pi^{\ell-2}(v))}\circ t_{\pi^{\ell-2}(v)}\right]\circ$
$\displaystyle\circ\left[\left(t_{\pi^{\ell-2}(v)}\right)^{-1}\circ
g^{\prime}_{\sigma(\pi^{\ell-3}(v))}\circ t_{\pi^{\ell-2}(v)}\right]\circ$
$\displaystyle\circ\dotsb\circ\left[\left(t_{\pi^{2}(v)}\right)^{-1}\circ
g^{\prime}_{\sigma(\pi(v))}\circ
t_{\pi(v)}\right]\circ\left[\left(t_{\pi(v)}\right)^{-1}\circ
g^{\prime}_{\sigma(v)}\circ t_{v}\right]$ $\displaystyle(\text{by
}\eqref{congtgt4})$ $\displaystyle=$ $\displaystyle
g_{\pi^{\ell-1}(v)}\circ\left(t_{\pi^{\ell-1}(v)}\right)^{-1}\circ
g^{\prime}_{\sigma(\pi^{\ell-2}(v))}\circ\dotsb\circ
g^{\prime}_{\sigma(\pi(v))}\circ g^{\prime}_{\sigma(v)}\circ t_{v}$
$\displaystyle=$ $\displaystyle
g_{\pi^{\ell-1}(v)}\circ\left(t_{\pi^{\ell-1}(v)}\right)^{-1}\circ\left(g^{\prime}_{\sigma(\pi^{\ell-1}(v))}\right)^{-1}\circ\left[\left(g^{\prime}\right)^{\ell}\right]_{\sigma(v)}\circ
t_{v}$ $\displaystyle(\text{by }\eqref{defXi})$ $\displaystyle=$
$\displaystyle
g_{\pi^{\ell-1}(v)}\circ\left(t_{\pi^{\ell-1}(v)}\right)^{-1}\circ\left(g^{\prime}_{\sigma(\pi^{\ell-1}(v))}\right)^{-1}\circ
t_{v}\circ\left[g^{\ell}\right]_{v}.$ $\displaystyle(\text{by
}\eqref{congtgt3})$

Therefore

$g^{\prime}_{\sigma(\pi^{\ell-1}(v))}=t_{v}\circ
g_{\pi^{\ell-1}(v)}\circ\left(t_{\pi^{\ell-1}(v)}\right)^{-1}$

which ends the proof of (5.2) in all cases so that, defining $t$ by means of
$\sigma$ and the $t_{u}$’s, $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$,
we get $tgt^{-1}=g^{\prime}$. ∎

######  Proposition 5.3.

With the notation in (2.11) and (5.1), for all $u\in V_{\mathcal{T}}\setminus
W_{\mathcal{T}}$ we have
$(\varphi^{g})_{u}=\varphi^{\left[g^{\ell}\right]_{u}}$.

###### Proof.

Since $g$ sends $\mathcal{T}_{\pi^{j}(u)}$ to $\mathcal{T}_{\pi^{j+1}(u)}$,
then $u^{\prime},v^{\prime}\in\mathcal{T}_{u}$ belong to the same $g$-orbit if
and only if $v^{\prime}=g^{k}(u^{\prime})$ with $k$ a multiple of $\ell$. By
(5.1) this happens if and only if
$\left(\left[g^{\ell}\right]_{u}\right)^{k/\ell}(u^{\prime})=v^{\prime}$, that
is if and only if $u^{\prime},v^{\prime}$ belongs to the same
$\left[g^{\ell}\right]_{u}$-orbit. ∎

######  Theorem 5.4.

  1. (a)

Two elements $g,g^{\prime}\in\mbox{\rm Aut}(\mathcal{T})$ are conjugate if and
only if the corresponding tree compositions $\varphi^{g}$ and
$\varphi^{g^{\prime}}$ are equivalent.

  2. (b)

For every compositional tree $\mathcal{P}$ of $\mathcal{T}$ and for every
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ there exists $g\in\mbox{\rm
Aut}(\mathcal{T})$ such that $\varphi^{g}=\psi$.

###### Proof.

  1. (a)

Suppose that $g,g^{\prime}$ are conjugate: there exists $t\in\mbox{\rm
Aut}(\mathcal{T})$ such that $g^{\prime}=tgt^{-1}$. We define a tree
isomorphism $\gamma\colon\mathcal{P}^{g}\rightarrow\mathcal{P}^{g^{\prime}}$
by means of the natural correspondence between $g$-orbits and
$g^{\prime}$-orbits: if $\mathcal{P}^{g}\ni
x=\\{u,g(u),\dotsc,g^{\ell-1}(u)\\}$ we set

$\begin{split}\gamma(x)\coloneqq x^{\prime}\quad\text{ where
}\quad\mathcal{P}^{g^{\prime}}\ni
x^{\prime}=&\\{t(u),t(g(u)),\dotsc,t(g^{\ell-1}(u))\\}\\\
\equiv&\\{t(u),g^{\prime}(t(u)),\dotsc,(g^{\prime})^{\ell-1}(t(u))\\}.\end{split}$

Then we have
$\left(\gamma\circ\varphi^{g}\right)(u)=x^{\prime}=\left(\varphi^{g^{\prime}}\circ
t\right)(u)$, that is $\gamma\circ\varphi^{g}=\varphi^{g^{\prime}}\circ t$ and
$\varphi^{g}$ is equivalent to $\varphi^{g^{\prime}}$.

Conversely, suppose that $\varphi^{g}$ and $\varphi^{g^{\prime}}$ are
equivalent: there exist $\beta\in\mbox{\rm Aut}(\mathcal{T})$ and a tree
isomorphism $\gamma\colon\mathcal{P}^{g}\rightarrow\mathcal{P}^{g^{\prime}}$
such that the following diagram is commutative:

$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta}$$\scriptstyle{\varphi^{g}}$$\textstyle{\mathcal{P}^{g}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\textstyle{\
\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{g^{\prime}}}$$\textstyle{\mathcal{P}^{g^{\prime}}}$
(5.5)

Suppose that $\pi,\pi^{\prime}$ and $U_{g}$ are as in Lemma 5.2. The proof is
by induction on $h\coloneqq H(\mathcal{T})$. For $h=1$ it is obvious but we
need to precise some facts. Choose $u\in U_{g}$ and set
$x\coloneqq\varphi^{g}(u)$, so that $\left(\varphi^{g}\right)^{-1}(x)$ is the
$\pi$-orbit of $u$. The $\beta$-image of $\left(\varphi^{g}\right)^{-1}(x)$ is
$\left(\varphi^{g^{\prime}}\right)^{-1}(\gamma(x))$, the $\pi^{\prime}$-orbit
of $\beta(u)$. Therefore these orbits are cyclic permutations of the same
lenght, say $\ell$, so that there exists a bijection
$\sigma_{u}\colon\left(\varphi^{g}\right)^{-1}(x)\rightarrow\left(\varphi^{g^{\prime}}\right)^{-1}(\gamma(x))$
such that $\sigma_{u}\left(\pi^{k}(u)\right)=\pi^{\prime k}(\sigma_{u}(u)))$,
$k=0,1,\dotsc,\ell-1$; we may also require that $\sigma(u)=\beta(u)$. The set
of all $\sigma_{u},u\in U_{g}$, define a permutation of $V_{\mathcal{T}}$ such
that $\sigma\circ\pi\circ\sigma^{-1}=\pi^{\prime}$, with the further property
$\sigma\Bigl{(}\left(\varphi^{g}\right)^{-1}(x)\Bigr{)}=\left(\varphi^{g^{\prime}}\right)^{-1}(\gamma(x))$,
which implies that $\gamma\circ\varphi^{g}=\varphi^{g^{\prime}}\circ\sigma$.

Now suppose that $h\geq 2$. Arguing as in the case $h=1$ we may construct a
permutation $\sigma\in\mbox{\rm Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}$
such that

$\sigma\circ\pi\circ\sigma^{-1}=\pi^{\prime},\quad\left(\gamma\rvert_{V_{\mathcal{T}}}\right)\circ\left(\varphi^{g}\rvert_{V_{\mathcal{T}}}\right)=\left(\varphi^{g^{\prime}}\rvert_{V_{\mathcal{T}}}\right)\circ\sigma\quad\text{and}\quad\sigma(u)=\beta(u)\text{
for all }u\in U_{g}.$

We have just to notice that now each $\sigma_{u}\in\mbox{\rm
Aut}(\mathcal{T})\rvert_{V_{\mathcal{T}}}$ because all the subtrees

$\mathcal{T}_{v},\quad
v\in\left(\varphi^{g}\right)^{-1}(x)\bigcup\left(\varphi^{g^{\prime}}\right)^{-1}(\gamma(x)),$

are isomorphic; cf. (3.25). Now consider the automorphism
$\beta^{-1}g^{\prime}\beta$. By the first (the only if) part of the proof,
$\varphi^{g^{\prime}}$ and $\varphi^{\beta^{-1}g^{\prime}\beta}$ are
equivalent and there exists a tree isomorphism
$\gamma^{\prime}\colon\mathcal{P}^{g^{\prime}}\rightarrow\mathcal{P}^{\beta^{-1}g^{\prime}\beta}$
such that