$\gamma^{\prime}\circ\varphi^{g^{\prime}}=\varphi^{\beta^{-1}g^{\prime}\beta}\circ\beta^{-1}.$
(5.6)

By transitivity, also $\varphi^{g}$ and $\varphi^{\beta^{-1}g^{\prime}\beta}$
are equivalent; in particular, for all $u\in U_{g}$, setting
$x\coloneqq\varphi^{g}(u)$, $x^{\prime}\coloneqq\gamma(x)$, we have

$\displaystyle\gamma^{\prime}_{x^{\prime}}\circ\gamma_{x}\circ\left(\varphi^{g}\right)_{u}=$
$\displaystyle\gamma^{\prime}_{x^{\prime}}\circ\left(\varphi^{g^{\prime}}\right)_{\beta(u)}\circ\beta_{u}$
$\displaystyle(\text{by }\eqref{firstldell2}\text{ and }\eqref{stardiagp25})$
$\displaystyle=$
$\displaystyle\left(\varphi^{\beta^{-1}g^{\prime}\beta}\right)_{u},$
$\displaystyle(\text{by }\eqref{phigammap26})$

that is $\left(\varphi^{g}\right)_{u}$ and
$\left(\varphi^{\beta^{-1}g^{\prime}\beta}\right)_{u}$ are isomorphic, so that
also equivalent. By Proposition 5.3, also

$\varphi^{\left[g^{\ell}\right]_{u}}\qquad\text{ and
}\qquad\varphi^{\left[\left(\beta^{-1}g^{\prime}\beta\right)^{\ell}\right]_{u}}$

are equivalent. Now we may invoke the inductive hypothesis: there exists
$\widetilde{t}_{u}\in\mbox{\rm Aut}(\mathcal{T}_{u})$ such that:
$\widetilde{t}_{u}\circ\left[g^{\ell}\right]_{u}\circ\left(\widetilde{t}_{u}\right)^{-1}=\left[(\beta^{-1}g^{\prime}\beta)^{\ell}\right]_{u}$.
Therefore, from Lemma 5.1 we deduce that

$\widetilde{t}_{u}\circ\left[g^{\ell}\right]_{u}\circ\left(\widetilde{t}_{u}\right)^{-1}=\left(\beta^{-1}\right)_{\beta(u)}\circ\left[(g^{\prime})^{\ell}\right]_{\beta(u)}\circ\left[\left(\beta^{-1}\right)_{\beta(u)}\right]^{-1},$

and since $\sigma(u)=\beta(u)$ finally we have

$t_{u}\circ\left[g^{\ell}\right]_{u}\circ(t_{u})^{-1}=\left[(g^{\prime})^{\ell}\right]_{\sigma(u)},\quad\text{
for all }u\in U_{g},$

if we set
$t_{u}\coloneqq\left[\left(\beta^{-1}\right)_{\beta(u)}\right]^{-1}\circ\widetilde{t}_{u}\equiv\beta_{u}\circ\widetilde{t}_{u}$
(cf. (2.8)). We end the proof by invoking Lemma 5.2

  2. (b)

By induction on $h$. If $h=1$ this is trivial, but we need to fix the
notation. Suppose that $\psi\colon V_{\mathcal{T}}\rightarrow V_{\mathcal{P}}$
is a surjective map, for every $x\in V_{\mathcal{P}}$ fix
$u_{x}\in\psi^{-1}(x)$ and choose an arbitrary cycle $\pi_{x}$ in
$\psi^{-1}(x)$, say
$u_{x}\rightarrow\pi_{x}(u_{x})\rightarrow\dotsb\rightarrow\left(\pi_{x}\right)^{\ell_{x}-1}(u_{x})\rightarrow
u_{x}$, where $\ell_{x}\coloneqq\left\lvert\psi^{-1}(x)\right\rvert$. Then the
product $\pi\coloneqq\prod_{x\in V_{\mathcal{P}}}\pi_{x}$ yields a permutation
whose associated composition is $\psi$.

Now suppose that $h\geq 2$. We denote by $\tau_{u,v}$ the $\tau$’s of $\psi$
(cf. Theorem 3.1); actually, we will use just the $\tau$’s at the first level
and in the case $\psi(u)=\psi(v)$, when $\omega_{x,x}$ is the identity and we
have strict equivalence as in (2.9). Then we argue as in the case $h=1$ at the
first level: we use the same notation and we construct the $\pi_{x}$’s and
their product $\pi$. After that we apply induction to each subtree
$\mathcal{T}_{u_{x}}$, $x\in V_{\mathcal{P}}\setminus W_{\mathcal{P}}$,
getting automorphisms $\widetilde{g}_{x}\in\mbox{\rm
Aut}(\mathcal{T}_{u_{x}})$ such that

$\varphi^{\widetilde{g}_{x}}=\psi_{u_{x}}.$ (5.7)

Then for every $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ we define an
isomorphisms $g_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{\pi(u)}$ by
setting

$g_{\pi^{k}(u_{x})}\coloneqq\tau_{\pi^{k+1}(u_{x}),u_{x}}\circ\widetilde{g}_{x}\circ\tau_{u_{x},\pi^{k}(u_{x})}$
(5.8)

for all $x\in V_{\mathcal{P}}\setminus W_{\mathcal{P}}$ and
$k=0,1,\dotsc,\ell_{x}-1$. At this point, we can define $g\in\mbox{\rm
Aut}(\mathcal{T})$ by means of (2.6), using $\pi$ at the first level and the
$g_{u}$’s. By the case $h=1$ we have
$\psi\rvert_{V_{\mathcal{T}}}=\varphi^{g}\rvert_{V_{\mathcal{T}}}$. Moreover,
for every $x\in V_{\mathcal{P}}\setminus W_{\mathcal{P}}$, we have:

$\displaystyle\left[g^{\ell_{x}}\right]_{u_{x}}=$ $\displaystyle
g_{\pi^{\ell_{x}-1}(u_{x})}\circ g_{\pi^{\ell_{x}-2}(u_{x})}\circ\dotsb\circ
g_{\pi(u_{x})}\circ g_{u_{x}}$ $\displaystyle(\text{by }\eqref{defXi})$
$\displaystyle=$ $\displaystyle\widetilde{g}_{x}$ $\displaystyle(\text{by
}\eqref{proptau2b}\text{ and }\eqref{defgpik})$

and therefore

$\displaystyle\left(\varphi^{g}\right)_{u_{x}}=$
$\displaystyle\varphi^{\left[g^{\ell_{x}}\right]_{u_{x}}}$
$\displaystyle(\text{by Proposition }\ref{Propconj})$ $\displaystyle=$
$\displaystyle\varphi^{\widetilde{g}_{x}}$
$\displaystyle(\left[g^{\ell_{x}}\right]_{u_{x}}=\widetilde{g}_{x})$
$\displaystyle=$ $\displaystyle\psi_{u_{x}}$ $\displaystyle(\text{by
}\eqref{phipsigux})$

and finally

$\displaystyle\left(\varphi^{g}\right)_{\pi^{k}(u_{x})}=$
$\displaystyle\left(\varphi^{g}\right)_{u_{x}}\circ\left[(g^{k})_{u_{x}}\right]^{-1}$
$\displaystyle(\text{by }\eqref{starp25May})$ $\displaystyle=$
$\displaystyle\left(\varphi^{g}\right)_{u_{x}}\circ\left(\widetilde{g}_{x}\right)^{-k}\circ\tau_{u_{x},\pi^{k}(u_{x})}$
$\displaystyle(\text{by }\eqref{firstldell2},\eqref{proptau2b}\text{ and
}\eqref{defgpik})$ $\displaystyle=$
$\displaystyle\psi_{u_{x}}\circ\tau_{u_{x},\pi^{k}(u_{x})}$
$\displaystyle(\text{by
}\left(\varphi^{g}\right)_{u_{x}}=\varphi^{\widetilde{g}_{x}}\text{ and
}\varphi^{\widetilde{g}_{x}}\circ\widetilde{g}_{x}=\varphi^{\widetilde{g}_{x}})$
$\displaystyle=$ $\displaystyle\psi_{\pi^{k}(u_{x})}.$ $\displaystyle(\text{by
}\eqref{diagTRSuv2})$

This ends the proof that $\varphi^{g}=\psi$.

∎

######  Corollary 5.5.

There is a natural bijection between the set of all conjugacy classes of
$\mbox{\rm Aut}(\mathcal{T})$ and $\mathsf{Par}(\mathcal{T})$ (cf. Definition
4.7). It is obtained by associating to every conjugacy class $C$ of $\mbox{\rm
Aut}(\mathcal{T})$ the tree of partition $(\Lambda,\mathcal{Q})$ representing
the equivalence class of tree compositions $\left\\{\varphi^{g}\colon g\in
C\right\\}$.

###### Proof.

It follows immedately from Theorem 4.5 and Theorem 5.4. ∎

We recall that a group $G$ is ambivalent when every element of $G$ is
conjugate to its inverse.

######  Corollary 5.6.

The group $\mbox{\rm Aut}(\mathcal{T})$ is ambivalent.

###### Proof.

Just note that $\varphi^{g}=\varphi^{g^{-1}}$ because $g$ and $g^{-1}$ have
the same orbits on $\mathcal{T}$. ∎

The following corollary has an obvious elementary proof but we prefer to
deduce it from the theory of this section.

######  Corollary 5.7.

The group $\mbox{\rm Aut}(\mathcal{T})$ is trivial if and only if
$\mathcal{T}$ has only the identity composition.

######  Example 5.8.

It is easy to check that, in the notation of Example 4.4, $\Lambda_{\text{\rm
id}}$ represents the trivial conjugacy class $\\{\mbox{\rm
id}_{\mathcal{T}}\\}$ while $\Lambda_{\text{\rm tv}}$ represents the conjugacy
class made up of all those $g\in\mbox{\rm Aut}(\mathcal{T})$ which are
transitive on each level of the tree (spherically transitive automorphisms).
See also [3, Theorem (4.6)], where the fact that the spherically transitive
automorphisms form a single conjugacy class is proved for infinite spherically
homogeneous trees.

##  6 Common refinements of tree compositions

If $V$ is a set and $V=\bigsqcup_{i=1}^{n}A_{i}=\bigsqcup_{j=1}^{m}B_{j}$ are
two compositions of $V$ a refinement of them is a composition
$V=\bigsqcup_{k=1}^{l}C_{k}$ such that for every $1\leq k\leq l$ there exists
$i,j$ such that $C_{k}\subseteq A_{i}\cap B_{j}$. Their intersection
composition is given by $V=\bigsqcup_{A_{i}\cap B_{j}\neq\emptyset}(A_{i}\cap
B_{j})$ and every refinement of them is also a refinement of their
intersection composition. In the following example, we describe these
elementary facts in our “arrow style” in order to prepare the reader for the
case of tree compositions.

######  Example 6.1.

Suppose that $V,A,X,Y$ are sets and that we have the following commutative
diagram of surjective maps:

$\textstyle{X}$$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta}$$\scriptstyle{\tau}$$\textstyle{Y}$

Then

$V=\underbrace{\bigsqcup_{a\in
A}\delta^{-1}(a)}_{(*)}=\underbrace{\bigsqcup_{x\in
X}\varphi^{-1}(x)}_{(**)}=\underbrace{\bigsqcup_{y\in Y}\psi^{-1}(y)}_{(***)}$
(6.1)

are compositions of $V$; cf. Example 2.7. Moreover, for all $x\in X,y\in Y$,

$\begin{split}\varphi^{-1}(x)\cap\psi^{-1}(y)=&\delta^{-1}(\theta^{-1}(x))\cap\delta^{-1}(\tau^{-1}(y))\\\
=&\delta^{-1}\left[\theta^{-1}(x)\cap\tau^{-1}(y)\right]\\\
=&\bigsqcup_{a\in\theta^{-1}(x)\cap\tau^{-1}(y)}\delta^{-1}(a).\end{split}$
(6.2)

We set

$A^{\prime}\coloneqq\\{(x,y)\in X\times
Y\colon\varphi^{-1}(x)\cap\psi^{-1}(y)\neq\emptyset\\}$ (6.3)

and define the map $\varepsilon\colon V\rightarrow A^{\prime}$ by setting, for
all $v\in V$,

$\varepsilon(v)=(x,y)\quad\text{ if }\quad
v\in\varphi^{-1}(x)\cap\psi^{-1}(y),$ (6.4)

and also $\vartheta^{\prime}\colon A^{\prime}\rightarrow X$ by setting, for
all $(x,y)\in A^{\prime}$, $\vartheta^{\prime}(x,y)=x$, $\tau^{\prime}\colon
A^{\prime}\rightarrow Y$ by setting, $\tau^{\prime}(x,y)=y$, and finally
$\gamma\colon A\rightarrow A^{\prime}$ by setting

$\gamma(a)=(x,y)\quad\text{ if }\quad a\in\theta^{-1}(x)\cap\tau^{-1}(y).$

Then

$V=\bigsqcup_{(x,y)\in
A^{\prime}}\left[\varphi^{-1}(x)\cap\psi^{-1}(y)\right]\equiv\bigsqcup_{(x,y)\in
A^{\prime}}\varepsilon^{-1}(x,y)$ (6.5)

is the intersection composition of $(**)$ and $(***)$ in (6.1). From (6.2) we
get:

$V=\bigsqcup_{(x,y)\in
A^{\prime}}\;\bigsqcup_{a\in\gamma^{-1}(x,y)}\delta^{-1}(a)$

which is a refinement of (6.5) and coincides with $(*)$ in (6.1), because

$A=\bigsqcup_{(x,y)\in A^{\prime}}\gamma^{-1}(x,y).$

We have illustrated the obvious fact that every common refinement of $(**)$
and $(***)$ in (6.1) is also a refinement of (6.5) and we have the following
commutative diagram of surjective maps:

$\textstyle{X}$$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon}$$\scriptstyle{\delta}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\scriptstyle{\vartheta}$$\scriptstyle{\tau}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta^{\prime}}$$\scriptstyle{\tau^{\prime}}$$\textstyle{Y}$
(6.6)

From Definition 2.4.1 it follows that a refinement of
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ is another tree composition
$\varepsilon\in\mathsf{C}(\mathcal{P},\mathcal{R})$ with a tree composition
$\vartheta\in\mathsf{C}(\mathcal{R},\mathcal{P})$ such that the following
diagram is commutative:

$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\varepsilon}$$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{R}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta}$

######  Definition 6.2.

Given two tree compositions $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$
and $\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$, of the same tree
$\mathcal{T}$, a common refinement of the couple $(\varphi,\psi)$ is a tree
composition $\varepsilon\in\mathsf{C}(\mathcal{T},\mathcal{R})$ together with
two tree compositions $\vartheta\in\mathsf{C}(\mathcal{R},\mathcal{P})$ and
$\tau\in\mathsf{C}(\mathcal{R},\mathcal{M})$ such that the following diagram
is commutative:

$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{\mathcal{R}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta}$$\scriptstyle{\tau}$$\textstyle{\mathcal{M}}$
(6.7)

A common refinement is trivial when $\mathcal{R}\equiv\mathcal{T}$ and
$\varepsilon\in\mbox{\rm Aut}(\mathcal{T})$; in particular, common refinements
always exist. Given two couples of tree compositions

---
$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{\mathcal{T}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{\prime}}$$\scriptstyle{\psi^{\prime}}$$\textstyle{\mathcal{M}}$$\textstyle{\mathcal{M}}$
(6.8)

