CMSO-Transducing Tree-Like Graph Decompositions

We use standard terminology of graph theory, and we fix some notations. Given a directed graph $G$, its sets of vertices and edges are denoted by $V(G)$ and $E(G)$, respectively. We denote by uv an edge $(u,v)\in E(G)$. An undirected graph is no more than a directed graph for which $E(G)$ is symmetric (i.e., $uv\in E(G)\iff vu\in E(G)$). The notions of paths, connected components, etc… are defined as usual. Given a subset $Z$ of $V(G)$, we denote by $G[Z]$ the sub-graph of $G$ induced by $Z$.

A tree is a connected undirected graph without cycles. In the context of trees, we use a slightly different terminology than for graphs. In particular, vertices are called nodes, nodes of degree at most $1$ are called leaves, and nodes of degree greater than $1$ are called inner. The set of leaves is denoted $L(T)$; thus the set of inner nodes is $V(T)\setminus L(T)$. For a node $t$ of a tree $T$ and a neighbor $s$ of $t$, we denote by $T_s^t$ the connected component of $T-t$ containing $s$. We sometimes consider rooted trees, namely trees with a distinguished node, called the root. Rooted trees enjoy a natural orientation of their edges toward the root, which induces the usual notions of parent, child, sibling, ancestor and descendant. Hence, we represent a rooted tree by a set of nodes with an ancestor/descendant relationship (instead of specifying the root). We use the convention that every node is one of its own ancestors and descendants. We refer to ancestors (resp. descendants) of a node that are not the node itself as proper ancestors (resp. proper descendants). For a node $t$ of a rooted tree $T$, we denote by $T_t$ the subtree of $T$ rooted in $t$ (i.e., the restriction of $T$ to the set of descendants of $t$).

A set system is a pair $(U,𝒮)$ where $U$ is a finite set, called the universe, and $𝒮$ is a family of subsets of $U$ where $\mathrm{\varnothing }\notin 𝒮$, $U\in 𝒮$, and $\{a\}\in 𝒮$ for every $a\in U$.²²2Though these restrictions on $𝒮$ are not usual for set systems, it is convenient for our contribution and it does not significantly impact the generality of set systems: every family $ℱ$ of subsets of $U$ can be associated with a set system $(U,𝒮)$ where $𝒮=\left(ℱ\setminus \{\mathrm{\varnothing }\}\right)\cup \left\{U\right\}\cup \{\{a\}\mid a\in U\}$. Two sets $X$ and $Y$ overlap if they are neither disjoint nor related by containment. A set system $(U,𝒮)$ is said to be laminar (aka overlap-free) when no two sets from $𝒮$ overlap. By extension, a set family $𝒮$ is laminar if $(\bigcup 𝒮,𝒮)$ is a laminar set system (note this also requires that $\mathrm{\varnothing }\notin 𝒮$, $\bigcup 𝒮\in 𝒮$, and $\{a\}\in 𝒮$ for every $a\in \bigcup 𝒮$).

A laminar family $𝒮$ of subsets of $U$ naturally defines a rooted tree where the nodes are the sets from $𝒮$, the root is $U$, and the ancestor relation corresponds to set inclusion. We call this rooted tree the laminar tree of $U$ induced by $𝒮$ (or laminar tree of $(U,𝒮)$). In this rooted tree, the leaves are the singletons $\{x\}$ for $x\in U$, which we identify with the elements themselves. That is to say, $L(T)=U$. Laminar trees have the property that each inner node has at least two children. Observe also that the size of a laminar tree is linearly bounded in the size of the universe.

Let $a\in \pi (S)$ and let $s={\pi }^{-1}(a)$. By definition, $s$ is an ancestor of $a$ which belongs to $S$. Let $y$ be the least ancestor of $a$ that is contained in $S$. As $s$ is an ancestor of $a$ belonging to $S$, $y$ must be a descendant of $s$. Hence, $y$ is $s$-requested in $(\pi ,\sigma )$. Additionally, by Item 3 of Remark 3, $y$ is $y$-requested in $(\pi ,\sigma )$. Since $(\pi ,\sigma )$ has unique request, $y=s$. Thus, $s$ is the least ancestor of $a$ which belongs to $S$. $◀$

