Transducing Linear Decompositions of Tournaments

In Section 2, we introduce an infinite monoid ${ℭ}_K$ corresponding to linear clique-width decompositions of width $K$, and a finite quotient $M_K$ of ${ℭ}_K$. This gives us the power to use Simon’s forest factorisation theorem, stated in Section 2, which for any word in ${ℭ}_K$ yields a factorisation, subject to regularity conditions relative to $M_K$, and with depth only depending on $|M_K|$. In Section 3, we use induction on the factorisation given by Simon’s theorem to prove a weakening of Theorem 3: we construct a transduction which yields not a clique-width decomposition, but simply the associated vertex ordering. Section 4 then shows how to transduce from this ordering to the linear clique-width decomposition, completing the proof of Theorem 3, and finally shows how it implies Theorem 4.

Omitted proofs can be found in the full version of the paper.

We denote by $[n]$ the interval of integers $\{1,\mathrm{\dots },n\}$. A tournament $T=(V,E)$ is a directed graph with for each pair $u\ne v$ of vertices in $V$, exactly one of the two possible directed edges $(u,v)$ or $(v,u)$ in $E$. We also write $V(T)≔V$ and $E(T)≔E$ for the vertex and edge sets of $T$, and denote an oriented edge $(u,v)\in E(T)$ as $u\to v$ to emphasise its orientation. A bipartite tournament $B=(L,R,E)$ is defined similarly restricting to edges between the two vertex sets $L$ and $R$: the edge set $E$ consists of exactly one of $u\to v$ or $v\to u$ for each pair of vertices $u\in L$ and $v\in R$. In a tournament $T$, two disjoint subsets of vertices $A,B\subset V(T)$ are called homogenous if the edges between them are either all oriented from $A$ to $B$, i.e. $a\to b$ is an edge for all $a\in A$ and $b\in B$, or inversely all from $B$ to $A$.

There are several graph complexity measures that are equivalent to (linear) clique-width. For our purposes, we will use the monoid structure defined in Section 2.

Our logic terminology is standard, we refer to [6] for instance. We refer also to [6] for definitions of transductions. In our setting, an FO transduction is a composition of the following atomic transductions:

• $\mathrm{■}$

  interpretation, which consists in adding to the input structure a new relation defined by an FO-formula,

• $\mathrm{■}$

  colouring, which consists in adding unary relations to the input structure,

• $\mathrm{■}$

  filtering, which consists in outputting the input only if it satisfies an FO-formula.

• $\mathrm{■}$

  universe restriction, which consists in restricting the universe of the input to the elements satisfying an FO formula, and binding each relation to the restricted universe.

It is well-known that any FO transduction can be equivalently expressed using only one instance of each operation, in the following order: colouring, filtering, interpretation, and universe restriction²²2Usually one allows copying first to linearly increase the domain, but we do not use copying in our setting.. If $\mathrm{\Phi }$ is an FO transduction, we denote by $\mathrm{\Phi }(K)$ the set of outputs for input $K$. A transduction $\mathrm{\Phi }$ is an extension transduction if for any input $S$ of $\mathrm{\Phi }$, any $T\in \mathrm{\Phi }(S)$ is an extension of $S$.

A bag is essentially a tournament with some additional information describing how it should be glued with other bags, so as to define a deterministic product operation on bags. For $k\in \mathbb{N}$, a bag $B$ of order $k$ consists of the following:

1. 1.

   An internal tournament $(V(B),E^{\text{int}}(B))$, whose vertices $V(B)$ and edges $E^{\text{int}}(B)$ are called internal vertices and internal edges.

2. 2.

   A boundary bipartite tournament $([k],V(B),E^{\partial }(B))$. Here, $1,\mathrm{\dots },k$ are called input vertices, and stand for colour classes of vertices to the left of $B$.

3. 3.

   A colouring ${\lambda }_B:V(B)\to [k]$ of the internal vertices.

4. 4.

   A recolouring function ${\rho }_B:[k]\to [k]$, which can be seen as a re-colouring of the input vertices.