the common refinements $\varepsilon\in\mathsf{C}(\mathcal{T},\mathcal{R})$ (of
$(\varphi,\psi)$) and
$\varepsilon^{\prime}\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{R}^{\prime})$
(of $(\varphi^{\prime},\psi^{\prime})$) are equivalent if there exist tree
isomorphisms $\zeta\colon\mathcal{T}\rightarrow\mathcal{T}^{\prime}$ and
$\gamma\colon\mathcal{R}\rightarrow\mathcal{R}^{\prime}$ such that the
following diagram is commutative:

$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta}$$\scriptstyle{\varphi}$$\scriptstyle{\varepsilon}$$\scriptstyle{\psi}$$\textstyle{\mathcal{R}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\scriptstyle{\vartheta}$$\scriptstyle{\tau}$$\textstyle{\mathcal{T}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi^{\prime}}$$\scriptstyle{\varepsilon^{\prime}}$$\scriptstyle{\varphi^{\prime}}$$\textstyle{\mathcal{R}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau^{\prime}}$$\scriptstyle{\vartheta^{\prime}}$$\textstyle{\mathcal{M}}$
(6.9)

If $\mathcal{R}=\mathcal{R}^{\prime}$, $\vartheta=\vartheta^{\prime}$,
$\tau=\tau^{\prime}$ and $\gamma$ is the identity of $\mbox{\rm
Aut}(\mathcal{R})$ we say that they are strictly equivalent. Clearly, if
$\varepsilon$ and $\varepsilon^{\prime}$ are equivalent as in (6.9) then
$\gamma\circ\varepsilon$ and $\varepsilon^{\prime}$ are strictly equivalent.

The couples $(\varphi,\psi)$ and $(\varphi^{\prime},\psi^{\prime})$ in (6.8)
are strictly equivalent if there exists an isomorphism
$\zeta\colon\mathcal{T}\rightarrow\mathcal{T}^{\prime}$ such that the
following diagram is commutative:

$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{\mathcal{T}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{\prime}}$$\scriptstyle{\psi^{\prime}}$$\textstyle{\mathcal{M}}$
(6.10)

######  Proposition 6.3.

The couples in (6.8) are strictly equivalent if and only if every common
refinement of one couple is equivalent to a common refinement of the other
couple, as in (6.9). Moreover, if this is the case, then we may take the same
$\zeta$ in (6.10) and in (6.9).

###### Proof.

For the if part, just note that the diagram (6.10) is part of (6.9). For the
only if part, assume the existence of $\zeta$ and the commutativity of (6.10).
Take $\varepsilon\in\mathsf{C}(\mathcal{T},\mathcal{R})$, a common refinement
of $\varphi$ and $\psi$ as in (6.7). Define
$\varepsilon^{\prime}\colon\mathcal{T}^{\prime}\rightarrow\mathcal{R}$ by
setting $\varepsilon^{\prime}\coloneqq\varepsilon\circ\zeta^{-1}$, take
$\mathcal{R}^{\prime}=\mathcal{R}$, $\gamma=$ the identity and set
$\vartheta^{\prime}\coloneqq\vartheta$, $\tau^{\prime}\coloneqq\tau$. Then

$\vartheta^{\prime}\circ\varepsilon^{\prime}=\vartheta\circ\varepsilon\circ\zeta^{-1}=\varphi\circ\zeta^{-1}=\varphi^{\prime}\qquad\text{
and
}\qquad\tau^{\prime}\circ\varepsilon^{\prime}=\tau\circ\varepsilon\circ\zeta^{-1}=\psi\circ\zeta^{-1}=\psi^{\prime}$

and we have two equivalent common refinements. ∎

######  Remark 6.4.

Suppose that we have a common refinement as in (6.7) and that
$w,v\in\mathcal{T}$ are distinct vertices such that
$\varepsilon(v)=\varepsilon(w)\eqqcolon a$. Then we have the following strict
equivalence of common refinements:

$\textstyle{\mathcal{P}_{\vartheta(a)}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta}$$\scriptstyle{\varphi_{v}}$$\scriptstyle{\varepsilon_{v}}$$\scriptstyle{\psi_{v}}$$\textstyle{\mathcal{R}_{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta_{a}}$$\scriptstyle{\tau_{a}}$$\textstyle{\mathcal{T}_{w}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{w}}$$\scriptstyle{\varepsilon_{w}}$$\scriptstyle{\varphi_{w}}$$\textstyle{\mathcal{M}_{\tau(a)}}$
(6.11)

Indeed, we can use the isomorphism
$\zeta\colon\mathcal{T}_{v}\rightarrow\mathcal{T}_{w}$ given by the tree
composition $\varepsilon$ (cf. the regularity condition in Definition 2.1). In
particular, the couples $(\varphi_{v},\psi_{v})$ and $(\varphi_{w},\psi_{w})$
are strictly equivalent.

######  Remark 6.5.

In the notation of Example 6.1, suppose that $\varphi^{\prime}\colon
V\rightarrow X$, $\psi^{\prime}\colon V\rightarrow Y$ is another couple of
surjective maps and set

$A^{\prime\prime}\coloneqq\\{(x,y)\in X\times
Y\colon(\varphi^{\prime})^{-1}(x)\cap(\psi^{\prime})^{-1}(y)\neq\emptyset\\}.$

Then $(\varphi,\psi)$ and $(\varphi^{\prime},\psi^{\prime})$ are strictly
equivalent (cf. (6.10)) if and only if

$\left\lvert\varphi^{-1}(x)\cap\psi^{-1}(y)\right\rvert=\left\lvert(\varphi^{\prime})^{-1}(x)\cap(\psi^{\prime})^{-1}(y)\right\rvert,\quad\text{for
all }(x,y)\in X\times Y.$ (6.12)

Indeed, if this is the case, we can define $\pi\in\mbox{\rm Sym}(V)$ in such a
way that

$\pi\left[\varphi^{-1}(x)\cap\psi^{-1}(y)\right]=(\varphi^{\prime})^{-1}(x)\cap(\psi^{\prime})^{-1}(y),$
(6.13)

for all $(x,y)\in A^{\prime}\equiv A^{\prime\prime}$. Note also that (6.12)
implies that the common refinements of $(\varphi,\psi)$ and
$(\varphi^{\prime},\psi^{\prime})$, given by $A^{\prime}\equiv
A^{\prime\prime}$, are strictly equivalent. Indeed, if we define $\delta\colon
V\rightarrow A^{\prime}$ by setting $\delta(v)=(x,y)$, for all
$v\in(\varphi^{\prime})^{-1}(x)\cap(\psi^{\prime})^{-1}(y)$, we have the
commutative diagram

$\textstyle{X}$$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi}$$\scriptstyle{\varepsilon}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta^{\prime}}$$\scriptstyle{\tau^{\prime}}$$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta}$$\scriptstyle{\psi^{\prime}}$$\scriptstyle{\varphi^{\prime}}$$\textstyle{Y}$

######  Theorem 6.6.

Given two tree compositions $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$
and $\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ then there exists a common
refinement as in (6.7) such that the following coarseness condition is
verified (cf. Remark 6.4): if $a,b\in\mathcal{R}$ are distinct siblings,
$\vartheta(a)=\vartheta(b)\eqqcolon x$, $\tau(a)=\tau(b)\eqqcolon y$,
$u,v\in\mathcal{T}$ and

$\varepsilon(u)=a,\qquad\qquad\qquad\varepsilon(v)=b,$ (6.14)

then the common refinements