Notice that, by Item 1 of Remark 3, a similar result holds for each $b\in \sigma (S)$. It follows that the sets $\pi (S)$ and $\sigma (S)$ characterize $(\pi ,\sigma )$.

Let $s\in S$, $a=\pi (s)$, and $s^{\prime }={\pi }^{\prime -1}(a)$. Both $s$ and $s^{\prime }$ are the least ancestor of $a$ which belongs to $S$, hence $s=s^{\prime }$ and ${\pi }^{\prime }(s)=a$. Thus $\pi ={\pi }^{\prime }$. By Item 1 of Remark 3, we also obtain that $\sigma ={\sigma }^{\prime }$. $◀$

Let $A$ and $B$ be two disjoint subsets of $L$. We call such a pair $(A,B)$ a bi-colouring. We say that $(A,B)$ identifies $S$ if there exists a pair $(\pi ,\sigma )$ identifying $S$ with unique request such that $\pi (S)=A$ and $\sigma (S)=B$. By the previous lemma, for a fixed set $S\subseteq V\setminus L$ the pair $(\pi ,\sigma )$ identifying $S$ is unique when it exists. We will also prove that $S$ is actually uniquely determined from $(A,B)$. Before that, we state the following technical lemma.

Let $x$ be an inner node. We consider the set $S^{\prime }=S\setminus (V(T_x)\setminus \{x\})$ of all nodes which are not proper descendants of $x$ and the restrictions ${\pi }^{\prime }$ and ${\sigma }^{\prime }$ of, respectively, $\pi$ and $\sigma$ to $S^{\prime }$. By Item 2 of Remark 3 $({\pi }^{\prime },{\sigma }^{\prime })$ identify $S^{\prime }$ with unique request. We denote $A^{\prime }={\pi }^{\prime }(S^{\prime })$ and $B^{\prime }={\sigma }^{\prime }(S^{\prime })$, thus $(A^{\prime },B^{\prime })$ identify $S^{\prime }$. Let $A_x^{\prime }=A^{\prime }\cap V(T_x)$ and $B_x^{\prime }=B^{\prime }\cap V(T_x)$ be the sets of representatives contained in $T_x$ of nodes in $S^{\prime }$. Let $a$ be an element of $A_x^{\prime }$. The element $s_a={\pi }^{-1}(a)$ is an ancestor of $x$ because it is an ancestor of $a\in V(T_x)$ and belongs to $S^{\prime }$ whence not to $V(T_x)\setminus \{x\}$. Therefore, $x$ is $s_a$-requested. As $({\pi }^{\prime },{\sigma }^{\prime })$ has unique request, there exists at most one element in $A_x^{\prime }$. Similarly, $B_x^{\prime }$ has size at most $1$. Moreover, $A_x^{\prime }\cap B_x^{\prime }=\mathrm{\varnothing }$ by Item 4 of Remark 3. We thus we have three cases:

Case $A_x^{\prime }\cup B_x^{\prime }=\mathrm{\varnothing }$.

Then there is no $s\in S^{\prime }$ such that $\pi (s)\in V(T_x)$ or $\sigma (s)\in V(T_x)$. Hence, $x$ is not requested in $(\pi ,\sigma )$, in particular, $x\notin S$.

Let $c$ be a child of $x$. If $\left|A\cap V(T_c)\right|\ne \left|B\cap V(T_c)\right|$, then there exists $a\in (A\cup B)\cap V(T_c)$ such that, assuming without loss of generality that $a\in A$ and denoting $s_a={\pi }^{-1}(a)$, $\sigma (s_a)\notin V(T_c)$. Hence, $s_a$ is a proper ancestor of $c$, thus, equivalently, an ancestor of $x$, implying that $x$ is $s_a$-requested in $(\pi ,\sigma )$. This contradicts the above argument. So, $\left|A\cap V(T_c)\right|=\left|B\cap V(T_c)\right|$ for each child $c$ of $x$.

Case $A_x^{\prime }\cup B_x^{\prime }=\{a\}$.