A visual representation of bags is depicted in Figure 1 below. We do not define linear clique-width and refer to [7] for its definition. The objective is to prove that if a tournament has linear clique-width $k$, then it is a value of a word from a finite alphabet composed of bags. Let us define for that the multiplication operator on bags. Intuitively, when multiplying on the right by the bag $B$, the following happens: edges are added between any $v\in V(B)$ and all existing vertices of colour $c$ according to the direction of the edge $c\to v$ or $c\leftarrow v$ in $E^{\partial }(B)$. Then, existing vertices have their colours modified by applying ${\rho }_B$, while internal vertices of $B$ are given their colour from ${\lambda }_B$.

Formally, the product $B_1\cdot B_2$ of two bags $B_1$ and $B_2$ of order $k$ is defined as follows:

1. 1.

   The internal vertices are $V(B_1\cdot B_2)≔V(B_1)\uplus V(B_2)$. Internal edges $E^{\text{int}}(B_1\cdot B_2)$ are obtained as follows: Inside $V(B_1)$ and $V(B_2)$ respectively, edges are exactly as in $E^{\text{int}}(B_1)$ and $E^{\text{int}}(B_2)$. Between them, for $x\in V(B_1)$ with colour $c≔{\lambda }_{B_1}(x)$ and $y\in V(B_2)$, there is an edge $x\to y$ (resp. $x\leftarrow y$) if and only if $c\to y$ (resp. $c\leftarrow y$) is a boundary edge in $E^{\partial }(B_2)$.

2. 2.

   For $i\in [k]$ an input vertex and $x\in V(B_2)$, there is a boundary edge $i\to x$ (resp. $x\to i$) in $E^{\partial }(B_1\cdot B_2)$ if and only if there is the edge ${\rho }_{B_1}(i)\to x$ (resp. $x\to {\rho }_{B_1}(i)$) in $E^{\partial }(B_2)$. When $x\in V(B_1)$, the edge between $i$ and $x$ is simply the same as in $E^{\partial }(B_1)$.

3. 3.

   The colouring ${\lambda }_{B_1\cdot B_2}$ of internal vertices coincides with ${\rho }_{B_2}\circ {\lambda }_{B_1}$ inside $V(B_1)$, and simply with ${\lambda }_{B_2}$ inside $V(B_2)$.

4. 4.

   Finally, the recolouring function is ${\rho }_{B_2}\circ {\rho }_{B_1}$.

In this product, we think of $B_1$ as being to the left of, or earlier than $B_2$. See Figure 1 for an example. Note that we only define the product of two bags of the same order, although it would be simple to lift this restriction by extending the set of colours of one bag. It is easy to check that the product is associative, and the empty bag with identity recolouring is the neutral element. Thus, the set of bags of order $k$ has a monoid structure. We often write $AB$ instead of $A\cdot B$ when it is clear from the context.

A bag is called atomic if it has at most one internal vertex. We denote by ${ℭ}_k$ the submonoid generated by atomic bags of order $k$. The following essentially says that we can concentrate on ${ℭ}_k$ when dealing with tournaments of linear clique-width at most $k$.

Thanks to Lemma 5, we call by extension any word $B_1\cdot B_2\cdot \mathrm{\dots }\cdot B_n$ of atomic bags a linear decomposition.

We next define some finite abstraction of bags. The first step is to define types of vertices inside a bag. Consider a bag $B$ and an internal vertex $v\in V(B)$. The type of $v$ describes its interactions with bags which may be multiplied to the left or right of $B$. Specifically, ${\mathrm{𝗍𝗒𝗉𝖾}}_B(v)$ consists of the following information:

1. 1.

   the colour ${\lambda }_B(v)$, and

2. 2.

   the direction of edges $i\to v$ or $i\leftarrow v$ for each input vertex $i\in [k]$.

We use $\sigma ,\tau ,\mathrm{\dots }$ to denote vertex types. When the order $k$ of the bag is fixed, there are only $k\cdot 2^k$ distinct vertex types.