---
$\textstyle{\mathcal{P}_{x}}$$\textstyle{\mathcal{P}_{x}}$$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon_{u}}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\psi_{u}}$$\textstyle{\mathcal{R}_{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta_{a}}$$\scriptstyle{\tau_{a}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon_{v}}$$\scriptstyle{\varphi_{v}}$$\scriptstyle{\psi_{v}}$$\textstyle{\mathcal{R}_{b}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta_{b}}$$\scriptstyle{\tau_{b}}$$\textstyle{\mathcal{M}_{y}}$$\textstyle{\mathcal{M}_{y}}$

are not equivalent (cf. (6.9)); if $a,b$ are leaves this must be interpreted
in the following trivial way: it is impossible that both
$\vartheta(a)=\vartheta(b)$ and $\tau(a)=\tau(b)$. Moreover, if

$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{\mathcal{U}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta}$$\scriptstyle{\omega}$$\textstyle{\mathcal{M}}$
(6.15)

is an arbitrary common refinement of $(\varphi,\psi)$ then there exists a tree
composition $\gamma\in\mathsf{C}(\mathcal{U},\mathcal{R})$ such that the
following diagram is commutative:

$\textstyle{\mathcal{P}}$$\textstyle{\mathcal{T}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon}$$\scriptstyle{\delta}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\textstyle{\mathcal{U}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\scriptstyle{\eta}$$\scriptstyle{\omega}$$\textstyle{\mathcal{R}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta}$$\scriptstyle{\tau}$$\textstyle{\mathcal{M}}$
(6.16)

In particular, the common refinement $\mathcal{R}$ satisfying the coarseness
condition is unique up to equivalences (cf. (6.9)).

###### Proof.

By induction on $h$, the numbers of levels of $\mathcal{T}$. If $h=1$ we are
in the setting of Example 2.7 and Example 6.1: we have $\mathcal{T}\equiv V$,
$\mathcal{P}\equiv X$, $\mathcal{M}\equiv Y$ and, in the notation of Example
6.1, we set $\mathcal{R}\coloneqq A^{\prime}$,
$\vartheta\coloneqq\vartheta^{\prime}$, $\tau\coloneqq\tau^{\prime}$,
$\varepsilon$ as in (6.4). Therefore if
$(x_{1},y_{1}),(x_{2},y_{2})\in\mathcal{R}$ and
$\vartheta(x_{1},y_{1})=\vartheta(x_{2},y_{2})$,
$\tau(x_{1},y_{1})=\tau(x_{2},y_{2})$ then $(x_{1},y_{1})=(x_{2},y_{2})$ and
the coarseness condition in the statement is verified in the trivial way. In
other words,

$V=\bigsqcup_{a\in A^{\prime}}\varepsilon^{-1}(a)$ (6.17)

and we have $\varphi(u)=\varphi(v)$ and $\psi(u)=\psi(v)$ if and only if
$\varepsilon(u)=\varepsilon(v)$. Finally, any other common refinement must be
also a refinement of $\mathcal{R}$; in particular, $\mathcal{R}$ is unique.

Now suppose $h\geq 2$ and consider the decomposition (2.3). First of all, we
apply the construction in the case $h=1$ to $W_{\mathcal{T}}$, getting
$W_{\mathcal{R}}$, $\theta\rvert_{W_{\mathcal{R}}}$,
$\tau\rvert_{W_{\mathcal{R}}}$ and $\varepsilon\rvert_{W_{\mathcal{T}}}$.
Then, from the inductive hypothesis, we deduce that for each $v\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ there exists a unique common
refinement

---
$\textstyle{\mathcal{P}_{\varphi(v)}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon^{\prime}_{v}}$$\scriptstyle{\varphi_{v}}$$\scriptstyle{\psi_{v}}$$\textstyle{\mathcal{R}_{\varepsilon^{\prime}(v)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta^{\prime}_{\varepsilon^{\prime}(v)}}$$\scriptstyle{\tau^{\prime}_{\varepsilon^{\prime}(v)}}$$\textstyle{\mathcal{M}_{\psi(v)}}$
(6.18)

that verifies the coarseness condition in the statement. Consider the
following equivalence relation (which leads to a refinement of (6.17)): for
$u,v\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ we say that $u\sim v$ if
$\varphi(u)=\varphi(v)\eqqcolon x$, $\psi(u)=\psi(v)\eqqcolon y$ and the
common refinements $\varepsilon^{\prime}_{u}$ and $\varepsilon^{\prime}_{v}$
are equivalent, as in the following diagram (cf. (6.9)):

$\textstyle{\mathcal{P}_{x}}$$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta_{v,u}}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\varepsilon^{\prime}_{u}}$$\scriptstyle{\psi_{u}}$$\textstyle{\mathcal{R}_{\varepsilon^{\prime}(u)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma_{\varepsilon^{\prime}(u),\varepsilon^{\prime}(v)}}$$\scriptstyle{\vartheta^{\prime}_{\varepsilon^{\prime}(u)}}$$\scriptstyle{\tau^{\prime}_{\varepsilon^{\prime}(u)}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{v}}$$\scriptstyle{\varepsilon^{\prime}_{v}}$$\scriptstyle{\varphi_{v}}$$\textstyle{\mathcal{R}_{\varepsilon^{\prime}(v)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau^{\prime}_{\varepsilon^{\prime}(v)}}$$\scriptstyle{\vartheta^{\prime}_{\varepsilon^{\prime}(v)}}$$\textstyle{\mathcal{M}_{y}}$
(6.19)

Then we can use (2.5) to define $\mathcal{R}$: its first level is $A\sqcup
W_{\mathcal{R}}$, where $A\coloneqq\left(V_{\mathcal{T}}\setminus
W_{\mathcal{T}}\right)/\sim$, then for each $a\in A$ we choose a
representative $u_{a}$ in the equivalence class corresponding to $a$ and set
$\mathcal{R}_{a}\coloneqq\mathcal{R}_{u_{a}}$. After that, for all $v$ in the
equivalence class corresponding to $a$ set $\varepsilon(v)=a$,
$\vartheta(v)=\varphi(v),\tau(v)=\psi(v)$ and then

$\begin{split}&\varepsilon_{v}\coloneqq\varepsilon^{\prime}_{u_{a}}\circ\zeta_{u_{a},v}\equiv\gamma_{\varepsilon^{\prime}(u_{a}),\varepsilon^{\prime}(v)}\circ\varepsilon^{\prime}_{v},\qquad(\text{by
}\eqref{stepcpmmref})\\\
&\theta_{a}\coloneqq\theta^{\prime}_{\varepsilon^{\prime}(u_{a})}\qquad\text{and}\qquad\tau_{a}\coloneqq\tau^{\prime}_{\varepsilon^{\prime}(u_{a})}.\end{split}$

From the commutativity of (6.19) it follows that

$\theta_{\varepsilon(v)}\circ\varepsilon_{v}=\theta^{\prime}_{\varepsilon^{\prime}(u_{a})}\circ\gamma_{\varepsilon^{\prime}(u_{a}),\varepsilon^{\prime}(v)}\circ\varepsilon^{\prime}_{v}=\theta^{\prime}_{\varepsilon^{\prime}(v)}\circ\varepsilon^{\prime}_{v}=\varphi_{v}$

and similarly $\tau_{\varepsilon(v)}\circ\varepsilon_{v}=\psi_{v}$. Then we
can use (2.6) to define $\varepsilon$, $\vartheta$ and $\tau$ and we get a
common refinement.

The coarseness condition is clearly verified at the first level while, at
lower levels, it follows from the inductive hypothesis when $u,v$ in (6.14)
are distinct siblings. Otherwise, we may take $v^{\prime}$ sibling of $u$ such
that $\varepsilon(v)=\varepsilon(v^{\prime})=b$ and we can invoke Remark 6.4
to deduce that $\varepsilon_{v}$ and $\varepsilon_{v^{\prime}}$ are strictly
equivalent; but $\varepsilon_{u}$ and $\varepsilon_{v^{\prime}}$ are not
equivalent by the inductive hypothesis.

Finally, suppose that we have an arbitrary common refinement as in (6.15).
First of all, the construction in (6.6) applied to $W_{\mathcal{T}}$ yields
the diagram (6.16) restricted to the leaves at the first level. Then for each
$u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ we may apply the inductive
hypothesis to the common refinement
$\delta_{u}\in\mathsf{C}\left(\mathcal{T}_{u},\mathcal{U}_{c}\right)$, where
$c\coloneqq\delta(u)$, deducing that there exists
$\gamma_{c}\in\mathsf{C}\left(\mathcal{U}_{c},\mathcal{R}_{a}\right)$, where
$a\coloneqq\varepsilon(u)$, such that the following diagram, for the moment
without $\mathcal{T}_{v}$ and its arrows, is commutative
($x\coloneqq\varphi(u),y\coloneqq\psi(u)$):

$\textstyle{\mathcal{P}_{x}}$$\textstyle{\mathcal{T}_{v}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\zeta}$$\scriptstyle{\varphi_{v}}$$\scriptstyle{\psi_{v}}$$\scriptstyle{\delta_{v}}$$\textstyle{\mathcal{U}_{c}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma_{c}}$$\scriptstyle{\eta_{c}}$$\scriptstyle{\omega_{c}}$$\textstyle{\mathcal{R}_{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\vartheta_{a}}$$\scriptstyle{\tau_{a}}$$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varepsilon_{u}}$$\scriptstyle{\delta_{u}}$$\scriptstyle{\varphi_{u}}$$\scriptstyle{\psi_{u}}$$\textstyle{\mathcal{M}_{y}}$
(6.20)

Then, at the first level, we may construct $\gamma\colon
V_{\mathcal{U}}\setminus W_{\mathcal{U}}\rightarrow V_{\mathcal{R}}\setminus
W_{\mathcal{R}}$ (cf. (6.16)) arguing as in Example 6.1, but taking into
account Remark 6.4 and the equivalence relation $\sim$ introduced in the
preceding part of the proof. Now we give the details. If $v\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, $v\neq u$ and also $\delta(v)=c$
then the regularity condition in Definition 2.1 applied to $\delta$ yields an
isomorphism $\zeta\colon\mathcal{T}_{v}\rightarrow\mathcal{T}_{u}$ such that
$\delta_{v}=\delta_{u}\circ\zeta$. We have also
$\varphi_{v}=\eta_{c}\circ\delta_{v}$ and
$\psi_{v}=\omega_{c}\circ\delta_{v}$, by Definition 6.2. Then the whole
diagram (6.20) is commutative: for instance

$\varphi_{v}=\eta_{c}\circ\delta_{v}=\eta_{c}\circ\delta_{u}\circ\zeta=\varphi_{u}\circ\zeta.$

It follows that
$\varepsilon_{u}\circ\zeta\colon\mathcal{T}_{v}\rightarrow\mathcal{R}_{a}$
yields a common refinement of $\varphi_{v}$ and $\psi_{v}$, which satisfies
the coarseness condition because it is strictly equivalent to
$\varepsilon_{u}$. Therefore, the construction of $\mathcal{R}$ (that is the
definition of $\sim$) forces $\varepsilon(v)=a$ too. In conclusion, we may set
$\gamma(c)=a$ and this ends the construction of $\gamma$ at the first level of
$\mathcal{U}$ and also the proof. ∎

######  Definition 6.7.

The tree composition $\varepsilon\in\mathsf{C}(\mathcal{T},\mathcal{R})$ in
Theorem 6.6 will be called the coarsest common refinement of the couple
$(\varphi,\psi)\in\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$.
We say that the coarsest common refinement is trivial if $\varepsilon$ is an
isomorphism.

Clearly, both from its construction that from its properties, it follows that,
for every $v\in\mathcal{T}$ which is internal, $\mathcal{R}_{\varepsilon(v)}$
with the maps $\vartheta_{\varepsilon(v)}$ and $\tau_{\varepsilon(v)}$, is the
coarsest common refinement of $(\varphi_{v},\psi_{v})$.

######  Proposition 6.8.

Two couples of tree compositions as in (6.8) are strictly equivalent (cf.
(6.10)) if and only if their coarsest common refinements are equivalent, as in
(6.9). Moreover, if this is the case, then we may take the same isomorphism
$\zeta$ in both equivalences.

###### Proof.

Specialize Proposition 6.3 to the case of the coarsest common refinements. ∎

######  Lemma 6.9.

The coarsest common refinement of tree compositions
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ is trivial if and only if the
following condition is verified: for all pair of distinct siblings
$u,v\in\mathcal{T}$, $\varphi(u)=\varphi(v)$ and $\psi(u)=\psi(v)$ imply that
the couples $(\varphi_{u},\psi_{u})$ and $(\varphi_{v},\psi_{v})$ are not
strictly equivalent. If $u,v$ are leaves then this condition must interpreted
in the following trivial way: it is impossible that both
$\varphi(u)=\varphi(v)$ and $\psi(u)=\psi(v)$.

###### Proof.

If the condition in the statement is verified then a pair of distinct siblings
cannot have the same image under a common refinement $\varepsilon$ (cf. Remark
6.4) and therefore $\varepsilon$ must be injective,. Conversely, if
$\varepsilon$ is injective and $u,v$ are distinct siblings as in the statement
then $\varepsilon(u)\neq\varepsilon(v)$ so that, by Theorem 6.6, the couples
$(\varphi_{u},\psi_{u})$ and $(\varphi_{v},\psi_{v})$ are not strictly
equivalent. ∎

######  Remark 6.10.

Two couples of tree compositions as in (6.8) may have trivial coarsest common
refinements that are not equivalent. This is an obvious fact in the case of
set compositions: in the notations of Example 6.1, suppose that
$V=\\{1,2,3,4,5\\}$, $X=\\{a,b,c\\}$ and set

$\begin{split}&\varphi(1)=a,\varphi(2)=\varphi(3)=b,\varphi(4)=\varphi(5)=c,\;\varphi^{\prime}=\varphi,\\\
&\psi(1)=a,\psi(2)=\psi(4)=b,\psi(3)=\psi(5)=c,\;\psi^{\prime}(1)=\psi^{\prime}(2)=c,\psi^{\prime}(3)=\psi^{\prime}(4)=b,\psi^{\prime}(5)=a.\end{split}$

Then both the couples $(\varphi,\psi)$ and $(\varphi^{\prime},\psi^{\prime})$
have trivial coarsest common refinements because the relative $\varepsilon$’s
in (6.4) are injective ($\lvert\varphi^{-1}(x)\cap\psi^{-1}(y)\rvert\leq 1$
and $\lvert\varphi^{\prime-1}(x)\cap\psi^{\prime-1}(y)\rvert\leq 1$ for
$x,y=a,b,c$) but they are not strictly equivalent because the condition in
(6.12) is not satisfied: $\lvert\varphi^{-1}(a)\cap\psi^{-1}(c)\rvert=0$ while
$\lvert\varphi^{\prime-1}(a)\cap\psi^{\prime-1}(c)\rvert=1$; equivalently a
permutation $\pi\in\mbox{\rm Sym}\\{1,2,3,4,5\\}$ such that
$\varphi\circ\pi=\varphi^{\prime}$ requires that $\pi(1)=1$ while
$\psi\circ\pi=\psi^{\prime}$ requires $\pi(5)=1$ (the key fact is that
$\varphi$ and $\psi$ determine the same one-point part, namely $\\{1\\}$,
while for $\varphi^{\prime}$ and $\psi^{\prime}$ they are diffent: $\\{1\\}$
and $\\{5\\}$) Therefore their coarsest common refinements are not equivalent.
Note also that $\varphi,\varphi^{\prime},\psi,\psi^{\prime}$ are all strictly
equivalent set compositions.

In what follows, the action (2.10) in the case $k=1_{\text{\rm
Aut}(\mathcal{P})}$ will be denoted by:

$g\varphi\coloneqq\varphi\circ g^{-1},$ (6.21)

for all $g\in\mbox{\rm Aut}(\mathcal{T})$. Clearly, this action preserves the
type and, by Theorem 4.1, it is transitive on the set of all compositions of
the same type

######  Lemma 6.11.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{Q})$ are tree compositions of
$\mathcal{T}$. Then the group of all $g\in\mbox{\rm Aut}(\mathcal{T})$ such
that $g\varphi=\varphi$ and $g\psi=\psi$ is trivial (reduced to the identity)
if and only if their coarsest common refinement
$\varepsilon\colon\mathcal{T}\rightarrow\mathcal{R}$ is trivial.

###### Proof.

Suppose that the coarsest common refinement
$\varepsilon\in\mathsf{C}(\mathcal{T},\mathcal{R})$ is trivial and that
$g\varphi=\varphi,g\psi=\psi$. If $h=1$, from the characterization of
$\mathcal{R}\equiv A^{\prime}$ in Example 6.1 and the description of $\pi$ in
Remark 6.5, we deduce that $g$ is trivial (now $\varphi^{\prime}=\varphi$,
$\psi^{\prime}=\psi$ and, by (6.4),
$\lvert\varphi^{-1}(x)\cap\psi^{-1}(y)\rvert\leq 1$ for all $x\in X,y\in Y$,
so that (6.13) forces $\pi=$ the identity). If $h\geq 2$ then from Lemma 6.9
and the definition of $\sim$ in the proof of Theorem 6.6 it follows that $g$
is trivial at the first level and then we can apply induction to the
restrictions of $g$ to each $\mathcal{T}_{u},u\in V_{\mathcal{T}}\setminus
W_{\mathcal{T}}$, to deduce that $g_{u}$ is also trivial.

If $\varepsilon$ is not injective then there exists $v\in\mathcal{T}$, which
is internal, such that

$\varepsilon|_{\text{\rm Ch}(v)}\colon\text{\rm Ch}(v)\rightarrow\text{\rm
Ch}(\varepsilon(v))$

is not injective, so that there exist distinct $u,w\in\text{\rm Ch}(v)$ such
that $\varepsilon(u)=\varepsilon(w)\eqqcolon a$. Then the tree compositions
$\varepsilon_{u}\in\mathsf{C}(\mathcal{T}_{u},\mathcal{R}_{a})$ and
$\varepsilon_{w}\in\mathsf{C}(\mathcal{T}_{w},\mathcal{R}_{a})$ are equivalent
and therefore we can define a nontrivial $g\in\mbox{\rm Aut}(\mathcal{T})$ by
setting

$\begin{split}&g\text{ switches }\mathcal{T}_{u}\text{ and
}\mathcal{T}_{w}\text{ by means of the equivalence;}\\\ &g\text{ fixes all the
vertices outside }\mathcal{T}_{u}\text{ and }\mathcal{T}_{w}.\end{split}$
(6.22)

It follows that $\varepsilon=\varepsilon\circ g$ so that, recalling (6.7),
$g\varphi=\vartheta\circ\varepsilon\circ
g^{-1}=\vartheta\circ\varepsilon=\varphi$ and similarly $g\psi=\psi$. ∎

######  Remark 6.12.

In the notations of Definition 6.2 and assuming that $\varepsilon$ is the
coarsest common refinement, suppose that $v\in\mathcal{T}$ is internal,
$a=\varepsilon(v)$, $x\in\text{\rm Ch}(\varphi(v))$ and $y\in\text{\rm
Ch}(\psi(v))$. Then

$\begin{split}\text{\rm Ch}(v)\cap\varphi^{-1}(x)\cap\psi^{-1}(y)=&\text{\rm
Ch}(v)\cap\varepsilon^{-1}[\vartheta^{-1}(x)]\cap\varepsilon^{-1}[\tau^{-1}(y)]\\\
=&\text{\rm Ch}(v)\cap\varepsilon^{-1}\left[\text{\rm
Ch}(a)\cap\vartheta^{-1}(x)\cap\tau^{-1}(y)\right].\end{split}$

If $h=1$, so that $v$ and $a$ are the roots, then $\left\lvert\text{\rm
Ch}(a)\cap\vartheta^{-1}(x)\cap\tau^{-1}(y)\right\rvert\leq 1$; cf. the
definition of $A^{\prime},\vartheta^{\prime},\tau^{\prime}$ in Example 6.1. In
the general cases, this cardinalty may be greater than $1$: see the case
$h\geq 2$ in the proof of Theorem 6.6, where $A$ is obtained as a refinement
of the $A^{\prime}$ of the case $h=1$. In particular, the composition

$\text{\rm Ch}(v)=\bigsqcup\limits_{\begin{subarray}{c}x\in\text{\rm
Ch}(\varphi(v))\\\ y\in\text{\rm Ch}(\psi(v))\end{subarray}}\left[\text{\rm
Ch}(v)\cap\varphi^{-1}(x)\cap\psi^{-1}(y)\right]$

may be coarser than $\text{\rm Ch}(v)=\bigsqcup\limits_{b\in\text{\rm
Ch}(a)}\left[\text{\rm Ch}(v)\cap\varepsilon^{-1}(b)\right]$. It follows that,
in the general case height $>1$, the ”intersection matrix”
$\left\lvert\text{\rm Ch}(v)\cap\varphi^{-1}(x)\cap\psi^{-1}(y)\right\rvert$
is not as useful as the coarsest common refinement because it is associated to
a composition which may be too much coarse.

##  7 Tree compositions with $0-1$ intersection and transposition

######  Definition 7.1.

We say that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ have $0-1$ intersection if the
following condition is verified: for each $v\in\mathcal{T}$ which is internal
we have

$\left\lvert\varphi^{-1}(x)\cap\psi^{-1}(y)\right\rvert\leq 1,$ (7.1)

for all $x\in\text{\rm Ch}(\varphi(v)),y\in\text{\rm Ch}(\psi(v))$.

######  Example 7.2.

If $h=1$ and $V=\\{1,2,3,4,5\\}$ then the partitions
$\\{\\{1,2,3\\},\\{4,5\\}\\}$ and $\\{\\{1,4\\},\\{2,5\\},\\{3\\}\\}$ have
$0-1$ intersection. Clearly, $\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\}\\}$
have $0-1$ intersection with every other partition.

######  Remark 7.3.

The apparently weaker condition $\left\lvert\text{\rm
Ch}(v)\cap\varphi^{-1}(x)\cap\psi^{-1}(y)\right\rvert\leq 1$ is equivalent to
(7.1); the weakness of it might derive from the possibility of the existence
of other vertices $w\in\mathcal{T},w\neq v$ with $\varphi(w)=\varphi(v)$ and
$\psi(w)=\psi(v)$ and a child in $\varphi^{-1}(x)\cap\psi^{-1}(y)$, but we now
show that this is impossible. Indeed, assuming that $x\in\text{\rm
Ch}(\varphi(v)),y\in\text{\rm Ch}(\psi(v))$ we may consider the paths
$\\{\emptyset\\},v_{1},v_{2},\dotsc,v_{k-1}=v$ in $\mathcal{T},\;$
$\\{\emptyset\\},x_{1},x_{2},\dotsc,x_{k}=x$ in $\mathcal{P}\;$ and
$\\{\emptyset\\},y_{1},y_{2},\dotsc,y_{k}=y\text{ in }\mathcal{M}$. Therefore
$x_{j}=\varphi(v_{j})$ and $y_{j}=\psi(v_{j})$, $j=1,2,\dotsc,k-1$ and we can
apply the weaker condition to $x_{1},y_{1}$, then to $x_{2},y_{2}$, and so on,
getting that $\varphi^{-1}(x_{j})\cap\psi^{-1}(y_{j})=\\{v_{j}\\}$,
$j=1,2,\dotsc,k-1$, and finally (7.1).

######  Lemma 7.4.

If $\varphi$ and $\psi$ have $0-1$ intersection then their coarsest common
refinement is trivial.

###### Proof.

If (7.1) is verified, then the equivalence relation $\sim$ in the proof of
Theorem 6.6 is trivial (each equivalence class is a singleton). By induction,
also the common refinements in (6.18) must be trivial. ∎

######  Remark 7.5.

The converse of Lemma 7.4 is not true: the point is that, in the proof of
Theorem 6.6 for $h\geq 2$, the equivalence relation $\sim$ leads to a
refinement of (6.17). Indeed, suppose that $H(\mathcal{T})=2$, with
$V_{\mathcal{T}}=\\{u,v\\}$,
$\lvert\mathcal{T}_{u}\rvert=\lvert\mathcal{T}_{v}\rvert$ and then that
$\mathcal{P}=\mathcal{Q}$ with $V_{\mathcal{P}}=\\{x\\}$. We may use Example
6.1 and Remark 6.10 to construct
$\varphi,\psi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ in such a way that the
conditions in Lemma 6.9 are satisfied. For instance, if
$\widetilde{\mathcal{T}}_{u}=\\{1,2,3,4,5\\}$,
$\widetilde{\mathcal{T}}_{v}=\\{6,7,8,9,10\\}$ and
$\widetilde{\mathcal{P}}_{x}=\\{a,b,c\\}$ we may set

$\begin{split}&\varphi(1)=a,\varphi(2)=\varphi(3)=b,\varphi(4)=\varphi(5)=c,\;\varphi(6)=a,\varphi(7)=\varphi(8)=b,\varphi(9)=\varphi(10)=c,\\\
&\psi(1)=a,\psi(2)=\psi(4)=b,\psi(3)=\psi(5)=c,\;\psi(10)=a,\psi(6)=\psi(7)=b,\psi(8)=\psi(9)=c.\end{split}$

That is, $\varphi$ and $\psi$ coincide with those in Remark 6.10 while
$\varphi^{\prime}$ and $\psi^{\prime}$ are equivalent to those in Remark 6.10.
Then

$\lvert\varphi_{u}^{-1}(i)\cap\psi_{u}^{-1}(j)\rvert\leq 1\text{ and
}\lvert\varphi_{v}^{-1}(i)\cap\psi_{v}^{-1}(j)\rvert\leq 1,\text{ for
}i,j=a,b,c$ (7.2)

but there is not a bijection
$\zeta\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{v}$ such that
$\varphi_{u}=\varphi_{v}\circ\zeta$ and $\psi_{u}=\psi_{v}\circ\zeta$ (cf.
(6.10)) because the first condition requires $\zeta(1)=6$ while the second
$\zeta(1)=10$; equivalently, (6.12) is not satisfied. That is, the couples
$(\varphi_{u},\psi_{u})$ and $(\varphi_{v},\psi_{v})$ (which are just set
partitions) are not strictly equivalent and the map $\varepsilon$ in (6.7) is
injective at the first level. Moreover, from (7.2) it follows that also
$\varepsilon_{u}$ and $\varepsilon_{v}$ are injective. Therefore every common
refinement of $\varphi$ and $\psi$, in particular the coarsest one, is
trivial, but (7.1) is not satisfied because
$\varphi^{-1}(x)\cap\psi^{-1}(x)=\\{u,v\\}$. On the other hand, from the
construction of $\varepsilon$ in (6.4) we deduce that, in the case $h=1$, the
converse of Lemma 7.4 holds true.

In this section, we use the notion of conjugate of a numerical partition; if
$\lambda$ is a numerical partition we indicate by $\lambda^{t}$ its conjugate;
cf. [8, 21]. We want to generalize this notion and some of its properties to
tree compositions, but we will use the term transpose for tree compositions
(and conjugate for numerical compositions).

######  Theorem 7.6.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$,
$\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ is its quotient and that
$\\{\lambda^{a}\colon a\in\mathcal{Q}\\}$ is the associated tree of
partitions; cf. Definition 4.2. There exists a tree composition
$\varphi^{t}\in\mathsf{C}(\mathcal{T},\mathcal{P}^{t})$ (a transpose of
$\varphi$) such that:

  1. (a)

if $\alpha^{t}\in\mathsf{C}(\mathcal{P}^{t},\mathcal{Q}^{t})$ is the quotient
of $\varphi^{t}$ then $\mathcal{Q}^{t}=\mathcal{Q}$ and
$\alpha^{t}\circ\varphi^{t}=\alpha\circ\varphi$;

  2. (b)

if for every $a\in\mathcal{Q}$ we denote by $\mu^{a}$ the numerical partition
associated to $a$ by the tree composition
$\varphi^{t}\in\mathsf{C}(\mathcal{T},\mathcal{P}^{t})$, then $\mu^{a}$ is the
conjugate of $\lambda^{a}$;

  3. (c)

the tree compositions $\varphi$ and $\varphi^{t}$ have $0-1$ intersection.

We may also construct
$\alpha^{t}\in\mathsf{C}(\mathcal{P}^{t},\mathcal{Q}^{t})$ in such a way that
$\varphi$ and $\varphi^{t}$ have the same $\tau$’s in (3.1) (and we assume
that they satisfy all the properties in Theorem 3.1).

###### Proof.

The proof is by induction on $h\coloneqq H(\mathcal{T})$. For $h=1$ this is a
standard construction; see the definition of $m^{\lambda}$ in [8, Section 7]
or the $0-1$ matrix in [21, 2.1.1]. For future reference, we prefer to
indicate it in our notation. We have a partition
$V_{\mathcal{T}}=\\{\varphi^{-1}(x)\colon x\in V_{\mathcal{P}}\\}$ of type
$\lambda$ and we assume that $V_{\mathcal{P}}=\\{x_{1},x_{2},\dotsc,x_{k}\\}$
where the elements are numbered in such a way that

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

Then take a set $V_{\mathcal{P}^{t}}$ of cardinality $l\coloneqq\lambda_{1}$,
say $V_{\mathcal{P}^{t}}=\\{y_{1},y_{2},\dotsc,y_{l}\\}$. Put the elements of
$V_{\mathcal{T}}$ in the boxes of a Young diagram of shape $\lambda$ in such a
way that the elements of $\varphi^{-1}(x_{i})$ are in the $i$-th row,
$i=1,2,\dotsc,k$. Then define $\varphi^{t}\colon V_{\mathcal{T}}\rightarrow
V_{\mathcal{P}^{t}}$ in such a way that the elements of
$(\varphi^{t})^{-1}(y_{j})$ are in the $j$-the column, $j=1,2,\dotsc,l$. This
way we get that

$\left\lvert\varphi^{-1}(x_{i})\cap\left(\varphi^{t}\right)^{-1}(y_{j})\right\rvert=\left\\{\begin{array}[]{ll}1&\mbox{
if }1\leq j\leq\lambda_{i},\\\ 0&\mbox{ otherwise,}\end{array}\right.\quad\leq
1,$ (7.3)

for all $x_{i}\in V_{\mathcal{P}},y_{j}\in V_{\mathcal{P}^{t}}$. In
particular,
$\left\lvert(\varphi^{t})^{-1}(y_{j})\right\rvert=\lambda_{j}^{t}$,
$j=1,2,\dotsc,l$. The condition
$\alpha^{t}\circ\varphi^{t}=\alpha\circ\varphi$ is trivially verified because
$\alpha\circ\varphi$ sends all elements of $V_{\mathcal{T}}$ to a singelton
and, in this case, the $\tau$’s do not exist.

Suppose now that $h\geq 2$. If $W_{\mathcal{T}}$ is not empty, we may apply to
it the same construction of the case $h=1$, getting $W_{\mathcal{P}^{t}}$ and
$\varphi^{t}\rvert_{W_{\mathcal{T}}}$. After that, by Theorem 3.1, for every
$a\in V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ we choose
$v_{a}\in(\alpha\circ\varphi)^{-1}(a)$, so that $\\{\varphi_{v_{a}}\colon a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}\\}$ is a set of representatives for
the equivalence classes of the set of tree compositions $\\{\varphi_{v}\colon
v\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}\\}$. By the inductive
hypothesis, for each $a\in V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ there
exist tree compositions