Assume, without loss of generality, that $a\in A$, and denote $s_a={\pi }^{-1}(a)$ and $b=\sigma (s_a)$. We have that $s_a$ is a proper ancestor of $x$, since it is the least common ancestor of $a\in V(T_x)$ and $b\notin V(T_x)$. Thus, $x$ is $s_a$-requested and $s_a\ne x$ so $x\notin S$.

Let $c$ be a child of $x$. If $\left|A\cap V(T_c)\right|\ne \left|B\cap V(T_c)\right|$, then it means that there exists $z\in (A\cup B)\cap V(T_c)$, such that either $z\in A$ and $s_z={\pi }^{-1}(z)\notin V(T_c)$, or $z\in B$ and $s_z={\sigma }^{-1}(z)\notin V(T_c)$. In both cases, $s_z$ is a proper ancestor of $c$, whence an ancestor of $x$. Thus, $x$ is $s_z$-requested in $(\pi ,\sigma )$. However, $x$ is $s_a$-requested in $(\pi ,\sigma )$ which has unique request, hence $s_z=s_a$. If $z\in B$, it follows that $z=b$, which contradicts the fact $b\notin V(T_x)$. Hence, $z\in A$ and thus, $z=\pi (s_a)=a$. Therefore, $\left|(A\setminus \{a\})\cap V(T_c)\right|=\left|B\cap V(T_c)\right|$ for each child $c$ of $x$.

Case $A_x^{\prime }=\{a\}$ and $B_x^{\prime }=\{b\}$.

Let $s_a={\pi }^{-1}(a)$ and $s_b={\sigma }^{-1}(b)$. The node $x$ is $s_a$-requested and $s_b$-requested in $(\pi ,\sigma )$, so, by the unique request property, $s_a=s_b$. Since $s_a$ is the least common ancestor of $a$ and $b$, it belongs to $V(T_x)$ whence $s_a=x$ implying $x\in X$.

Let $c$ be a child of $x$. If $\left|A\cap V(T_c)\right|\ne \left|B\cap V(T_c)\right|$, then there exists $z\in (A\cup B)\cap V(T_c)$ such that either $z\in A$ and $s_z={\pi }^{-1}(z)\notin V(T_c)$, or $z\in B$ and $s_z={\sigma }^{-1}(z)\notin V(T_c)$. In both cases, $s_z$ is a proper ancestor of $c$, whence an ancestor of $x$, and thus $x$ is $s_z$-requested in $(\pi ,\sigma )$. However, $x$ is $x$-requested in $(\pi ,\sigma )$ which has unique request, hence $s_z=x$ and thus $z\in \{a,b\}$. Therefore, $\left|(A\setminus \{a\})\cap V(T_c)\right|=\left|(B\setminus \{b\})\cap V(T_c)\right|$ for each child $c$ of $x$. Because the least common ancestor of $a$ and $b$ is $x$, there is no child $c$ of $x$ containing both $a$ and $b$ as leaves, i.e., $\{a,b\}⊈V(T_c)$.

This concludes the proof of the statement. $◀$

It follows that for each bi-colouring $(A,B)$, there exists at most one set $S$ of inner nodes identified by $(A,B)$.

We proceed by contradiction and thus assume $S\ne S^{\prime }$. Let $s\in S\setminus S^{\prime }$. By Lemma 6, the number of children $c$ of $s$ for which the set $(A\cup B)\cap V(T_c)$ has odd size is $2$ since $s\in S$, while it should also be less than $2$ since $s\notin S^{\prime }$. A contradiction. $◀$

When $(A,B)$ identifies a set $S$, we call $A$-representative (resp. $B$-representative) of $s\in S$ the leaf $\pi (s)\in A$ (resp. $\sigma (s)\in B$), where $(\pi ,\sigma )$ witnessing that $(A,B)$ identifies $S$. An example of bi-colouring identifying a subset of inner nodes is given in Figure 2.

Not every set of inner nodes has a bi-colouring identifying it. To ensure that such a pair exists, we consider thin sets of inner nodes. While thin sets always have bi-colourings identifying them, it is also guaranteed that the set of inner nodes can be partitioned into only 4 thin sets. A subset $X\subseteq V\setminus L$ is thin when, for each $x\in X$ not being the root, on the one hand, the parent $p_x$ of $x$ does not belong to $X$, and on the other hand, $x$ admits at least one sibling (including possible leaves) that does not belong to $X$. Having a thin set $X$ allows to find branches avoiding it.