Next, we define the abstraction of a bag. If $B$ is a bag and $\tau$ is a vertex type, we denote by $\tau (B)≔\{v\in V(B):{\mathrm{𝗍𝗒𝗉𝖾}}_B(v)=\tau \}$ the set of vertices with type $\tau$ in $B$. The type $\tau$ is inhabited in $B$ if $\tau (B)$ is non-empty. The abstraction of $B$, denoted by $⟦B⟧$, now consists of the following information:

1. 1.

   the recolouring function ${\rho }_B:[k]\to [k]$,

2. 2.

   the set of inhabited vertex types in $B$, and

3. 3.

   for each pair of inhabited types $\sigma ,\tau$, whether $\sigma (B)$ and $\tau (B)$ are homogeneous or not in the internal tournament of $B$, and when they are, the direction of edges $\sigma (B)\to \tau (B)$ or $\sigma (B)\leftarrow \tau (B)$.

We use $\alpha ,\beta ,\mathrm{\dots }$ to denote abstractions of bags. For fixed order $k$, the number of bag abstractions is some constant $2^{2^{O(k)}}$.

One checks that the map $B\mapsto ⟦B⟧$ from bags to abstractions is a monoid homomorphism. We denote by $M_k$ this monoid of abstractions of bags of order $k$. We summarise all these properties in the following.

Given a linear decomposition $B=B_1{B}_2\mathrm{\dots }{B}_n$, Simon’s theorem gives a factorisation forest, which is a more structured way to construct $B$ from $B_1,\mathrm{\dots },B_n$, subject to some restrictions relative to a finite semigroup $S$ of our choice – in our case the monoid of abstractions.

The general setting of Simon’s theorem is the following. Consider a (usually infinite) semigroup $\mathrm{\Sigma }$ and a generating set $A\subset \mathrm{\Sigma }$, a finite semigroup $S$, and a homomorphism $\phi :\mathrm{\Sigma }\to S$. In our case, $\mathrm{\Sigma }$ are the bags, $A$ the atomic bags, $S$ the abstractions, and $\phi (B)=⟦B⟧$. Simon’s theorem deals with two kinds of factorisations of elements $w\in \mathrm{\Sigma }$:

binary factorisation:

$w=w_1\cdot w_2$ for $w_1,w_2\in \mathrm{\Sigma }$ with no further restriction.

idempotent factorisation:

$w=w_1\cdot \mathrm{\dots }\cdot w_n$, where the number $n$ of factors is unrestricted, but the factors must all map to the same $e=\phi (w_i)$ in $S$, which furthermore must be idempotent, meaning $e\cdot e=e$.

Simon’s theorem states that any $w\in \mathrm{\Sigma }$ can be reduced down to generators in $A$ by applying the previous two operations nested only up to a depth bounded by a linear function of $|S|$. This process is described as a factorisation forest for $w$.

Let us introduce some terminology allowing to count binary and idempotent factorisations separately. A factorisation forest has depth $(p,q)$ if the nesting depth of idempotent operations is at most $p$, and that of binary operations is at most $q$. Formally:

• $\mathrm{■}$

  Generators $a\in A$ have a factorisation forest of depth $(0,0)$.

• $\mathrm{■}$

  If $w_1,w_2$ have factorisation forests of depth $(p_1,q_1)$ and $(p_2,q_2)$ respectively, then $w_1\cdot w_2$ has a factorisation forest of depth

  $$(\max \{p_1,p_2\},\max \{q_1,q_2\}+1).$$

• $\mathrm{■}$

  If $w_1,\mathrm{\dots },w_n\in \mathrm{\Sigma }$ satisfy $\phi (w_i)=e$ for some idempotent $e\in S$ and all $1\le i\le n$, and there are $p,q\in \mathbb{N}$ such that each $w_i$ has a factorisation forest of depth $(p_i,q_i)$, then $w_1\cdot \mathrm{\dots }\cdot w_n$ has a factorisation forest of depth $(\max \{p_1,\mathrm{\dots },p_n\}+1,\max \{q_1,\mathrm{\dots },q_n\})$.