$\varphi^{t}_{a}\in\mathsf{C}\left(\mathcal{T}_{v_{a}},\mathcal{P}^{t}_{a}\right)\qquad\text{
and
}\qquad\alpha^{t}_{a}\in\mathsf{C}\left(\mathcal{P}^{t}_{a},\mathcal{Q}_{a}\right)$

such that (a), (b) and (c) are verified and $\varphi^{t}_{a}$ have the same
$\tau$’s of $\varphi_{a}$ and a related set of $\omega^{t}$’s as in (3.1) (in
what follows, the $\omega$’s of $\varphi^{t}$ will be denoted by
$\omega^{t}$).

For each $a\in V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$, let $\mu^{a}$ be the
conjugate of $\lambda^{a}$ and define $V_{\mathcal{P}^{t}}\setminus
W_{\mathcal{P}^{t}}$ and $\alpha^{t}|_{V_{\mathcal{P}^{t}}\setminus
W_{\mathcal{P}^{t}}}\colon V_{\mathcal{P}^{t}}\setminus
W_{\mathcal{P}^{t}}\rightarrow V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ in
the following way:

$V_{\mathcal{P}^{t}}\setminus W_{\mathcal{P}^{t}}=\bigsqcup_{a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}}X^{t}_{a},$

where each $X^{t}_{a}$ is a set of cardinality $\ell(\mu^{a})$, and
$\left(\alpha^{t}\right)^{-1}(a)=X^{t}_{a}$ (cf. (4.7) and (4.8)). As in the
case $h=1$, for each $a\in V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ construct
a set partition $(\alpha\circ\varphi)^{-1}(a)=\left\\{V_{a,y}\colon y\in
X^{t}_{a}\right\\}$, of type $\mu^{a}$, which has $0-1$ intersection with
$\\{\varphi^{-1}(x):x\in\alpha^{-1}(a)\\}$, so that (c) is satisfied at the
first level. Then define $\varphi^{t}|_{V_{\mathcal{T}}\setminus
W_{\mathcal{T}}}$ in such a way that
$\left(\varphi^{t}\right)^{-1}(y)=V_{a,y}$, for all $y\in X^{t}_{a}$. Then
also (b) is verified at the first level and
$(\alpha\circ\varphi)^{-1}(a)=\left(\alpha^{t}\circ\varphi^{t}\right)^{-1}(a)$
by construction, so that
$\alpha\circ\varphi\rvert_{V_{\mathcal{T}}}=\alpha^{t}\circ\varphi^{t}\rvert_{V_{\mathcal{T}}}$
(this is the second condition in (a)).

After that, the construction of $\mathcal{P}^{t}$, $\alpha^{t}$ and
$\varphi^{t}$ may be completed in the following way: for all $a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ and $x\in X^{t}_{a}$, take
$\mathcal{P}^{t}_{x}$ isomorphic to $\mathcal{P}^{t}_{a}$, fix an isomorphism
$\omega^{t}_{x,a}\colon\mathcal{P}_{a}^{t}\rightarrow\mathcal{P}_{x}^{t}$ and
define $\mathcal{P}^{t}$ by means of (2.5). Set

$\alpha^{t}_{x}\coloneqq\alpha^{t}_{a}\circ\omega^{t}_{a,x},$ (7.4)

where, as usual, $\omega^{t}_{a,x}$ is the inverse of $\omega^{t}_{x,a}$, so
that $\alpha^{t}_{x}$ is strictly equivalent to $\alpha^{t}_{a}$. For each
$u\in V_{a,x}$, by means of the first level $\tau$’s of $\varphi$, set

$\varphi^{t}_{u}\coloneqq\omega^{t}_{x,a}\circ\varphi^{t}_{v_{a}}\circ\tau_{v_{a},u}.$
(7.5)

Hence, by means of (2.6), $\alpha^{t}$ is defined on the whole
$\mathcal{P}^{t}$, $\varphi^{t}$ on the whole $\mathcal{T}$ and the following
diagram, corresponding to (3.1) at the first level, is commutative:

$\textstyle{\mathcal{T}_{v_{a}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{t}_{v_{a}}}$$\scriptstyle{\tau_{u,v_{a}}}$$\textstyle{\mathcal{P}^{t}_{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha^{t}_{a}}$$\scriptstyle{\omega^{t}_{x,a}}$$\textstyle{\mathcal{Q}_{a}}$$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{t}_{u}}$$\textstyle{\mathcal{P}^{t}_{x}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\alpha^{t}_{x}}$

We complete the definition of the $\omega^{t}$’s at the first level as in the
second equation in (3.12):

$\omega^{t}_{x,y}\coloneqq\omega^{t}_{x,a}\circ\omega^{t}_{a,y},$ (7.6)

for all $x,y\in\alpha^{-1}(a)$, $a\in V_{\mathcal{Q}}\setminus
W_{\mathcal{Q}}$; note that the first equation in (3.12) is verified by the
hypothesis on the $\tau$’s. It is easy to check that, at the first level,
(3.1) is commutative (cf. (3.14)) while (3.4) is obvious. In particular, if
$x=y$ then (7.6) yields $\omega^{t}_{x,x}=\mbox{\rm
id}_{\mathcal{P}^{t}_{x}}$, so that if $u,v\in V_{\mathcal{T}}\setminus
W_{\mathcal{T}}$ and $\varphi^{t}(u)=\varphi^{t}(v)$ then $\varphi^{t}_{u}$
and $\varphi^{t}_{v}$ are strictly equivalent.

Now we prove $\alpha\circ\varphi=\alpha^{t}\circ\varphi^{t}$ on each first
level subtree: if $u\in(\alpha\circ\varphi)^{-1}(a)$, $a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$, then

$\displaystyle\alpha_{\varphi(u)}^{t}\circ\varphi_{u}^{t}=$
$\displaystyle\alpha^{t}_{a}\circ\omega^{t}_{a,\varphi(u)}\circ\omega^{t}_{\varphi(u),a}\circ\varphi^{t}_{v_{a}}\circ\tau_{v_{a},u}$
$\displaystyle(\text{by }\eqref{defalphat}\text{ and }\eqref{defphit})$
$\displaystyle=$
$\displaystyle\alpha_{a}\circ\varphi_{v_{a}}\circ\tau_{v_{a},u}$
$\displaystyle(\text{inductive hypothesis within }\mathcal{T}_{v_{a}})$
$\displaystyle=$ $\displaystyle\alpha_{\varphi(u)}\circ\varphi_{u}.$
$\displaystyle(\text{by }\eqref{diagTRSuv})$

In order to complete the definition of the $\omega^{t}$’s we can use the
second equation in (3.18) while for the $\tau$’s of $\varphi$ we may assume
that the first equation in (3.18) is satisfied: see also Remark 3.2. Then all
the properties of the $\omega^{t}$’s in Theorem 3.1 may be proved in the same
manner, including the commutatitivity of (3.1) at every level. In particular,
the identity $\omega^{t}_{x,x}=\mbox{\rm id}_{P^{t}_{x}}$ for each
$x\in\mathcal{P}^{t}$ which is internal implies that $\varphi^{t}$ is indeed a
tree composition. In order to prove that $\alpha^{t}$ is the quotient of
$\varphi^{t}$ we may invoke the commutativity of (3.1) and the following
observation: if $u,v\in\mathcal{T}$ are siblings and
$\alpha^{t}\circ\varphi^{t}(u)\neq\alpha^{t}\circ\varphi^{t}(v)$ then also
$\alpha\circ\varphi(u)\neq\alpha\circ\varphi(v)$ so that, by Theorem 3.1(b),
$\varphi_{u}$ and $\varphi_{v}$ are not equivalent; then Theorem 4.5 ensures
that also $\varphi^{t}_{u}$ and $\varphi^{t}_{v}$ are not equivalent because
the relative tree of partitions may not be isomorphic.

The property in (b) is now obvious: it is satisfied, by construction, at the
first level and within each $\mathcal{T}_{v_{a}}$, $a\in
V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$, and $\varphi^{t}_{u}$ is equivalent
to $\varphi^{t}_{v_{a}}$ by (7.5). We end by proving the $0-1$ intersection
property in (c) Suppose that $u\in\mathcal{T}$ is internal,
$u\in\mathcal{T}_{\widetilde{u}}$ with $\widetilde{u}\in V_{\mathcal{T}}$,
$x\in\text{\rm Ch}\left(\varphi(u)\right)$, $y\in\text{\rm
Ch}\left(\varphi^{t}(u)\right)$ and $\widetilde{x}$ (resp. $\widetilde{y}$) is
the ancestor of $\varphi(u)$ (resp. $\varphi^{t}(u)$) at the first level. From
the $0-1$ property at the first level it follows that
$\left(\varphi\right)^{-1}(\widetilde{x})\bigcap\left(\varphi^{t}\right)^{-1}(\widetilde{y})=\\{\widetilde{u}\\}$,
so that
$\left(\varphi\right)^{-1}(\mathcal{P}_{\widetilde{x}})\bigcap\left(\varphi^{t}\right)^{-1}(\mathcal{P}_{\widetilde{y}})\subseteq\mathcal{T}_{\widetilde{u}}$.
Therefore

$\begin{split}\left(\varphi\right)^{-1}(x)\bigcap\left(\varphi^{t}\right)^{-1}(y)=&\left(\varphi_{\widetilde{u}}\right)^{-1}(x)\bigcap\left(\varphi_{\widetilde{u}}^{t}\right)^{-1}(y)\\\
(\text{by }\eqref{diagTRSuv}\text{ and
}\eqref{defphit})=&\left[\tau_{\widetilde{u},v_{a}}\circ\left(\varphi_{v_{a}}\right)^{-1}\circ\omega_{a,\widetilde{x}}\right](x)\bigcap\left[\tau_{\widetilde{u},v_{a}}\circ\left(\varphi_{v_{a}}^{t}\right)^{-1}\circ\omega^{t}_{a,\widetilde{y}}\right](y)\\\
=&\tau_{\widetilde{u},v_{a}}\left\\{\left[\left(\varphi_{v_{a}}\right)^{-1}(\omega_{a,\widetilde{x}}(x))\right]\bigcap\left[\left(\varphi^{t}_{v_{a}}\right)^{-1}(\omega^{t}_{a,\widetilde{y}}(y))\right]\right\\}\\\
\end{split}$

so that

$\left\lvert\left(\varphi\right)^{-1}(x)\bigcap\left(\varphi^{t}\right)^{-1}(y)\right\rvert=\left\lvert\left[\left(\varphi_{v_{a}}\right)^{-1}(\omega_{a,\widetilde{x}}(x))\right]\bigcap\left[\left(\varphi^{t}_{v_{a}}\right)^{-1}(\omega^{t}_{a,\widetilde{y}}(y))\right]\right\rvert\leq
1$ (7.7)

and now we prove the last inequality in (7.7): we have

$\begin{split}&\varphi_{v_{a}}\circ\tau_{v_{a},\widetilde{u}}(u)=\omega_{a,\widetilde{x}}\circ\varphi_{\widetilde{u}}(u)=\omega_{a,\widetilde{x}}(\varphi(u))\quad\text{
and }\quad x\in\text{\rm Ch}\left(\varphi(u)\right)\\\
&\Longrightarrow\quad\omega_{a,\widetilde{x}}(x)\in\text{\rm
Ch}\left[\varphi_{v_{a}}(\tau_{v_{a},\widetilde{u}}(u))\right]\end{split}$

and similarly

$\varphi^{t}_{v_{a}}\circ\tau_{v_{a},\widetilde{u}}(u)=\omega^{t}_{a,\widetilde{y}}(\varphi^{t}(u))\quad\text{
and }\quad y\in\text{\rm
Ch}\left(\varphi^{t}(u)\right)\quad\Longrightarrow\quad\omega^{t}_{a,\widetilde{y}}(y)\in\text{\rm
Ch}\left[\varphi^{t}_{v_{a}}(\tau_{v_{a},\widetilde{u}}(u))\right]$

so that, by the inductive hypothesis, we may apply the $0-1$ property within
$\mathcal{T}_{v_{a}}$.

∎

######  Remark 7.7.

As specified in the statement, a transpose of $\varphi$ is a tree composition
$\varphi^{t}$ with all the properties in Theorem 7.6. But note that
$\varphi^{t}$ is not unique nor a tree composition strictly equivalent to
$\varphi^{t}$ is still a transpose; these facts are obvious even in the case
$h=1$. On the other hand, if
$\psi\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P})$ is strictly equivalent
to $\varphi$, say $\psi=\varphi\circ\beta$ where
$\beta\colon\mathcal{T}^{\prime}\rightarrow\mathcal{T}$ is an isomorphism,
then $\varphi^{t}\circ\beta$ is a transpose of $\psi$, because all the
properties in Theorem 7.6 are clearly preserved by $\beta$; cf. Remark 2.6,
Remark 3.5 and Theorem 4.5. Finally, since the conditions in Theorem 7.6 are
symmetric, $\varphi$ is a transpose of $\varphi^{t}$.

######  Example 7.8.

In the notation of Example 3.7, $\mbox{\rm tv}_{\mathcal{T}}$ is a transpose
of $\mbox{\rm id}_{\mathcal{T}}$ and vice versa; see also Example 4.4 for the
case of a spherically homogeneous tree.

######  Theorem 7.9.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\varphi^{\prime}\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P}^{\prime})$ are
equivalent, $\varphi^{t}\in\mathsf{C}(\mathcal{T},\mathcal{P}^{t})$ is a
transpose of $\varphi$ and $\varphi^{\prime
t}\in\mathsf{C}(\mathcal{T}^{\prime},\mathcal{P}^{\prime t})$ is a transpose
of $\varphi^{\prime}$. Then also $\varphi^{t}$ and $\varphi^{\prime t}$ are
equivalent.

###### Proof.

From Theorem 4.5 it follows that $\varphi$ and $\varphi^{\prime}$ determine
isomorphic tree of partitions. But then also $\varphi^{t}$ and
$\varphi^{\prime t}$ determine isomorphic tree of partitions, because they are
obtained from those of $\varphi$ and $\varphi^{\prime}$ just by replacing
$\lambda_{a}$ with $\lambda_{a}^{t}$. Then, again from Theorem 4.5, it follows
that also $\varphi^{t}$ and $\varphi^{\prime t}$ are equivalent. ∎

######  Theorem 7.10.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ are two tree compositions of
$\mathcal{T}$. If their coarsest common refinement is trivial (cf. Definition
6.7) then $\varphi\leqq\psi^{t}$ (and also, by symmetry,
$\psi\leqq\varphi^{t}$) with respect to the total order in (4.18).

###### Proof.

Let $\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ and
$\beta\in\mathsf{C}(\mathcal{M},\mathcal{N})$ be the quotients respectively of
$\varphi$ and $\psi$. The proof is by induction on $h\coloneqq
H(\mathcal{T})$, and for every $h$ we will use also induction on $\lvert
V_{\mathcal{Q}})\rvert$, the number of first level vertices of $\mathcal{Q}$.
For $h=1$ the theorem is just a weak form of the easy part of the Gale-Ryser
Theorem: we have replaced the majorization order with the lexicographic order;
see [21, 1.4.17]. Recall also that in this case the converse of Lemma 7.4
holds true; cf. Remark 7.5.

Suppose now that $h\geq 2$. If $\varphi$ and $\psi^{t}$ are equivalent there
is nothing to prove, so that we assume that they are not equivalent. Let
$a_{0}$ be the greatest element in $V_{\mathcal{Q}}$ and $b_{0}$ the greatest
element in $V_{\mathcal{N}}$, with respect to the order (4.16). We denote by
$\Lambda\colon\mathcal{Q}\ni a\mapsto\lambda^{a}$, respectively
$\Gamma\colon\mathcal{N}\ni b\mapsto\mu^{b}$, the tree of partitions
associated to $\varphi$, respectively to $\psi^{t}$. We will use the following
algorithm, based on the definitions of (4.15), (4.16) and (4.18).

  1. 1.

If there exists $b\in V_{\mathcal{N}}$, $b\neq b_{0}$, such that
$(\alpha\circ\varphi)^{-1}(a_{0})\cap(\beta\circ\psi)^{-1}(b)\neq\emptyset$
then we may choose a vertex $v$ in this nonempty set. By Lemma 6.9, the
coarsest common refinement of $\varphi_{v}$ and $\psi_{v}$ is trivial and
therefore, by the inductive hypothesis, we have
$\varphi_{v}\leqq\psi_{v}^{t}$, so that $\Lambda_{a_{0}}\leq\Gamma_{b}$. Since
$\psi_{v}^{t}<\psi_{w}^{t}$ for every $w\in(\psi^{t})^{-1}(b_{0})$ then
$\Gamma_{b}<\Gamma_{b_{0}}$, and we conclude that $a_{0}<^{\prime}b_{0}$. From
(4.17) we deduce that $\Lambda<\Gamma$, that is $\varphi<\psi^{t}$.

  2. 2.

If
$(\alpha\circ\varphi)^{-1}(a_{0})\subseteq(\beta^{t}\circ\psi^{t})^{-1}(b_{0})$
then again $\varphi_{v}\leqq\psi_{v}^{t}$ for every
$v\in(\alpha\circ\varphi)^{-1}(a_{0})$. If actually $\varphi_{v}<\psi_{v}^{t}$
we deduce that $\varphi<\psi^{t}$.

  3. 3.

If
$(\alpha\circ\varphi)^{-1}(a_{0})\subseteq(\beta^{t}\circ\psi^{t})^{-1}(b_{0})$
and $\varphi_{v},\psi_{v}^{t}$ are equivalent but
$\lambda^{a_{0}}=\left\lvert(\alpha\circ\varphi)^{-1}(a_{0})\right\rvert<\left\lvert(\beta^{t}\circ\psi^{t})^{-1}(b_{0})\right\rvert=\mu^{b_{0}}$
again $\varphi<\psi^{t}$.

  4. 4.

If $(\alpha\circ\varphi)^{-1}(a_{0})=(\beta^{t}\circ\psi^{t})^{-1}(b_{0})$ and
$\varphi_{v},\psi_{v}^{t}$ are equivalent but $\lambda^{a_{0}}<\mu^{b_{0}}$
again $\varphi<\psi^{t}$.

  5. 5.

The last case: if
$(\alpha\circ\varphi)^{-1}(a_{0})=(\beta^{t}\circ\psi^{t})^{-1}(b_{0})$,
$\varphi_{v},\psi_{v}^{t}$ are equivalent and also
$\lambda^{a_{0}}=\mu^{b_{0}}$ (so that $a_{0}=^{\prime}b_{0}$) then we can
delete $a_{0}$ and $b_{0}$, that is the subtrees $\mathcal{T}_{v}$,
$v\in(\alpha\circ\varphi)^{-1}(a_{0})$, and their images in $\mathcal{P}$,
$\mathcal{M}$, $\mathcal{Q}$, $\mathcal{N}$. Denote by $\mathcal{T}^{\prime}$,
$\mathcal{P}^{\prime}$, etc. the trees obtained after deletion and
$\varphi^{\prime},\psi^{\prime}$, etc. the relative maps, which are obviously
tree compositions, quotients, etc. By Lemma 6.9, the coarsest common
refinement of $\varphi^{\prime},\psi^{\prime}$ is still trivial; moreover,
$\varphi^{\prime}$ and $(\psi^{t})^{\prime}$ cannot be equivalent. Otherwise,
we might construct an equivalence between $\varphi$ and $\psi^{t}$ by means of
Theorem (4.5), using also the fact that $a_{0}=^{\prime}b_{0}$.

Now we show that, assuming the result for height=$h-1$, we may prove it for
height=$h$ by induction on $\lvert V_{\mathcal{Q}}\rvert$. If $\lvert
V_{\mathcal{Q}}\rvert=1$ then we have two possibilities. If $\lvert
V_{\mathcal{N}}\rvert\geq 2$ then the algorithm stops at step 1. If $\lvert
V_{\mathcal{N}}\rvert=1$ then it stops at step 2. or 4., because we have
assumed that $\varphi$ and $\psi^{t}$ are not equivalent. If $\lvert
V_{\mathcal{N}}\rvert\geq 2$ we may apply the algorithm; if it arrives at step
5 we delete $a_{0}$ and $b_{0}$ and invoke induction on $\lvert
V_{\mathcal{Q}}\rvert$. ∎

######  Theorem 7.11.

Suppose that $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$,
$\alpha\in\mathsf{C}(\mathcal{P},\mathcal{Q})$ is its quotient and that
$\\{\lambda^{a}\colon a\in\mathcal{Q}\\}$ is the associated tree of
partitions; cf. Definition 4.2. If
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{P}^{t})$ is strictly equivalent to a
transposed $\varphi^{t}$ of $\varphi$ and the coarsest common refinement
$\varepsilon\colon\mathcal{T}\rightarrow\mathcal{R}$ of the couple
$(\varphi,\psi)$ is trivial then there exists $g\in\mbox{\rm
Aut}(\mathcal{T})$ such that:

$g\varphi=\varphi\qquad\text{ and }\qquad g\varphi^{t}=\psi.$

In particular, the couples $(\varphi,\psi)$ and $(\varphi,\varphi^{t})$ are
strictly equivalent and $\mathcal{R}$ is equivalent to the coarsest common
refinement of $(\varphi,\varphi^{t})$ (in the sense of (6.9)).

###### Proof.

The proof is by induction on the height $h\coloneqq H(\mathcal{T})$. For $h=1$
this is essentially the uniqueness of $m^{\lambda}$ in [8, Section 7] or of
the $0-1$ matrix in [21, 2.1.1] and we give a proof of it in the notation of
the first part of the proof of Theorem 7.6. The strict equivalence between
$\psi$ and $\varphi^{t}$ implies that if
$V_{\mathcal{P}}=\\{y_{1},y_{2},\dotsc,y_{l}\\}$ then
$\lvert\psi^{-1}(y_{j})\rvert=\lambda^{t}_{j},\quad j=1,2,\dotsc,h.$ Since
$\mathcal{R}$ is trivial, from Remark 6.5 it follows that

$\left\lvert\varphi^{-1}(x_{i})\cap\psi^{-1}(y_{j})\right\rvert\leq 1,\quad
i=1,2,\dotsc,k,\;j=1,2,\dotsc,l.$ (7.8)

Then

$\sum_{j=1}^{l}\left\lvert\varphi^{-1}(x_{i})\cap\psi^{-1}(y_{j})\right\rvert=\lambda_{i}\quad\text{
and
}\quad\sum_{i=1}^{k}\left\lvert\varphi^{-1}(x_{i})\cap\psi^{-1}(y_{j})\right\rvert=\lambda^{t}_{j}.$
(7.9)