If $T_s$ has height $0$, then $s$ is a leaf and taking $t=s$ trivially gives the expected path. Otherwise, $s$ is an inner node and, because $X$ is thin, $s$ has at least one child $c_s$ not belonging to $X$. By induction, there is a path from some leaf $t\in V(T_{c_s})$ to $c_s$ avoiding $X$ and, since $s\notin X$, this path could be extended into a path from $t$ to $s$ avoiding $X$. $◀$

The previous lemma allows to identify every thin set.

We proceed by induction on the size of $X$. If $X=\mathrm{\varnothing }$, the result is trivial. Let $n\in \mathbb{N}$ and suppose that for every thin set of size $n$ there exists a pair of injections identifying it with unique request. Let $X$ be a thin set of size $n+1$, and let $s\in X$ be of minimal depth. Clearly, $X\setminus \{s\}$ is thin and thus there exists, by induction, a pair $(\pi ,\sigma )$ of injections from $X\setminus \{s\}$ to $L$ identifying $X\setminus \{s\}$ with unique request. Since $X$ is thin and $s\in X$, we can find two distinct children $c_a$ and $c_b$ of $s$ not belonging to $X$.⁵⁵5Remember that every inner node of $T$ has at least two children (including possible leaves). Then, by Lemma 8, there exists a leaf $a\in V(T_{c_a})$ (resp. a leaf $b\in V(T_{c_b})$) such that the path from $a$ to $c_a$ (resp. from $b$ to $c_b$) avoids $X$. In particular, for each node $y$ along these paths, since $y$ has no ancestor that belongs to $X$ but $s$, $y$ is not requested in $(\pi ,\sigma )$. Hence, extending $\pi$ (resp. $\sigma$) in such a way that, besides mapping each $x\in X\setminus \{s\}$ to $\pi (x)$ (resp. to $\sigma (x)$), it maps $s$ to $a$ (resp. to $b$), we obtain a pair $(\widehat{\pi },\widehat{\sigma })$ of injections from $X$ to $L$ that identifies $X$ with unique request. $◀$

A family $F=(A_1,B_1),\mathrm{\dots },(A_n,B_n)$ of bi-colourings identifies a set $S\subseteq V\setminus L$, if there exists a partition $(S_1,\mathrm{\dots },S_n)$ of $S$ such that, for each $i\in [n]$, $(A_i,B_i)$ identifies $S_i$. Whenever $S=V\setminus L$ we say that $F$ identifies $T$. A collection of subsets of $V\setminus L$ is thin if each of its subsets is thin. We now show that there exists a thin $4$-partition.

We build such a thin $4$-partition as follows. First, consider the partition $(D_e,D_o)$ of $V\setminus L$ in which $D_e$ (resp. $D_o=V\setminus (D_e\cup L)$) is the set of all inner nodes of even (resp. odd) depth. Second, arbitrarily fix one child $c_x$ of $x$ for each inner node $x$, and consider the set $C=\{c_x\mid x\in V\setminus L\}\setminus L$, inducing a partition $(C,\overline{C})$ of $V\setminus L$ where $\overline{C}=V\setminus (L\cup C)$. By refining these two bi-partitions, we obtain a $4$-partition which is thin by construction.5 $◀$

Hence, four bi-colourings are enough to identify $T$. For an example see Figure 3.

The result immediately follows from Lemmas 9 and 10.$◀$

First, we define a formula ${\varphi }_{A,B}(X)$ that, under the above assumption, is satisfied exactly when $X$ belongs to $S$. According to Lemma 6, this happens if and only if $X$ is a node of $T$ (i.e., $\mathrm{𝖲𝖤𝖳}(X)$ is satisfied) and there exists $a\in X\cap A$ and $b\in X\cap B$ such that for each child $Z$ of $X$, $\{a,b\}⊈Z$ and the set $(Z\setminus \{a,b\})\cap (A\cup B)$ has even size. This property is easily expressed in ${\mathrm{C}}_2\mathrm{MSO}$, using the $\mathrm{MSO}$-formula $\mathrm{𝖼𝗁𝗂𝗅𝖽}(X,Y)$ defined previously, as well as the predicate $\mathrm{𝖲𝖤𝖳}$:

Now, we can easily define ${\mathrm{𝗋𝖾𝗉𝗋}}_{A,B}(a,X)$ based on Lemma 4:

This concludes the proof. $◀$

We are now ready to prove the theorem.

The ${\mathrm{C}}_2\mathrm{MSO}$-transduction is obtained by composing the following atomic ${\mathrm{C}}_2\mathrm{MSO}$-transductions. The transduction makes use of the formulas ${\mathrm{𝗋𝖾𝗉𝗋}}_{A,B}(a,X)$ given by Lemma 12.

1. 1.

   Guess a family of four bi-colourings ${(A_i,B_i)}_{i\in [4]}$ identifying $T$ (which exists by Corollary 11).

2. 2.

   Copy the input graph four times, thus introducing four binary relations ${({\mathrm{𝖼𝗈𝗉𝗒}}_i)}_{i\in [4]}$ where ${\mathrm{𝖼𝗈𝗉𝗒}}_i(x,y)$ indicates that $x$ is the $i$-th copy of the original element $y$.

3. 3.

   Filter the universe keeping only the original elements as well as the $i$-th copy of each vertex $a$ for which there exists $X$ such that ${\mathrm{𝗋𝖾𝗉𝗋}}_{A_i,B_i}(a,X)$.

4. 4.

   Define the relation $\mathrm{𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋}(x,y)$ so that it is satisfied exactly when there exist $x^{\prime }$, $X$, $i$, and $Y$ such that, on the one hand $\mathrm{𝖽𝖾𝗌𝖼}(Y,X)$ and ${\mathrm{𝖼𝗈𝗉𝗒}}_i(x,x^{\prime })\wedge {\mathrm{𝗋𝖾𝗉𝗋}}_{A_i,B_i}(x^{\prime },X)$, and, on the other hand, either $y$ is an original element and $Y=\{y\}$, or there exists $y^{\prime }$ and $j$ such that ${\mathrm{𝖼𝗈𝗉𝗒}}_j(y,y^{\prime })\wedge {\mathrm{𝗋𝖾𝗉𝗋}}_{A_j,B_j}(y^{\prime },Y)$.

$◀$

On the $\{\mathrm{𝖲𝖤𝖳}\}$-structure $𝕊$, it is routine to define an $\mathrm{MSO}$-formula ${\varphi }_{\mathrm{𝖲𝖤𝖳}!}(Z)$ that identifies those subsets $Z\subseteq U$ that are strong members of $𝒮$:

Hence, we can design an $\mathrm{MSO}$-interpretation that outputs the $\mathrm{\Sigma }\cup \{\mathrm{𝖲𝖤𝖳}!\}$-structure corresponding to $𝔸$ equipped with the set unary predicate $\mathrm{𝖲𝖤𝖳}!$ that selects strong members of $𝒮$. Thus, up to renaming the predicates $\mathrm{𝖲𝖤𝖳}!$ and $\mathrm{𝖲𝖤𝖳}$, by Theorem 2, we can produce, through a ${\mathrm{C}}_2\mathrm{MSO}$-transduction, the $\mathrm{\Sigma }\cup \{\mathrm{𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋}\}$-structure $𝔸\bigsqcup 𝕋$ where $𝕋$ is the tree-structure modeling the laminar tree $T$ induced by ${𝒮}_{!}$ with $L(T)=U$ (once the output obtained, the interpretation drops the set predicate $\mathrm{𝖲𝖤𝖳}!$ which is no longer needed). $◀$

Clearly, the laminar tree $T$ of a weakly-partitive set system $(U,𝒮)$ does not characterize $(U,𝒮)$. However, as shown by the below theorem, a labeling of its inner nodes and a controlled partial ordering of its nodes are sufficient to characterize all the sets of $𝒮$. For $Z$ a set equipped with a partial order  and $X$ a subset of $Z$, we say that $X$ is a -interval whenever defines a total order on $X$ and for every $a,b\in X$ and every $c\in Z$, implies $c\in X$.