Since this definition depends on the choice of semigroup $S$ and morphism $\phi$, we will call it a factorisation forest over $\phi$ to disambiguate.

In the case of bags, we will apply Theorem 7 to the monoid ${ℭ}_K$ with atomic bags as generators, and the abstraction homomorphism $⟦\cdot ⟧:{ℭ}_K\to M_K$. Since we will only consider factorisation forests over the abstraction homomorphism, we will omit the “over $⟦\cdot ⟧$” qualifier in the rest of this work.

The proof of our main result proceeds by induction over the depth of a given factorisation forest. At some point during this induction, we may need to restrict the bag considered to a subset of vertices. In general, this does not preserve the factorisation depth. Indeed, deleting vertices in a bag may change its abstraction, and what was an idempotent factorisation may thus stop being one. This section describes a sufficient condition to control the depth of factorisation forests when deleting vertices.

Given a bag $B$ and a subset $X\subseteq V(G)$ of internal vertices, we denote by $B[X]$ the bag obtained by deleting any internal vertex of $B$ outside $X$, and restricting the edges and colouring map of $B$ to $X$. If $\mathrm{\Gamma }$ is a set of vertex types, then we denote by $\mathrm{\Gamma }(B)={\bigcup }_{\tau \in \mathrm{\Gamma }}\tau (B)$ the set of vertices with type in $\mathrm{\Gamma }$, and we say that $\mathrm{\Gamma }(B)$ is a union of types. When deleting vertices from bags, we will only delete unions of types, which is sufficient to control the factorisation depth.

By Lemma 5, any tournament $T$ with linear clique-width $k$ is also the internal tournament of some bag $B$ in ${ℭ}_k$. Furthermore, by Theorem 7, this bag $B$ has factorisation depth at most $(|M_k|,2|M_k|)$, where $M_k$ is the monoid of abstractions of arity $k$, whose size is a function of $k$ only. Thus, Theorem 9 follows from the next statement and the arguments given above for checking that an ordering has small cut-rank.

We once again insist that the output ${\mathrm{\Phi }}_{(p,q)}^k(T)$ needs to contain some linear ordering of $T$ with the required cut-rank, but may also contain other structures where is interpreted arbitrarily (possibly not even as a linear ordering). Thus we will show that if non-deterministic steps follow the “right” choices, then the transduction produces the desired ordering, while ignoring anything resulting from a “wrong” choice.

Let us begin the proof of Lemma 10, by induction on the pair $(p,q)$ ordered lexicographically. Choose the bound $f(k,p,q)$ to satisfy:

Consider a bag $B\in {ℭ}_K$ whose internal tournament is $T$, and with factorisation depth $(p,q)$.

In the base case $p=q=0$, the bag $B$ is atomic, and the result is trivial. Assume now that $p>0$ or $q>0$, so that the Simon’s factorisation of $B$ has either a binary or an idempotent operation at the root. The transduction ${\mathrm{\Phi }}_{(p,q)}^k$ starts by guessing which of these two cases occurs (this can be simulated using a colouring step), and will continue with a different transduction for each.

Assume $B=B_1\cdot B_2$ where $B_1,B_2$ have factorisations of depth at most $(p,q-1)$. We use a non-deterministic colouring to guess the bipartition $V(B_1),V(B_2)$. Then, by restricting the quantifiers to $V(B_i)$, one can simulate applying the transduction ${\mathrm{\Phi }}_{(p,q-1)}^k$ obtained by induction to each $T[V(B_i)]$. Thus, we obtain linear orderings of cut-rank at most $f(k,p,q-1)$ for $T[V(B_1)]$ and $T[V(B_2)]$ respectively.

Define on $T$ by , where coincides with inside $V(B_i)$. One can transduce from and the bipartition $V(B_1),V(B_2)$. Since we are dealing with bags of arity $k$, we have $\mathrm{𝗋𝗄}(V(B_1);V(B_2))⩽k$. Since has cut-rank at most $f(k,p,q-1)$ in $T[V(B_i)]$ for $i\in \{1,2\}$, this implies that has cut-rank at most $f(k,p,q-1)+k\le f(k,p,q)$.