We want to show that, as in (7.3),

$\left\lvert\varphi^{-1}(x_{i})\cap\psi^{-1}(y_{j})\right\rvert=\left\\{\begin{array}[]{ll}1&\mbox{
if }1\leq j\leq\lambda_{i}\\\ 0&\mbox{ otherwise.}\end{array}\right.$ (7.10)

First of all, (7.8), $l=\lambda_{1}$ and first equality in (7.9) for $i=1$
imply (7.10) for $i=1$. Similarly, (7.8), $k=\lambda^{t}_{1}$ and second
equality in (7.9) for $j=1$ imply (7.10) for $j=1$. Moreover, if
$\lambda_{1}>\lambda_{2}$ then $\lambda_{j}^{t}=1$ for
$j=\lambda_{2}+1,\dotsc,l$ so that the second equality in (7.9) yields (7.10)
for $i\geq 2$ and $\lambda_{2}+1\leq j\leq l$. Similarly, if
$\lambda^{t}_{1}>\lambda^{t}_{2}$ then $\lambda_{i}=1$ for
$i=\lambda^{t}_{2}+1,\dotsc,k$ so that the first equality in (7.9) yields
(7.10) for $j\geq 2$ and $\lambda^{t}_{2}+1\leq i\leq k$. Then we can use an
easy inductive procedure: we delete $\varphi^{-1}(x_{1})\cup\psi^{-1}(y_{1})$;
if $\lambda_{1}>\lambda_{2}$ we delete also $\\{y_{j}\colon
j=\lambda_{2}+1,\dotsc,l\\}$ while if $\lambda^{t}_{1}>\lambda^{t}_{2}$ we
delete also $\\{x_{i}\colon i=\lambda^{t}_{2}+1,\dotsc,k\\}$ and then we can
repeat the argument above (induction on $\lvert V_{\mathcal{T}}\rvert$).

By (7.3) and (7.10) we can choose $\pi\in\mbox{\rm
Sym}\left(V_{\mathcal{T}}\right)$ such that

$\pi\left(\varphi^{-1}(x_{i})\cap(\varphi^{t})^{-1}(y_{j})\right)=\varphi^{-1}(x_{i})\cap\psi^{-1}(y_{j}).$
(7.11)

In particular, $\pi\in\mbox{\rm
Sym}\left(\varphi^{-1}(x_{1})\right)\times\mbox{\rm
Sym}\left(\varphi^{-1}(x_{2})\right)\times\dotsb\times\mbox{\rm
Sym}\left(\varphi^{-1}(x_{k})\right)$, which implies that
$\varphi\circ\pi=\varphi$, and
$\pi\bigl{(}(\varphi^{t})^{-1}(y_{j})\bigr{)}=\psi^{-1}(y_{j})$,
$j=1,2,\dotsc,l$, which implies that $\psi\circ\pi=\varphi^{t}$.

Now suppose that $h\geq 2$. On $W_{\mathcal{T}}$ we may argue as in the case
$h=1$ and prove that there exists $\pi\in\mbox{\rm Sym}(W_{\mathcal{T}})$ such
that $\varphi\rvert_{W_{\mathcal{T}}}\circ\pi=\varphi\rvert_{W_{\mathcal{T}}}$
and
$\psi\rvert_{W_{\mathcal{T}}}\circ\pi=\varphi^{t}\rvert_{W_{\mathcal{T}}}$.

Then we may suppose that $\varphi,\psi$ and $\varphi^{t}$ have the same
quotient tree $\mathcal{Q}$ and that $\alpha^{t}$ is also the map of the
quotient of $\psi$ (cf. Remark 3.5) with the same tree of partitions (cf.
Theorem 4.5). We have

$(\alpha\circ\varphi)^{-1}(a)=(\alpha^{t}\circ\varphi^{t})^{-1}(a)=(\alpha^{t}\circ\psi)^{-1}(a),\quad\text{
for all }a\in V_{\mathcal{Q}},$ (7.12)

where the first equality follows from
$\alpha\circ\varphi=\alpha^{t}\circ\varphi^{t}$ in Theorem 7.6(a) while the
second will be proved now. First of all, from (4.7) it follows that

$\lvert(\alpha^{t}\circ\varphi^{t})^{-1}(a)\rvert=\lvert(\alpha^{t}\circ\psi)^{-1}(a)\rvert;$
(7.13)

moreover, the tree compositions

$\left\\{\varphi^{t}_{v}:v\in(\alpha^{t}\circ\varphi^{t})^{-1}(a)\right\\}\;\text{
and }\;\left\\{\psi_{u}:u\in(\alpha^{t}\circ\psi)^{-1}(a)\right\\}\;\text{ are
all equivalent,}$ (7.14)

because $\psi$ and $\varphi^{t}$ are strictly equivalent. The second identity
in (7.12) is obvious for the unique $a\in W_{\mathcal{Q}}$ (if it exists). Now
suppose that $a_{1},a_{2},\dotsc,a_{m}$ are the elements of
$V_{\mathcal{Q}}\setminus W_{\mathcal{Q}}$ numbered in such a way that
$\varphi^{t}_{v_{1}}>\varphi^{t}_{v_{2}}>\dotsb>\varphi^{t}_{v_{m}}$, if
$v_{i}\in(\alpha^{t}\circ\varphi^{t})^{-1}(a_{i})$, $i=1,2,\dotsc,m$. If
$u\in(\alpha^{t}\circ\varphi^{t})^{-1}(a_{m})$ then $(\varphi_{u},\psi_{u})$
have a trivial common refinement (by the hypothesis and by Lemma 6.9) and
therefore from Theorem 7.10 we deduce that $\psi_{u}\leqq\varphi_{u}^{t}$.
From (7.14) and the minimality of $\varphi^{t}_{v_{m}}$ we deduce that
$\psi_{u}$ is equivalent to $\varphi^{t}_{u}$ so that (7.13) and (7.14) imply
that the second equality in (7.12) holds true for $a=a_{m}$. By iterating the
procedure, we may prove the second equality in (7.12) for all $a_{i}$.

Within each set $(\alpha\circ\varphi)^{-1}(a)$, $a\in V_{\mathcal{Q}}\setminus
W_{\mathcal{Q}}$, the restriction of the map $\varepsilon$ determines a
trivial common refinement of the restrictions of $\varphi$ and $\psi$ and the
associated numerical partitions (cf. Definition 4.2) are $\lambda^{a}$ and
$(\lambda^{a})^{t}$. Therefore, by the case $h=1$, there exists
$\pi\in\prod\limits_{x\in V_{\mathcal{P}}}\mbox{\rm
Sym}\left(\varphi^{-1}(x)\right)$ such that

$\varphi\rvert_{V_{\mathcal{T}}}\circ\pi=\varphi\rvert_{V_{\mathcal{T}}}\quad\text{
and
}\quad\psi\rvert_{V_{\mathcal{T}}}\circ\pi=\varphi^{t}\rvert_{V_{\mathcal{T}}}$
(7.15)

(on $(\alpha\circ\varphi)^{-1}(a)$, $a\in W_{\mathcal{Q}}$, if not empty,
$\pi$ was constructed above). Just note that in each
$(\alpha\circ\varphi)^{-1}(a)$, $a\in V_{\mathcal{Q}}\setminus
W_{\mathcal{Q}}$, it is reproduced the condition (7.11).

Now suppose that $g^{\prime}\in\mbox{\rm Aut}(\mathcal{T})$ is the
automorphism of the strict equivalence between $\psi$ and $\varphi^{t}$, that
is $\psi\circ g^{\prime}=\varphi^{t}$, and set $\sigma\coloneqq
g^{\prime}\rvert_{V_{\mathcal{T}}}$. From (7.15) it follows that

$\varphi^{t}\rvert_{V_{\mathcal{T}}}=\varphi^{t}\rvert_{V_{\mathcal{T}}}\circ\sigma^{-1}\circ\pi.$
(7.16)

Then $\varphi^{t}(u)=\varphi\left(\sigma^{-1}(\pi(u))\right)$ for all $u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$ so that, by (3.7), $\varphi^{t}_{u}$
and $\varphi^{t}_{\sigma^{-1}(\pi(u))}$ are strictly equivalent and we use the
$\tau$’s to modify $g^{\prime}$: we define the isomorphisms

$g^{\prime\prime}_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{\pi(u)}\quad\text{
by setting }\quad g^{\prime\prime}_{u}\coloneqq
g^{\prime}_{\sigma^{-1}(\pi(u))}\circ\tau_{\sigma^{-1}(\pi(u)),u},\quad\text{
for all }\;u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}},$ (7.17)

where $\tau$ is as in (3.1) both for $\varphi$ and $\varphi^{t}$ (cf. Theorem
7.6) and, by (2.6), $g^{\prime}_{\sigma^{-1}(\pi(u))}$ is an isomorphism from
$\mathcal{T}_{\sigma^{-1}(\pi(u))}$ to $\mathcal{T}_{\pi(u)}$.

$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{\prime\prime}_{u}}$$\scriptstyle{\tau_{\sigma^{-1}(\pi(u)),u}}$$\textstyle{\mathcal{T}_{\sigma^{-1}(\pi(u))}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{\prime}_{\sigma^{-1}(\pi(u))}}$$\textstyle{\mathcal{T}_{\pi(u)}}$

After that, again by means of (2.6), we define $g^{\prime\prime}\in\mbox{\rm
Aut}(\mathcal{T})$ by setting
$g^{\prime\prime}(u,w)\coloneqq(\pi(u),g^{\prime\prime}_{u}(w))$, for all
$u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, $w\in\mathcal{T}_{u}$, and
$g^{\prime\prime}\rvert_{W_{\mathcal{T}}}\coloneqq\pi\rvert_{W_{\mathcal{T}}}$
. It follows that

$\displaystyle(\psi\circ g^{\prime\prime})_{u}=$
$\displaystyle\psi_{\pi(u)}\circ g^{\prime\prime}_{u}$ $\displaystyle(\text{by
}\eqref{firstldell2})$ $\displaystyle=$ $\displaystyle\psi_{\pi(u)}\circ
g^{\prime}_{\sigma^{-1}(\pi(u))}\circ\tau_{\sigma^{-1}(\pi(u)),u}$
$\displaystyle(\text{by }\eqref{defgsec})$ $\displaystyle=$
$\displaystyle\varphi^{t}_{\sigma^{-1}(\pi(u))}\circ\tau_{\sigma^{-1}(\pi(u)),u}$
$\displaystyle(\text{by }\psi\circ g^{\prime}=\varphi^{t}\text{ and
}\eqref{firstldell2})$ $\displaystyle=$ $\displaystyle\varphi^{t}_{u},$
$\displaystyle(\text{by }\eqref{diagTRSuv2b}\text{ and }\eqref{sigpi})$

that is, recalling also the second equation in (7.15),

$\psi\circ g^{\prime\prime}=\varphi^{t}.$ (7.18)

In other words, $g^{\prime\prime}$ is a modified form of $g^{\prime}$ which is
equal to $\pi$ on the first level.

From (7.15) it follows that $\varphi(\pi(u))=\varphi(u)$ when $u\in
V_{\mathcal{T}}$ and therefore, by (3.7),
$\varphi_{\pi(u)}=\varphi_{u}\circ\tau_{u,\pi(u)}$. On the other hand,
$\varphi^{t}_{u}\circ\tau_{u,\pi(u)}$ is not necessarily equal to
$\varphi^{t}_{\pi(u)}$: we should apply (3.1) which involves the $\omega^{t}$
(cf. the proof of Theorem 7.6); actually, if $u\neq\pi(u)$ then the $0-1$
intersection property at the first level forces
$\varphi^{t}(\pi(u))\neq\varphi^{t}(u)$ because otherwise

$\left\lvert\varphi^{-1}(x)\cap\left(\varphi^{t}\right)^{-1}(y)\right\rvert\geq
2\quad\text{ if }\quad x=\varphi(u),y=\varphi^{t}(u).$

But we can say that $\varphi^{t}_{u}\circ\tau_{u,\pi(u)}$ is a transpose of
$\varphi_{\pi(u)}$ because $\tau_{u,\pi(u)}$ is an isomorphism that determines
strict equivalences between $\varphi_{u}$ and $\varphi_{\pi(u)}$ and between
$\varphi^{t}_{u}$ and $\varphi^{t}_{u}\circ\tau_{u,\pi(u)}$: see Remark 7.7.
Similarly, from (7.18) it follows that

$\psi_{\pi(u)}\circ\left(g_{u}^{\prime\prime}\circ\tau_{u,\pi(u)}\right)=\varphi^{t}_{u}\circ\tau_{u,\pi(u)},$

that is $\psi_{\pi(u)}$ and $\varphi^{t}_{u}\circ\tau_{u,\pi(u)}$ are strictly
equivalent. By the hypothesis of the Theorem and Lemma 6.9, the couple
$(\varphi_{\pi(u)},\psi_{\pi(u)})$ has a trivial coarsest common refinement.
Then we may apply induction to the copule $(\varphi_{\pi(u)},\psi_{\pi(u)})$
with $\varphi^{t}_{u}\circ\tau_{u,\pi(u)}$ as a transpose of
$\varphi_{\pi(u)}$: there exists $\widetilde{g}_{\pi(u)}\in\mbox{\rm
Aut}(\mathcal{T}_{\pi(u)})$ such that

$\varphi_{\pi(u)}\circ\widetilde{g}_{\pi(u)}=\varphi_{\pi(u)}\qquad\text{and}\qquad\psi_{\pi(u)}\circ\widetilde{g}_{\pi(u)}=\varphi^{t}_{u}\circ\tau_{u,\pi(u)}.$
(7.19)

After that, for all $u\in V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, we use
again the $\tau$’s to define an isomorphism
$g_{u}\colon\mathcal{T}_{u}\rightarrow\mathcal{T}_{\pi(u)}$ by setting

$g_{u}\coloneqq\widetilde{g}_{\pi(u)}\circ\tau_{\pi(u),u}\qquad\qquad\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
20.14206pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathcal{T}_{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
36.02953pt\raise-14.40553pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.8264pt\hbox{$\scriptstyle{g_{u}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
65.98785pt\raise-33.16875pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.25694pt\hbox{$\scriptstyle{\tau_{\pi(u),u}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.35277pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
35.98785pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 74.97571pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-11.98785pt\raise-39.18608pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathcal{T}_{\pi(u)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
29.36955pt\raise-47.0472pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.36111pt\hbox{$\scriptstyle{\widetilde{g}_{\pi(u)}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
65.98785pt\raise-39.18608pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
35.98785pt\raise-39.18608pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
65.98785pt\raise-39.18608pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathcal{T}_{\pi(u)}}$}}}}}}}\ignorespaces}}}}\ignorespaces$
(7.20)

Then we have

$\displaystyle\varphi_{\pi(u)}\circ g_{u}=$
$\displaystyle\varphi_{\pi(u)}\circ\widetilde{g}_{\pi(u)}\circ\tau_{\pi(u),u}$
$\displaystyle(\text{by }\eqref{defgud})$ $\displaystyle=$
$\displaystyle\varphi_{\pi(u)}\circ\tau_{\pi(u),u}$ $\displaystyle(\text{by
}\eqref{defgu11d})$ $\displaystyle=$ $\displaystyle\varphi_{u}$
$\displaystyle(\text{by }\eqref{diagTRSuv2b}\text{ and }\eqref{vargpsi})$

and