Furthermore, $T$ and $\lambda$ are uniquely determined from $𝒮$, and, for each inner node $t$ of $T$ labeled by $\mathrm{𝗅𝗂𝗇𝖾𝖺𝗋}$, only two orders  are possible, one being the inverse of the other (indeed, inverting an order  does preserve the property of being a -interval). Hence, every weakly-partitive family $𝒮$ is characterized by a labeled and partially-ordered tree  where $T$ is the laminar tree induced by the subfamily ${𝒮}_{!}$ of strong sets of $𝒮$, $\lambda :V(T)\setminus L(T)\to \{\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾},\mathrm{𝗉𝗋𝗂𝗆𝖾},\mathrm{𝗅𝗂𝗇𝖾𝖺𝗋}\}$ is the labeling function, and  is the partial order over $V(T)$. As, up-to inverting some of the orders, is unique, we abusively call it the weakly-partitive tree induced by $𝒮$. Conversely, a weakly-partitive tree characterizes the unique weakly-partitive set system which induced it.

We naturally model a weakly-partitive tree  of a partitive set system $(U,𝒮)$ by the $\{\mathrm{𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋},\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾},\mathrm{𝖻𝖾𝗍𝗐𝖾𝖾𝗇𝖾𝗌𝗌}\}$-structure $𝕋$ of universe $U_{𝕋}=V(T)$ such that $⟨V(T),{\mathrm{𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋}}_{𝕋}⟩⊑𝕋$ models $T$ with $L(T)=U$, ${\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾}}_{𝕋}$ is a unary relation which selects the inner nodes of $T$ of label $\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾}$, i.e., ${\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾}}_{𝕋}={\lambda }^{-1}(\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾})$, and ${\mathrm{𝖻𝖾𝗍𝗐𝖾𝖾𝗇𝖾𝗌𝗌}}_{𝕋}$ is a ternary relation selecting triples $(x,y,z)$ satisfying or . (Although it is possible, through a non-deterministic $\mathrm{MSO}$-transduction, to define  from ${\mathrm{𝖻𝖾𝗍𝗐𝖾𝖾𝗇𝖾𝗌𝗌}}_{𝕋}$, the use of ${\mathrm{𝖻𝖾𝗍𝗐𝖾𝖾𝗇𝖾𝗌𝗌}}_{𝕋}$ rather than  ensures unicity of the output weakly-partitive tree.) The inner nodes of $T$ that are labeled by $\mathrm{𝗅𝗂𝗇𝖾𝖺𝗋}$ can be recovered through an $\mathrm{MSO}$-formula as those inner nodes whose children are related by $\mathrm{𝖻𝖾𝗍𝗐𝖾𝖾𝗇𝖾𝗌𝗌}$. The inner nodes labeled by $\mathrm{𝗉𝗋𝗂𝗆𝖾}$ can be recovered through an $\mathrm{MSO}$-formula as those inner nodes that are labeled neither by $\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾}$ nor by $\mathrm{𝗅𝗂𝗇𝖾𝖺𝗋}$. Using Theorem 14, it is routine to design an $\mathrm{MSO}$-transduction which takes as input a weakly-partitive tree and outputs the weakly-partitive set system which induced it. The inverse ${\mathrm{C}}_2\mathrm{MSO}$-transduction is the purpose of the next result. The proof is omitted due to space constraints.

If $𝒮$ is partitive then the weakly-partitive tree it induces enjoys a simple form, and is truly unique. Indeed, the label $\mathrm{𝗅𝗂𝗇𝖾𝖺𝗋}$ and, thus, the partial order , are not needed.

Hence, in case of a partitive set systems $(U,𝒮)$, we can consider the simpler object $(T,\lambda )$, called the partitive tree induced by $𝒮$ (or the partitive tree of $(U,𝒮)$) in which $\lambda$ maps $V(T)\setminus L(T)$ to $\{\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾},\mathrm{𝗉𝗋𝗂𝗆𝖾}\}$. As a direct consequence of Theorems 16 and 15, we can produce, through a ${\mathrm{C}}_2\mathrm{MSO}$-transduction, the partitive tree induced by a partitive set system and naturally modeled by an $\{\mathrm{𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋},\mathrm{𝖽𝖾𝗀𝖾𝗇𝖾𝗋𝖺𝗍𝖾}\}$-structure.