Assume now we are given an idempotent factorisation, that is $B=B_1\cdot \mathrm{\dots }\cdot B_n$ where $⟦B_i⟧=\alpha$ for all $1\le i\le n$, with $\alpha$ idempotent, and each $B_i$ has factorisation depth at most $(p-1,q)$.

Consider the quasi-ordering $⪯$ of $V(B)$ defined by $V(B_1)⪯\mathrm{\cdots }⪯V(B_n)$, and call $\sim$ the equivalence relation whose classes are $V(B_1),\mathrm{\dots },V(B_n)$. Suppose in a first time that we are given $⪯$ (transducing it will be the core of this proof). The Parallel Application Lemma [1, Lemma 5.6] allows to apply ${\mathrm{\Phi }}_{(p-1,q)}^k$ to each $B_i$ simultaneously, yielding a relation which inside each $B_i$ is interpreted as a linear ordering of cut-rank at most $f(k,p-1,q)$.

Define to be the linear ordering which coincides with inside each bag $B_i$, and with $⪯$ between the bags. Clearly can be transduced from and $⪯$, and it is not hard to check that its cut-rank depends only on the cut-rank of $⪯$ and of .

We are thus only left with the core problem of transducing the quasi-ordering $⪯$. Unfortunately, it is not always possible to transduce exactly $⪯$. For instance $B$ might have two strongly connected components $X_1,X_2$, each intersecting all $B_j$. Then, we might be able to transduce $⪯$ inside each $X_i$, but it will be impossible to transduce $⪯$ between $X_1$ and $X_2$. Indeed, as $X_1$ and $X_2$ are distinct strongly connected components, we infer that the edges are all oriented from one of them to the other one. For all integers , to transduce $⪯$, we should have that the elements of $X_2\cap B_i$ come before the elements of $X_1\cap B_k$, and the elements of $X_2\cap B_j$ come after the elements of $X_1\cap B_k$. However, the adjacency between $X_1$ and $X_2$ is homogenous and can be therefore transduced from an independent set (or a clique), which is not possible to order in CMSO. In this case, we need to reorganise the decomposition of $B$ by first separating $X_1$ and $X_2$, and then decomposing each of them. The precise statement we prove is thus the following.

Assuming Lemma 11, we conclude as follows. From the quasi-ordering $⪯$, it is simple to transduce the equivalence relation $\sim$ with equivalence classes $X_1,\mathrm{\dots },X_m$. Recall that we do induction on $(p,q)$ ordered lexicographically, hence we can assume the transduction ${\mathrm{\Phi }}_{(p-1,q+2p)}^k$ is already defined. Using the Parallel Application Lemma [1, Lemma 5.6], this transduction can be again applied to each $X_i$ in parallel. This yields a relation which inside each $T[X_i]$ is a linear ordering with cut-rank at most $f(k,p-1,q+2p)$. Define to coincide with inside each $X_i$ and with $⪯$ between the different $X_i$, which is easily transduced from . Using Condition 2 of Lemma 11, it is not hard to prove that has cut-rank at most

This concludes the idempotent case, and thus the proof of Lemma 10.

We are now going to prove Lemma 11. From now on, we fix some $k\in \mathbb{N}$, and consider a factorisation $B=B_1\cdot \mathrm{\dots }\cdot B_n$, where all $B_i$ have the same idempotent abstraction $\alpha$, and have factorisation depth at most $(p-1,q)$. We also call $T=(V,E)$ the internal tournament of $B$.

Recall that Lemma 11 asks for a transduction depending only on $k$. As the very first step of this transduction, one may use non-deterministic colouring to guess the abstraction $\alpha$ (for which there are only finitely many possibilities for a fixed $k$, by Lemma 6). We may thus instead allow the transductions constructed in this section to depend on both $k$ and $\alpha$ (but not $B$, the factorisation, or $p,q$).