$\displaystyle\psi_{\pi(u)}\circ g_{u}=$
$\displaystyle\psi_{\pi(u)}\circ\widetilde{g}_{\pi(u)}\circ\tau_{\pi(u),u}$
$\displaystyle(\text{by }\eqref{defgud})$ $\displaystyle=$
$\displaystyle\varphi^{t}_{u}\circ\tau_{u,\pi(u)}\circ\tau_{\pi(u),u}$
$\displaystyle(\text{by }\eqref{defgu11d})$ $\displaystyle=$
$\displaystyle\varphi^{t}_{u}.$ $\displaystyle(\text{by }\eqref{proptau2b})$

Finally, we define $g\in\mbox{\rm Aut}(\mathcal{T})$ by means of (2.6),
setting $g(u,w)\coloneqq(\pi(u),g_{u}(w))$ for all $u\in
V_{\mathcal{T}}\setminus W_{\mathcal{T}}$, $w\in\mathcal{T}_{u}$, and
$g\rvert_{W_{\mathcal{T}}}\coloneqq\pi\rvert_{W_{\mathcal{T}}}$. Taking also
(7.15) into account, from (2.7) we deduce that $\varphi\circ g=\varphi$ and
$\psi\circ g=\varphi^{t}$, that is $g\varphi=\varphi$ and $g\varphi^{t}=\psi$;
cf. (6.21). ∎

##  8 The irreducible representations of $\mbox{\rm Aut}(\mathcal{T})$

Now we set the stage for the application of Mackey’s theory of induced
representations for which we refer to [4, 8, 9, 11, 12, 30].

######  Definition 8.1.

If $\mathcal{P},\mathcal{M}$ are compositional trees for $\mathcal{T}$ we
define $\mathsf{I}(\mathcal{T};\mathcal{P},\mathcal{M})$ as the set of all
equivalence classes of coarsest common refinements of couples
$(\varphi,\psi)\in\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$;
cf. Definition 6.7.

We denote by $[\mathcal{R}]$ an element of
$\mathsf{I}(\mathcal{T};\mathcal{P},\mathcal{M})$. If
$(\varphi,\psi)\in\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$
then we denote by $[\mathcal{R}](\varphi,\psi)$ the equivalence classes in
$\mathsf{I}(\mathcal{T};\mathcal{P},\mathcal{M})$ containing the coarsest
common refinement of $(\varphi,\psi)$. The diagonal action of $\mbox{\rm
Aut}(\mathcal{T})$ on
$\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$
is given by:

$g(\varphi,\psi)\coloneqq(\varphi\circ g^{-1},\psi\circ
g^{-1}),\qquad\text{for
}(\varphi,\psi)\in\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M}),\quad
g\in\mbox{\rm Aut}(\mathcal{T});$

cf. (6.21).

By Theorem 4.1, a strict equivalence class of $\mathcal{P}$-compositions of a
rooted tree $\mathcal{T}$ is determined by the type of its elements and by
Remark 4.6 they coincide with the orbits of $\mbox{\rm Aut}(\mathcal{T})$ on
$\mathsf{C}(\mathcal{T},\mathcal{P})$. Using the notation in (6.21), if
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ we set

$(\mathcal{P},\lvert\varphi^{-1}\rvert)\coloneqq\\{g\varphi\colon
g\in\mbox{\rm Aut}(\mathcal{T})\\}.$

That is, we indicate by $(\mathcal{P},\lvert\varphi^{-1}\rvert)$ the
$\mbox{\rm Aut}(\mathcal{T})$-orbit on $\mathsf{C}(\mathcal{T},\mathcal{P})$
containing $\varphi$. The stabilizer of $\varphi$ in $\mbox{\rm
Aut}(\mathcal{T})$ will be denoted $K_{\varphi}$ so that
$(\mathcal{P},\lvert\varphi^{-1}\rvert)=\mbox{\rm
Aut}(\mathcal{T})/K_{\varphi}$ as homogeneous spaces and (cf. Remark 4.6)

$\mathsf{C}(\mathcal{T},\mathcal{P})=\bigsqcup_{\lvert\varphi^{-1}\rvert\in\mathsf{C}_{T}(\mathcal{T},\mathcal{P})}(\mathcal{P},\lvert\varphi^{-1}\rvert).$

######  Proposition 8.2.

The couples
$(\varphi,\psi),(\varphi^{\prime},\psi^{\prime})\in\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$
belong to the same $\mbox{\rm Aut}(\mathcal{T})$ diagonal orbit if and only if
$[\mathcal{R}](\varphi,\psi)=[\mathcal{R}](\varphi^{\prime},\psi^{\prime})$.
Moreover, $\psi,\psi^{\prime}\in\mathsf{C}(\mathcal{T},\mathcal{M})$ belong to
the same $K_{\varphi}$-orbit if and only if
$[\mathcal{R}](\varphi,\psi)=[\mathcal{R}](\varphi,\psi^{\prime})$.

###### Proof.

From Proposition 6.8 it follows that
$\mathsf{I}(\mathcal{T};\mathcal{P},\mathcal{M})$ parametrizes the strict
equivalence classes of the couples $(\varphi,\psi)$ and these strict
equivalence classes coincide with the orbits of $\mbox{\rm Aut}(\mathcal{T})$
on
$\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$.
∎

######  Definition 8.3.

If $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and
$\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ are fixed tree compositions we
denote by
$\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)$ the
set of all equivalence classes of coarsest common refinements of couples
$(\varphi^{\prime},\psi^{\prime})\in(\mathcal{P},\lvert\varphi^{-1}\rvert)\times(\mathcal{P},\lvert\psi^{-1}\rvert)$.

By Proposition 8.2,
$\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)$
parametrizes the diagonal orbits of $\mbox{\rm Aut}(\mathcal{T})$ on
$\mathsf{C}(\mathcal{T},\mathcal{P})\times\mathsf{C}(\mathcal{T},\mathcal{M})$
and the $K_{\varphi}$-orbits on $(\mathcal{P},\lvert\psi^{-1}\rvert)$; see
[11, Corollary 10.4.13]. Then for each
$[\mathcal{R}]\in\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)$
we can choose $\psi_{[\mathcal{R}]}\in(\mathcal{P},\lvert\psi^{-1}\rvert)$
such that
$[\mathcal{R}]\left(\varphi,\psi_{[\mathcal{R}]}\right)=[\mathcal{R}]$ and
then $t_{[\mathcal{R}]}\in\mbox{\rm Aut}(\mathcal{T})$ such that
$t_{[\mathcal{R}]}\psi=\psi_{[\mathcal{R}]}$. It follows that
$t_{[\mathcal{R}]}K_{\psi}t_{[\mathcal{R}]}^{-1}=K_{\psi_{[\mathcal{R}]}}$.
Moreover,

$H_{[\mathcal{R}]}\coloneqq
K_{\varphi}\cap\left(t_{[\mathcal{R}]}K_{\psi}t_{[\mathcal{R}]}^{-1}\right)\;\text{
is the stabilizer in }\;K_{\varphi}\;\text{ of }\;\psi_{[\mathcal{R}]}$ (8.1)

and the orbits of $K_{\varphi}$ on $(\mathcal{P},\lvert\psi^{-1}\rvert)$ are

$\left\\{k\psi_{[\mathcal{R}]}\colon k\in
K_{\varphi}\right\\}\equiv\left\\{kt_{[\mathcal{R}]}\psi\colon k\in
K_{\varphi}\right\\},\qquad[\mathcal{R}]\in\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert).$

Finally,

$\mbox{\rm
Aut}(\mathcal{T})=\bigsqcup_{[\mathcal{R}]\in\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)}K_{\varphi}t_{[\mathcal{R}]}K_{\psi}$
(8.2)

is the decomposition of $\mbox{\rm Aut}(\mathcal{T})$ into double
$K_{\varphi}-K_{\psi}$ cosets, cf. [11, Section 11.3].

We define the sign representation $\text{sign}\colon\mbox{\rm
Aut}(\mathcal{T})\rightarrow\\{\pm 1\\}$ of $\mbox{\rm Aut}(\mathcal{T})$
inductively as follows. If $H(\mathcal{T})=1$ then it is the usual sign
representation of the symmetric group. If $H(\mathcal{T})>1$ then we use the
notions and notation in Example 3.7, we assume that sign is defined on the
groups $\mbox{\rm Aut}\left(\mathcal{T}_{u_{c}}\right)$, $c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}$ and we set

$\text{sign}(g)\coloneqq\text{sign}\left(g\rvert_{V_{\mathcal{T}}}\right)\cdot\prod_{c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}}\prod\limits_{v\in\text{\rm
tv}^{-1}(c)}\text{sign}\left(\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\right),$ (8.3)

where we have chosen and used a system of $\tau$’s for the trivial composition
(cf. Definition 3.3). Clearly $\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\in\mbox{\rm Aut}\left(\mathcal{T}_{u_{c}}\right)$.

######  Lemma 8.4.

The function sign in (8.3) is a representation of $\mbox{\rm
Aut}(\mathcal{T})$ and it does not depend on the choice of the $\tau$’s.

###### Proof.

If $g,g^{\prime}\in\mbox{\rm Aut}(\mathcal{T})$ then

$\begin{split}\text{sign}(g^{\prime}g)=&\text{\rm
sign}\left[(g^{\prime}g)\rvert_{V_{\mathcal{T}}}\right]\cdot\prod_{\begin{subarray}{c}c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}\\\ v\in\text{\rm
tv}^{-1}(c)\end{subarray}}\text{sign}\left[\tau_{u_{c},g^{\prime}g(v)}\circ(g^{\prime}g)_{v}\circ\tau_{v,u_{c}}\right]\\\
(\text{by }\eqref{firstldell2}\text{ and
}\eqref{proptau2b})\quad=&\text{sign}\left(g^{\prime}\rvert_{V_{\mathcal{T}}}\right)\cdot\text{sign}\left(g\rvert_{V_{\mathcal{T}}}\right)\cdot\prod_{\begin{subarray}{c}c\in
V_{\mathcal{C}}\setminus W_{\mathcal{C}}\\\ v\in\text{\rm
tv}^{-1}(c)\end{subarray}}\Bigl{\\{}\text{sign}\left[\tau_{u_{c},g^{\prime}g(v)}\circ
g^{\prime}_{g(v)}\circ\tau_{g(v),u_{c}}\right]\cdot\\\
&\qquad\cdot\text{sign}\left[\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\right]\Bigr{\\}}\\\ (\text{by
}\eqref{squaresigmap17})\quad=&\text{sign}(g^{\prime})\cdot\text{sign}(g).\end{split}$

Now suppose that the $\tau^{\prime}_{u,v}$’s form another pseudogroup of
equivalences for the trivial composition. Then for every $v\in\text{\rm
tv}^{-1}(c)$ there exists $\widetilde{g}_{v}\in\mbox{\rm
Aut}\left(\mathcal{T}_{u_{c}}\right)$ such that
$\tau^{\prime}_{v,u_{c}}=\tau_{v,u_{c}}\circ\widetilde{g}_{v}$ and therefore

$\begin{split}\prod_{v\in\text{\rm
tv}^{-1}(c)}\text{sign}\left(\tau^{\prime}_{u_{c},g(v)}\circ
g_{v}\circ\tau^{\prime}_{v,u_{c}}\right)=&\prod_{v\in\text{\rm
tv}^{-1}(c)}\text{sign}\left(\widetilde{g}_{g(v)}^{-1}\circ\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\circ\widetilde{g}_{v}\right)\\\
=&\prod_{v\in\text{\rm
tv}^{-1}(c)}\text{sign}\left(\widetilde{g}_{g(v)}^{-1}\right)\cdot\text{sign}\left(\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\right)\cdot\text{sign}\left(\widetilde{g}_{v}\right)\\\
(\text{by }\eqref{squaresigmap17})\quad=&\prod_{v\in\text{\rm
tv}^{-1}(c)}\text{sign}\left(\tau_{u_{c},g(v)}\circ
g_{v}\circ\tau_{v,u_{c}}\right).\end{split}$

∎

Equivalently, the sign representation may be defined by means of the
decomposition (3.24) and very elementary Clifford theory but our definition is
more suitable for explicit computations (cf. the proof of (8.6)) and it is in
line with our previous notation.

We denote by $\iota_{G}$ the trivial representation of the group $G$.

######  Definition 8.5.

If $\varphi$ is a tree composition of $\mathcal{T}$ we set

$M^{\lvert\varphi^{-1}\rvert}\coloneqq\mbox{\rm Ind}_{K_{\varphi}}^{\text{\rm
Aut}(\mathcal{T})}\iota_{K_{\varphi}}\quad\text{ and
}\quad\widetilde{M}^{\lvert\varphi^{-1}\rvert}\coloneqq\mbox{\rm
Ind}_{K_{\varphi}}^{\text{\rm Aut}(\mathcal{T})}\text{sign}.$

Clearly, $M^{\lvert\varphi^{-1}\rvert}$ is the permutation representation of
$\mbox{\rm Aut}(\mathcal{T})$ on $(\mathcal{P},\lvert\varphi^{-1}\rvert)$.

######  Proposition 8.6.

If $\varphi$ and $\psi$ are equivalent as compositions of $\mathcal{T}$ then,
as $\mbox{\rm Aut}(\mathcal{T})$-representations,
$M^{\lvert\varphi^{-1}\rvert}$ is equivalent to $M^{\lvert\psi^{-1}\rvert}$
and $\widetilde{M}^{\lvert\varphi^{-1}\rvert}$ is equivalent to
$\widetilde{M}^{\lvert\psi^{-1}\rvert}$.

###### Proof.

If $\varphi$ and $\psi$ are equivalent tree compositions as in the first
diagram in (2.13), but with $\mathcal{T}_{1}=\mathcal{T}_{2}=\mathcal{T}$,
then $\psi=\omega\circ\varphi\circ\tau^{-1}$, with $\tau\in\mbox{\rm
Aut}(\mathcal{T})$ and $\omega$ an isomorphism between the corresponding
compositional trees. Therefore $\psi\circ
g^{-1}=\omega\circ\varphi\circ\left(\tau^{-1}\circ
g^{-1}\circ\tau\right)\circ\tau^{-1}$ for all $g\in\mbox{\rm
Aut}(\mathcal{T})$ and it follows that

$K_{\varphi}=\tau^{-1}K_{\psi}\tau.$ (8.4)

From [7, Proposition 3.1.11] we deduce that the homogeneous spaces $\mbox{\rm
Aut}(\mathcal{T})/K_{\varphi_{1}}$ and $\mbox{\rm
Aut}(\mathcal{T})/K_{\varphi_{2}}$ are isomorphic and therefore the
corresponding permutation representations are equivalent.

Similarly, now we show that (8.4) implies that
$\widetilde{M}^{\lvert\psi^{-1}\rvert}$ and
$\widetilde{M}^{\lvert\varphi^{-1}\rvert}$ are equivalent representations.
Indeed, $\widetilde{M}^{\lvert\psi^{-1}\rvert}$ is the space of all functions
$f\colon\mbox{\rm Aut}(\mathcal{T})\rightarrow\mathbb{C}$ such that
$f(gk)=\text{sign}(k^{-1})f(g)$, for all $g\in\mbox{\rm Aut}(\mathcal{T})$,
$k\in K_{\psi}$, with the left regular representation (cf. [11, Section
1.11]); then the map
$T\colon\widetilde{M}^{\lvert\psi^{-1}\rvert}\rightarrow\widetilde{M}^{\lvert\varphi^{-1}\rvert}$
given by $[Tf](g)\coloneqq f(g\circ\tau^{-1})$, for all $g\in\mbox{\rm
Aut}(\mathcal{T})$, is an equivalence between the induced representations
(very easy to check). ∎

In the case $h=1$ (the representation theory of the symmetric group)
Proposition 8.6 corresponds to the equivalence between the permutation and the
sign-induced modules associated to the Young subgroups corresponding to the
same numerical partition; cf. [21, p. 36].

Denote by
$\mathsf{I}_{0}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)$
the set of all
$[\mathcal{R}]\in\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)$
which represent equivalence classes of trivial common refinements.

######  Proposition 8.7.

If $\varphi$ and $\psi$ are tree compositions of $\mathcal{T}$ then

$\text{\rm dim}\mbox{\rm Hom}_{\text{\rm
Aut}(\mathcal{T})}\left(M^{\lvert\varphi^{-1}\rvert},M^{\lvert\psi^{-1}\rvert}\right)=\left\lvert\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)\right\rvert$
(8.5)

and

$\text{\rm dim}\mbox{\rm Hom}_{\text{\rm
Aut}(\mathcal{T})}\left(M^{\lvert\varphi^{-1}\rvert},\widetilde{M}^{\lvert\psi^{-1}\rvert}\right)=\left\lvert\mathsf{I}_{0}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)\right\rvert.$
(8.6)

###### Proof.

The identity in (8.5) follows from (8.2) and Mackey’s intertwining numbers
Theorem (cf. [8, (6.2)], [11, Corollary 11.4.5]). Similarly, Mackey’s formula
for the invariants (cf. [8, Theorem 6.1], [11, Corollary 11.4.4]) yields

$\mbox{\rm Hom}_{\text{\rm
Aut}(\mathcal{T})}\left(M^{\lvert\varphi^{-1}\rvert},\widetilde{M}^{\lvert\psi^{-1}\rvert}\right)=\bigoplus_{[\mathcal{R}]\in\mathsf{I}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert\psi^{-1}\rvert)}\mbox{\rm
Hom}_{H_{[\mathcal{R}]}}\left(\iota,\text{sign}\right),$

where $\iota$ and sign are respectively the trivial and the sign
representations of $H_{[\mathcal{R}]}$. But if $\mathcal{R}$ is not trivial
then $H_{[\mathcal{R}]}$ contains some $g$ with $\text{sign}(g)=-1$; for
instance, from the inductive definition (8.3) it follows that the sign of the
$g$ in (6.22) is $\,-1$ and from Lemma 6.11 and (8.1) it follows that this $g$
belongs to $H_{[\mathcal{R}]}$. If this is the case then the trivial and the
sign representations are not equivalent and therefore the corresponding Hom
space is trivial. By contrast, if $\mathcal{R}$ is trivial then also
$H_{[\mathcal{R}]}$ is trivial and the corresponding Hom space is one-
dimensional and this ends the proof of (8.6). ∎

######  Corollary 8.8.

The $\mbox{\rm Aut}(\mathcal{T})$-representations
$M^{\lvert\varphi^{-1}\rvert}$ and
$\widetilde{M}^{\lvert(\varphi^{t})^{-1}\rvert}$ have a unique irreducible
common constituent, which is contained in both of them with multiplicity one.

###### Proof.

From Theorem 7.11 it follows that if $\varphi^{t}$ is a transpose of $\varphi$
then
$\left\lvert\mathsf{I}_{0}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert(\varphi^{t})^{-1}\rvert)\right\rvert=1$
and then we may apply (8.6). ∎

######  Definition 8.9.

In the notation of Definition 4.7, let
$\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ and denote by $\Lambda$ the
associated tree of partitions. Then we define $S^{\Lambda}$ as the unique
irreducible common constituent of $M^{\lvert\varphi^{-1}\rvert}$ and
$\widetilde{M}^{\lvert(\varphi^{t})^{-1}\rvert}$ (cf. Corollary 8.8). By
Theorem 7.9 and Proposition 8.6, $S^{\Lambda}$ does not depend on the choice
of $\varphi$ and of its transposed $\varphi^{t}$ but just on $\Lambda$.

Finally, we are in position to give a list of all irreducible representations
of the group of automorphisms of $\mathcal{T}$.

######  Theorem 8.10.

The set $\\{S^{\Lambda}:\Lambda\in\mathsf{Par}(\mathcal{T})\\}$ is a complete
list of pairwise, inequivalent representations of the group $\mbox{\rm
Aut}(\mathcal{T})$.

###### Proof.

First of all, we prove that if
$(\Lambda,\mathcal{Q}),(\Gamma,\mathcal{N})\in\mathsf{Par}(\mathcal{T})$ are
not isomorphic, then $S^{\Lambda}$ and $S^{\Gamma}$ are not equivalent.
Indeed, if $\varphi\in\mathsf{C}(\mathcal{T},\mathcal{P})$ is associated to
$(\Lambda,\mathcal{Q})$ and $\psi\in\mathsf{C}(\mathcal{T},\mathcal{M})$ to
$(\Gamma,\mathcal{N})$, by (8.6) and Definition 8.9, the equivalence of
$S^{\Lambda}$ and $S^{\Gamma}$ would lead to
$\left\lvert\mathsf{I}_{0}(\mathcal{T};\lvert\varphi^{-1}\rvert,\lvert(\psi^{t})^{-1}\rvert)\right\rvert\neq
0$, so that, by Theorem 7.10 and recalling that $\psi$ is a transpose of
$\psi^{t}$, $\varphi<\psi$; by symmetry, we get also $\psi<\varphi$ and this
is impossible. Therefore the irreducible representations in the statement are
pairwise inequivalent and, by Corollary 5.5, this system is also complete. ∎

######  Example 8.11.

In the notation of Example 3.7 we have: $K_{\text{\rm
id}_{\mathcal{T}}}=\\{1_{\text{\rm Aut}(\mathcal{T})}\\}$ and $K_{\text{\rm
tv}_{\mathcal{T}}}=\mbox{\rm Aut}(\mathcal{T})$. Therefore $M^{\lvert\text{\rm
id}_{\mathcal{T}}^{-1}\rvert}$ is the regular representation of $\mbox{\rm
Aut}(\mathcal{T})$, $M^{\lvert\text{\rm tv}_{\mathcal{T}}^{-1}\rvert}$
coincides with the trivial representation $\iota_{\text{\rm
Aut}(\mathcal{T})}$ and $\widetilde{M}^{\lvert\text{\rm
tv}_{\mathcal{T}}^{-1}\rvert}$ is the sign representation. If we denote by
$\Lambda_{\text{\rm id}}$ and $\Lambda_{\text{\rm tv}}$ the trees of
partitions respectively of the identity and trivial composition (see Example
4.4 for the case of a spherically homogeneous tree), taking Example 7.8 into
account, we have

$S^{\Lambda_{\text{\rm tv}}}\text{ is the trivial representation},\qquad
S^{\Lambda_{\text{\rm id}}}\text{ is the sign representation}.$

Finally, arguing as in [21, p. 36], we can prove that, for every tree
composition $\varphi$ of $\mathcal{T}$ with associated tree of partitions
$\Lambda$, we have

$S^{\Lambda_{\text{\rm id}}}\otimes
M^{\lvert\varphi^{-1}\rvert}\sim\widetilde{M}^{\lvert\varphi^{-1}\rvert}\quad\text{
and }\quad S^{\Lambda_{\text{\rm id}}}\otimes S^{\Lambda}\sim S^{\Lambda^{t}}$

where $\Lambda^{t}$ is the tree of partitions associated to any transposed
$\varphi^{t}$ of $\varphi$. Indeed, the first equivalence follows from an easy
application of [11, Corollary 11.1.17]; the second equivalence follows from
the fact that $S^{\Lambda_{\text{\rm id}}}\otimes S^{\Lambda}$ is contained
both in $S^{\Lambda_{\text{\rm id}}}\otimes
M^{\lvert\varphi^{-1}\rvert}\sim\widetilde{M}^{\lvert\varphi^{-1}\rvert}$ and
in $S^{\Lambda_{\text{\rm
id}}}\otimes\widetilde{M}^{\lvert(\varphi^{t})^{-1}\rvert}\sim
M^{\lvert(\varphi^{t})^{-1}\rvert}$, so that it coincides with
$S^{\Lambda^{t}}$.

######  Open Problem 8.12.

Is it possible to generalize other results of representation theory from the
symmetric group to $\mbox{\rm Aut}(\mathcal{T})$? For instance, is it possible
to compute the dimension of the irreducible representations $S^{\Lambda}$? Is
it possible to describe the decomposition into irreducible representations of
the permutation representations $M^{\lvert\varphi^{-1}\rvert}$ in Definition
8.5 obtaining a Young rule for $\mbox{\rm Aut}(\mathcal{T})$? A first step
toward this direction is in [6], which contains the decomposition of the
permutation representations in Example 2.9 (and generalizes [21, Lemma
2.2.19]). Other interesting intermediate steps might be: the case
$H(\mathcal{T})=2$ (cf. Example 2.8); the case of a spherically homogeneous
binary tree (cf. Example 4.9 and [26]) and the permutation representations in
Example 2.10.

######  Open Problem 8.13.

If $G_{j}$ is a finite group acting on a finite set $X_{j}$, $j=1,2,\dotsc,h$,
then we may construct the iterated wreath product

$G_{h}\wr G_{h-1}\wr\dotsb\wr G_{2}\wr G_{1}.$ (8.7)

It is a group of permutations of $X_{1}\times X_{2}\times\dotsb\times X_{h}$,
which may be seen as the set of leaves of a spherically homogeneous rooted
tree; see [10, Section 2.1.3]. The description of the conjugacy classes of
wreath products and of their irreducible representations (by means of Clifford
theory) in [21, Chapter 4] and [10, Chapter 2], might be used to study the
representation theory of groups of the form (8.7). An example is in [26],
which is devoted to the case of iterated wreath product of cyclic groups. The
present paper contains the representation theory of iterated wreath products
of symmetric groups as in (2.2) as a particular case but it is not obtained by
means of Clifford theory. We suppose that the case of arbitrary finite groups
should require the development of suitable combinatorial tools to manage the
iteration of Clifford theory and that these tools should have the same
complexity of the combinatorics developed in the present paper.

## References

  * [1] R.M. Adin, Y Roichman, On characters of wreath products, Comb. Theory, 2 (2022), no. 2, Paper No. 17, 12 pp.
  * [2] M. Aigner Combinatorial theory. Grundlehren der Mathematischen Wissenschaften, 234. Springer-Verlag, Berlin-New York, 1979.
  * [3] H. Bass, M. V. Otero-Espinar, D. Rockmore, C. Tresser, Cyclic renormalization and automorphism groups of rooted trees. Lecture Notes in Math., 1621 Springer-Verlag, Berlin, 1996.
  * [4] D. Bump, Lie groups. Grad. Texts in Math., 225 Springer-Verlag, New York, 2004.
  * [5] T. Ceccherini-Silberstein and M. Coornaert, Exercises in cellular automata and groups, Springer Monographs in Mathematics, Springer, Cham, 2023.
  * [6] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Trees, wreath products and finite Gelfand pairs, Adv. Math., 206 (2006), no. 2, 503–537.
  * [7] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Harmonic Analysis on Finite Groups. Representation theory, Gelfand pairs and Markov chains. Cambridge Studies in Advanced Mathematics, 108. Cambridge University Press, Cambridge, 2008.
  * [8] T. Ceccherini-Silberstein, A. Machì, F. Scarabotti and F. Tolli, Induced representation and Mackey theory. J. Math. Sci. (N.Y.) 156 (2009), no. 1, 11–28.
  * [9] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Representation theory of the symmetric groups: the Okounkov-Vershik approach, character formulas, and partition algebras. Cambridge Studies in Advanced Mathematics 121, Cambridge University Press 2010.
  * [10] T. Ceccherini-Silberstein, F.Scarabotti and F.Tolli: Representation Theory and Harmonic Analysis of wreath products of finite groups. London Mathematical Society Lecture Note Series 410, Cambridge University Press, 2014.
  * [11] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Discrete Harmonic Analysis. Representations, Number Theory, Expanders, and the Fourier Transform. Cambridge Studies in Advanced Mathematics, 172. Cambridge University Press, Cambridge, 2018.
  * [12] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Gelfand triples and their Hecke algebras—harmonic analysis for multiplicity-free induced representations of finite groups. With a foreword by Eiichi Bannai. Lecture Notes in Mathematics, 2267. Springer, Cham, (2020)
  * [13] A. J. Coleman, Induced representations with applications to Sn and GL(n) Queen’s Papers in Pure and Appl. Math., No. 4 Queen’s University, Kingston, ON, 1966
  * [14] R. Diestel, Graph Theory, Fifth edition, Grad. Texts in Math., 173 Springer, Berlin, 2017.
  * [15] A. Figà-Talamanca, C. Nebbia, Harmonic analysis and representation theory for groups acting on homogeneous trees. London Math. Soc. Lecture Note Ser., 162 Cambridge University Press, Cambridge, 1991.
  * [16] P. W. Gawron, V. V. Nekrashevych, V. I. Sushchansky, Conjugation in tree automorphism groups Internat. J. Algebra Comput. 11 (2001), no.5, 529–547.
  * [17] R.I. Grigorchuk, Just infinite branch groups. New horizons in pro-$p$ groups, 121–179, Progr. Math., 184, Birkhäuser Boston, Boston, MA, 2000.
  * [18] C. Godsil, G. Royle, Algebraic graph theory. Grad. Texts in Math., 207 Springer-Verlag, New York, 2001.
  * [19] M. Gromov, Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc.  1 (1999), no. 2, 109–197.
  * [20] N. Jacobson, Basic algebra, vol. 1 (2nd ed.), Dover, 2009.
  * [21] G. D. James, A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics and its Applications 16, Addison Wesley, Reading, MA, 1981.
  * [22] A. Kerber, J. Tappe, On permutation characters of wreath products. Discrete Math. 15 (1976), no.2, 151–161.
  * [23] S. J. Mayer, On the irreducible characters of the symmetric group, Advances in Math. 15 (1975), 127–132.
  * [24] A. Mishra, M. K. Srinivasa, The Okounkov-Vershik approach to the representation theory of $G\sim S_{n}$, J. Algebraic Combin., 44 (2016), no. 3, 519–560.
  * [25] G. I. Olšhanskiĭ, Classification of the irreducible representations of the automorphism groups of Bruhat-Tits trees, Functional Anal. Appl. 11 (1977), no. 1, 26–34.
  * [26] R.C. Orellana, M.E. Orrison, D.N. Rockmore, Rooted trees and iterated wreath products of cyclic groups. Adv. in Appl. Math. 33 (2004), no.3, 531–547.
  * [27] B. E. Sagan, The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition Grad. Texts in Math., 203 Springer-Verlag, New York, 2001.
  * [28] B. E. Sagan, Combinatorics: the art of counting. Graduate Studies in Mathematics, 210. American Mathematical Society, Providence, RI, 2020.
  * [29] R.P. Stanley, Enumerative combinatorics. Volume 1. Second edition. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 2012.
  * [30] S. Sternberg, Group theory and physics. Cambridge University Press, Cambridge, 1994.

Fabio Scarabotti, Dipartimento SBAI, Sapienza Università di Roma, via A.
Scarpa 8, 00161, Roma, Italy
Istituto Nazionale di Alta Matematica “Francesco Severi”, 00185 Roma, Italy
e-mail<EMAIL_ADDRESS>