For a vertex $x\in V(B_i)$, we call $\mathrm{𝗂𝖽𝗑}(x)=i$ the index of $x$. Our goal is to answer (with an FO transduction) the question: given $x,y$, is $\mathrm{𝗂𝖽𝗑}(x)⩽\mathrm{𝗂𝖽𝗑}(y)$? To be formal, for a subset $X$ of $V(B)$, we say that a transduction $\mathrm{\Phi }$ orders $X$ according to $⪯$ if $\mathrm{\Phi }$ is an extension FO transduction, and there is some $(V,E,{⪯}^{\prime })\in \mathrm{\Phi }(T)$ such that $⪯$ and ${⪯}^{\prime }$ coincide on $X$.

Using the non-determinism of transductions, one may show that it suffices to consider vertices whose indices differ by at least some constant. That is, say that $\mathrm{\Phi }$ approximately orders $X$ according to $⪯$ if $\mathrm{\Phi }$ is an extension FO transduction, and there is $(V,E,{⪯}^{\prime })\in \mathrm{\Phi }(T)$ such that $⪯,{⪯}^{\prime }$ coincide for any pair $x,y\in X$ that satisfies $|\mathrm{𝗂𝖽𝗑}(x)-\mathrm{𝗂𝖽𝗑}(y)|⩾2$. When $X$ hits all bags of the factorisation, if we can approximately order $X$, then we can also order it:

Let us call $\rho$ the recolouring function of the bags $B_i$. It is the same for all bags since it is part of the abstraction $\alpha$, and it is idempotent ($\rho \circ \rho =\rho$). Consider any vertex of $B$, say $x\in V(B_i)$. In the bag $B_i$, $x$ is given some colour ${\lambda }_{B_i}(x)$, which we call its initial colour ${\lambda }_{init}(x)$. Then, as we multiply by $B_{i+1}$, the colour of $x$ changes to $\rho ({\lambda }_{init}(x))$. Continuing with $B_{i+2}$ will again recolour $x$ by applying $\rho$, but since $\rho$ is idempotent, this does nothing. Thus, for any $j>i$, the colour of $x$ in $B_1\cdot \mathrm{\dots }\cdot B_j$ is $\rho ({\lambda }_{init}(x))$. We call this its final colour and denote it by ${\lambda }_{fin}(x)$.

Recall that to define the abstraction $\alpha$ of the bags $B_i$, we first defined the vertex type ${\mathrm{𝗍𝗒𝗉𝖾}}_{B_i}(x)$ of $x$ inside the bag $B_i$, which indicates its colour ${\lambda }_{B_i}(x)$, i.e. the initial colour, and the direction of edges between $x$ and input vertices in $B_i$. In what follows, the type of a vertex $x$ will always be understood relative to the bag $B_i$ containing it, and we shorten it to $\mathrm{𝗍𝗒𝗉𝖾}(x)$. Using a non-deterministic colouring, we can guess the types of all vertices in $B$, and we assume this colouring to be given in all subsequent lemmas. With this in hand, we can already order the vertices of a given type $\tau$. Denote by $V_{\tau }={\bigcup }_i\tau (B_i)$ the set of vertices of type $\tau$. Note that if $V_{\tau }$ is non-empty, then it intersects all bags $B_1,\mathrm{\dots },B_n$. Indeed whether or not $B_i$ contains a vertex of type $\tau$ is indicated by the abstraction $\alpha$.

Thus we can order the vertices of each type independently, and the issue is now to combine these orderings. Denote by $\mathrm{\Gamma }$ the set of inhabited vertex types in $B_1,\mathrm{\dots },B_n$. Recall that subsets of vertices $X,Y$ are called homogeneous if either all edges are oriented from $X$ to $Y$, or all from $Y$ to $X$. We define the synchronisation graph $G^{\mathrm{𝗌𝗒𝗇}}$ with vertices $\mathrm{\Gamma }$, in which $\sigma ,\tau$ are adjacent if and only if $V_{\sigma }$ and $V_{\tau }$ are not homogeneous.

We show that when $G^{\mathrm{𝗌𝗒𝗇}}$ is connected, one can transduce the quasi-ordering $⪯$ corresponding to the original decomposition $B_1\cdot \mathrm{\dots }\cdot B_n$:

When $G^{\mathrm{𝗌𝗒𝗇}}$ is connected, Lemma 14 concludes the proof of Lemma 11. Note in that case that the given factorisation $B=B_1\cdot \mathrm{\dots }\cdot B_n$ is not modified, i.e. the partition $\{X_1,\mathrm{\dots },X_m\}$ in the conclusion of Lemma 11 is exactly $\{B_1,\mathrm{\dots },B_n\}$, and conditions (1) and (2) of the statement are trivial. We now handle the case where $G^{\mathrm{𝗌𝗒𝗇}}$ is disconnected by slightly modifying this decomposition.

Assume that $G^{\mathrm{𝗌𝗒𝗇}}$ has several connected components that we enumerate as ${\mathrm{\Theta }}_1,\mathrm{\dots },{\mathrm{\Theta }}_r$. We then reorganise the decomposition of $B$. For $i\in [n]$ and $t\in [r]$, call $X_{t,i}$ the set of internal vertices of $B_i$ with types in ${\mathrm{\Theta }}_t$. By Lemma 14, for each $t\in [r]$, the set $V_{{\mathrm{\Theta }}_t}$ can be ordered according to $⪯$ with a transduction. Let ${⪯}^{\prime }$ be the quasi-ordering on the partition $\{X_{t,i}\mid i\in [n],t\in [r]\}$ obtained by ordering first according to the index $t$ of the connected component ${\mathrm{\Theta }}_t$ of the type, and then by the index $i$ of the bag $B_i$, i.e.

One can prove that this quasi-ordering ${⪯}^{\prime }$ has small cut-rank. We can therefore complete the proof of Lemma 11, by checking the three conditions of the statement.

1. 1.

   Firstly, each $T[X_{t,i}]$ is the internal tournament of a bag in ${ℭ}_k$ of factorisation depth at most $(p-1,q+2p)$. Indeed, this follows from Lemma 8 since $T[X_{t,i}]$ is the restriction of $T[V(B_i)]$ to some union of types, and $B_i$ is a bag in ${ℭ}_k$ and has factorisation depth at most $(p-1,q)$ by assumption.

2. 2.

   We can prove that the quasi-ordering $X_{1,1}{⪯}^{\prime }\mathrm{\cdots }{⪯}^{\prime }{X}_{1,n}{⪯}^{\prime }\mathrm{\cdots }{⪯}^{\prime }{X}_{r,1}{⪯}^{\prime }\mathrm{\cdots }{⪯}^{\prime }{X}_{r,n}$ has cut-rank at most $k\cdot (2^k+1)$.

3. 3.

   Finally, there is an extension FO transduction ${\mathrm{\Psi }}_k$ depending only on $k$ such that for $T=(V,E)$ the internal tournament of $B$, we have $(V,E,{⪯}^{\prime })\in {\mathrm{\Psi }}_k(T)$. Indeed, from Lemma 14, we can obtain the restriction of ${⪯}^{\prime }$ to any $V_{{\mathrm{\Theta }}_t}$ by a transduction depending only on $k,\alpha ,\mathrm{\Theta }$. By first guessing the type of each vertex, ordering by types between the different sets $V_{{\mathrm{\Theta }}_1},\mathrm{\dots },V_{{\mathrm{\Theta }}_r}$, and by the previous transductions inside each $V_{{\mathrm{\Theta }}_t}$, we obtain the desired quasi-ordering ${⪯}^{\prime }$.

   This transduction depends on $k$, the abstraction $\alpha$ of bags, and the synchronisation graph $G^{\mathrm{𝗌𝗒𝗇}}$. Since there are only finitely many possible choices for $\alpha$ and for $G^{\mathrm{𝗌𝗒𝗇}}$ when $k$ is fixed, thus the transduction ${\mathrm{\Psi }}_k$ may first guess $\alpha$ and $G^{\mathrm{𝗌𝗒𝗇}}$, and then proceed as above.

This completes the proof of Lemma 11, and with it Theorem 9.