signature $\mu$, $S$ is chainable. Thus, it suffices to prove that the cardinality of bounds of $\text{Chain}_\mu$ is bounded. If the signature $\mu$ is finite and $m$ is the maximum of the arity, $\text{Chain}_\mu$ is the union of finitely many ages of chainable structures. Since a finite union of hereditary classes with finitely many bounds has finitely many bounds, $\text{Chain}_\mu$ has finitely many bounds. This fact was obtained by Jean [99], who also proved that the class $\text{Monom}_\mu$ of monomorphic structures of signature $\mu$ has only finitely many bounds (these two classes are universal in the sense of Tarski).

Frasnay obtained Theorem 5.6 through a deep analysis of the structure of permutation groups attached to chainable structures. Theorem 5.7, which is an equivalent form, follows from the fact that $\text{Chain}_\mu$ is hereditarily wqo. Indeed, from that, the age of each chainable structure is hereditarily wqo, hence, by Theorem 4.10, the cardinality of its bounds is bounded. The price to pay with this simplification is the absence of numerical estimates.

**Theorem 5.8.** Let $\mathfrak{C}$ be a hereditary class of finite structures. Then the following properties are equivalent.

(i) $\mathfrak{C}$ is an infinite ideal of $\Omega_\mu$ containing no proper infinite ideal;

(ii) $\mathfrak{C}$ is Jónsson, that is, $o(\mathfrak{C}) = \omega$;

(iii) $\mathfrak{C}$ is the age of a countable chainable structure.

**Proof.** (iii) $\Rightarrow$ (ii). If $\mathfrak{C}$ is the age of a chainable relational structure then it is totally ordered by embeddability and has order type $\omega$, thus it is Jónsson.

(ii) $\Rightarrow$ (i). If $\mathfrak{C}$ is Jónsson it does not contain any proper infinite initial segment hence it does not contain any proper infinite ideal.

(i) $\Rightarrow$ (iii). According to Theorem 2.8, $\mathfrak{C}$ is the age of a countable structure, say $R := (V, (\rho_i)_{i \in I})$. If $\mathfrak{C}$ contains no proper infinite subage, then $\text{Age}(R_{\upharpoonright V'}) = \text{Age}(R) = \mathfrak{C}$ for every infinite subset $V'$ of $V$. If $I'$ is any subset of $I$, this property holds for the reduct $R^{\upharpoonright I'}$. If $I'$ is finite, Lemma 5.5 ensures that $R^{\upharpoonright I'}$ has an infinite chainable restriction $R_{\upharpoonright V'}^{\upharpoonright I'}$. Hence, $\text{Age}(R_{\upharpoonright V'}) = \text{Age}(R^{\upharpoonright I'})$. It follows that $R^{\upharpoonright I'}$ is chainable. The compactness argument given after the proof of Lemma 5.5 yields that $R$ is chainable. $\square$

**5.2. An illustration: Cameron's theorem on monomorphic permutation groups.** A group $G$ of permutations on a set $V$ is monomorphic (or set-homogeneous) if for every integer $n$ and two $n$-element subsets $A$ and $B$ of $V$ there exists an element $\sigma$ of $G$ that maps $A$ to $B$ (said differently, the group $G$ acts transitively on subsets of $V$ of a fixed finite cardinality). Cameron [27] proved that on a countable set there are essentially five monomorphic closed groups (for the definition of closed group, see Subsection 1.4.6). In order to present his result, let us recall three well known structures associated to a chain $C := (V, \le)$.

* The betweeness relation $B_C := (V, b_C)$ associated to $C$, where $b_C$ is the set of triples $(x_1, x_2, x_3)$ such that either $x_1 < x_2 < x_3$ or $x_3 < x_2 < x_1$.

* The circular order $T_C := (V, t_C)$ associated to $C$, where $t_C$ is the set of triples $(x_1, x_2, x_3)$ such that $x_{\sigma(1)} < x_{\sigma(2)} < x_{\sigma(3)}$ for some circular permutation $\sigma$ of $\{1, 2, 3\}$.

* The betweeness relation $D_C := (V, d_C)$ associated to the circular order, where $d_C$ is the set of quadruples $(x_1, x_2, x_3, x_4)$ such that $x_{\sigma(1)} < x_{\sigma(2)} < x_{\sigma(3)} < x_{\sigma(4)}$ or $x_{\sigma(4)} < x_{\sigma(3)} < x_{\sigma(2)} < x_{\sigma(1)}$ for some circular permutation $\sigma$ of $\{1, 2, 3, 4\}$.

By construction, these three structures are chainable by $C$. Furthermore, if $C$ is isomorphic to the chain of rational numbers, these three structures are actually homogeneous.

Here is Cameron's theorem.

**Theorem 5.9.** [35] A monomorphic closed group on a countable set is isomorphic, as a permutation group, to one of the following automorphism groups:

(a) $\mathfrak{S}(\mathbb{Q})$, the full symmetric group on the set of rationals, viewed as the automorphism group of the equality relation;

(b) $\text{Aut}(\mathbb{Q})$, the automorphism group of the chain of rational numbers;

(c) $\text{Aut}(B_{\mathbb{Q}})$, the automorphism group of the betweeness relation associated to the chain of rational numbers;
(d) Aut($T_Q$), the automorphism group of the circular order associated with the chain of rational numbers;

(e) Aut($D_Q$), the automorphism group of the betweeness relation associated to the circular order on the rationals.

In addition to the original paper of Cameron [27], there are two research papers [95], [155] and Chapter 13 in Fraïssé's book [76] giving a proof, as well as a presentation in [115].

We give some hints for a proof. We rely on [115].

Clearly, the groups mentioned in the theorem above are monomorphic and closed. The proof of the converse has three parts. Let $G$ be a closed monomorphic group. Since $G$ is closed, $G$ is the automorphism group of a relational structure $R$. If $G$ is monomorphic, $R$ is monomorphic. From Theorem 5.4, $R$ is chainable. This is the first part. Now among the chains chaining $R$ we claim that one is isomorphic to the chain of rational numbers. Indeed, let $C$ be a chain chaining $R$. According to (1) of Lemma 2.18, there is a free operator $\mathcal{P}$ transforming $C$ to $R$. Let $R'$ be the image by $\mathcal{P}$ of the chain of rational numbers. Then $R'$ and $R$ have the same age. One can show that $R'$ is uniformly prehomogeneous. This $R'$ is unique up to isomorphism for its age. Since $R$ is homogeneous, it is uniformly prehomogeneous, hence $R$ and $R'$ are isomorphic (see 2.5 Lemme de préservation, p.320 [155]). This is the second part.

The third part is more subtle. It relies on properties discovered by Frasnay [81, 82] of pairs of chains chaining the same structure. Underlying this are the notions of group sequences, indicative sequences and results of Frasnay that we present briefly (according to the presentation in [115], Subsection 3.2, p. 100).

Let $R$ be a chainable relational structure with domain $V$, and $C$ be a chain (with the same domain $V$) chaining $R$. Let $n$ be an integer such that $n \le |V|$ and let $A := a_1 <_C \dots <_C a_n$ be a $n$-element subset of $V$ ordered by $C$. The set of permutations $\sigma$ of $\underline{n} := \{1, \dots, n\}$ such that the map $a_i \to a_{\sigma(i)}$ is an automorphism of $R \upharpoonright_A$ forms a group. Since $C$ chains $R$, this group is independent of the $n$-element set $A$ and we denote it by $\text{Aut}_n(R, C)$. The sequence of these groups is called the *group-sequence* of the pair $(R, C)$.

To a bichain $B := (V, C, C')$ we associate a sequence of permutations groups, called the *indicative sequence* of the bichain. Let $n$ be a positive integer not larger than the cardinality of $V$, and let $A$ be a $n$-element subset of $V$. Order $A$ by $C$ into the sequence $a_1 <_C \dots <_C a_n$. Let $\sigma$ be the unique permutation of $\underline{n}$ which reorders it into $a_{\sigma(1)} <_C \dots <_C a_{\sigma(n)}$ in the order of $C'$. The collection of these permutations $\sigma$ for $n$ fixed, $A$ belonging to all the $n$-element subsets of $V$, generates a subgroup $\text{Ind}_n(B)$ of $\mathfrak{S}(n)$, called the $n^{th}$ *indicative group of B*. The sequence of these indicative groups is the *indicative sequence of B*. We can now recall the following result of Frasnay ([82], p. 263).

**Lemma 5.10.** The indicative sequence of a bichain $B := (V, C, C')$ whose components have no extreme elements is the group-sequence of one of the five relations defined in Theorem 5.9.

Since for every embedding $\varphi$ of $R$ into $R$, the inverse image of the chain $C$ by $\varphi$ provides a chain $C'$ chaining $R$, automorphisms of $R$ are automorphisms of one of the five relations above. The proof of the theorem follows.

**5.3. Almost chainability, almost monomorphy.** The notions of almost chainable and almost monomorphic structures extend the notions of chainability and monomorphy. Results of Subsection 5.1, notably Theorem 5.7, extend to these structures (see [79, 80, 152, 155]). These results are presented below, but first we mention the profile, which emerged on the occasion of research on almost monomorphy and is examined in Section 6. Here, we just recall the definition. The *profile* of a class $\mathfrak{C}$ of finite relational structures is the function $\varphi_{\mathfrak{C}}$ that counts for every integer $n$ the number $\varphi_{\mathfrak{C}}(n)$ of members of $\mathfrak{C}$ on $n$ elements, isomorphic members being identified. The *profile* of a relational structure $R$, denoted by $\varphi_R$, is the profile of its age.

**Definitions 5.11.** Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure and $K$ be a subset of $V$. The relational structure $R$ is $K$-monomorphic if for every nonnegative integer $n$ and every $A, A' \in [V \setminus K]^n$ there is an isomorphism from $R \upharpoonright_A$ onto $R \upharpoonright_{A'}$ which extends by the identity on $K$ to an isomorphism of $R \upharpoonright_{A \cup K}$ onto $R \upharpoonright_{A' \cup K}$. If $L := (V \setminus K, \le)$ is a chain, $R$ is $(K, L)$-chainable if every local isomorphism of $L$, once extended by the identity on $K$, is a local isomorphism of $R$. The structure $R$ is $K$-chainable if it is $(K, L)$-chainable
for some chain $L$. It is almost monomorphic, resp. almost chainable, if it is $K$-monomorphic, resp. $K$-chainable for some finite subset $K$ of $V$.

It is immediate to see that a relational structure $R := (V, (\rho_i)_{i \in I})$ is $K$-chainable if and only if $R$ is freely interpretable by a structure $S := (V, \leq, (a_k)_{k \in K})$ where $\leq$ is a linear order on $V$, $K$ is an initial segment of the chain $(V, \leq)$ and the $a_k$'s are constants defining $K$. This fact allows to apply (2) of Lemma 2.18. It yields:

**Lemma 5.12.** If $R$ is almost chainable then every $R'$ with $\text{Age}(R')$ included into $\text{Age}(R)$ is almost chainable.

We will see in Theorem 5.16 that the notions of $K$-monomorphy and $K$-chainability coincide when $V \setminus K$ is infinite. This requires Ramsey's theorem and the compactness theorem of first order logic. But, before, it is worth recording the following result. It has some importance and requires no tools.

**Theorem 5.13.** Let $R$ be a relational structure and $K$ be a subset of $V(R)$. If $V(R) \setminus K$ is infinite and $R$ is $K$-monomorphic (or $K$-chainable), then $\varphi_R$ is non-decreasing, that is, $\varphi_R(n) \leq \varphi_R(n+1)$ for every integer $n$. Furthermore, $\max\{\varphi_R(n) : n \in \mathbb{N}\} \leq 2^{|K|}$, if $K$ is finite.

**Proof.** We relax the condition $V(R) \setminus K$ infinite, supposing only that $n < |V(R) \setminus K|$ and prove that $\varphi_R(n) \leq \varphi_R(n+1)$. Let $(\tau_i)_{i \leq \varphi_R(n)}$ be the types of the $n$-element restrictions of $R$. For each $\tau_i$, let $F_i$ be such that $R_{\upharpoonright F_i}$ has type $\tau_i$ and the cardinality of $K \cap F_i$ is minimum. Let $x_i \in V(R) \setminus (K \cup F_i)$. We claim that the restrictions $R_{\upharpoonright F_i \cup \{x_i\}}$ are pairwise non-isomorphic, proving that $\varphi_R(n) \leq \varphi_R(n+1)$. If the claim does not hold, there are $i \neq j$ such that the restrictions $R_{\upharpoonright F_i \cup \{x_i\}}$ and $R_{\upharpoonright F_j \cup \{x_j\}}$ are isomorphic. Without loss of generality, we may suppose that $|K \cap F_i| \geq |K \cap F_j|$. Let $f$ be an isomorphism from $R_{\upharpoonright F_i \cup \{x_i\}}$ onto $R_{\upharpoonright F_j \cup \{x_j\}}$. Let $y_i := f(x_i)$. Then $R_{\upharpoonright F_i}$ and $R_{\upharpoonright F_j \cup \{x_j\} \setminus \{y_i\}}$ are isomorphic. If $y_i \notin K$ then since $R$ is $K$-monomorphic, $R_{\upharpoonright F_j \cup \{x_j\} \setminus \{y_i\}}$ and $R_{\upharpoonright F_j}$ are isomorphic, hence $R_{\upharpoonright F_i}$ and $R_{\upharpoonright F_j}$ are isomorphic. This is impossible. Hence $y_i \in K$. But then $f(F_i) \subseteq F_j \cup \{x_j\} \setminus \{y_j\}$, hence $|f(F_i) \cap K| < |F_j \cap K| \leq |F_i \cap K|$, contradicting our choices of $F_i$ and $F_j$. Finally, note that if two $n$-element subsets coincide on $K$ then the restrictions to these subsets are isomorphic, hence $\varphi_R(n) \leq 2^{|K|}$. $\square$

From Ramsey's theorem, Fraïssé deduced the "lemma of the almost chainable restriction".

**Lemma 5.14.** Let $R$ be a relational structure with domain $V$ and $K$ be a subset of $V$. If $V$ is infinite, $K$ is finite and the signature of $R$ is finite then there is an infinite subset $V'$ of $V$ containing $K$ on which the restriction $R' := R_{\upharpoonright V'}$ is $K$-chainable.

The proof is a straightforward adaptation of the proof of Lemma 5.5.

There is a "dual version" of this result (see [152], III.2.2.3, p.326). It requires less than the finiteness of the signature.

**Lemma 5.15.** Let $R$ be a relational structure with domain $V$ and $V'$ be a set containing $V$. Let $C := (V' \setminus V, \leq)$ be a chain. If $\text{Age}(R)$ is level-finite, then there is a relational structure $R'$ extending $R$ on $V'$ which is $(V, C)$-chainable and which has the same age as $R$.

The proof is based on Lemma 5.14 and the compactness theorem of first order logic. The use of this latter result is easier through the Diagram Method of Robinson: give names to the elements of $V$, use axioms to describe the diagram of $R$ and $C$ and express the $(V, C)$-chainability of finite reducts. Use Lemma 5.14 to get the consistency of those axioms. Obtain an extension of $R$ and restrict it to $V'$. Use the fact that $\text{Age}(R)$ is level-finite to prove that this restriction has the same age as $R$.

The analog of Theorem 5.4 also follows from Lemma 5.14 and compactness.

**Theorem 5.16.** Let $R$ be a relational structure with domain $V$ and $K$ be a subset of $V$. If $V \setminus K$ is infinite, then $R$ is $K$-monomorphic if and only if it is $K$-chainable.

**Proposition 5.17.** If an infinite relational structure $R$ is almost chainable then there is a least subset (for set inclusion) $K$ for which it is $K$-chainable. This set $K$ is the kernel $\ker(R)$ of $R$.
**Proof.** Let $R$ be $K$-chainable with $K$ finite. Since $V(R) \setminus K$ is infinite then for every $x \in V \setminus K$, $\text{Age}(R_x) = \text{Age}(R)$, hence $\text{ker}(R) \subseteq K$. Conversely, if $A$ is any finite subset of $V \setminus \text{ker}(R)$ then, since $K$ is finite, there is some local isomorphism of $R$ mapping $A$ on some subset $A'$ disjoint from $K \cup A$ and fixing $\text{ker}(R)$ pointwise (Lemma 3.33). Since $R_{\upharpoonright K \cup A'}$ is $K$-chainable, $R_{\upharpoonright \text{ker}(R) \cup A'}$ is $\text{ker}(R)$-chainable, hence $R_{\upharpoonright \text{ker}(R) \cup A}$ is $\text{ker}(R)$-chainable. Via the Compactness Theorem of First Order Logic, $R$ is $\text{ker}(R)$-chainable. $\square$

The existence of a least $K$ was discovered by Fraïssé; eventually, it leads to the notion of kernel of an arbitrary relational structure.

**Proposition 5.18.** (1) If the signature of a countable relational structure $R$ is finite then $V(R)$ is the union of an increasing sequence $(V_n)_{n \in \mathbb{N}}$ of countable subsets such that each restriction $R_{\upharpoonright V_n}$ is almost chainable.

(2) Every level-finite and infinite age $\mathfrak{A}$ is the union of an increasing chain of ages of infinite almost chainable structures.

**Proof.** Let $R$ be countable with $\mathfrak{A} := \text{Age}(R)$.

(1) Let $(x_n)_{n \in \mathbb{N}}$ be an enumeration of $V(R)$. Define a sequence $(K_n, V_n)_{n \in \mathbb{N}}$ such that $K_n := \{x_0, \dots, x_{n-1}\} \subset V_n \subseteq V(R)$, $V_n$ is infinite, $R_{\upharpoonright V_n}$ is $K_n$-chainable and $V_{n+1} \setminus K_{n+1} \subseteq V_n$. If $(K_n, V_n)$ is defined, apply Lemma 5.5 to $R_{\upharpoonright K_n \cup \{x_{n+1}\}}$ and define $(K_{n+1}, V_{n+1})$.

(2) Apply Lemma 5.15. Get some extension $R'$ with $\text{Age}(R') = \mathfrak{A}$ which is $V(R)$-chainable. Enumerate $K$ by a sequence $x_0, \dots, x_n, \dots$; set $K_0 := \emptyset$, $K_n := \{x_0, \dots, x_{n-1}\}$ for $n \ge 1$. Then $R_n := R_{\upharpoonright K_n \cup (V(R') \setminus K)}$ is $K_n$-chainable. The sequence of the ages of $R_n$ is increasing and their union covers $\text{Age}(R)$. $\square$

An infinite hereditary class of finite structures is well-founded with respect to embeddability, but not necessarily level-finite. If it is level-finite, then Lemma 5.3 applies. This yields:

**Proposition 5.19.** Let $\mu$ be a finite signature.

(a) Each infinite hereditary subclass $\mathfrak{C}$ of $\Omega_\mu$ contains the age of an infinite chainable structure.

(b) The number of such ages is finite.

(c) For each $T \in \Omega_\mu$ there is a minimal infinite age containing $T$.

(d) Each minimal infinite age containing $T \in \Omega_\mu$ is the age of an almost chainable structure.

**Proof.** (a) Since the signature $\mu$ is finite, $\mathfrak{C}$ is level-finite, hence by Lemma 5.3 it contains a Jónsson hereditary subclass. This class has ordinal length $\omega$, hence by Theorem 5.8, this subclass is the age of a chainable relational structure.

(b) By definition, for each chainable structure $R$ there is some chain $C$ chaining $R$. Since $R$ is freely interpretable by $C$ there is a free operator $\mathcal{P}$ such that $\mathcal{P}(C) = R$. The number of free operators transforming binary relations into relational structures of signature $\mu$ ($\mu$ finite) is finite (cf. [75] Ch.4, 4.3.4, p. 90) hence the number of ages of chainable structures of signature $\mu$ is finite.

(c) Since $\mu$ is finite, $\Omega_\mu$ is level-finite hence, by Proposition 2.13, $\text{Id}(\Omega_\mu)$ is topologically closed in $\mathcal{P}(\Omega_\mu)$. The set of finite ages included in $\Omega_\mu$ is open in $\text{Id}(\Omega_\mu)$. Indeed, since $\mu$ is finite, if $\mathfrak{C}$ is a finite age it has finitely many bounds, and thus $\mathfrak{C}$ is an isolated point of $\text{Id}(\Omega_\mu)$ (the set of ages containing no bound of $\mathfrak{C}$ and containing $T$ such that $\downarrow T = \mathfrak{C}$ is equal to $\{\mathfrak{C}\}$). From this, the set of infinite members of $\text{Id}(\Omega_\mu)$ is topologically closed, hence it is closed under intersection of totally ordered families. Apply Zorn's lemma to obtain that every infinite member is above some minimal one.

(d) Let $\mathfrak{C}$ be an infinite minimal age containing $T$. Let $R$ be such that $\text{Age}(R) = \mathfrak{C}$. Let $K$ be a subset of the base $V$ of $R$ such that $R_{\upharpoonright K}$ is isomorphic to $T$. According Lemma 5.5, there is an infinite subset $V'$ of $V$ containing $K$ on which the restriction $R' := R_{\upharpoonright V'}$ is $K$-chainable. Then $\text{Age}(R') = \mathfrak{C}$. $\square$

**Remark 5.20.** The conclusion of (a) holds also if $\mathfrak{C}$ is level-finite. But, without some hypothesis, the conclusion of (a) may be false. There are hereditary classes containing arbitrarily large chainable finite
structures with no age of an infinite chainable structure included into it. For an example, consider the class of structures of the form $R := (V, (\rho_n)_{n \in \mathbb{N}})$ where $V$ is finite and for some $n(V) \ge |V|$, $\rho_n(V)$ is a linear order on $V$, all $\rho_n$ are equal to $\rho_n(V)$ for $n \le n(V)$ and equal to the empty binary relation for $n > n(V)$.

**Theorem 5.21.** The age of an almost chainable structure is hereditarily wqo. If the signature is bounded, then the cardinality of its bounds is bounded.

**Proof.** Let $R := (V, (\rho_i)_{i \in I})$ be an almost chainable relational structure. Let $K$ be a finite subset of $V$ and $\le$ be a linear order on $V \setminus K$ witnessing that $R$ is $K$-chainable. Let $S := (V, \rho, a_1, \dots, a_k)$ be the relational structure where $\rho$ is the linear order on $V$ extending the linear order $\le$ on $V \setminus K$ and putting all elements of $K$ before those of $V \setminus K$, and $a_1, \dots, a_k$ are constants defining $K$. We claim that $\text{Age}(S)$ is hereditarily wqo. Indeed, any map $f$ from a finite subset $F$ of $V$ into a poset $P$ yields a pair of words, the first with domain included in $K$ the second included in $V \setminus K$. If $P$ is wqo, then from Higman's theorem, the set of these maps is wqo proving our claim. Now, since $R$ is freely interpretable by $S$, $\text{Age}(R)$ is hereditarily wqo. The second part of the Theorem is a consequence of Theorem 4.10. $\square$

The finiteness of the number of bounds was obtained in [80] by reducing it to the finiteness of bounds of chainable structures. The proof occupies the whole paper.

We conclude this subsection by looking at several parameters of a hereditary classe $\mathfrak{C}$ of finite structures.

(1) The number of infinite ages included in $\mathfrak{C}$. If $\mathfrak{C}$ is level-finite this is the cardinality of the set $\text{Id}^{(1)}(\mathfrak{C})$ of non isolated points of the topological space $\text{Id}(\mathfrak{C})$.

(2) The least number of chains needed to cover $\mathfrak{C}$, called the *covering number* of $\mathfrak{C}$ and denoted by $\text{cov}(\mathfrak{C})$.

(3) The supremum $\sup \varphi_{\mathfrak{C}}$ of the profile of $\mathfrak{C}$, that is the supremum of the cardinalities $\kappa$ such that there are $\kappa$ pairwise non-isomorphic members of $\mathfrak{C}$ on the same number of elements. When $\kappa$ is finite, $\mathfrak{C}$ is said to be *finimorphic*, a notion invented by Fraïssé. (It was present in his 1968 graduate course of the theory of relations; see also [79].)

(4) The ordinal length $o(\mathfrak{C})$ when $\mathfrak{C}$ is wqo. Like every ordinal, the ordinal $o(\mathfrak{C})$ can be written $o(\mathfrak{C}) = \omega \cdot \beta + p$ for a unique pair $(\beta, p)$ of ordinals such that $p < \omega$. The ordinal $\beta$, denoted by $\frac{1}{\omega} \cdot o(\mathfrak{C})$, is the *quotient* of $\mathfrak{C}$ by $\omega$.

**Theorem 5.22.** Let $\mathfrak{A}$ be an infinite ideal made of finite structures. Then the following properties are equivalent:

(i) $\mathfrak{A}$ is the age of an almost chainable structure;

(ii) $\mathbf{H}(\mathfrak{A}) = \omega + p$ where $p$ is the largest integer such that there is an increasing sequence $\mathfrak{A}_0 \subset \mathfrak{A}_1 \subset \dots \subset \mathfrak{A}_p = \mathfrak{A}$ of infinite ages;

(iii) the number of infinite ages included in $\mathfrak{A}$ is finite.

When one of these conditions holds, the number of infinite ideals included in $\mathfrak{A}$ is $|\text{Id}^{(1)}(\mathfrak{A})|$ and satisfies:

$$ (5.1) \qquad |\text{Id}^{(1)}(\mathfrak{A})| = \frac{1}{\omega} \cdot o(\mathfrak{A}) = \sup \varphi_{\mathfrak{C}} = \text{cov}(\mathfrak{A}). $$

**Proof.** (i) $\Rightarrow$ (iii). Let $R := (V, (\rho_i)_{i \in I})$ be an almost chainable structure with age $\mathfrak{A}$. Then $R$ is freely interpretable by $S := (V, \le, a_1, \dots, a_\ell)$ where $\le$ is a linear order on $V$ and $a_1, \dots, a_\ell$ are constants defining an initial segment of the chain $(V, \le)$. Let $\mathcal{P}$ be a free operator transforming $S$ to $R$. According to (2) of Lemma 2.18 each age included in $\text{Age}(R)$ is the image by $\mathcal{P}$ of an age included in $\text{Age}(S)$. Trivially, the number of infinite ages included in the age of $S$ is at most $2^\ell$. It follows that $\text{Age}(R)$ contains only finitely many ages.

(iii) $\Rightarrow$ (ii). This is immediate.

(ii) $\Rightarrow$ (i). According to Theorem 2.8, $\mathfrak{A}$ contains a countably infinite ideal, say $\mathfrak{A}_0$. The height of $\mathfrak{A}_0$, if it exists, is at least $\omega$. Since $\mathbf{H}(\mathfrak{A}) = \omega + p$, the set of countable ages containing $\mathfrak{A}_0$ and included in $\mathfrak{A}$ has height at most $p+1$. Hence, this set contains a maximal member for set inclusion, say $\mathfrak{A}'$. I claim that
A' = A. Otherwise, since A \ A' is up-directed and A' is countable we may, as in the proof of Theorem 2.8, build a countable ideal properly containing A', contradicting its maximality. Since A' is countable, this is the age of some relational structure $R := (V, (\rho_i)_{i \in I})$. The chains of infinite subages of A have length at most $p+1$, hence according to (3) of Lemma 3.31, $\ker(R)$ is finite. Let $I'$ be a finite subset of $I$. According to (1) of Proposition 5.18, $V$ is the union of an increasing sequence $(V_n)_{n \in \mathbb{N}}$ of countable subsets such that each restriction $R_{\upharpoonright V_n}^{I'}$ is almost chainable. Since for each chain $(X_n)_{n \in \mathbb{N}}$ of infinite subsets of $V$ the sequence $(\text{Age}(R_{\upharpoonright X_n}))_{n \in \mathbb{N}}$ is stationary, the sequence $(\text{Age}(R_{\upharpoonright X_n})')_{n \in \mathbb{N}}$ is stationary too. Hence, $\text{Age}(R^{I'})$ is almost chainable. Since $\ker(R^{I'}) \subseteq \ker(R)$, there is some finite $I'_0$ such that $\ker(R^{I'}) = \ker(R^{I'_0})$ for all finite $I'$ containing $I_0$. Hence, each $R^{I'}$ is $K$-chainable for $K := \ker(R^{I'_0})$. Via the compactness theorem of first order logic, $R$ is $K$-chainable, hence almost chainable.

We prove that if (iii) holds, that is, if $|\mathrm{Id}^{(1)}(\mathfrak{A})|$ is finite, then the following inequalities hold:

$$ (5.2) \qquad |\mathrm{Id}^{(1)}(\mathfrak{A})| \le \frac{1}{\omega} \cdot o(\mathfrak{A}) \le \sup \varphi_{\mathfrak{A}} \le \mathrm{cov}(\mathfrak{A}) \le |\mathrm{Id}^{(1)}(\mathfrak{A})|. $$

(a) $\mathrm{cov}(\mathfrak{A}) \le |\mathrm{Id}^{(1)}(\mathfrak{A})|$. Indeed, let $\mathfrak{A}_0, \dots, \mathfrak{A}_{d-1}$ be an enumeration of $\mathrm{Id}^{(1)}(\mathfrak{A})$ in a non-decreasing order. For $i < d$, let $X_i := \mathfrak{A}_i \cup \bigcup_{j<i} \mathfrak{A}_j$. Then $X_i$ is nonempty ($\mathfrak{A}_i$ is join irreducible) and totally ordered ($\mathfrak{A}_i$ is almost chainable). Since the $X_i$'s cover $\mathfrak{A}$ into $d$ chains, $\mathrm{cov}(\mathfrak{A}) \le d$.

(b) $\sup \varphi_{\mathfrak{A}} \le \mathrm{cov}(\mathfrak{A})$. This is trivial.

(c) $\frac{1}{\omega} \cdot o(\mathfrak{A}) \le \sup \varphi_{\mathfrak{A}}$. Since $\mathfrak{A}$ is infinite, it has no largest element, hence $o(\mathfrak{A})$ is a limit ordinal, that is, $o(\mathfrak{A}) = \omega \cdot \alpha$ for some ordinal $\alpha$. Since the number of infinite ages included in $\mathfrak{A}$ is finite, $\alpha$ is finite. Let $L$ be a linear extension of $\mathfrak{A}$ with order type $\omega \cdot \alpha$. Write it $L = L_0 + \dots + L_i + \dots + L_{\alpha-1}$ with each $L_i$ having order type $\omega$. We claim that we may select $\tau_i \in L_i$ such that all $\tau_i$'s have the same cardinality, say $n$. This proves that $\varphi_{\mathfrak{A}}(n) \ge \alpha = \frac{1}{\omega} \cdot o(\mathfrak{A})$. The claim holds because for each $i < \alpha$ there is an integer $n_i$ such that for each $n \ge n_i$ some $\tau_i$ with cardinality $n$ belongs to $L_i$ (to see that note that each $L_i$ is a convex subset of $\mathfrak{A}$ and this subset is wqo).

(d) $|\mathrm{Id}^{(1)}(\mathfrak{A})| \le \frac{1}{\omega} \cdot o(\mathfrak{A})$. Proceed by induction on $\alpha := \frac{1}{\omega} \cdot o(\mathfrak{A})$. If $\alpha = 1$, then $o(\mathfrak{A}) = \omega$, $\mathfrak{A}$ is Jónsson, $|\mathrm{Id}^{(1)}(\mathfrak{A})| = 1$, and the inequality holds. If $\alpha > 1$ then as above let $L$ be a linear extension of $\mathfrak{A}$ with order type $\omega \cdot \alpha$. Write it $L = L_0 + \dots + L_i + \dots + L_{\alpha-1}$ with each $L_i$ having order type $\omega$. Apply induction on $L_0 + \dots + L_i + \dots + L_{\alpha-2}$ and $L_{\alpha-1}$. $\square$

For a hereditary class, an extra hypothesis is needed and the result is a bit less precise.

**Theorem 5.23.** Let $\mathfrak{C}$ be a hereditary class of finite structures with a finite signature. Then the following properties are equivalent:

(i) each age $\mathfrak{A} \subseteq \mathfrak{C}$ is the age of an almost chainable structure;

(ii) $\mathfrak{C}$ is a finite union of ages of almost chainable structures;

(iii) $\mathfrak{C}$ is coverable by finitely many chains;

(iv) $\mathfrak{C}$ is finimorphic;

(v) $\mathbf{H}(\mathfrak{A}) < \omega \cdot 2$ for every $\mathfrak{A} \in \mathrm{Id}(\mathfrak{C})$;

(vi) $o(\mathfrak{C}) < \omega^2$;

(vii) $\mathfrak{C}$ contains only finitely many infinite ages.

**Proof.** We prove $(i) \Rightarrow (ii) \Rightarrow (iii) \Rightarrow (iv) \Rightarrow (v) \Rightarrow (i)$ and $(iii) \Rightarrow (vi) \Rightarrow (vii) \Rightarrow (i)$.

(i) $\Rightarrow (ii)$. First, $\mathfrak{C}$ is wqo. Otherwise, by Lemma 3.12, $\mathfrak{C}$ contains an age with infinitely many bounds in $\mathfrak{C}$. This is impossible since each age included in $\mathfrak{C}$ is the age of an almost chainable structure and such ages have only finitely many bounds. Since $\mathfrak{C}$ is wqo, it is a finite union of ages and these ages are ages of almost chainables structures, as required.

(ii) $\Rightarrow (iii)$. Each age of an almost chainable relation is coverable by finitely many chains.
(iii) ⇒ (iv). This is trivial.

(iv) ⇒ (v). If $\mathfrak{C}$ contains a sequence $\mathfrak{A}_0 \subset \mathfrak{A}_1 \cdots \subset \mathfrak{A}_n$ of infinite ages, then $\max \varphi_{\mathfrak{A}_n} \ge n + 1$.

(v) ⇒ (i) and (vii) ⇒ (i). Let $\mathfrak{A}$ be an infinite age. According to Proposition 5.18, $\mathfrak{A}$ is the union of an infinite increasing sequence of ages of infinite almost chainable structures. If, according to (vii), $\mathfrak{A}$ contains only finitely many infinite subages or, according to (v), $\mathbf{H}(\mathfrak{A}) < \omega \cdot 2$, the sequence is stationary. Thus, $\mathfrak{A}$ is the age of an almost chainable structure.

(iii) ⇒ (vi). If a poset is a finite union of well ordered chains, the ordinal length is majorized by the Hessenberg sum of these ordinals (Carruth [50]). Each chain in $\mathfrak{C}$ is either finite or has order type $\omega$, so the ordinal length is at most $\omega \cdot n$.

(vi) ⇒ (vii). This is essentially a property of posets. Suppose that $\mathfrak{C}$ is a poset with $o(\mathfrak{C}) = \omega \cdot m + n$ for $m, n < \omega$, and prove that $\mathfrak{C}$ contains at most $m$ infinite ideals with no largest element. The proof is by induction on $o(\mathfrak{C})$. If $o(\mathfrak{C}) < \omega$, there is nothing to prove. If $o(\mathfrak{C}) = \omega + n$, then $\mathfrak{C}$ minus a finite set is Jónsson, hence it contains only one infinite age. If $o(\mathfrak{C}) \ge \omega \cdot 2$, there is an initial segment $\mathfrak{C}'$ such that $o(\mathfrak{C}') = \omega \cdot (m-1)$ and $o(\mathfrak{C} \setminus \mathfrak{C}') = \omega + n$. Apply induction to $\mathfrak{C}'$. $\square$

Note that without the finiteness of the signature, condition (i) is too weak to imply (vii). Indeed, let $\mathfrak{C} := \text{Age}(R) \cup \text{Bound}(\text{Age}(R))$ where $R := (\mathbb{N}, (\rho_i)_{i \in \mathbb{N}})$, each $\rho_i$ being the complete graph on the set $\mathbb{N}$. With respect to embeddability, the set $\mathfrak{C}$ is the union of a chain, namely $\text{Age}(R)$, and an antichain, namely $\text{Bound}(\text{Age}(R))$. This latter set is infinite, it contains each $B_m := (\{0,1\}, (\beta_n)_{n \in \mathbb{N}})$ where $\beta_n$ is the empty graph for $n \ne m$ and $\beta_m$ is the complete graph on $\{0,1\}$.

**5.4. Almost multichainability.** Finite ages and ages of infinite almost chainable structures are the first layers of a decomposition of the set of ages. The ages we encounter next are those of almost multichainable relational structures.

We introduce first the product of a relational structure by a chain, from which multichainable structures are a special case.

**5.4.1. Product of a relational structure by a chain and multichainability.** Let $S := (W, (\tau_i)_{i \in I})$ be a relational structure of signature $\mu := (m_i)_{i \in I}$ and $L := (D, \le)$ be a chain. A relational structure $R$ of signature $\mu$ is a product of $S$ and $L$ if:

(a) the domain of $R$ is $D \times W$;

(b) for every $x \in D$ the map $y \to (x, y)$ is an isomorphism from $S$ to $R_{\upharpoonright\{x\} \times W}$;

(c) for each local isomorphism $f$ of $L$, the map $(f, 1_W)$, which maps $(x, y)$ to $(f(x), y)$, is a local isomorphism of $R$.

If $W$ is finite, the relational structure $R$ is said to be *multichainable*, the cardinality of $W$ is a width of $R$.

This notion was introduced in [149] and published in [152]. In that paper, it appears under the name of *D-multiple* of $R$ (see IV.3.3.2). It appears also in [157], p.264. (In this reference $R$ is defined on the direct product $V \times D$. We denote by $S \otimes L$ such a product (despite the fact that $S$ and $L$ do not determine it). If $|W| = 1$, $L$ chains this product. Hence $R$ is chainable.

We may note that the age of a product $S \otimes L$ is inexhaustible if $L$ is infinite. Several properties involving the notion of inexhaustibility are stated in [152] (for example, Lemme fondamental IV.3.3.5, Corollaire IV.3.3.6. Proposition IV.3.3.7). We extract the following result from Lemme fondamental IV.3.3.5 and Proposition 4.21, p. 266, of [157].

**Proposition 5.24.** Let $\mathfrak{B}$ be an inexhaustible age and $S$ be a relational structure such that $\text{Age}(S) \subseteq \mathfrak{B}$. If $\mathfrak{B}$ is level-finite then for every infinite chain $L$ there is some product $S \otimes L$ such that $\text{Age}(S \otimes L) \subseteq \mathfrak{B}$.

**Proof.** This result extends (a) of Proposition 5.19. It uses the same tools, namely Ramsey's theorem and the compactness theorem of first order logic. We suppose first that $S \in \mathfrak{B}$. Since $\mathfrak{B}$ is inexhaustible there is
a structure $R$ on the direct product $N \times V(S)$ such that for $n \in N$ the map $y \to (n, y)$ is an isomorphism from $S$ to $R_{\upharpoonright\{n\} \times V(S)}$ and $\mathrm{Age}(R) \subseteq \mathfrak{B}$. Let $\mu := (m_i)_{i \in I}$ be the signature of $R$. From Ramsey's theorem, we obtain that for every finite subset $I' \subseteq I$ there is an infinite subset $N_{I'}$ of $N$ such that the reduct $R^{\upharpoonright I'}$ restricted to $N_{I'} \times V(S)$ is a product of the reduct $S^{\upharpoonright I'}$ and the chain $(N_{I'}, \leq)$. Being level-finite, $\mathfrak{B}$ is reduct-closed by (a) of Proposition 2.16. Hence, for every finite chain $L$ there is a product $S \otimes L$ belonging to $\mathfrak{B}$. Next, suppose that $\mathrm{Age}(S) \subseteq \mathfrak{B}$. Let $D$ be a set and $L := (D, \leq)$ be a chain. Let $I' \subseteq I$, $V' \subseteq V(S)$, $D' \subseteq D$ be three finite sets. Let $S' := S_{\upharpoonright V'}^{\upharpoonright I'}$ and $\mathfrak{B}' := \mathfrak{B}^{\upharpoonright I'}$. Since $S' \in \mathfrak{B}'$, we obtain from our first case applied to $S'$ and $\mathfrak{B}'$ that there exists some product $S_{\upharpoonright V'}^{\upharpoonright I'} \otimes L_{\upharpoonright D'} \in \mathfrak{B}^{\upharpoonright I'}$. By compactness, there is some product $R := S \otimes L$ on $D \times V(S)$ such that $\mathrm{Age}(R) \subseteq \mathfrak{B}$. Since $\mathfrak{B}$ is level-finite, $\mathfrak{B} = \mathfrak{B}$ and the collection of $R'$ such that $\mathrm{Age}(R') \subseteq \mathfrak{B}$ is reduct-closed by Proposition 2.16, hence $\mathrm{Age}(R) \subseteq \mathfrak{B}$. $\square$

**Remark 5.25.** If $\mathfrak{B}$ is not level-finite, the conclusion of the proposition above may be false. Let $R := (V, (\rho_n)_{n \in N})$ where $V$ is the set $2^{[N]}$ of $0-1$ sequence which are $0$ almost everywhere, and where $\rho_n$ is the binary relation defined by $\rho_n(u, v) := 1$ if $n$ is the least integer such that $u_{\upharpoonright[n\to]} = v_{\upharpoonright[n\to]}$ and $\rho_n(u, v) := 0$ otherwise. Let $\mathfrak{B} = \mathrm{Age}(R)$. Then $\mathfrak{B}$ is inexhaustible and contains no monomorphic structure on three elements. To see the inexhaustibility of $\mathfrak{B}$, let $t \in V$ and $T_t : V \to V$ defined by setting $T_t(u) := u \oplus t$ (the Boolean sum of $u$ and $t$). Then $\rho_n(u, v) = \rho_n(u \oplus t, v \oplus t)$, hence $T_u$ is an automorphism of $R$. For every $n \in N$, $\delta_n$ (defined by $\delta_n(m) = 1$ if $m = n$ and $0$ otherwise), and $V_n := \{u \in V : u(m) = 0$ for all $m \ge n\}$, the map $T_{\delta_n}$ maps $R_{\upharpoonright V_n}$ to a disjoint copy. The non monomorphy of a 3-element restriction of $R$ is due to the fact that the set of $u_{\upharpoonright[n\to]}$ for $u \in V$ and $n \in N$ has the structure of a binary tree; hence, if $u, v, w$ are three distinct elements there is some $n$ such that $\rho_n(u, v) = \rho_n(v, w) = \rho_n(u, w)$ does not hold.

**Corollary 5.26.** (Corollary IV.3.3.6 of [152]) Let $R$ be a relational structure and $L$ be a chain. If $\mathrm{Age}(R)$ is inexhaustible and level-finite then some product of $R$ and $L$ has the same age as $R$.

5.4.2. *Almost multichainability and cellularity.* We first extend the notion of multichainability to multi-chainability over a set.

Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure. If $K$ is a subset of $V$, we say that $R$ is *multichainable over $K$, or $K$-multichainable* if there there is an enumeration $(a_{x,y})_{(x,y) \in L} \times W$ of the elements of $V \setminus K$ by a set $L \times W$, where $W$ is finite and $L$ is a linearly ordered set, such that for every local isomorphism $f$ of $L$ the map $(f, 1_W)$ extended by the identity on $K$ is a local isomorphism of $R$ (the map $(f, 1_W)$ is defined by $(f, 1_W)(a_{x,y}) := a_{f(x),y}$). We say that $R$ is *almost multichainable* if $R$ is multichainable over some finite set $F$. The pair $(|F|, |W|)$ is the *parameter of almost multichainability*.

If in the above definition we suppose that $L$ is not ordered and we impose that for every permutation $f$ of $L$ the map $(f, 1_{W})$ extended by the identity on $F$ is a local isomorphism of $R$ then we say that $R$ is *cellular*.

The notion of almost multichainability was introduced in [149] (see [158] for further references and discussions). The special case $|K| = 1$ is the notion of almost chainability introduced by Fraïssé. The notion of cellularity was introduced by Schmerl [183]. It is illustrated in Section 6 with Theorem 6.17.

Fraïssé's lemma about the almost chainable restriction extends as follows.

**Lemma 5.27.** Let $R$ be a relational structure with finite signature and domain $V$, and let $K$ be a finite subset of $V$. Let $S \in \mathrm{Age}(R)$. If there are infinitely many restrictions of $R$ isomorphic to $S$ and whose domains are pairwise disjoint, then we may extract a family of these restrictions whose union with $K$ forms a multiple of $S$ by an infinite chain that is $K$-multichainable.

**Proof.** The proof is a straightforward application of Ramsey's theorem. Let $(F_p)_{p \in N}$ be a family of pairwise disjoint subsets of $V \setminus K$ such that each restriction $R_{\upharpoonright F_p}$ is isomorphic to $S$ by some isomorphism $f_p$ from $R_{\upharpoonright F_p}$ to $S$.

Let $W$ be the domain of $S$, and let $m$ be the maximum of the signature of $R$. Say that two $m$-element subsets $H$ and $H'$ of $N$ ordered as the integers are equivalent if for the unique order isomorphism $h : H \to H'$, the map $\bigcup_{p \in H} f_h^{-1}(p) \circ f_p$ from $\bigcup_{p \in H} F_p$ to $\bigcup_{p' \in H'} F_{p'}$ extends the identity on $K$ to a local isomorphism of $R$. The signature of $R$ being finite, the number of equivalence classes is finite. Hence, from Ramsey's theorem
there is an infinite subset $X$ of $\mathbb{N}$ such that all $m$-element subsets belong to the same class. The restriction of $R$ to $K \cup \bigcup_{p \in X} F_p$ has the required property. $\square$

**Proposition 5.28.** Let $R$ be a relational structure with finite signature and domain $V$, and $K := \ker(R)$. Let $L := (D, \leq) $ be a chain. Then there is an extension $R'$ on a set $V'$ containing $V$ such that $\mathrm{Age}(R') = \mathrm{Age}(R)$ and $R'_{\upharpoonright V' \setminus K}$ is a multiple of $R_{\upharpoonright V \setminus K}$ over $K$ by a chain $L$.

**Proof.** This is a direct consequence of Lemma 5.4.2 above and the Compactness Theorem of first order Logic. This latter result, being applied through the Diagram Method of Robinson as in the proof of Lemma 5.15. Set $V' := K \cup (D \times (V \setminus K))$. To obtain an $R'$ satisfying the conclusion of Proposition, give names to the elements of $V'$; for each element $a \in D$ use the natural bijection of $V$ onto $K \cup (\{a\} \times (V \setminus K))$ to write axioms expressing that the diagram of $R$ and $R'_{\upharpoonright K \cup (\{a\} \times (V \setminus K))}$ are the same. Then express the fact that $R'_{\upharpoonright V' \setminus K}$ is a multiple of $R_{\upharpoonright V \setminus K}$ over $K$ by the chain $L$. Use Lemma 2 to get the consistency of these axioms. The Compactness Theorem of first order Logic yields the existence of the desired $R'$. $\square$

As it stands, the notion of almost multichainability is not flexible enough; in particular, it is not preserved by restriction. For example, the relational structure $Q := (\mathbb{Q}, \leq, U)$, made of the natural order on the rational numbers and a unary relation $U$ dividing $\mathbb{Q}$ into two dense sets, is not almost multichainable. But it has the same age as a multichainable relational structure. In fact, a restriction of $Q$ to a subchain of type $\omega$ on which the values of $U$ alternate is multichainable with the same age as $Q$.

In order to clarify this fact (and to rectify Proposition 4.18 of [157]), we find it convenient to introduce the notion of almost multichain$. For that, we recall that a weak order is an order which is the lexicographical sum of antichains indexed by a chain (alternatively, the binary relation $x$ is incomparable to $y$ or $x = y$ is an equivalence relation).

**Definition 5.29.** An almost multichain$^{-}$ is a relational structure $M := (V, \leq, U_1, \dots, U_k, a_1, \dots a_\ell)$, where $\leq$ is a weak order on $V$, $a_1, \dots a_\ell$ are constants, the set $F := \{a_1, \dots a_\ell\}$ is an equivalence class attached to $\leq$ which is before all others, the relations $U_1, \dots U_k$ are unary relations inducing a partition of $V \setminus F$ into chains of the weak order. A relational structure is almost multichainable$^{-}$ if it is freely interpretable by some almost multichain$^{-}$.

**Example 5.30.** If $R := (V, (\rho_i)_{i \in I})$ is almost multichainable with a set $F$ and an enumeration $(a_{x,y})_{(x,y) \in L \times W}$ of the elements of $V \setminus F$ by a set $L \times W$, where $W$ is finite and $L$ is a linearly ordered set, then $V$ is the lexicographical sum of $F$ and of the sets $W_y := \{a_{x,y} : x \in W\}$ where $y \in L$, ordered according to the chain $L$. Since the sets $U_x := \{a_{x,y} : y \in L\}$ for $x \in W$ form a partition of $V \setminus L$ into chains, the corresponding relational structure $M$ is an almost multichain$^{-}$ and interprets freely $R$.

Other examples are relational structures made of a chain and finitely many unary relations. But, note that not every almost multichainable relational structure has this form. For a simple example, let $R$ be the weak order made of the lexicographical sum of copies of the two element antichain by an infinite chain. This relation is almost multichainable but not freely interpretable by a chain with unary relations added.

**5.4.3. Alternative definition.** Almost multichainable$^{-}$ structures are freely interpretable by structures made of a weak order whose antichains have finite bounded size and finitely many unary relations. It is not difficult to see that the converse holds. Instead of this notion, we chose a definition ythat is closer to that of almost multichainable structure. Note that with this later definition, no local isomorphism can move an element within an equivalence class. These structures can be described as follows:

**Proposition 5.31.** The class of almost multichainable$^{-}$ relational structures is the least class $\mathfrak{M}$ of relational structures containing each weak order whose antichains have a finite bounded size, containing every relational structure freely interpretable by some member of $\mathfrak{M}$ and containing every member of $\mathfrak{M}$ with some unary relation added.
From the definition of almost multichain⁻, the restriction of an almost mutichain⁻ is an almost multichain⁻. Applying the Compactness Theorem of first order logic in the form of (2) of Lemma 2.18 (with *R* replaced by *M* and *S* replaced by *R*), we get that if *R* is an almost multichainable⁻ structure and the age of some *R*' is included into the age of *R* then *R*' is almost multichainable⁻. This does not say how almost multichainable⁻ structures relate to those that are almost multichainable. The answer is the following, but it requires a proof.

**Theorem 5.32.** An infinite relational structure *R* is almost multichainable⁻ if and only if some restriction of *R* is almost multichainable and has the same age as *R*.

In particular, infinite ages of almost multichainable⁻ structures and ages of almost multichainable structures coincide. Before proving this result, we obtain the following consequence.

**Corollary 5.33.** If an infinite age *A* is included in the age of an almost multichainable structure, then *A* is the age of an almost multichainable structure.

**Proof.** Let $\mathfrak{B}$ be the age of an almost multichainable structure $R$ containing $\mathfrak{A}$. Then $R$ is almost multichainable⁻. According to Theorem 5.32 some restriction of $R$ is almost multichainable and has the same age as $R$. This proves our claim. □

The proof of Theorem 5.32 is based on the notion of wqo and Higman's theorem. We prove first:

**Theorem 5.34.** The age of an almost multichainable relational structure, and more generally of an almost multichainable⁻ relational structure, is wqo. In fact, it is hereditarily bqo.

**Proof.** Part 1 of Theorem 4.19 [157] asserts that the age of an almost multichainable relational structure is very-well-quasi-ordered. The proof consisted in encoding members of the age by words over a finite alphabet and apply Higman's Theorem on words. The proof applies with no changes to almost multichainable⁻ relational structures. In fact, it only relies on the fact that the age of a chain labelled by a wqo is wqo. Indeed, we claim that this property ensures that the age of a structure $M := (V, \leq, U_1, \dots, U_k)$ made of a weak order whose antichains have finite bounded size and with finitely many unary relations $U_1, \dots, U_k$ is wqo. Since the age of an almost multichainable⁻ relational structure is freely interpretable by some $M$ of the form above, it is wqo too. To deduce our claim, we prove that members of the age of $M$ can be encoded by labelled chains (as we have seen, they are not necessarily interpreted by labelled chains). For that, let $L$ be the chain of equivalence classes of the weak order $\leq$. Then, write $V$ as the lexicographical sum of the equivalence classes $K$ indexed by $L$. To each finite subset $H$ of $V$ associate the sequence $K_1, \dots, K_n$ of the equivalence classes on which $K_i \cap H$ is nonempty, this sequence being enumerated in the order of $L$. Then, to this sequence associate the word $C_H := H_{K_1} \cdots H_{K_n}$ whose letters $H_{K_i}$ are the sets $H_{K_i} := \{j : U_j \cap K_i \cap H \neq \emptyset\}$. Order the letters by set inclusion. From Higman's theorem, the collection of these words forms a wqo and in fact a bqo. The encoding of $M_{\uparrow H}$'s by the $C_H$'s is such that $C_H \leq C_{H'}$ implies that $M_{\uparrow H} \leq M_{\uparrow H'}$. The fact that $\text{Age}(M)$ is bqo follows. Adding a coloring of $V$ by unary relations or by members of a wqo will not change the outcome. Hence $\text{Age}(M)$ is hereditarily bqo. □

Due to the encoding of the members of an age of an almost multichainable structure by words over a finite alphabet, we have the following result (see part 2 of Theorem 4.19 of [157]):

**Theorem 5.35.** The height of the age of almost multichainable structures is always strictly less than $\omega^\omega$.

**Proof.** Let $R$ be an almost multichainable structure. Then $R$ is freely interpretable by a relational structure $M$ as in Example 5.30. Let $(k, p)$ be the parameters of $M$. We claim that

$$ (5.3) \qquad \mathbf{H}(\text{Age}(R)) \leq \mathbf{H}(\text{Age}(M)) < \omega^{2^p-1} + \omega. $$

The first inequality relies on a general property of free interpretability.
**Lemma 5.36.** If the set $\mathrm{Id}(\mathrm{Age}(M))$, ordered by set inclusion, of ages included in the age of a relational structure $M$ is well-founded, then for every relational structure $R$, freely interpretable by $M$, the set $\mathrm{Id}(\mathrm{Age}(R))$ is well founded and

$$ (5.4) \qquad \mathbf{H}(\mathrm{Age}(R)) \leq \mathbf{H}(\mathrm{Age}(M)). $$

**Proof.** Let $R$ be freely interpretable by $M$, and let $\mathcal{P}$ be a free operator transforming $M$ into $R$. The latter induces a transformation of the subages of $M$ into subages of $R$. According to (2) of Lemma 2.18, for each age $\mathfrak{A}$ belonging to $\mathrm{Id}(\mathrm{Age}(R))$ there is some age $\mathfrak{M}$ belonging to $\mathrm{Id}(\mathrm{Age}(M))$ such that $\mathcal{P}$ transforms $\mathfrak{M}$ to $\mathfrak{A}$. This implies that $\mathrm{Id}(\mathrm{Age}(R))$ is well founded as soon as $\mathrm{Id}(\mathrm{Age}(M))$ is. The inequality follows from a straightforward induction. $\square$

For the second inequality, let $(k, p)$ be the parameters of $M$. Suppose first that $k = 0$, that is, $\ker(M)$ is empty. In this case, $\mathrm{Age}(M)$ is essentially the free ordered monoid generated by the collection of nonempty subsets of $\{1, \dots, p\}$ ordered by set inclusion. If we order these subsets by the equality relation, the free ordered monoid is $\mathrm{Age}(\mathbb{Q}, U_1, \dots, U_{2^p-1})$ and hence, $o(\mathrm{Age}(\mathbb{Q}, U_1, \dots, U_{2^p-1})) = \omega^{\omega^{2^p-2}}$ from Example 3.16. We have $o(\mathrm{Age}(M)) \leq o(\mathrm{Age}(\mathbb{Q}, U_1, \dots, U_{2^p-1}))$, and thus $o(\mathrm{Age}(M)) \leq \omega^{\omega^{2^p-2}}$.

From Theorem 3.15, we have $o(\mathrm{Age}(M)) = \omega^\alpha \cdot q$ with $\omega \cdot \alpha \leq \mathbf{H}(\mathrm{Age}(M)) < \omega \cdot (\alpha + 1)$. Hence, $\alpha \leq \omega^{2^p-2}$ and thus $\mathbf{H}(\mathrm{Age}(M)) < \omega \cdot (\omega^{2^p-2} + 1) = \omega^{2^p-1} + \omega$. If $k \neq 0$, then according to (2) of Lemma 3.34, $\mathbf{H}(\mathrm{Age}(M)) = \mathbf{H}(\mathrm{Age}(M')) + r$, where $M'$ is a reduction over the kernel of $M$ and $r < \omega$. This yields $\mathbf{H}(\mathrm{Age}(M)) < \omega^{2^p-1} + \omega$ as claimed. Note that for $p = 1$, $R$ is almost chainable and so $\mathbf{H}(\mathrm{Age}(R)) < \omega \cdot 2$, as already seen. $\square$

5.4.4. **Towards a proof of Theorem 5.32.** The proof uses the notion of indecomposable labelled chain and well-quasi ordering. A labelled chain is a pair $(C, \ell)$ where $C$ is a chain and $\ell$ is a map from $C$ into a poset $P$. Chains labelled by the same poset can be compared by embeddability, like one compares chains with a fixed finite number of unary relations added. We say that a labelled chain $(C, \ell)$ is age-indecomposable if for every partition of the chain $C$ into an initial and a final interval $I$ and $J$, the age of one of the restrictions $(C, \ell)_{\upharpoonright I} (C, \ell)_{\upharpoonright J}$ is equal to the age of $(C, \ell)$.

**Lemma 5.37.** If a chain $(C, \ell)$ is labelled by a finite poset or more generally by a wqo then $C$ decomposes into finitely many disjoint intervals $I_1, \dots, I_i, \dots I_n$ such that each restriction $(C, \ell)_{\upharpoonright I_i}$ is age-indecomposable.

**Proof.** The proof is typical of the strength of the notion of wqo. Suppose that there is some labelled chain for which the above property does not hold. Since the age of every chain labelled by a wqo is wqo, the collections of these ages is well-founded w.r.t. set inclusion. Hence, there is a labelled chain $(C, \ell)$ for which the above property does not hold and the age of $(C, \ell)$ is minimal. We claim that $(C, \ell)$ is age-indecomposable. Indeed, let if for every partition $I, J$ of the chain $C$ into an initial and a final interval, the ages of the restrictions $(C, \ell)_{\upharpoonright I}$ and $(C, \ell)_{\upharpoonright J}$ are smaller that the age of $(C, \ell)$ then, due to the minimality of that age, each of these restriction has a finite decomposition, hence $(C, \ell)$ has a finite decomposition. Since we suppose it has not such a decomposition, one of these ages is the same as the age of $(C, \ell)$. But then $(C, \ell)$ is age-indecomposable, contradicting our hypothesis. $\square$

**Lemma 5.38.** Every infinite and age-indecomposable labelled chain $(C, \ell)$, labelled by a finite poset, embeds a labelled chain with the same age as $(C, \ell)$ which is an $\omega$ or $\omega^*$-sum of copies of a finite labelled chain $(Q, q)$.

**Proof.** Let $(q_1, \dots, q_m)$ be an enumeration of the set of maximal elements of the range of $\ell$. We may view this enumeration as a labelled chain $(Q, q)$. Since $(C, \ell)$ is age-indecomposable, $(Q, q)$ embeds in $(C, \ell)$. From Ramsey's theorem, an $\omega$-sum or an $\omega^*$-sum of copies of $(Q, \ell)$ embeds in $(C, \ell)$. It has the same age as $(C, \ell)$. $\square$

**Proof of Theorem 5.32.** Let $R$ be an almost multichainable$^-$ relational structure. Let

$$ M := (V(R), \leq, U_1, \dots, U_k, a_1, \dots, a_\ell) $$
be an almost multichain$^-$ interpreting $R$. Let $L$ be the chain of equivalence classes $K$ of the weak order $\leq$. For each $K$ set $\ell(K) := \{j : U_j \cap K \neq \emptyset\}$. Looking at these sets $\ell(K)$ as letters, these letters being subsets of $\{1, \dots, k\}$ ordered by set inclusion, we get the labelled chain $(L, \ell)$. Applying Lemmas 5.37 and 5.38 we get that $(L, \ell)$ embeds a finite lexicographical sum $(L, \ell_1) + \cdots + (L, \ell_m)$ where $(L_i, \ell_i)$ is either finite or an $\omega$ or an $\omega^*$-sum of copies of a finite labelled chain $(Q_i, q_i)$. Let $I$ be the set of infinite $L_i$'s. For each $i \in I$, $L_i$ decomposes into an union $\bigcup_{n \in \omega} Q_{i,n}$ such that $(Q_i, \ell_{\upharpoonright Q_{i,n}})$ is isomorphic to $(Q_i, q_i)$. For $n \leq \omega$, let

$$K_n := \bigcup_{1 \leq i \leq m} Q_{i,n} \text{ and let } F := \bigcup_{i \notin I} L_i.$$

Let $V'$ be the set union of $F$ and the $K_n$'s and let $\leq'$ be the weak order on $V'$ whose classes are $F$ and the $K_n$'s ordered as $\omega$. Adding to the restrictions of the $U_j$ to $V'$ some unary relations so that no element on an equivalence class can be moved by a local isomorphism we get an almost multichain. It interprets freely $R'_{\upharpoonright V'}$. It follows that $R_{\upharpoonright V'}$ is almost multichainable with the same age as $R$. $\square$

An immediate application of Theorem 4.10 is this:

**Theorem 5.39.** *The age of an almost multichainable relational structure with a finite signature has finitely many bounds.*

**5.5. Ages of height strictly smaller than $\omega^2$.** The central result of this subsection is Theorem 5.42 asserting that ages of height strictly smaller that $\omega^2$ are ages of almost multichainable structures.

A special case is given by the following consequence of Proposition 5.26 (see Corollary 4.22 of [157]).

**Proposition 5.40.** *If the age $\mathfrak{A}$ of a denumerable structure $R$ is inexhaustible and level-finite, then $\mathfrak{A}$ is the union of an increasing sequence $(\mathfrak{A}_n)_{n \in \mathbb{N}}$ where each $\mathfrak{A}_n$ is the age of a product of some finite relational structure by an infinite chain. If furthermore $\mathfrak{A}$ has a height and $\mathbf{H}(\mathfrak{A}) < \omega^2$ then $\mathfrak{A}$ is the age of a product of a finite relational structure by a chain.*

**Proof.** Let $L$ be an infinite chain. According to Corollary 5.26 some product $R \otimes L$ has the same age as $R$. Let $(V_n)_{n \in \mathbb{N}}$ be an increasing sequence of finite subsets $V_n$ of $V$ whose union is $V(R)$. Set

$$\mathfrak{A}_n := \text{Age}((R \otimes L) \upharpoonright (V(L) \times V_n)).$$

Suppose that $\mathfrak{A}$ has a height. Since $\mathfrak{A}_n$ is inexhaustible $\mathbf{H}(\mathfrak{A}_n)$ is a limit ordinal (Corollary 3.38). Since $\mathbf{H}(\mathfrak{A}) < \omega^2$, the sequence $(\mathfrak{A}_n)_{n \in \mathbb{N}}$ must be stationary. So $\text{Age}(\mathfrak{A}) = \mathfrak{A}_n$ for some $n \in \mathbb{N}$. $\square$

Proposition 5.40 extends as follows:

**Proposition 5.41.** *If an age $\mathfrak{A}$ is almost inexhaustible and level-finite, then this is the age of the union $S$ of an increasing sequence $(S_n)_{n \in \mathbb{N}}$ of almost multichainable structures each having the same kernel as $S$. Consequently, if $\mathfrak{A}$ is not the age of an almost multichainable structure, it contains ages of height $\omega \cdot n$ for each integer $n$. Furthermore, if $\mathfrak{A}$ has a height and $\mathbf{H}(\mathfrak{A}) < \omega^2$, then $\mathfrak{A}$ is the age of an almost multichainable structure.*

**Proof.** If $R$ is any structure with age $\mathfrak{A}$, the age of a reduction of $R$ over its kernel, say $R_{\ker(R)}$, is inexhaustible. Then there is some $R'$ with the same age as $R$ such that $R'_{\ker(R')}$ is a product of some structure $R''$ by an infinite chain. Apply Proposition 5.40 to $R'_{\ker(R')}$. $\square$

**Theorem 5.42.** *Let $\mathfrak{A}$ be the age of a relational structure with finite signature. If $\mathbf{H}(\mathfrak{A}) < \omega^2$ then $\mathfrak{A}$ is the age of an almost multichainable relational structure.*

This result is stated as Théorème III-1.1. in “Caractérisation combinatoire et topologique des âges les plus simples” [149]. This is a nontrivial result. It is an immediate consequence of Proposition 5.41 and of the following result.

**Proposition 5.43.** *Let $\mathfrak{A}$ be the age of a relational structure with finite signature. If $\mathbf{H}(\mathfrak{A}) < \omega^2$, then $\mathfrak{A}$ is almost inexhaustible.*
A proof of this proposition was given in [157] Theorem 4.24, p. 267, for binary structures, and also in Proposition 4.6 of this paper. A proof of an equivalent statement is given in “II-Théorème central” of “Caractérisation combinatoire et topologique des âges les plus simples” [149]. This statement is the following:

**Proposition 5.44.** Let $\mathfrak{A}$ be the age of a relational structure with finite signature. If every proper subage of $\mathfrak{A}$ is very-well-quasi-ordered, then either $\mathfrak{A}$ is almost inexhaustible or $\mathbf{H}(\mathfrak{A}) \ge \omega^2$.

Let us prove that Proposition 5.43 and Proposition 5.44 are equivalent. Suppose Proposition 5.43 true. We derive Proposition 5.44 as follows. Let $\mathfrak{A}$ be the age of a relational structure with finite signature such that every proper subage of $\mathfrak{A}$ is very-well-quasi-ordered. Necessarily, $\mathrm{Id}(\mathfrak{A})$ is well-founded, hence $\mathbf{H}(\mathfrak{A})$ is well defined. If $\mathfrak{A}$ is not almost inexhaustible, then $\mathbf{H}(\mathfrak{A}) \ge \omega^2$ by Proposition 5.43. Hence $\mathfrak{A}$ satisfies the conclusion of Proposition 5.44. Conversely, suppose Proposition 5.44 true. Let $\mathfrak{A}$ be the age of a relational structure with finite signature. If $\mathfrak{A}$ is very-well-quasi-ordered, it is $1^-$-wqo, hence almost inexhaustible by Corollary 4.5. If $\mathfrak{A}$ is not very-well-quasi-ordered but $\mathbf{H}(\mathfrak{A}) < \omega^2$, then $\mathfrak{A}$ contains a minimal subage $\mathfrak{A}'$ which is not very-well-quasi-ordered. Since $\mathfrak{A}' \subseteq \mathfrak{A}$, $\mathbf{H}(\mathfrak{A}') < \mathbf{H}(\mathfrak{A}) < \omega^2$. Proposition 5.44 ensures that $\mathfrak{A}'$ is almost inexhaustible. By Proposition 5.41, $\mathfrak{A}'$ is the age of a almost multichainable structure. By Theorem 5.34 it is hereditarily wqo, which is a contradiction.

The proof of Proposition 5.44 has two parts. First, we show in Proposition 5.49 below, that the collection of subages of $\mathfrak{A}$ contains chains of type $\omega \cdot n$ for every integer $n$ provided that the complement of the kernel $\ker(R)$ of some $R$ with age $\mathfrak{A}$ is not val-finite, a notion invented by Fraïssé [77], Section 4, p.325, that we will recall below in Subsection 5.5.1. Supposing that every proper subage of $\mathfrak{A}$ is hereditarily wqo, $\mathrm{Id}(\mathfrak{A})$ is well-founded. Under the hypothesis on $R$, $\mathbf{H}(\mathfrak{A}) \ge \omega^2$.

Next, we suppose that for every $R$ with age $\mathfrak{A}$, the complement of $\ker R$ is val-finite. Then we show that $R$ is freely interpretable by some relational structure $M$ such that $\ker(R)$ and $V \setminus \ker(R)$ are interval of $M$ and the restrictions $M_{\upharpoonright V \setminus \{x\}}$ for $x \in \ker(R)$ are hereditarily wqo. We show then that this is impossible, completing the proof of Proposition 5.44.

**5.5.1.** *Val-finite subsets of a relational structure and wqo.* The notion of *fini-val* (in french), invented by Fraïssé, generalizes the notion of module also introduced by him under the name of *interval* and independently by Gallai [84].

Let $R$ be a relational structure with domain $V$, $K$ be a subset of $V$ and $m$ be a nonnegative integer. Two $m$-tuples $\bar{x} := (x_1, \dots, x_m)$ and $\bar{x}' := (x'_1, \dots, x'_m)$ belonging to $(V \setminus K)^m$ are $m$-equivalent over $K$ when the transformation of $\bar{x}$ into $\bar{x}'$ extended by the identity on $K$ induces a local isomorphism of $R$. This defines an equivalence relation on $(V \setminus K)^m$. We denote by $\theta_{R,K}(m)$ the number of these equivalence classes. Then the subset $V \setminus K$ is said to be *val-finite* over $K$ if for each positive integer $m$ the number $\theta_{R,K}(m)$ is finite. Recall that a subset $A$ of the domain $V$ of a relational structure $R$ is an *interval* if every local isomorphism of $R_{\upharpoonright A}$ extended by the identity on $V \setminus A$ is a local isomorphism of $R$. For example, if $R$ is made of binary relations, each one being either reflexive or irreflexive, then $A$ is an interval if and only if it is autonomous (as defined in Subsection 3.3.3). As observed by Fraïssé, one has:

**Lemma 5.45.** Let $R$ be a relational structure with a finite signature and let $A$ be a subset of its domain $V$. If $A$ is an interval, then $A$ is val-finite over $V \setminus A$. Moreover $A$ is val-finite over $V \setminus A$ if and only if there is some relational structure $M$ with finite signature interpreting $R$ and such that $A$ is an interval of $M$.

For the proof of the second assertion, note that if $m$ is the maximum of the signature of $R$, then since the number $\theta_{R,A}(m)$ of equivalence classes over $V \setminus A$ is finite, we may find a finite subset $F \subseteq V \setminus A$ such that two $m$-uples of $A$ that are equivalent over $F$ are equivalent over $V \setminus A$. If we label the elements of $F$ with constants $a_1, \dots, a_k$ ($k := |F|$), then the relational structure $M := R \cdot a_1 \cdots a_k$ has the required property. From this proof, we may extract the following characterization.

**Lemma 5.46.** Let $R$ be a relational structure with domain $V$ and a finite signature and let $A$ be a subset of $V$. Then $A$ is a val-finite subset of $V$ if and only if there is some finite subset $F$ of $V \setminus A$ such that the local isomorphisms of $R_{\upharpoonright A}$, which can be extended by the identity on $V \setminus A$ to local isomorphisms of $R$, are
exactly the local isomorphisms of $R_{\upharpoonright W}$, which can be extended by the identity on $F$ to local isomorphisms of $R$.

We note that the finiteness of $F$ relies on the fact that the signature of $R$ is finite. As shown in [77], the notion of finite-val set gives rise to a Boolean structure.

**Theorem 5.47.** The set of val-finite subsets of the domain $V$ of a relational structure with a finite signature forms a Boolean algebra: it contains $V$, $\emptyset$ and it is closed under complementation, finite unions and intersections.

The following fact will be used in the proof of Proposition 5.49.

**Lemma 5.48.** Let $R$ be a relational structure, $K$ be a subset of $V(R)$ such that $R$ is $K$-multichainable with parameters $W$ and $L := (D, \leq)$. If $m$ is any integer, the number of $m$-equivalence classes over $K$ is bounded by an integer depending on $w := |W|$ and $m$.

**Proof.** We may suppose that $V(R) = K \cup (D \times W)$ and that for every local isomorphism $f$ of the chain $L$ the map $(f, 1_W)$, extended by the identity on $K$ is a local isomorphism of $R$. In this case, $\theta_{R,K}(m) \leq (w \times m)^m$. $\square$

The first occurrence of the notion of a val-finite set in this context is given by the following.

**Proposition 5.49.** Let $\mathfrak{A}$ be the age of a relational structure with finite signature. Then $\mathfrak{A}$ contains a chain of subages of order type $\omega \cdot n$ for every integer $n$ whenever the complement of the kernel $\ker(R)$ of some $R$ with age $\mathfrak{A}$ is not val-finite over $\ker(R)$.

**Proof.** The proof will use Theorem 3.37. With this result, it suffices to prove that if the complement of the kernel of some relational structure $R$ with $\text{Age}(R) = \mathfrak{A}$ is not val-finite, then for each integer $n$, the set $\text{Id}(\mathfrak{A})$ of subages of $\mathfrak{A}$ contains a chain $(\mathfrak{A}_p)_{1 \leq p \leq n}$ of subages such that each interval $[\mathfrak{A}_p, \mathfrak{A}_{p+1}]$, $1 \leq p < n$ contains infinitely many subages. Indeed, the collection of chains of type $\omega+1$ in $[\mathfrak{A}_p, \mathfrak{A}_{p+1}]$, $p < n$, provides the required chain of type $\omega \cdot n$.

We will prove that $\mathfrak{A}$ contains the age of an almost multichainable relational structure $S$ such that $\mathbf{H}(\text{Age}(S)) = \omega \cdot n + r$ for some integer $r$. The domain of the structure $S$ will be of the form $V(S) = K \cup (D \times W)$, where $K = \ker S$ and $S_{\upharpoonright W}$ and $L := (D, \leq)$ are the parameters, and such that $W$ contains a strictly increasing sequence $W_1 \subseteq \dots \subseteq W_n = W$, with $|W_1| = 1$.

Let $V_p := K \cup (L \times W_p)$ and $S_p := S_{\upharpoonright V_p}$ for $p \leq n$. Provided that the ages $\mathfrak{A}_p := \text{Age}(S_p)$ are all distinct, the intervals $[\mathfrak{A}_p, \mathfrak{A}_{p+1}]$, $p < n$ will contain infinitely many subages. If not, then, according to Formula 3.2 of Subsection 3.6.2, $\ker(S_{p+1}) = \ker(S_p) \cup F'$, for some finite subset $F'$ of $V_{p+1}$. But all $S_p$'s have the same kernel, namely, $K$, and hence every finite subset of $V_{p+1}$ can be embedded in $V_p$, thus proving that $\mathfrak{A}_p = \mathfrak{A}_{p+1}$. To ensure that the $\mathfrak{A}_p$ are distinct, we choose some $R$ with $\text{Age}(R) = \mathfrak{A}$ such the complement of the kernel $A$ of $R$ is not val-finite.

Let $k$ be a positive integer such that $R$ contains infinitely many $k$-equivalence classes over $A$. Define $(W_p)_{p \leq n}$ as follows. Pick a $k$-tuple $(b_1, \dots, b_k)$ in $V \setminus A$ and set $W_0 := \{b_1, \dots, b_k\}$, and suppose that $W_p$ was defined. According to Lemma 5.48, the number of $k$-equivalence classes over $A$ of any extension multichainable over $A$ of the form $L \times W_p$ is bounded. Since the number of $k$-equivalence classes over $A$ is infinite, some $k$-tuple $\{b'_1, \dots, b'_k\}$ of $V \setminus A$ is not equivalent to any of the $k$-tuples extracted from the above extension. Set $W_{p+1} := W_p \cup \{b'_1, \dots, b'_k\}$.

Now, $W$ being defined, if for every finite subset $F$ of $A$ we can find infinitely many copies of $W$ pairwise disjoint, and disjoint from $V \setminus A$, then we will be able to extract a family of these copies such that the restriction of $R$ to the union $U$ of these copies augmented with $F$, forms a multiple of $W$ by an infinite chain which is $F$-multichainable. Choose $F$ such that the local isomorphisms of $R_{\upharpoonright U}$ that extend the identity on $A$, are exactly those extensions of the identity on $F$. Then $F$ is the kernel of $R_{\upharpoonright U}$. Hence, setting $S := R_{\upharpoonright U}$, we get the required conclusion. According to Proposition 5.4.2, from $R$ as above we may find an extension $R'$ with the same age such that $R'_{\upharpoonright V' \setminus A}$ is a multiple of $R_{\upharpoonright V \setminus A}$ over $A$ by a chain $L$. Hence, if we construct $W$ in $R'$ instead of $R$, we will be able to extract infinitely many copies mentioned above, which completes
the proof of Proposition 5.49.

☐

To complete the proof of Theorem 5.42 we will need the following result.

**Proposition 5.50.** Let $R$ with domain $V$ and let $A$ be and infinite subset of $V$ such that $V \setminus A$ is val-finite, and for each $x \in L$, $\text{Age}(R \upharpoonright \{x\})$ is very-well-quasi-ordered. Then the following assertions hold.

(1) $R$ is freely interpretable by some relational structure $M$ for which $A$ and $V \setminus A$ are two intervals, and the age of the restriction $M \upharpoonright V \setminus \{x\}$ is very-well-quasi-ordered for every $x \in V$.

(2) Suppose that $A = \ker R$, and let $k < k'$ be two integers, $x_0 \in A$, and let $(M_n)_{n \in \mathbb{N}}$ be a sequence of relational structures $M_n := (R_n, U_n^1, \dots, U_n^{k'})$ where $R_n := R \upharpoonright F_n$ is a finite restriction of $R$, each $U_n^i$ is a subset of $F_n$ for $1 \le i < k'$, with $U_n^i \subseteq U_n^{k'+1}$ for $k+1 \le i \le k'$. If for each $x \in V$, the set $\{n \in \mathbb{N}: x \in U_n^{k'+1}\}$ is finite, then there are $n, m \in \mathbb{N}$, $n < m$, and an embedding $f: M_n \setminus \{x_0\} \to M_m \setminus \{x_0\}$ such that $f|_{U_n^{k'+1}}$ extended by the identity on $x_0$ is an embedding of $M_{\upharpoonright U_n^{k'+1} \cup \{x_0\}}$ into $M_{\upharpoonright U_n^{k'} \cup \{x_0\}}$.

**Proof.** (1). Since $V \setminus A$ is val-finite, $A$ is val-finite by Theorem 5.47. Apply Lemma 5.46 to get two finite subsets $F$ and $G$ of $V \setminus A$ and $A$, respectively, such that the local isomorphisms of $R_{\upharpoonright A}$ and $R_{\upharpoonright V \setminus A}$ that extend by the identity on $F$ and on $G$ are those that extend the identity on $V \setminus A$ and $A$, respectively.

Set $M := R \cdot a_1 \cdots a_k \cdot b_1 \cdots b_\ell$ where $a_1, \dots, a_k$ and $b_1, \dots, b_\ell$ are constants enumerating $F$ and $G$, respectively.

(2). This sentence is only interesting if all the $F_n$ contain $x_0$. Supposing that the conclusion does not hold, we derive a contradiction. We may suppose without loss of generality that this sequence is minimal in the Nash-Williams sense. We may go to the “limit”, constructing a multirelational structure

$$M_\omega := R_\omega \cdot U_\omega^1 \cdots U_\omega^{k'},$$

such that for every proper restriction of $M_n$, there is some embedding $f$ satisfying the conditions above. We may chose for $R_\omega$ a restriction of some extension of $R$ such that all $x \in K$ are outside the union of the $U_\omega^{k+1}, \dots, U_\omega^{k'}$'s. By (1), the local automorphisms of $M_\omega$ that induce local isomorphisms of $M_\omega \upharpoonright \{x_0\} \cup U_\omega^{k+1}$, are the local isomorphisms of a relational structure whose age is very-well-quasi ordered. Since one can transform the $M_n$'s into bounds of this relational structure, and since there are only finitely many, we get a contradiction. ☐

5.5.2. *End of the proof of Theorem 5.42.* Let $\mathfrak{A}$ be the age of an almost multichainable relational structure with $\mathbf{H}(\mathfrak{A}) < \omega^2$. According to Proposition 5.49, the complement of $\ker(R)$ of every $R$ with age $\mathfrak{A}$ is val-finite over $\ker(R)$.

Our aim is to prove that $\ker(R)$ is finite. Suppose that this is not the case. Consider $R$ with age $\mathfrak{A}$, countable base $V$, and infinite kernel $K$. According to the equivalence between Proposition 5.43 and Proposition 5.44, we may suppose that the age of $R_{\upharpoonright V \setminus \{x\}}$ is hereditarily wqo, for every $x \in V$. In order to get a contradiction, let us enumerate the members of $V$ into a chain $C$ order isomorphic to the chain $\mathbb{N}$ of positive integers, and let us suppose that the first element $x_0$ of $C$ is in $K$. Since $K$ is infinite, we may find an infinite sequence of finite subsets $F_n$ of $V$ with $a_n \in F_n \cap K$ such that the sequence of restrictions $B_n := R_{\upharpoonright F_n} \cdot a_n$ forms an antichain with respect to embedabbility. This sequence being bad, we may suppose that it is minimally bad in the Nash-Williams sense (that is, no sequence with a strictly smaller prefix can be bad). Due to our hypothesis on $R$, only finitely many $F_n$ do not contain $x_0$. In fact, due to the minimality, all $F_n$ contain $x_0$. Now we proceed as in [147]. In order make the proof simpler, we suppose that $R$ is made of binary relations (the present proof extends to arbitrary arities, while the one given in (1) of Theorem 4.24, p. 267, [157], does not). To $B_n$ we associate the relational structure $M := R_{\upharpoonright F_n} \cdot U_n \cdot b_n$, where $U_n$ is a maximal final section of $C_{\upharpoonright F_n}$ and $b_n$ is the element just before $U_n$ such that for infinitely many $n'$ there exists $f$ defined on $F_n$ and with values in $F_{n'}$, inducing an embedding of $B_{n-x_0}$ in $B_{n'}$ and an embedding of $B_n \upharpoonright \{x_0, a_n\} \cup U_n \cdot x_0$ in $B_{n'}$.

There are not infinitely many integers $n$ such that for any two of them, say, $n$ and $n'$, a map $f$ from $F_n$ to $F_{n'}$, which leaves $x_0$ fixed,
• transforms $a_n$ and $b_n$ into $a_{n'}$ and $b_{n'}$, respectively,

• sends $U_n$ into $U_{n'}$, and

• induces an embedding of $B_{n-x_0}$ into $B_{n'}$, and an embedding of $B_n \upharpoonright \{x_0, a_n\} \cup U_n$ into $B_{n'}$.

According to (2) of Proposition 5.50, we may suppose that there is some element $x_1$ in $K$ which belongs to infinitely many $U_n$'s. Since the $B_n$'s are incomparable this is impossible.

This completes proof of Theorem 5.42.

5.5.3. *Ages of multichainable relational structures of height at least $\omega^2$.*

**Theorem 5.51.** If an age of a relational structure with finite signature has no height then it contains an age of height $\omega^2$.

**Proof.** If an age $\mathfrak{A}$ has no height, $\mathfrak{A}$ is not wqo. According to Lemma 3.12, $\mathfrak{A}$ contains a wqo age $\mathfrak{B}$ with infinitely many bounds in $\mathfrak{A}$. Being wqo, this age has a height. According to Theorems 5.34 and 5.42, its height cannot be less than $\omega^2$. $\square$

**Corollary 5.52.** Every age of height at most $\omega^2$ is wqo.

**Theorem 5.53.** Let $n$ and $p$ be two integers. There are finitely many ages of height $\omega^n + p$ in a given finite signature.

**Proof.** One shows by induction on $\omega.n + p$ (and some effort) that the parameters of almost multichainable relational structures of height $\omega^n+p$ are bounded, hence by Lemma 2.18 there are only finitely many. $\square$

This result is the best possible. If the arity is at least 2, there are infinitely many ages of height $\omega^2$ and in fact a continuum (see Subsection 7.2).

Let $\mathfrak{A}$ be an age. Let $\mathrm{Id}(\mathrm{Almulti}(\mathfrak{A}))$ be the collection of subages of $\mathfrak{A}$ which are ages of almost multichainable relational structures. Ordered by set inclusion $\mathrm{Id}(\mathrm{Almulti}(\mathfrak{A}))$ is well founded. Let $\mathrm{Id}(\mathrm{Almulti}_{<\alpha}(\mathfrak{A}))$ be the collection of those which have height $< \alpha$. According to Theorem 5.53 $\mathrm{Id}(\mathrm{Almulti}_{<\omega^2}(\mathfrak{A}))$ is level finite

**Problem 16.** Does $\mathrm{Id}(\mathrm{Almulti}_{<\omega^2}(\mathfrak{A}))$ always level finite (for $\alpha \le \omega^\omega$)?

Our last result refines Proposition 5.49.

**Theorem 5.54.** If an age $\mathfrak{A}$ contains ages of height $\omega \cdot n$, for each integer $n$, then it contains an age of height $\omega^2$.

**Proof.** According to Theorem 5.53, $\mathrm{Id}(\mathrm{Almulti}_{<\omega^2}(\mathfrak{A}))$ is level-finite. Hence, by König's lemma, $\mathrm{Id}(\mathrm{Almulti}_{<\omega^2}(\mathfrak{A}))$ contains a chain of order type at least $\omega^2$. $\square$

**Problem 17.** Describe ages of multichainable relational structures $R$ such that $\mathbf{H}(\mathrm{Age}(R)) < \omega^2$.

5.6. **Monomorphic decomposition.** I present below the notion of monomorphic decomposition of a relational structure introduced in [165] with an approach presented in [140]. A relational structure admitting a finite monomorphic decomposition is a very particular kind of almost multichainable structure. Its age has height strictly smaller than $\omega^2$. These structures play a pivotal role in the study of age algebras.

Let $R$ be a relational structure. A subset $V'$ of $V(R)$ is a *monomorphic part* of $R$ if for every integer $k$ and every pair $A, A'$ of $k$-element subsets of $V(R)$, the induced structures on $A$ and $A'$ are isomorphic whenever $A \setminus V' = A' \setminus V'$. A *monomorphic decomposition* of $R$ is a partition $\mathcal{P}$ of $V(R)$ into monomorphic parts. A monomorphic part which is maximal for set inclusion among monomorphic parts is a *monomorphic component* of $R$. The monomorphic components of $R$ form a monomorphic decomposition of $R$ of which, every monomorphic decomposition of $R$ is a refinement (Proposition 2.12 of [165]). This decomposition is denoted by $\mathcal{P}(R)$ and called *minimal* or *canonical* and the number of its infinite blocks is called the *monomorphic dimension* of $R$. The canonical decomposition can be introduced via an equivalence relation as follows. Let $R$ be a relational structure and $V := V(R)$. Let $x$ and $y$ be two elements of $V$. Let $A$ be a
finite subset of $V \setminus \{x, y\}$, we say that $x$ and $y$ are *A-equivalent* and we set $x \cong_{A,R} y$ if the restrictions of $R$ to $\{x\} \cup A$ and $\{y\} \cup A$ are isomorphic. Let $k$ be a nonnegative integer, we set $x \cong_{k,R} y$ if $x \cong_{A,R} y$ for every $k$-element subset $A$ of $V(R) \setminus \{x, y\}$. We set $x \cong_{\le k,R} y$ if $x \cong_{k',R} y$ for every $k' \le k$ and $x \cong_R y$ if $x \cong_{k,R} y$ for every $k$. For example, the $\emptyset$-equivalence is an equivalence relation on $V$, two vertices $x$ and $y$ being equivalent if and only if the restrictions of $R$ to $x$ and $y$ are isomorphic. As it is easy to see:

**Corollary 5.55.** The relations $\cong_{k,R}$, $\cong_{\le k,R}$ and $\cong_R$ are equivalence relations on $V$. Furthermore, each equivalence class of $\cong_R$ is a monomorphic part of $R$, and each monomorphic part is included in some equivalence class.

The latter result yields:

**Proposition 5.56.** The equivalence classes of $\cong_R$ form a decomposition of $R$ into monomorphic parts and every decomposition into monomorphic parts is finer. Thus, the decomposition of $R$ into equivalence classes of $\cong_R$ coincides with the decomposition of $R$ into monomorphic components.

**Theorem 5.57.** A relational structure $R := (V, (\rho_i)_{i \in I})$ admits a finite monomorphic decomposition if and only if there exists a linear order $\le$ on $V$ and a finite partition $(V_x)_{x \in X}$ of $V$ into intervals of $C := (V, \le)$ such that every local isomorphism of $C$ which preserves each interval is a local isomorphism of $R$. Moreover, there exists such a partition whose number of infinite blocks is the monomorphic dimension of $R$.

In other words, $R := (V, (\rho_i)_{i \in I})$ admits a finite monomorphic decomposition if and only if $R$ is freely interpretable by a structure of the form $S := (V, \le, (u_1, \dots, u_l))$ where $\le$ is a linear order and $u_1, \dots, u_l$ are finitely many unary relations determining a partition of $V$ into intervals of $(V, \le)$.

A straightforward application of the Compactness Theorem of First Order Logic yields:

**Theorem 5.58.** A relational structure $R$ admits a finite monomorphic decomposition if and only if there is some integer $\ell$ such that every member of $\text{Age}(R)$ has a monomorphic decomposition into at most $\ell$ classes.

The following property allows to test the existence of a finite monomorphic decomposition by looking at the relations composing $R$, see [140], p. 168 and [144].

**Proposition 5.59.** Let $m \in \mathbb{N}$. An ordered relational structure $R := (V, \le, (\rho_i)_{i<m})$ has a finite monomorphic decomposition if and only if every $R_i := (V, \le, \rho_i)$ ($i<m$) has such a decomposition.

## 6. WQO AGES AND PROFILE

As already said, the *profile* of a hereditary class $\mathcal{C}$ of finite relational structures is the function $\varphi_{\mathcal{C}}$ which counts for every integer $n$ the number $\varphi_{\mathcal{C}}(n)$ of members of $\mathcal{C}$ on $n$ elements, isomorphic members being identified. We say that the *profile* of a relational structure $R$, denoted by $\varphi_R$, is the profile of its age. Hence, $\varphi_R(n)$ is the number of induced substructures of $R$ on $n$ elements, isomorphic substructures being identified. There is a parent notion, the *labelled profile*; instead of counting up to isomorphism, one counts all possible structures on $n$ elements. Since $n$-element chains have no nontrivial automorphism, the labelled profile of a hereditary class $\mathcal{C}$ is the profile of the class $\mathcal{C}.\mathcal{L}$ made of structures of the form $(S, L)$ where $S \in \mathcal{C}$ and $L$ is a linear order on the same domain as $S$. This notion started with Scheinerman and Zito [182]. The two notions have a common feature. There are jumps in their behavior. Several dozen papers have been written on these notions. We will not attempt to present a synthesis of results but instead will present results, which have interested me since Fraïssé and I started to think about the *profile* (the name of “profile” for this counting function was proposed to us by William Craig in 1969). We will present an overview, with results of Cameron on the orbital profile in that setting, and conclude with a recent result by Falque and Thiéry [67] solving conjectures of Cameron and Macpherson.

### 6.1. A basic result.

**Theorem 6.1.** The profile of an infinite relational structure is non-decreasing.
The result was conjectured with Fraïssé in [79] (Problème 2.5.3, p.1627). The proof, based on Ramsey’s theorem, appears in Fraïssé’s *Cours de Logique* [75] in 1971 (Exercice 8, p.113). The result was improved in 1976 by showing that $\varphi_R(n) \le \varphi_R(n+p)$ provided that the domain of $R$, possibly finite, has at least $2n+p$ elements (with $n+p \ge n \ge 0$) [148]. The proof of this improvement is based on the non-degeneracy of the Kneser matrix of the $n$-element subsets of a $2n+p$ element set, a result obtained independently by Gottlieb [88] and Kantor [102].

With what we did in Subsection 5.3, the proof of Theorem 6.1 is almost immediate. Indeed, let $R := (V, (\rho_i)_{i \in I})$ be an infinite relational structure and $n$ be an integer. Then, by a double counting argument, one gets $\varphi_R(n) \le (n+1)\varphi_R(n+1)$. In particular, if $\varphi_R(n)$ is infinite then $\varphi_R(n+1)$ is infinite too and $\varphi_R(n) \le \varphi_R(n+1)$. Thus, one may suppose $\varphi_R(n)$ finite. In this case, there is a finite subset $I'$ of $I$ such that the reduct $R' := R^{I'}$ satisfies $\varphi_{R'}(n) = \varphi_R(n)$ and there is a finite subset $K$ of $V$ containing a representative of each isomorphism type of $n$-element restrictions of $R'$. According to Lemma 5.14, there is an infinite subset $V'$ of $V$ containing $K$ on which the restriction $R'' := R_{V'}$ is $K$-chainable. According to Theorem 5.13, $\varphi_{R''}(n) \le \varphi_{R''}(n+1)$. Since $\varphi_R(n) = \varphi_{R'}(n) = \varphi_{R''}(n)$ and $\varphi_{R''}(n+1) \le \varphi_{R'}(n+1) \le \varphi_R(n+1)$, the inequality $\varphi_R(n) \le \varphi_R(n+1)$ follows.

This result points to the importance of the notion of an almost chainable structure. It suggests to first look at hereditary classes with bounded profile and beyond. We do that in the next subsection.

**6.2. Bounded profile and beyond.** The notion of profile leads to complete Theorem 5.22 with the following characterization (see [79], 2.5.2, p. 1627):

**Theorem 6.2.** The profile $\varphi_R$ of a relational structure $R$ is bounded above, that is, $\text{Age}(R)$ is finimorphic, if and only if $R$ is almost chainable.

With what we know, the proof is immediate: if $R$ is almost chainable then $\varphi_R$ is bounded above by $2^{\lceil \ker(R) \rceil}$ where $\ker(R)$ is the kernel of $R$. For the converse, the conclusion is immediate if $R$ is finite. If $R$ is infinite then since $\varphi_R$ is bounded above, $\text{Age}(R)$ is level-finite. Hence (2) of Proposition 5.18 applies: $\text{Age}(R)$ is an increasing union of a sequence of infinite almost chainable ages. Since $\varphi_R$ is bounded, this sequence is stationary. The conclusion follows.

Let $G$ be a permutation group acting on a set $V$ and let $R$ be a relational structure encoding $G$. Then, the kernel of $R$ is the union $U$ of the finite $G$-orbits of the one-element sets (hence the kernel of $R$ is empty if $G$ has no finite orbit).

Closed monomorphic groups are described in Theorem 5.9. In terms of orbital profile these groups are those of orbital profile equal to 1.

From Theorem 6.2, we immediately have this result.

**Theorem 6.3.** The orbital profile of a permutation group $G$ acting on a countable set $V$ is bounded if and only if $U$, the union of all finite orbits of $G$, is finite and $G$ acts on $V \setminus U$ as a monomorphic group.

The following result illustrates Theorem 5.23 (the crucial part is the implication $(iv) \Rightarrow (ii)$ of Theorem 5.23).

**Theorem 6.4.** The profile $\varphi_{\mathcal{C}}$ of a hereditary class $\mathcal{C}$ of relational structures is bounded above, that is, $\mathcal{C}$ is finimorphic, whenever $\mathcal{C}$ is a finite union of ages of almost chainable structures. The converse holds if the signature is finite.

As already seen, without a condition like the finiteness of the signature, there are hereditary classes of relational structures whose profile is bounded above and which are not finite unions of ages of almost chainable structures.

Above bounded profile, we have:

**Lemma 6.5.** (cf. [155], I.7, p. 318 and [157], Theorem 2.10). For every non-decreasing and unbounded map $\varphi : \mathbb{N} \to \mathbb{N}$, there is a relational structure $R$ such that $\varphi_R$ is unbounded and eventually bounded above by $\varphi$.
**Proof.** First, let $A$ be a subset of $\mathbb{N}$ and $R_A := (\mathbb{N}, (\rho_m)_{m \in A})$ where $\rho_m := \{(0, \dots, m)\}$ for $m \in A$. Then $\varphi_{R_A}(n) = |A \cap \{0, \dots, n-1\}| + 1$ for every $n \in \mathbb{N}$. Indeed, observe that if $F$ and $F'$ are two $n$-element subsets of $\mathbb{N}$, then the restrictions $R_{A \upharpoonright F}$ and $R_{A \upharpoonright F'}$ are isomorphic if and only if the largest $a, a' \in A$ such that $\{0, \dots, a\} \subseteq F$ and $\{0, \dots, a'\} \subseteq F'$ are equal. Next, let $\psi: \mathbb{N} \to \mathbb{N}$ be any non-decreasing and unbounded map such that $1 \le \psi(n) \le n + 1$ for all $n \in \mathbb{N}$. For $A := \{n \in \mathbb{N} : \psi(n) < \psi(n+1)\}$, we have $\varphi_{R_A} \le \psi$. Indeed, let $n \in \mathbb{N}$ and $\{n_1 < \dots < n_k\} = A \cap (\leftarrow n]$. From

$$1 \le \psi(n_1) < \psi(n_1+1) < \dots < \psi(n_k) < \psi(n_k+1) \le \psi(n),$$

we get $\psi(n) \ge k+1 = \varphi_{R_A}(n)$.

Finally, let $\varphi: \mathbb{N} \to \mathbb{N}$ be any non-decreasing and unbounded map; we may select $\psi: \mathbb{N} \to \mathbb{N}$ with $\psi$ non-decreasing and unbounded and eventually dominated by $\varphi$ such that $1 \le \psi(n) \le n+1$ for all $n$. Then, for $n$ large, $\varphi_{R_A}(n) \le \psi(n) \le \varphi(n)$. $\square$

The reader will notice that in these examples, if $\varphi$ is unbounded then the signature of $R_A$ is unbounded and also the kernel of $R_A$ is infinite (equal to $\mathbb{N}$). Let us see what happens if the signature or the kernel is finite.

**6.3. Jumps in the profile.** At the end of the 1970's, I noted that beyond bounded profiles, and provided that the relational structures satisfy some mild conditions, there are jumps in the behavior of their profiles, for instance, no profile grows as $\log n$ or $n \log n$.

In 1981, I proved that if the profile $\varphi_{\mathcal{C}}$ of a hereditary class $\mathcal{C}$ is unbounded then its growth is at least linear (in the sense that $\frac{\varphi_{\mathcal{C}}(n)}{n} \ge a$ for some constant $a > 0$ and all $n$) provided that the signature is bounded [155]. Thus is due to the fact that if $m$ is the maximum of the arity of the signature $\mu$ there is some integer $s(m)$ such that if the profile $\varphi_{\mathcal{C}}$ is constant from $n$ to $n+s(m)+1$ then it remains constant afterwards. The existence of $s(m)$ relies on Frasnay's theory.

Cameron [28] proved a similar result for the orbital profile of groups (see Subsection 1.4.6). If the orbital profile $\vartheta_G$ of a group $G$ is unbounded then $\vartheta_G(n) \ge \frac{n}{2} - c$ for some constant $c$ and all $n$.

Let us say that the *growth* of $\varphi_R$ is *polynomial of degree $k$* if $a \le \frac{\varphi_R(n)}{n^k} \le b$ where $a$ and $b$ are positive constants; the *growth is faster than every polynomial* if $\frac{\varphi_R(n)}{n^k}$ goes to infinity with $n$ for every $k$.

In my thesis [149], I obtained the following with a different approach.

**Theorem 6.6.** The growth of the profile $\varphi_R$ of a relational structure $R := (V, (\rho_i)_{i \in I})$ is either polynomial or faster than every polynomial provided that either the signature $\mu := (m_i)_{i \in I}$ is bounded above or the kernel $\ker(R)$ of $R$ is finite.

The fact that the signature $\mu := (m_i)_{i \in I}$ is bounded in Theorem 6.6 amounts to the fact that $R$ and some finite reduct have the same profile. This is essentially Lemma 2.8 of [155]. For the reader's convenience, we repeat the argument.

**Lemma 6.7.** Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure with signature $\mu := (m_i)_{i \in I}$. If $\mu$ is bounded and $\varphi_R(n)$ is finite for some $n \ge \max \mu$ then there is a reduct $R^{\upharpoonright I'}$ of $R$ with $I'$ finite and with the same profile as $R$. In particular $\varphi_R(n')$ is finite for every integer $n'$.

**Proof.** Let $q := \varphi_R(n)$ and $F_1, \dots, F_q$ be $q$ subsets of $V$ such that each $n$-element restriction of $R$ is isomorphic to one of the restrictions $R_{\upharpoonright F_1}, \dots, R_{\upharpoonright F_q}$. Let $Q := F_1 \cup \dots \cup F_q$. Say that two indices $i, i' \in I$ are equivalent if $m_i = m_{i'}$ and the restrictions of $\rho_i$ and $\rho_{i'}$ to $Q$ are equal. We claim that $i$ and $i'$ are equivalent if and only if $\rho_i = \rho_{i'}$. Indeed, suppose that $i$ and $i'$ are equivalent. Then $m_i = m_{i'}$. Let $m$ be the common value. Let $(x_1, \dots, x_m) \in V^m$, we prove that $\rho_i(x_1, \dots, x_m) = \rho_{i'}(x_1, \dots, x_m)$. For that, extend $\{x_1, \dots, x_m\}$ to an $n$-element subset $F$ of $V$. Since the restriction $R_{\upharpoonright F}$ is isomorphic to some $R_{\upharpoonright F_q}$, let $\psi$ such an isomorphism. Since $i$ and $i'$ are equivalent, $\rho_i(\psi(x_1), \dots, \psi(x_m)) = \rho_{i'}(\psi(x_1), \dots, \psi(x_m))$. Since $\psi$ is an isomorphism $\rho_i(x_1, \dots, x_m) = \rho_i(\psi(x_1), \dots, \psi(x_m))$ and also $\rho_{i'}(x_1, \dots, x_m) = \rho_{i'}(\psi(x_1), \dots, \psi(x_m))$. Hence $\rho_i(x_1, \dots, x_m) = \rho_{i'}(x_1, \dots, x_m)$ as claimed. The equivalence relation defined above has finitely
many classes. Taking a representative in each class yields a finite set $I'$. The reduct $R^{\upharpoonright I'}$ has the same local isomorphisms as $R$, hence the same profile. $\square$

In order to prove Theorem 6.6, we relate the growth of the profile of a relational structure $R$ to the height $H(Age(R))$ of the set $\mathrm{Id}(Age(R))$ of subages of $Age(R)$. We prove:

**Theorem 6.8.** Let $R$ be a relational structure such that the signature $\mu := (m_i)_{i \in I}$ is bounded above or the kernel $\ker(R)$ of $R$ is finite. Then, either $R$ is almost multichainable and $H(Age(R)) = \omega \cdot (k+1) + p$ with $p < \omega$, in which case $\varphi_R$ grows as a polynomial of degree $k$, or $\varphi_R$ grows faster than every polynomial.

A proof, complete for binary structures, is given in [157], Theorem 4.30, p. 269. Here are the essential ingredients of the proof and their organisation.

6.3.1. Ingredients for the proof of Theorem 6.8. First, in order to prove that the growth of the profile of a relational structure $R$ with finite kernel is polynomial, we show that it suffices to prove that the growth of a reduction over its kernel is polynomial.

For that, we say that the growth of a map $\varphi: \mathbb{N} \to \mathbb{N}$ is invariant under translation if $\varphi$ and its translate $n \to \varphi(n+1)$ have the same growth. In this case, $\varphi$ is bounded by an exponential function. Item (3) of Lemma 3.34 asserts that the growth of $\varphi_R$ is invariant under translation if and only if the growth of reduction $\varphi_M$ is invariant too, in which case there are the same. Since polynomial functions are invariant under translation, we get:

**Lemma 6.9.** If $\ker(R)$ is finite then $\varphi_R$ is bounded by a polynomial of degree $k$, resp. has polynomial growth of degree $k$, if and only if the profile $\varphi_M$ of a reduction $M$ is bounded by a polynomial of degree $k$, resp. has polynomial growth of degree $k$.

Next, we use Proposition 5.41, Theorem 5.42 and the following two statements:

**Theorem 6.10.** If the age $Age(R)$ of a relational structure $R$ is inexhaustible and $H(Age(R)) \le \omega \cdot (k+1)$, then

$$ \varphi_R(n) \le \binom{n+k}{k}, $$

for every integer $n$.

**Lemma 6.11.** If the age $Age(R)$ of a relational structure $R$ is inexhaustible and $H(Age(R)) = \omega \cdot (k+1)$, then $\varphi_R$ grows as a polynomial of degree $k$.

Theorem 5.42 and these two statements are proved in [157] (see Theorem 4.28, Lemma 4.29, p. 269, and (1) of Theorem 4.24) except that the proof of Theorem 5.42 ((1) of Theorem 4.24) is given only for binary structures.

6.3.2. Structure of the proof of Theorem 6.8. Let $R$ be a relational structure such that the signature $\mu := (m_i)_{i \in I}$ is bounded above or the kernel $\ker(R)$ of $R$ is finite. If for some integer $n$, $\varphi_R(n)$ is infinite then $\varphi_R(n')$ is infinite for all $n' \ge n$ hence the growth of $\varphi_R$ is faster than every polynomial.

**Case 1.** Assume that $\ker(R)$ is finite, that is, $R$ is almost inexhaustible. In this case, a reduct $M$ of $R$ is inexhaustible. According to Proposition 5.41, either $M$ is multichainable of height $\omega(k+1)$ or $Age(M)$ contains multichainable ages of height $\omega \cdot (k+1)$, for every integer $k$.

**Subcase 1.** $H(Age(M)) = \omega \cdot (k+1)$. Then $\varphi_M$ grows as a polynomial of degree $k$ from Theorem 6.10 and Lemma 6.11. According to Lemma 3.34, $H(Age(R)) = \omega \cdot (k+1) + p$. Lemma 6.9 asserts that $\varphi_R$ grows as a polynomial of degree $k$.

**Subcase 2.** $Age(M)$ contains multichainable ages of height at least $\omega \cdot (k+1)$ for arbitrarily large finite $k$. Since by Subcase 1 their profiles is polynomial of degree at least $k$, the profile of $Age(M)$ grows faster than every polynomial. Lemma 6.9 asserts that the same holds for $\varphi_R$.
**Case 2.** Assume that $\ker(R)$ is infinite. Hence, from our hypothesis, the signature $\mu$ is bounded. In this case, $\text{Age}(R)$ contains a subage of height $\omega^2$. Indeed, either $\text{Age}(R)$ is wqo, hence it has a height and by Theorem 5.42 this height is at least $\omega^2$, or $\text{Age}(R)$ is not wqo and, by Theorem 5.51, it contains a subage of height $\omega^2$. According to Theorem 5.42 the proper subages are almost multichainable and according to Case 1 their profile is polynomial and thus the growth of the profile of the subage of height $\omega^2$ is faster than every polynomial.

The reader will note that Case 1 is easier than Case 2.

Theorem 6.10 and Lemma 6.11 have a striking consequence for the orbital profile of permutation groups.

**Theorem 6.12.** The orbital profile of an oligomorphic group is either polynomial or faster than every polynomial.

Indeed, if $R$ encodes a permutation group $G$ acting on a set $V$ then the kernel $\ker(R)$ of $R$ is the set union of the finite orbits of the one-element subsets of $V$. If $\theta_G$ denotes the orbital profile of $G$ then the number of orbits of one-element subsets is at most $\theta_G(1)$, hence, $\ker(R)$ is finite provided that $G$ is oligomorphic.

These results suggest that the link between the height, or the ordinal length, and the growth rate of the profile extends too. This could be the case through hierarchies of functions labelled by ordinals, as is the case with the Wainer-Grzegorczyk hierarchy. But this would require that the arity is bounded. Indeed, if the signature is unbounded the conditions that $\text{Age}(R)$ is wqo and $\ker(R)$ is finite do not suffice. Our construction of ages yields ages with $o(\text{Age}(R)) = \omega^\omega$ and arbitrarily large growth rate ([164]).

**6.4. The age algebra of Cameron.** The notion of polynomial growth of a profile function is crude. There are at least two others. First, $\varphi_R(n)$ is equivalent to $a.n^k$ for some positive real $a$ and nonnegative integer $k$ (in standard notation $\varphi_R(n) \simeq a.n^k$). Next, $\varphi_R(n)$ is, for $n$ large enough, a quasi-polynomial, that is, a polynomial in $n$ with periodic coefficients. Since $\varphi_R$ is non-decreasing, this will give that $\varphi_R(n) \sim a \cdot n^k$. This quasi-polynomiality is better expressed in terms of the generating series of the profile $\mathcal{H}_{\varphi_R} := \sum \varphi_R(n)$. This is a rational fraction of the form

$$ (6.1) \qquad \frac{P(Z)}{(1-Z)(1-Z^2)\cdots(1-Z^{k+1})} $$

where $P$ is a polynomial with integer coefficients (possibly negative).

At the end of the seventies, Cameron, when considering the orbital profile $\theta_G$ of a permutation group $G$, conjectured that $\theta_G$ is asymptotically a polynomial (that is, $\theta_G(n) \simeq a.n^k$ for some $a, k$ when $n$ goes to infinity), whenever it is bounded above by a polynomial. He introduced an algebra, the Cameron algebra, made of the linear combinations of orbits of $G$. This algebra $A(G)$ is graded and decomposes in a direct sum of subspaces $A_n$ made of elements of degree $n$, the dimension of $A_n$ being $\theta_G(n)$. This implies that the generating series $H_G$ of $\theta_G$, that is, $H_G := \sum \theta_G(n)Z^n$, associated to the orbital profile is the Hilbert series of $A(G)$. Macpherson [126], p. 286, conjectured that the algebra $A(G)$ is finitely generated whenever $\theta_G$ is bounded above by a polynomial. The truth of the conjecture implies that $H_G$ is a rational fraction of the form 6.1 above [29], hence $\theta_G$ is a quasi-polynomial, from which Cameron's conjecture follows. The truth of Macpherson's conjecture was recently proved by Falque and Thiéry [66], [67].

Cameron extended his notion of algebra to ages. We reproduce below the presentation given in [165]. Let $\mathbb{K}$ be a field of characteristic 0, and $V$ be a set. For $n \ge 0$, denote by $[V]^n$ the set of subsets of $V$ of size $n$, and let $\mathbb{K}^{[V]^n}$ be the vector space of maps $f : [V]^n \to \mathbb{K}$. The set algebra is the graded connected commutative algebra $\mathbb{K}^{[V]^\omega} := \bigoplus_n \mathbb{K}^{[V]^n}$, where the product of $f : [V]^m \to \mathbb{K}$ and $g : [V]^n \to \mathbb{K}$ is defined as $fg : [V]^{m+n} \to \mathbb{K}$ such that:

$$ (6.2) \qquad (fg)(A) := \sum_{(A_1, A_2) : A=A_1 \oplus A_2} f(A_1)g(A_2). $$

Identifying a set $S$ with its characteristic function $\chi_S$, elements of the set algebra can be thought as (possibly infinite but of bounded degree) linear combinations of sets; the unit is the empty set, and the product of two sets is their disjoint union, or 0 if their intersection is non trivial.
Let $R$ be a relational structure with base set $V$. A map $f : [V]^m \to K$ is $R$-invariant if $f(A) = f(A')$ whenever $R_{\upharpoonright A}$ and $R_{\upharpoonright A'}$ are isomorphic. It is easy to show that the product of two $R$-invariant maps is again invariant. The $K$-vector space spanned by the $R$-invariant maps is therefore a graded connected commutative subalgebra of the set algebra, the *age algebra of $R$*, that we denote by $KA(R)$. It can be shown that two relational structures with the same age yield the same algebra (up to an isomorphism of graded algebras); thus the name, coined by Cameron who invented the notion [31]. If the profile of $R$ takes only finite values, then $KA(R)$ identifies with the set of (finite) linear combinations of elements of $Age(R)$ and, as pointed out by Cameron, $\varphi_R(n)$ is the dimension of the homogeneous component of degree $n$ of $KA(R)$; indeed, define an orbit as the collection of finite subsets $A$ of $V$ such that $R_{\upharpoonright A}$ have a given isomorphic type $\tau$, and define an orbit sum as the characteristic function of an orbit; more specifically, the *orbit sum* of an isomorphism type $\tau \in Age(R)$ is the characteristic function $o_\tau := \sum_{A \in [V]^{<\omega}_{\tau(A)=\tau}}$ of its representatives in $R$; then observe that the set of orbit sums form a basis of the age algebra $KA(R)$. By a slight abuse, we sometimes identify $\tau$ with its orbit sum to see it as an element of $KA(R)$.

Cameron gave the following illustration of the relevance of the age algebra. Let $e := \sum_{a \in V} \{a\}$, which we can think of as the sum of isomorphic types of the one-element restrictions of $R$. Let $U$ be the graded linear algebra $K[e] = \bigoplus_{n=0}^{\infty} K e^n$.

Cameron (see [31]) proved:

**Theorem 6.13.** If $R$ is infinite then $e$ is not a zero-divisor; namely for any $u \in KA(R)$, $eu = 0$ if and only if $u = 0$.

This result implies that $\varphi_R$ is non-decreasing. Indeed, the image of a basis of the vector space $KA(R)_n$ under multiplication by $e$ is a linearly independent subset of $KA(R)_{n+1}$.

The relationship between profiles and age algebras is particularly simple for relational structures with bounded profile. These structures (characterized in [79] for finite signature and in [155, Théorème 1.2] for arbitrary signature, by means of Ramsey's theorem) were defined in Section 5.3. We recall this relationship below. The following theorem links the profile with the age algebra in the context of almost chainable and almost monomorphic relational structures.

**Theorem 6.14.** Let $R$ be a relational structure on an infinite domain $V$. Then, the following properties are equivalent:

(a) the profile of $R$ is bounded;

(b) $R$ is almost monomorphic;

(c) $R$ is almost chainable;

(d) the Hilbert series is of the following form, with $P(Z) \in \mathbb{N}[Z]$:

$$ \mathcal{H}_R = \frac{P(Z)}{1-Z}; $$

(e) the age algebra is a finite dimensional linear-module over the linear-algebra $K[e]$, where $e := \sum_{a \in V} \{a\}$; in particular it is finitely generated and Cohen-Macaulay.

As a generalization, Théry and I [165] made the following conjecture:

**Problem 18.** If a relational structure $R$ has finite kernel and profile bounded above by some polynomial then the generating series of the profile is a rational fraction of the form 6.1 above.

The main result of [165] offers a complete solution for relational structures admitting a finite monomorphic decomposition into monomorphic components (see the definition in Subsection 5.6).

**Theorem 6.15.** If $R$ is an infinite relational structure with a finite monomorphic decomposition of dimension $k+1$ then the Hilbert series of the profile of the profile is a rational fraction of the form 6.1 above; in particular the profile $\varphi_R$ is eventually a quasi-polynomial of degree $k$, hence $\varphi_R(n) \sim an^k$.

Several important structures, for instance, tournaments with polynomial profiles have this property [20], but not graphs. The case of graphs was settled by Balogh et al. [12] – see Theorem 6.19.
We do not know if Problem 18 has a positive answer for cellular graphs. There are plenty of examples of relational structures whose generating series is a rational fraction of the type described above, but for which the age algebra is not finitely generated ([165, 166]).

**Problem 19.** Is the profile of a relational structure $R$ with finite signature bounded above by some exponential whenever the age of $R$ is well-quasi-ordered under embeddability?

Some hypothesis (like the boundedness of the signature) is needed but the answer is not known in the case of graphs. Without this hypothesis, one can build examples of wqo hereditary classes of arbitrarily large profiles (a joint result not yet published [164]). The problem above with the hypothesis that $\text{Age}(R)$ is hereditarily wqo was proposed in 2003 [163].

Paper [157] contains an overview, with a particular emphasis on profiles whose generating function is a rational fraction, the Cameron approach, and some problems linking properties of profiles and of rational languages. A famous result (Chomsky-Schützenberger's theorem, see [16]) asserts that the generating series of a regular language is a rational function (see [1]). This result is not far away from our considerations. Indeed, if $A$ is a finite alphabet, with say $k$ letters, and $A^*$ the set of words over $A$, then each word can be viewed as a finite chain coloured by $k$ colors. Hence $A^*$ can be viewed as the age of the relational structure $R$ made of the chain $\mathbb{Q}$ of rational numbers divided into $k$ colors in such a way that, between two distinct rational numbers, all colors appear. As pointed out by Cameron [6], the age algebra $\mathbb{Q}$. $\text{Age}(R)$ is isomorphic to the shuffle algebra

**6.5. The case of graphs and other binary structures.** During the last fifteen years, many results concerning the enumeration of classes of binary relations have appeared. Among them, it is worth noting the results of Albert and Atkinson [2], Balogh *et al.* [12, 8, 9, 11] (see [107, 200] for an overview). These results as well as the recent result by Albert *et al.* [3] proving that the generating series of the profile of a hereditary class of bichains is a rational fraction supports a positive answer to Problem 19 above.

The class of graphs provides interesting examples of profiles.

**Examples 6.16.** In each of the following $G$ is a graph.

(1) $\varphi_G(n) = 1$ for every $n \le |V(G)|$ if and only if $\varphi_G(2) \le 1$, that is, $G$ is a clique or an independent set. (This is trivial.)

(2) $\varphi_G$ is bounded if and only if $G$ is “almost constant” in the Fraïssé’s terminology, that is, there is a finite subset $F_G$ of vertices such that two pairs $\{x, y\}$ and $\{x', y'\}$ of vertices having the same intersection on $F_G$ are both edges or both non-edges.

(3) If $G$ is the direct sum of infinitely many edges, or the direct sum $K_\omega \oplus K_{\omega'}$ of two infinite cliques, then $\varphi_G(n) = \lfloor \frac{n}{2} \rfloor + 1$ and $\mathcal{H}_{\varphi_G} = \frac{1}{(1-x)(1-x^2)}$.

(4) Let $G$ be the direct sum $K_{(1,\omega)} \oplus \bar{K}_{\omega}$ of an infinite wheel and an infinite independent set, or the direct sum $K_{\omega} \oplus \bar{K}_{\omega}$ of an infinite clique and an infinite independent set. Then $\varphi_G(n) = n$. Hence, $\mathcal{H}_{\varphi_G} = 1 + \frac{x}{(1-x)^2} = \frac{1+x^3}{(1-x)(1-x^2)}$.

(5) Let $G$ be the direct sum of infinitely many $k$-element cliques or the direct sum of $k$ infinite cliques. Then $\varphi_G(n) = p_k(n) \approx \frac{n^{k-1}}{(k-1)!k!}$ and $\mathcal{H}_{\varphi_G} = \frac{1}{(1-x)\cdots(1-x^k)}$.

(6) If $G$ is either the direct sum of infinitely many infinite cliques, or an infinite path, then $\varphi_G(n) = p(n)$, the partition function.

(7) Let $C := (E, \le)$ be a chain and $K_{C, \frac{1}{2}}$ be the graph whose vertex set is $2 \times E$ and whose edge set is $\{(0, i), (1, j)\} : i < j \text{ in } C\}$. Such a graph is an *half-complete bipartite graph*. If $C$ is infinite, then $2^{n-2} \le \varphi_{K_{C, \frac{1}{2}}}(n) \le 2^{n-1}$ [126], hence its growth is exponential. In fact, one can check that: $\mathcal{H}_{K_{C, \frac{1}{2}}} = \frac{1-2x-x^2+3x^3-x^4}{(1-x)(1-2x)(1-2x^2)} = 1+x+2x^2+3x^3+6x^4+10x^5+20x^6+36x^7+72x^8+136x^9+O(x^{10})$.
(8) Let $\tilde{K}_{C, \frac{1}{2}}$ be the graph obtained from $K_{C, \frac{1}{2}}$ by adding all possible edges between vertices of the form $(1, i)$, for $i \in E$. Then $\varphi_{\tilde{K}_{C, \frac{1}{2}}}(n) = 2^{n-1}$.

Cellular graphs introduced in Subsection 5.4.2 enter in the picture.

**Theorem 6.17.** [157] (Theorem 2.14 p. 246) The profile of a graph is bounded by a polynomial if and only if this graph is cellular.

A straightforward computation shows that the profile of a cellular graph is bounded by a polynomial. The converse follows directly from Theorem 6.6 ensuring that a graph whose profile is bounded by a polynomial must be almost multichainable and from Lemma 6.18 below (see Lemma 2.15 p.246 in [157] for a proof).

**Lemma 6.18.** The growth of the profile of an almost multichainable graph which is not cellular is at least exponential.

A more precise result was obtained by Balogh, Bollobás, Saks and Sós [12].

**Theorem 6.19.** If $G$ is an undirected graph then either $\varphi_G$ is a quasi-polynomial of degree $k$, in which case $\varphi_G(n) \approx a \cdot n^k$, or $\varphi_G(n)$ is bounded below by $\mathfrak{p}(n)$, the partition function which counts the number of partitions of the integer $n$.

This improves Macpherson's result [126] asserting that in the latter case of the result above $\varphi_G$ is asymptotically bounded below by any function of the form $\exp(n^{\frac{1}{2}-\varepsilon})$ with $\varepsilon > 0$.

For ordered graphs the situation is a bit different. Balogh, Bollobás and Morris [9] proved that if $\mathcal{C}$ is a hereditary class of finite ordered graphs then its profile $\varphi_{\mathcal{C}}$ is either polynomial or is ranked by the Fibonacci functions (see Klazar [107] for recent developments). Using the notion of monomorphic decomposition, Oudrar [141] proves that the class $\mathcal{S}$ of ordered binary structures which do not have a finite monomorphic decomposition has a finite basis (a subset $\mathfrak{B}$ such that every member of $\mathcal{S}$ embeds some member of $\mathfrak{B}$). In the case of ordered reflexive directed graphs, the basis has 1242 members and the profile of their ages grows at least as fast as the Fibonacci function. From this, Oudrar gets a dichotomy result, recently extended to ordered relational structures [144]. We conclude this section by mentioning that a new parameter, *twin width*, has been introduced and linked to the growth rate of the profile of ordered graphs; see, for instance, [19, 86].

# 7. THE NUMBER OF WQO HEREDITARY CLASSES OF FINITE STRUCTURES

Due to Corollary 3.11, the number of wqo hereditary classes of finite structures is the number of wqo ages. As mentioned in Corollary 2.24, if the maximum of the signature is 1 and the number of unary symbols is finite, then $\Omega_\mu$ is wqo. Hence all ages included in $\Omega_\mu$ are wqo and there are only countably many. The situation is radically different if the maximum of the arity is at least 2. First, $\Omega_\mu$ is not wqo and next, the number of ages has the cardinality of the continuum (see Lemmas 2.21 and 2.23). I show below that there are $2^{\aleph_0}$ wqo ages.

## 7.1. The number of wqo ages of binary relations.

**Theorem 7.1.** There are $2^{\aleph_0}$ wqo ages of binary relations.

This result (in a slightly different form) is in [149] with a proof in [169]. It is far from being immediate. It goes through a coding of binary structures by a particular kind of infinite words on $\{0,1\}$, the so-called *uniformly recurrent words*. These binary structures and their encoding are simple to define, and are given below. After that, we will define another encoding leading to graphs.

To each infinite word $\mu := (u_n)_{n \in \mathbb{N}}$ on 0 and 1 let us associate the binary structure $R_\mu := (\mathbb{N}, \rho_\mu)$ where $\rho_\mu := \{(n, n+1) : n \in \mathbb{N}\} \cup \{(n, n) : \mu(n) = 1\}$. Hence, $R_u$ is a directed path with some loops. Let us also associate the set $\text{Fac}(\mu)$ of finite factors of $\mu$ and order it via the factor ordering. It is immediate to see that if $\mu$ and $\mu'$ are two infinite words then

$$ (7.1) \qquad \text{Fac}(\mu) \subseteq \text{Fac}(\mu') \text{ if and only if } \text{Age}(R_\mu) \subseteq \text{Age}(R_{\mu'}). $$
The words we choose are the uniformly recurrent words which appear in symbolic dynamics. Let us give the definition first: an infinite word $\mu$ on $\{0,1\}$ is uniformly recurrent if for every nonnegative integer $n$ there is some nonnegative integer $m$ such that each factor of $\mu$ of length $n$ is a factor of every factor of $\mu$ of length $m$. There are plenty of examples. For instance, consider Sturmian words: infinite words $u$ such that for each nonnegative integer, the number $\text{Fac}_n(\mu)$ of factors of $\mu$ with length $n$ is $n+1$. These words can be obtained as billiard words or rotation words. Two Sturmian words may have the same set of factors, but there are $2^{\aleph_0}$ Sturmian words, no two of which have the same set of finite factors. As an example, take the Sturmian words with different slopes $\alpha \in ]0,1[$, where the slope is the limit as $n$ goes to infinity of the proportion of 1's in factors of length $n$ (see Fogg [68], Chapter 6).

Since there are $2^{\aleph_0}$ uniformly recurrent words with distinct sets of finite factors, Theorem 7.1 follows from the following lemma.

**Lemma 7.2.** For every uniformly recurrent word $\mu$, $\text{Age}(R_\mu)$ is wqo.

The proof is based on two facts:

(a) $\text{Fac}(\mu)$ is a Jónsson poset, hence is wqo, whenever $\mu$ is uniformly recurrent;

(b) $\text{Age}(R_\mu)$ is the image by an order preserving map of the set $\text{Fac}(\mu)^*$ of finite words over $\text{Fac}(\mu)$ viewed as an alphabet, hence, by Higman's theorem, is wqo.

Here are some details.

Let us say that a subset $\mathfrak{J}$ of the set of finite words on $\{0,1\}$ is inexhaustible if it is not reduced to the empty word and if for every $v \in \mathfrak{J}$ there is some word $w$ such that $vwv \in \mathfrak{J}$. A word $\mu$ is recurrent if is not the empty word and every finite factor occurs infinitely often; this amounts to the fact that $\text{Fac}(\mu)$ is inexhaustible. We will use the following result, cf. Theorem 5 of [169].

**Theorem 7.3.** Let $\mu$ be an infinite word on $\{0,1\}$ with domain $\mathbb{N}$. Then, the following properties are equivalent:

(i) $\mu$ is uniformly recurrent;

(ii) $\mu$ is recurrent and $\text{Fac}(\mu)$ is wqo;

(iii) $\text{Fac}(\mu)$ equipped with the factor ordering is a countable Jónsson poset.

The equivalence between (i) and (iii) follows from the equivalence between (i) and (iii) of Theorem 5.2. Implication (ii) $\Rightarrow$ (iii) is detailed in [169].

Fact (a) is contained in Theorem 7.3. For the proof of (b), let $\mu$ be a uniformly recurrent word with domain $\mathbb{N}$ and $F$ be a finite subset of $\mathbb{N}$. This set is a finite union of disjoint intervals of $\mathbb{N}$, say $F_0, \dots, F_m$, two consecutive intervals $F_i, F_{i+1}$ being separated by at least some $a_i \in \mathbb{N}$. To each $F_i$, one may associate the word $v_i$ corresponding to the restriction of $u$ to the interval $F_i$ and to $F$ the finite sequence $S_F$ of finite words $v_0, \dots, v_m$, each $v_i$ being the restriction of $\mu$ to $F_i$. Since the collection of finite factors of $\mu$ is wqo for the factor ordering, Higman's theorem on words (Theorem 3.18) says that the collection of words over the alphabet $\text{Fac}(\mu)$, thus the collection of words of the form $S_F$, is wqo. Since, as it is easy to check, $S_F \le S_{F'}$ implies that $R_\mu \upharpoonright F$ embeds in $R_\mu \upharpoonright F'$, one gets that $\text{Age} R_\mu$ is wqo.

One may refine Theorem 7.1 as follows.

**Proposition 7.4.** There is a hereditary class of finite relational structures $\mathfrak{C}$ such that $\text{Id}(\mathfrak{C})$ has the cardinality of the continuum and every member of $\text{Id}(\mathfrak{C})$ is wqo (and in fact bqo).

**Proof.** Let $\mu$ be a uniformly recurrent word which is non periodic and let $F$ be the set of words $\mu'$ which have the same set of finite factors as $\mu$. For each $s \in F$, let $C_s := (\mathbb{N}, \rho_\mu, \bar{0})$ be the structure made of the binary relation $\rho_\mu$ on $\mathbb{N}$ defined by $\rho_\mu(n, m) = 1$ if either $m = n+1$ or $m = n$ and $\mu(n) = 1$, and $\bar{0}$ is the unary relation so that $\bar{0}(n) = 1$ if and only if $n = 0$. Let $\mathfrak{C} := \bigcup_{s \in F} \text{Age}(C_s)$. Then $\text{Id}(\mathfrak{C}) = \bigcup_{s \in F} \text{Id}(\text{Age}(C_s))$. Since $\mu$ is uniformly recurrent and is not periodic, $F$ has the cardinality of the continuum. Furthermore, each $\text{Age}(C_s)$ is bqo. $\square$

The graphs constructed above are directed with loops. One may replace them by undirected graphs, with loops, see the proof in [169]. But to get rid of loops, another construction is needed.
**7.2. The number of wqo ages of graphs.** To a word $\mu$ let us associate the graph $G_\mu$ whose vertex set $V(G_\mu)$ is $\{-1, 0, \dots, n-1\}$ if the domain of $\mu$ is $\{0, \dots, n-1\}$, $\{-1\} \cup \mathbb{N}$ if the domain of $\mu$ is $\mathbb{N}$, and $\mathbb{N}^*$ or $\mathbb{Z}$ if the domain of $\mu$ is $\mathbb{N}^*$ or $\mathbb{Z}$. For two vertices $i, j$ with $i < j$ we let $\{i, j\}$ be an edge of $G_\mu$ if and only if

$$ \mu_j = 1 \text{ and } j = i + 1, \text{ or} $$

$$ \mu_j = 0 \text{ and } j \neq i + 1. $$

For instance, if $\mu$ is the word defined on $\mathbb{N}$ by setting $\mu_i = 1$ for all $i \in \mathbb{N}$, then $G_\mu$ is the infinite one way path on $\{-1\} \cup \mathbb{N}$. Note that if $\mu'$ is the word defined on $\mathbb{N}$ by setting $\mu'_i = 1$ for all $i \in \mathbb{N} \setminus \{1\}$ and $\mu'_1 = 0$, then $G_{\mu'}$ is also the infinite one way path. In particular, the graphs $G_\mu$ and $G_{\mu'}$ have the same age but $\mu$ and $\mu'$ do not have the same sets of finite factors.

<figure><img src="image_4.png" /><figcaption>FIGURE 2. 0-1 words of length two and their corresponding graphs.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 3. Two distinct 0-1 sequences with isomorphic corresponding graphs.</figcaption></figure>

This correspondence between 0-1 words and graphs was considered in [189], (cf. Chapitre II, "Une classification des ages par la hauteur", page 19), and also in [190].

The notion of primality plays a crucial role in the study of the graphs associated to words.

We first note that all 0-1-graphs $G_\mu$ on $\mathbb{N}$, except four, are prime.

**Proposition 7.5.** If $\mu$ is a word with domain $\mathbb{N}$ then $G_\mu$ is prime if and only if $\mu \notin \{011111\dots, 100000\dots, 0011111\dots, 1100000\dots\}$. In particular, if $\mu$ is a recurrent then $G_\mu$ is prime.

An abstract characterization is the following:

**Lemma 7.6.** For a word $\mu$ with domain $\mathbb{N}$, $G_\mu$ is prime if and only if $\text{pr}(\mu) := \{n \in \mathbb{N} : G_{\upharpoonright[-1,0,...,n[} \text{ is prime}\}$ is cofinal in $\mathbb{N}$.

For a word $\mu$, let $l(\mu)$ be the supremum of the length of factors of $\mu$ made of 1 or of 0. Note that $l(\mu)$ is finite if $\mu$ is uniformly recurrent and nonconstant.

I list below some properties we will use, see [143]:

**Lemma 7.7.** (a) Let $\mu$ be a word and $F$ be a subset of its domain such that $G_\mu \upharpoonright F$ is prime. Then $F \setminus \{\min(F)\}$ is an interval of its domain.

(b) Let $w$ be a word of length $m$. If $m > l(w) + 4$ then the graph $G_w$ is prime.

(c) If $\mu$ is recurrent and $u \in \text{Fac}(\mu)$, then there exists $v \in \{0, 1\}^*$ such that $|v| \ge 4$, $vu \in \text{Fac}(\mu)$ and $G_{vu}$ is prime.

(d) Suppose that $\mu$ is recurrent and $l(\mu) \le 3$. Let $u, v$ be finite words such that $|v| \ge 3$ and $n > l(\mu) + 4$ and $G_{vu}$ is prime. If $G_{vu}$ embeds into $G_\mu$, then $u \in \text{Fac}(\mu)$.

(e) Let $w := w_1 \dots w_n$ be any finite word. If $G_{0^4w}$, resp., $G_{1^4w}$ embeds into $G_\mu$, then $0w$, resp., $1w$, is a factor of $\mu$.
In general, it is not true that two words with different sets of finite factors give different ages of graphs. But, as proved in [143]:

**Theorem 7.8.** Let $\mu$ and $\mu'$ be two words. If $\mu$ is recurrent and $\text{Age}(G_\mu) \subseteq \text{Age}(G_{\mu'})$, then $\text{Fac}(\mu) \subseteq \text{Fac}(\mu')$.

**Proof.** Let $u \in \text{Fac}(\mu)$. We prove that $u \in \text{Fac}(\mu')$. Apply Item (c) of Lemma 7.7 and get some $v \in \{0, 1\}^*$ with $|v| \ge 4$ such that $vu \in \text{Fac}(\mu)$ and $G_{vu}$ is prime. Since $G_{vu} \in \text{Age}(G_\mu) \subseteq \text{Age} G_{\mu'}$, $G_{vu}$ embeds in $G_w$ for some $w \in \mu'$. If $l(\mu) < 4$ then it follows from Item (d) that $u$ is a factor of $w$. If $l(\mu) \ge 4$ then there is $u' \in \text{Fac}(\mu)$ such that $u$ is a factor of $u'$ and either $0^4 u'$ or $1^4 u'$ is a factor of $\mu$. It follows from Item (e) that $u'$ is a factor of $w$, and so is $u$. Hence, $u \in \text{Fac}(\mu')$. $\square$

With the fact that there are $2^{\aleph_0}$ 0-1 recurrent words with distinct sets of factors, one obtains that there are $2^{\aleph_0}$ ages of the form $\text{Age}(G_\mu)$. Those ages are not necessarily wqo. To obtain wqo ages, it suffices to consider graphs associated to uniformly recurrent sequences.

This correspondence above between words and graphs appeared also in [205] and then in [40], the resulting graphs being called *chain graphs*. It was pointed out to us by Brignall [23] that chain graphs are the same objects as *pin sequences* (see [22] Subsection 2.6. p.41). In [143] the following was proved:

**Theorem 7.9.** For every 0-1 word $\mu$ the age $\text{Age}(G_\mu)$ consists of permutation graphs.

By considering uniformly recurrent words, one gets that

**Corollary 7.10.** There are $2^{\aleph_0}$ distinct wqo ages, each consisting of permutation graphs.

The ages that we have constructed are not only distinct but they are in fact incomparable under set inclusion. They fit in a category presented in the next subsection.

### 7.3. Primality and minimality.
The notions of primality and minimality are linked in two ways.

**Definition 7.11.** A binary relational structure $R$ is *minimal prime* if $R$ is prime and $R$ embeds in every induced prime substructure with the same cardinality.

**Definition 7.12.** A hereditary class $\mathcal{C}$ made of binary structures is *minimal prime* if it contains infinitely many prime structures, while every proper hereditary subclass contains only finitely many prime structures.

The first notion appears in [168], the second notion appears in the thesis of Oudrar [140] (see Theorem 5.12, p. 96, and Theorem 5.15, p. 98 of [140]) Several examples of minimal prime graphs and posets are given in [168]. We give below several properties of minimal prime structures and minimal prime classes. A full description of minimal prime hereditary classes of graphs is given in Subsection 7.4.

The relevance of the notion of minimal prime classes with the counting of wqo hereditary classes discussed in the previous section is due to the fact these classes are wqo (Theorem 7.14) and that due to their definition these classes are pairwise incomparable with respect to set inclusion.

We begin with some general properties of minimal prime hereditary classes. Denote by $\text{Prim}_\mu$ the class of finite binary structures of signature $\mu$ which are prime. Set $\text{Prim}(\mathcal{C}) := \text{Prim}_\mu \cap \mathcal{C}$ for every $\mathcal{C} \subseteq \Omega_\mu$. Say that a subclass $\mathcal{D}$ of $\text{Prim}_\mu$ is *hereditary* if it contains every member of $\text{Prim}_\mu$ that can be embedded into some member of $\mathcal{D}$.

These minimal prime classes satisfy the following properties (cf. Théorème 5.14, p.97, [140]):

**Theorem 7.13.** A hereditary class $\mathcal{C}$ of $\Omega_\mu$ is minimal prime if and only if $\text{Prim}(\mathcal{C})$ is a Jónsson poset which is cofinal in $\mathcal{C}$.

**Theorem 7.14.** A hereditary class of finite binary structures which contains infinitely many prime structures contains a minimal prime hereditary subclass, provided that the structures have a finite signature.

Theorem 7.13 is a translation of the definition of minimal prime class. However, in Theorem 7.14, a condition, like the one on the signature, is needed. A proof of Theorem 7.14 relies on the following lemma.
**Lemma 7.15.** If $\mu$ is finite then $\text{Prim}_\mu$ is level-finite.

**Proof.** Suppose for a contradiction that there exists an integer $n \ge 0$ such that the level $\text{Prim}_\mu(n)$ of $\text{Prim}_\mu$ is infinite and choose $n$ smallest with this property. Define

$$ \mathcal{C} := \{R \in \Omega_\mu : R < S \text{ for some } S \in \text{Prim}_\mu(n)\}. $$

Then $\mathcal{C}$ is a hereditary class of $\Omega_\mu$ containing only finitely many prime structures. According to (2) of Theorem 3.23, $\mathcal{C}$ has only finitely many bounds. This is not possible since the elements of $\text{Prim}_\mu(n)$ are bounds of $\mathcal{C}$. $\square$

**Proof of Theorem 7.14.** Let $\mathcal{C}$ be a hereditary class of $\Omega_\mu$ such that $\mathfrak{J} := \text{Prim}_\mu(\mathcal{C})$ is infinite. Since $\text{Prim}_\mu$ is level-finite, Lemma 5.3 ensures that $\mathfrak{J}$ contains an initial segment $\mathfrak{D}$ which is Jónsson. According to Theorem 7.13, $\downarrow \mathfrak{D}$ is minimal prime. This completes the proof. $\square$

The following result gathers the main properties we know about minimal prime structures.

**Theorem 7.16.** Every minimal prime hereditary class $\mathcal{C}$ is the age of some prime structure. Furthermore, if the signature is finite, this age is wqo. If it is exhaustible then it is hereditarily wqo and hence almost inexhaustible.

The first and second part form Theorem 19 of [143]. The third part is Lemma 23 and Theorem 20 of [143]. We give a proof.

**Proof of the first and second part of Theorem 7.16.** Let $\mathcal{C}$ be a minimal prime hereditary class. We first prove that it is the age of a prime structure. It follows from Theorem 7.13 that $\mathcal{C} = \downarrow \mathfrak{D}$ where $\mathfrak{D}$ is Jónsson. Since $\mathfrak{D}$ is Jónsson, it is up-directed. Thus $\mathcal{C}$ is an age. Since $\mathfrak{D}$ is up-directed and countable, it contains a cofinal sequence $R_0 \le R_1 \le \dots < R_n \le \dots$. We may define the limit $R$ of these $R_n$. Since the $R_n$'s are prime, $R$ is prime and $\text{Age}(R) = \mathcal{C}$.

Next we prove that $\mathcal{C}$ is wqo. Since $\mathfrak{D}$ is Jónsson, it is wqo. To prove that $\mathcal{C}$ is wqo, let $R \in \mathcal{C}$, consider $\mathcal{C} \setminus (\uparrow \{R\})$, and observe that it is enough to prove that $\mathcal{C} \setminus (\uparrow \{R\})$ is wqo by embeddability. Indeed, an antichain that contains $R$ must be in $\mathcal{C} \setminus (\uparrow \{R\})$. Now to prove that $\mathcal{C} \setminus (\uparrow \{R\})$ is wqo, we note that since $\mathcal{C} \setminus (\uparrow \{R\})$ is a proper hereditary class in $\mathcal{C}$, it contains only finitely many primes. It follows from Theorem 3.23 that $\mathcal{C} \setminus (\uparrow \{R\})$ is wqo. $\square$

For the proof of the third part, let $\mathcal{C}$ be a class of finite binary structures $S := (F, (\rho_i)_{i \in I})$ with $F$ finite and a given finite signature $\mu$. Denote by $\mathcal{C}^{+1}$ the class of $S := (F, (\rho_i)_{i \in I})$ such that there is some $a \in F$ such that $S_{\downarrow F \setminus \{a\}} \in \mathcal{C}$.

The following lemma is Proposition 5.32 p. 105 of [140] and Theorem 4.5 page 20 of [25]. A similar fact, but not explicit, appears in the proof of Theorem 4.24, p. 267 of [157]. For the reader's convenience, we give a proof.

**Lemma 7.17.** Let $\mathcal{C}$ be a hereditary class of binary structures with a finite signature. If the members of $\mathcal{C}$ are not necessarily finite and if these members when labelled by any better-quasi-order form a well-quasi-order, then $\mathcal{C}^{+1}$ has the same property. If $\mathcal{C}$ is made of finite structures and is hereditarily well-quasi-ordered, then $\mathcal{C}^{+1}$ is hereditarily well-quasi-ordered.

**Proof.** Let $I$ be such that each $S \in \mathcal{C}$ is of the form $S := (F, (\rho_i)_{i \in I})$. Let $W$ be a wqo. By hypothesis, the set $(2 \times 2 \times 2)^I$ is finite, hence, it is wqo by equality. The direct product $W' = W \times (2 \times 2 \times 2)^I$ is wqo. We encode the members of $\mathcal{C}^{+1}$ labelled by $W$, by members of $\mathcal{C}$ labelled by $W'$. Indeed, for each $S := (F, (\rho_i)_{i \in I}) \in \mathcal{C}^{+1}$ we select $a \in F$ such that $S_{\downarrow F \setminus \{a\}} \in \mathcal{C}$ and we label $S_{\downarrow F \setminus \{a\}}$ by the map $g_a$ defined for $x \in F \setminus \{a\}$ by $g_a(x) := (\rho_i(a, x), \rho_i(x, a), \rho_i(a, a))_{i \in I}$. Now if $f$ is a labelling of $F$ in $W$, we associate the labelling $f'$ of $F \setminus \{a\}$ by setting $f' := (f_{\downarrow F \setminus \{a\}}, g_a)$. By construction, if $S, S' \in \mathcal{C}$, an embedding $h$ from the labelled structure $S_{\downarrow F \setminus \{a\}}$ in the labelled structure $S'_{\downarrow F' \setminus \{a'\}}$ will extend to an embedding of the labelled structure $S$ in the labelled structure $S'$ with $a$ mapped to $a'$. The conclusion follows. $\square$
We deduce:

**Corollary 7.18.** Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure made of finitely many binary relations and let $a \in V$. If $\text{Age}(R_{\upharpoonright V \setminus \{a\}})$ is hereditarily well-quasi-ordered, then $\text{Age}(R)$ is hereditarily well-quasi-ordered.

**Proof.** If $a \notin \ker(R)$, there is nothing to prove. If $a \in \ker(R)$, we set $\mathcal{C} := \text{Age}(R_{\upharpoonright V \setminus \{a\}})$. We observe that $\text{Age}(R) \subseteq \mathcal{C}^+$ and we apply Lemma 7.17. $\square$

**Proof of the third part of Theorem 7.16.** Let $\mathcal{C}$ be a minimal prime hereditary class and $R$ be such that $\text{Age}(R) = \mathcal{C}$. Suppose that $\ker(R)$ is nonempty. Let $a \in \ker(R)$. Then $\text{Age}(R_{\upharpoonright V \setminus \{a\}}) \neq \text{Age}(R) = \mathcal{C}$. Since $\mathcal{C}$ is minimal prime, $\text{Age}(R_{\upharpoonright V \setminus \{a\}})$ contains only finitely many primes. Theorem 4.13 asserts that $\text{Age}(R_{\upharpoonright V \setminus \{a\}})$ is hereditarily wqo Corollary 7.18 asserts that $\text{Age}(R)$ is hereditarily wqo. Corollary 4.5 asserts that $\ker(R)$ is finite. With that the proof is complete. $\square$

Since each hereditary well-quasi-ordered class has finitely many bounds (Theorem 4.10) we have only countably many exhaustible minimal prime classes.

**Corollary 7.19.** If the signature is finite, there are at most countably many minimal prime classes $\mathcal{C}$ such that $\mathcal{C}$ is exhaustible.

As mentioned in Subsection 3.4, it is not known if a hereditary class of finite graphs which is wqo is bqo.

**Problem 20.**

(1) Is every minimal prime hereditary class of finite binary structures bqo?

(2) Is it true that $|\ker(\mathcal{R})| \le 2$ if $\text{Age}(R)$ minimal prime?

(3) Is the number of exhaustible minimal prime ages finite?

(4) Is it true that the age of a minimal prime binary structure is necessarily minimal prime?

As we will see, the answers to (2), (3), (4) are positive if one considers minimal prime classes of graphs. In this case, there are only five examples with a nonempty kernel. Even in the case of graphs we do not know the answer to (4). The converse is false in the sense that there are minimal prime ages of graphs such that no graph with that age is minimal prime.

We prove:

**Theorem 7.20.** If $\mathcal{C}$ is minimal prime and exhaustible, then every binary prime structure $R$ with $\text{Age}(R) = \mathcal{C}$ embeds a minimal prime structure.

The proof relies on a result of Delhommé and McKay, Theorem 8.2, presented in Section 8 and Lemma 7.17. We first prove the following result.

**Lemma 7.21.** If $\mathcal{C}$ is minimal prime and exhaustible then $\mathcal{C}^{\le \omega}$ is well-quasi-ordered.

**Proof.** Let $R$ with $\text{Age}(R) = \mathcal{C}$. Pick $a \in \ker(R)$. Let $\mathfrak{D} := \text{Age}(R_{\upharpoonright V(R) \setminus \{a\}})$. This age contains only finitely many primes. From Theorem 8.2, $\mathfrak{D}^{\le \omega}$ is well-quasi-ordered. Furthermore, members of $\mathfrak{D}^{\le \omega}$ when labelled by any finite set form a well-quasi-ordered set. According to Lemma 7.17, $(\mathfrak{D}^{\le \omega})^{+1}$ has the same property. Next, $\mathcal{C}^{\le \omega} \subseteq (\mathfrak{D}^{\le \omega})^{+1}$. Indeed, every member of $\mathcal{C}^{\le \omega}$ has a copy $R'$ in a countable extension $R''$ of $R$ having the same age as $R$, therefore, $\text{Age}(R'_{\upharpoonright V(R') \setminus \{a\}}) \subseteq \mathcal{C}$. Hence, $\mathcal{C}^{\le \omega}$ is well-quasi-ordered. $\square$

We now prove the following result.

**Lemma 7.22.** Let $\mathcal{C}$ be a hereditary class of $\Omega_{\mu}$. If $\mathcal{C}^{\le \omega}$ is well-founded then every prime member of $\mathcal{C}^{\le \omega}$, if any, embeds a minimal one.

**Proof of Theorem 7.20.** Let $R$ be a prime structure with $\text{Age}(R) = \mathcal{C}$. According to Lemma 7.21, $\mathcal{C}^{\le \omega}$ is well-quasi-ordered. According to Lemma 7.22, $R$ embeds a minimal prime member. $\square$
**7.4. Minimal prime ages of graphs.** We now give a complete description of minimal prime ages of graphs. It is based on a description by Chudnovsky et al. [40] of unavoidable prime graphs in large finite prime graphs (see also Malliaris and Terry [130]). Our result is based on our study of graphs associated to 0-1 sequences.

**Theorem 7.23.** Let $\mu$ be a 0-1 sequence on $\mathbb{N}$. The following statements are equivalent.

(i) $\mu$ is uniformly recurrent.

(ii) $\mu$ is recurrent and $\text{Age}(G_\mu)$ is minimal prime.

**Proof.** (i) $\Rightarrow$ (ii). Let $\mu$ be a uniformly recurrent word. If $\mu$ is constant, (ii) holds trivially. So we may suppose $\mu$ not constant, hence $l(\mu)$ is finite. Trivially, $\mu$ is recurrent. Hence, by Proposition 7.5, $G_\mu$ is prime. Hence, from Theorem 3.22 it follows that the set of prime graphs in $\text{Age}(G_\mu)$ is cofinal in $\text{Age}(G_\mu)$ hence infinite. Now, let $\mathcal{C}$ be a hereditary subclass of $\text{Age}(G_\mu)$ containing infinitely many prime graphs. We prove that $\mathcal{C} = \text{Age}(G_\mu)$. For that, we claim that $\mathcal{C}$ contains infinitely many primes of the form $G_w$. Since $\mu$ is uniformly recurrent, all $G_w$'s for $w \in \text{Fac}(\mu)$ belong to $\mathcal{C}$, from which the equality $\mathcal{C} = \text{Age}(G_\mu)$ follows. For the claim, note that by (a) of Lemma 7.7 if $G_\mu \upharpoonright F$ is a finite $m+1$-element prime subgraph of $G$, then $F \setminus \{\min F\}$ is an interval of $\mathbb{N}$, and by (c) of Lemma 7.7, if $m > l(\mu) + 4$, $G_{\mu \upharpoonright F \setminus \{\min F\}}$ is prime.

(ii) $\Rightarrow$ (i). If $\mu$ is constant, $\mu$ is uniformly periodic. So, we may suppose that $\mu$ is nonconstant. In this case, $l(\mu)$ is bounded. Otherwise, $\text{Fac}(0)$ or $\text{Fac}(1)$ (where 0 and 1 denote the constant words on $\mathbb{N}$) is included in $\text{Fac}(\mu)$, hence $\text{Age}(G_0)$ or $\text{Age}(G_1)$ is included in $\text{Age}(G_\mu)$. Since $\text{Age}(G_\mu)$ is minimal prime, it is equal to one of these ages, amounting to the fact that $\mu$ is constant. This is a contradiction.

We now prove that $\text{Fac}(\mu)$ is Jónsson and we apply Theorem 7.3. First, $\text{Fac}(\mu)$ is infinite since $\mu$ is recurrent. Next, let $X$ be an infinite initial segment of $\text{Fac}(\mu)$. We prove that $X = \text{Fac}(\mu)$. Since $l(\mu)$ is finite, we may apply Item (b) of Lemma 7.7. It yields that the set $X' := \{u \in X : G_u$ is prime$\}$ is infinite. Since $\text{Age}(G_\mu)$ is minimal prime, the set $G_X := \{G_u : u \in X'\}$ is cofinal in $\text{Age}(G_\mu)$, that is, $\downarrow G_X = \text{Age}(G_\mu)$. Let $u \in \text{Fac}(\mu)$. According to Item (c) of Lemma 7.7, since $\mu$ is recurrent and $u \in \text{Fac}(\mu)$ there is some $v \in \{0,1\}^*$ with $|v| \ge 3$ such that $vu \in \text{Fac}(\mu)$ and $G_{vu}$ is prime. Since $G_{vu} \in \text{Age}(G_\mu) \subseteq \downarrow G_X$, $G_{vu}$ embeds in $G_w$ for some $w \in X$. If $l(\mu) < 4$, it follows from (d) of Lemma 7.7, that $u$ is a factor of $w$. If $l(\mu) \ge 4$, then there is $u' \in \text{Fac}(\mu)$ such that $u$ is a factor of $u'$ and either $0^4 u'$ or $1^4 u'$ is a factor of $\mu$. It follows from Item (e) of Lemma 7.7 applied to either $v = 0^4$ or $v = 1^4$, that $u'$ is a factor of $w$, and so is $u$. Hence, $u \in X$ as required. $\square$

There are other minimal prime ages of graphs than those described in Theorem 7.23 above. But there are only eleven such ages.

Let $\mathcal{M}$ be the graphs $G_0, G_1, G_3, G_4, G_5$ and $G_6$ depicted in Figures 4 and 5. Let $\tilde{\mathcal{M}}$ be the list of these graphs and their complements. Let $\mathcal{L}$ be the set of the ages of these graphs and of their complements. It should be noted that the graphs $G_5, G_5^{\text{comp}}$ have the same age, hence $\mathcal{L}$ has eleven members.

**Proposition 7.24.** *Members of $\mathcal{M}$ and their complements are almost multichainable and minimal prime. Members of $\mathcal{L}$ are distinct and minimal prime, five of them are exhaustible.*

**Proof.** An inspection of the six members of $\mathcal{M}$ shows that $G_0, G_1$ and $G_4$ are multichainable with an empty kernel, the three others are almost multichainable with a one-element kernel, in the case of $G_3$ and $G_5$, and a two-element kernel in the case of $G_6$. This gives three exhaustible ages; with the ages of their complements added (and since $G_5$ and its complement $G_5^{\text{comp}}$ have the same age) this gives five exhaustible ages. The fact that these graphs are minimal prime is given in [168]. The second part of the theorem, notably the fact that the ages are distinct and minimal prime is detailed in Oudrar's thesis [140], Chapter 6, p. 109. $\square$

We conclude with the following result:

**Theorem 7.25.** *A hereditary class $\mathcal{C}$ of finite graphs is minimal prime if and only if $\mathcal{C} = \text{Age}(G_\mu)$ for some uniformly recurrent word $\mu$ on $\mathbb{N}$, or $\mathcal{C} \in \mathcal{L}$.*
<figure><img src="image_6.png" /><figcaption>FIGURE 4.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 5.</figcaption></figure>

We have seen with Theorem 7.23 and Proposition 7.24 that the ages in $\mathcal{L}$ are minimal prime. The converse is based on the theorem of Chudnovsky et al. [40] noted at the beginning of this subsection. One can also use an infinite version due to Malliaris and Terry [130].

In [40], Theorem 1.2, the authors prove that for every integer $n \ge 3$ there is an integer $N$ such that every prime graph with at least $N$ vertices contains one of the following graphs or their complements as an induced subgraph:

(1) the graph obtained from $K_{1,n}$ by subdividing every edge once;

(2) the line graph of $K_{2,n}$;

(3) the line graph of the graph in (1);

(4) the half-graph of height $n$;

(5) a prime graph induced by a chain of length $n$; and,
(6) two particular graphs obtained from the half-graph of height $n$ by making one side a clique and adding one vertex.

With this result, the proof that there are not other minimal prime ages of graphs than those of $\mathcal{L}$ is a simple exercise. Indeed, let $\mathcal{C}$ be a minimal prime age of graphs. Since $\mathcal{C}$ contains infinitely many prime graphs, it contains an infinite set $D$ of prime graphs belonging to one of the six types described in the theorem. Since $\mathcal{C}$ is minimal prime, $\downarrow D = \mathcal{C}$. If $D$ contains infinitely many primes in (1), respectively, in (2), in (3), in (4), then, via an inspection of the ages in $M$ (and in $\mathcal{L}$), $D \subseteq \text{Age}(G_3)$, respectively, $D \subseteq \text{Age}(G_0^{\text{comp}})$, $D \subseteq \text{Age}(G_4)$, $D \subseteq \text{Age}(G_1)$. And, if $D$ contains infinitely many primes in (6), then either $D \subseteq \text{Age}(G_5)$ or $D \subseteq \text{Age}(G_6)$. Since the ages of those $G_i$ are minimal prime then the previous inclusions yield the equality $\mathcal{C} = \text{Age}(G_i)$. The last possibility for $D$ is that $D$ is made of chains, that is, graphs in (5). In that case $\mathcal{C}$ is the age of some $G_\mu$ for $\mu$ uniformly recurrent.

## 8. EXTENSIONS OF LAVER'S THEOREM

Sierpinski [186] proved the existence of an infinite strictly decreasing sequence of subchains of the chain of real numbers. Fraïssé [71] conjectured that there is no infinite strictly decreasing sequence of countable chains and he made several other conjectures about the embeddability between countable chains. The fact that the class of countable chains contains no infinite strictly decreasing sequence and no infinite antichain, that is, the class of countable chains is wqo, was known under the name of Fraïssé's conjecture. This conjecture was positively solved by Laver [118] in 1971, using the Hausdorff decomposition theorem of scattered chains and the theory of better-quasi-ordering, due to Nash-Williams. Laver proved more strongly that the class of chains which are countable unions of scattered chains is bqo, hence wqo under embeddability. For a detailed exposition of Fraïssé's conjectures, bqo and Laver's proof, see Rosenstein's book [179], Chapters 9 and 10.

A consequence of the well-foundedness of the class of countable chains is the fact that every countable chain is a finite lexicographic sum of additively indecomposable chains. (Recall that a chain $\alpha$ is additively indecomposable if for every decomposition $\alpha = \alpha_1 + \alpha_2$ either $\alpha \le \alpha_1$ or $\alpha \le \alpha_2$.) The proof is a typical argument about well-founded sets. Indeed, if the property fails for some chain, there is some minimal chain $\alpha$ for which it fails. Decompose this chain into two parts $\alpha_1$ and $\alpha_2$ such that $\alpha = \alpha_1 + \alpha_2$. If $\alpha_1 < \alpha$ and $\alpha_2 < \alpha$ then, by the minimality of $\alpha$, $\alpha_1$ and $\alpha_2$ are finite sums of additively indecomposable chains and hence $\alpha$ is a finite sum, contradicting the choice of $\alpha$. Hence, either $\alpha \le \alpha_1$ or $\alpha \le \alpha_2$ and thus $\alpha$ is additively indecomposable, again contradicting the choice of $\alpha$. Thus no such $\alpha$ can exist.

Laver also showed that every additively indecomposable scattered chain can be obtained from the chains 0 and 1 by means of regular unbounded sums. (A lexicographical sum $\sum_{\mu<\kappa} \alpha_\mu$ or $\sum_{\mu<\kappa^*} \alpha_\mu$ of scattered types is regular and unbounded if $\kappa$ is an infinite regular ordinal and for every $\mu < \kappa$, the set $\{\nu : \alpha_\mu \le \alpha_\nu\}$ has cardinality $\kappa$). In [119], he gives a description of indivisible scattered chains, called strongly indecomposable in his paper. (Recall that a chain $\alpha$ is indivisible if for each partition of its domain into two parts $A$ and $B$ one of the parts embeds $\alpha$). Fraïssé, [74], p. 249, asked:

**Problem 21.** Which hereditary classes $\mathcal{C}$ of finite structures are such that the class $\overline{\mathcal{C}}^\omega$ (made of countable structures $R$ such that $\text{Age}(R) \subseteq \mathcal{C}$) is wqo?

The bqo character of $\mathcal{C}$ is not enough. Examples of bqo ages $\mathfrak{A}$ for which the collection of countable structures with this given age is not wqo were given in [149]. In fact, there are $2^{\aleph_0}$ bqo ages $\mathfrak{A}$ of graphs such that the class $\overline{\mathfrak{A}}^\omega$ of graphs with age included in $\mathfrak{A}$ is not well-founded. The ages of graphs $G_\alpha$ associated to non-periodic and uniformly recurrent words $\alpha$ in Subsection 7.2 are such structures [143], Remark 6, p. 23.

Here, we give some positive examples. A poset is *series-parallel* (see Subsection 3.3.1) if it does not embed an “$N$”, that is, the 4-element poset $\{a, b, a', b'\}$ with exactly the strict comparabilities $a < a'$, $b < b'$ and $b < a'$.

Thomassé [196] proved:

**Theorem 8.1.** The class of countable series-parallel posets is wqo (and in fact bqo).
An extension to binary structures was obtained independently by Delhommé [51] and McKay [133]:

**Theorem 8.2.** If a hereditary class $\mathfrak{C}$ of finite binary structures of finite arity contains only finitely many indecomposable members then the class of countable structures whose age is included into $\mathfrak{C}$ is bqo.

As for Thomassé's result, the proof relies on a result of Corominas on labelled trees [43] and the extension of Gallai decomposition theory [84] to 2-structures [60], notably the properties of tree-decompositions (see [91], [44]).

**Problems 22.**

(1) If the set $Ind(\mathfrak{C})$ of indecomposable structures contained in a hereditary class $\mathfrak{C}$ of finite binary structures is hereditarily bqo then the class of countable structures whose age is a subclass of $\mathfrak{C}$ is bqo.

(2) If a hereditary class $\mathfrak{C}$ of finite structures, not necessarily binary, is hereditarily bqo then the class of countable structures whose age is a subclass of $\mathfrak{C}$ is bqo (and even hereditarily bqo).

## 9. CONCLUDING REMARKS

We have surveyed several results and problems concerning wqo classes closed under induced substructures. We are forced to note that basic questions asked in the seventies are still unsolved. At least, our knowledge has progressed on some particular classes, like bichains. This could suggest putting some emphasis on ordered structures and particularly ordered graphs. Also, several interesting classes are closed under substructures (that is, via injective homomorphisms). Those made of graphs which are wqo have been characterized by Ding [58]. Does this extend to relational structures?

## REFERENCES

[1] D. Abdi, C. Laflamme, A. Tateno, R. Woodrow, *An example of Tateno disproving conjectures of Bonato-Tardif, Thomassé and Tyomkyn*, arXiv:2205.14679, 29 May 2022, 42 pp.

[2] M.H. Albert and M.D. Atkinson, *Simple permutations and pattern restricted permutations*, Discrete Math. **300** (2005), 1–15.

[3] M. Albert, R. Brignall, N. Ruškuc and V. Vatter, *Rationality for subclasses of 321-avoiding permutations*, European J. Comb. **78** (2019), 44–72.

[4] J-P. Allouche, J. Shallit, *Automatic sequences. Theory, applications, generalizations*, Cambridge University Press, Cambridge, 2003. xvi+571.

[5] R. Assous, M. Pouzet, *Jónsson posets*, Algebra Universalis **79** (2018), Art. 74, 26 pp.

[6] A. Atminas, V. Lozin, *Labelled induced subgraphs and well-quasi-ordering*, Order **32** (2015), 313–328.

[7] L. Babai, *Graph isomorphism in quasipolinomial time*, arXiv:1512.03547, 19 January 2016, 84 pp.

[8] J. Balogh, B. Bollobás and R. Morris, *Hereditary properties of partitions, ordered graphs and ordered hypergraphs*, European J. Comb. **8** (2006), 1263–1281.

[9] J. Balogh, B. Bollobás and R. Morris, *Hereditary properties of ordered graphs*, in Topics in discrete mathematics, 179–213, Algorithms Combin., 26, Springer, Berlin, 2006.

[10] J. Balogh, B. Bollobás, R. Morris, *Hereditary properties of combinatorial structures: posets and oriented graphs*, J. Graph Theory **56** (2007), no. 4, 311–332.

[11] J. Balogh, B. Bollobás and R. Morris, *Hereditary properties of tournaments*, Electron. J. Combin. **14** (2007), no. 1, Research Paper 60, 25 pp.

[12] J. Balogh, B. Bollobás, M. Saks and V. T. Sós, *The unlabelled speed of a hereditary graph property*, J. Combin. Theory Ser B **99** (2009), 9–19.

[13] J. Berstel, C. Reutenauer, *Noncommutative rational series with applications*. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp.

[14] M. Bekkali, M. Pouzet, D. Zhani, *Incidence structures and Stone-Priestley duality*, Ann. Math. Artif. Intell. **49** (2007), 27–38.

[15] C. Berge, *Les problèmes de flot et de tension*, Cah. Cent. Étud. Rech. Opér. **3** (1961), 69–93.

[16] J. Berstel et C. Reutenauer, *Les séries rationnelles et leurs langages*, Études et recherches en Informatique. Masson, Paris (1984) 132pp.

[17] A. Bonato, C. Tardif, *Mutually embeddable graphs and the tree alternative conjecture*, J. Combin. Theory Ser. B **96** (2006), 874–880.

[18] A. Bonato, H. Bruhn, R. Diestel, P. Sprüssel, *Twins of rayless graphs*, J. Combin. Theory Ser. B **101** (2011), 60–65.

[19] E. Bonnet, U. Giocanti, P. Ossona de Mendez, P. Simon, S. Thomassé, S. Toruńczyk, *Twin-width IV:ordered graphs and matrices*, arXiv:2102.03117v3, 5 July 2021, 53 pp.
[20] Y. Boudabbous, M. Pouzet, *The morphology of infinite tournaments; applications to the growth of their profile*, European J. Combin. **31** (2010), 461-481.

[21] S. Braunfeld, M.C. Laskowski, *Counting siblings in universal theories*, arXiv:1910.11230v3, 26 April 2019, 26 pp.

[22] R. Brignall, *Simplicity in relational structures and its application to permutation classes*, PhD Thesis, University of St Andrews, October 25, 2007.

[23] R. Brignall, Private communication, May 20, 2022.

[24] R. Brignall, M. Engen and V. Vatter, *A counterexample regarding labelled well-quasi-ordering*, Graphs Combin. **34** (2018), 1395-1409.

[25] R. Brignall, V. Vatter, *Labelled well-quasi-order for permutation classes*, arXiv:2103.08243, 14 May 2022, 48 pp.

[26] R. Brignall, V. Vatter, *Uncountably many enumerations of well-quasi-ordered permutation classes*, arXiv:2211.12397v2, 15 February 2023, 23 pp.

[27] P.J. Cameron, *Transitivity of permutation groups on unordered sets*, Math. Z. **48** (1976), 127-139.

[28] P.J. Cameron, *Orbits of permutation groups on unordered sets*. J. Lond. Math. Soc. (2) bf 17 (1978), 410-414.

[29] P.J. Cameron, *Orbits of permutation groups on unordered sets. II*. J. Lond. Math. Soc. (2), **23** (1981), 249-264.

[30] P.J. Cameron, *Oligomorphic permutation groups*. Cambridge University Press, Cambridge, 1990.

[31] P.J. Cameron, *The algebra of an age*, In Model theory of groups and automorphism groups (Blaubeuren, 1995), pp. 126-133. Cambridge Univ. Press, Cambridge, 1997.

[32] P.J. Cameron, *Sequences realized by oligomorphic permutation groups*, J. Integer Seq. **3**, Article 00.1.5 (electronic), 2000.

[33] P.J. Cameron, *Some counting problems related to permutation groups*, Formal power series and algebraic combinatorics (Toronto, ON, 1998), Discrete Math. **225** (2000), 77-92.

[34] P.J. Cameron, *On an algebra related to orbit-counting*. J. Group Theory **1** (1998), 173-179.

[35] P.J Cameron, *Homogeneous permutations. Permutation patterns* (Otago, 2003). Electron. J. Combin. **9** (2002/03), no. 2, Research paper 2, 9 pp.

[36] R. Carroy, Y. Pequignot, *From well to better, the space of ideals*, Fund. Math. **227** (2014), 247-270.

[37] I. Chakir, *Chains conditions in algebraic lattices*, Thèse d'État, 11 Mai 2009, Université Mohamed V, Faculté des Sciences, Rabat (Maroc), arXiv: 1609.07167v1, 22 Sept 2016, 94 pp.

[38] I. Chakir, M. Pouzet, *A characterization of well-founded algebraic lattices*, Contrib. Discrete Math. **13** (2018), 35-50.

[39] I. Chakir, M. Pouzet, *Infinite independent sets in distributive lattices*, Algebra Universalis **53** (2005), 211-225.

[40] M. Chudnovsky, R. Kim, S. Oum and P. Seymour, *Unavoidable induced subgraphs in large graphs with no homogeneous sets*. J. Combin. Theory Ser. B **118** (2016), 1-12.

[41] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, *The strong perfect graph theorem*, Ann. of Math. (2) **164** (2006), 51-229.

[42] P.M. Cohn, *Universal algebra*, Second edition. Mathematics and its Applications, 6. D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1981. xv+412 pp.

[43] E. Corominas, *On better-quasi-ordering countable trees*, Discrete Math. **53** (1985), 35-53.

[44] B. Courcelle, C. Delhommé, *The modular decomposition of countable graphs. Definition and construction in monadic second-order logic*, Theoret. Comput. Sci. **394** (2008), 1-38.

[45] P. Damaschke, *Induced subgraphs and well-quasi-ordering*. J. Graph Theory **14** (1990), 427-435.

[46] J. Dammak, G. Lopez, M. Pouzet, H. Si Kaddour, *Hypomorphy of graphs up to complementation*, J. Combin. Theory Ser. B **99** (2009), 84-96.

[47] B. A. Davey, H. A. Priestley, *Introduction to lattices and order*, Second edition, Cambridge University Press, New York, 2002.

[48] G.W. Day, *Superatomic Boolean algebras*, Pacific J. Math., **23** (1967), 479-489.

[49] N.G. de Bruijn, P. Erdös, *A color problem for infinite graphs and a problem in the theory of relations*, Indag. Math., **13** (1951), 371-373.

[50] D.H.J. de Jongh, R. Parikh, *Well-partial orderings and hierarchies*, Nederl. Akad. Wetensch. Proc. Ser. A **80** (Indag. Math. **39**) (1977), 195-207.

[51] C. Delhommé, *Nicely BQO grounded categories and 2-structures*, preprint, 2014.

[52] C. Delhommé, *personnal communication*.

[53] C. Delhommé, C. Laflamme, M. Pouzet, N. Sauer, *Divisibility of countable metric spaces*, European J. Combin. **28** (2007), 1746-1769.

[54] C. Delhommé, C. Laflamme, M. Pouzet, N. Sauer, *Indivisible ultrametric spaces*, Topology Appl. **155** (2008), 1462-1478.

[55] C. Delhommé, M. Pouzet, *Length of an intersection*, Mathematical Logic Quarterly **63** (2017), 243-255.

[56] C. Delhommé, M. Pouzet, N. Sauer, G. Sági, *Representation of ideals of relational structures*, Discrete Math. **309** (2009), 1374-1384.

[57] R. P. Dilworth, *A decomposition theorem for partially ordered sets*, Ann. of Math. (2) **51** (1950), 161-166.

[58] G. Ding, *Subgraphs and well-quasi-ordering*, J. Graph Theory **16** (1992), 489-502.

[59] B. Dushnik and E. W. Miller, *Partially ordered sets*, Amer. J. Math. **63** (1941), 600-610.

[60] A. Ehrenfeucht, T. Harju, G. Rozenberg, *The theory of 2-structures. A framework for decomposition and transformation of graphs*. World Scientific Publishing Co., Inc., River Edge, NJ, 1999.
[61] A. Ehrenfeucht, G. Rozenberg, *Theory of 2-structures. I. Clans, basic subclasssses, and morphisms*, Theoret. Comput. Sci. **70** (1990), 277-303.

[62] A. Ehrenfeucht, G. Rozenberg, *Theory of 2-structures, II. Representation through labeled tree families*, Theoret. Comput. Sci. **70** (1990), 305-342.

[63] M. H. El-Zahar, J. H. Schmerl, *On the size of jump-critical ordered sets*, Order **1** (1984), 3-5.

[64] P. Erdös, A. Tarski, *On families of mutually exclusive sets*, Ann. of Math. (2) **44** (1943), 315-329.

[65] P. Erdös, R. Rado, *Sets having divisor property*, Solution to problem 4358, Amer. Math. Monthly **59** (1952), 255-257.

[66] J. Falque, *Classification of p-oligomorphic groups; conjectures of Cameron and Macpherson*, Ph.D. thesis, Université Paris-Sud, November 2019, 136 pp.

[67] J. Falque, N. M. Thiéry, *Macpherson's conjecture holds: the orbit algebra of a permutation group with polynomial profile is finitely generated*, 30th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2018, Hanover), February 2018.

[68] P. Fogg, *Substitutions in dynamics, arithmetics and combinatorics*, V.Berthé, S.Ferenczi, C.Mauduit, A.Siegel (Eds), Springer 2012.

[69] R. Fraïssé, *On a decomposition of relations which generalizes the sum of ordering relations* Bull. Amer. Math. Soc. **59** (1953), 389.

[70] R. Fraïssé, *Sur la comparaison des types de relations*, C. R. Acad. Sci. Paris **226** (1948), 987-988.

[71] R. Fraïssé, *Sur la comparaison des types d'ordres*, C. R. Acad. Sci. Paris **226** (1948), 1330-1331.

[72] R. Fraïssé, *Sur quelques classifications des systèmes de relations*, Thèse, Paris (1953), *Alger-Math.* **1** (1954), 35-182.

[73] R. Fraïssé, *Sur l'extension aux relations de quelques propriétés des ordres*, Ann. Sci. Ecole Norm. Sup., **71** (1954), 361-388.

[74] R. Fraïssé, *Abritement entre relations et spécialement entre chaînes*, 1971 Symposia Mathematica, Vol. V (INDAM, Rome, 1969/70) pp. 203-251 Academic Press, London

[75] R. Fraïssé, *Cours de Logique Mathématique, tome 1, Relation et formule logique*, Gauthier-Villars, 1971, xiv+179.

[76] R. Fraïssé, *Theory of relations*, Revised edition. With an appendix by Norbert Sauer. Studies in Logic and the Foundations of Mathematics, 145. North-Holland Publishing Co., Amsterdam, 2000. ii+451.

[77] R. Fraïssé, *L'intervalle en théorie des relations, ses généralisations, filtre intervallaires et clôture d'une relation*, in "Orders, description and roles", M. Pouzet and D. Richard,éd. (L'Arbresle, 1982), Ann. Discrete Math. **23** (1984), 313-341.

[78] R. Fraïssé, G. Lopez, *La reconstruction d'une relation dans l'hypothèse forte: isomorphie des restrictions à chaque partie stricte de la base*. With an appendix by G. Lopez and C. Rauzy. Séminaire de Mathématiques Supérieures, 109. Presses de l'Université de Montréal, Montreal, QC, 1990. 139 pp.

[79] R. Fraïssé, M. Pouzet, *Interprétabilité d'une relation par une chaîne*. C. R. Acad. Sci. Paris Sér. A-B **272** (1971), A1624-A1627.

[80] R. Fraïssé, M. Pouzet, *Sur une classe de relations n'ayant qu'un nombre fini de bornes*, C. R. Acad. Sci. Paris Sér. A-B **273** (1971), A275-A278.

[81] C. Frasnay, *Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes*. Thèse. Paris. Annales Institut Fourier Grenoble **15** (1965), 415-524.

[82] C. Frasnay, *Chainable relations, rangements and pseudorangements*, in Orders: description and roles (L'Arbresle, 1982), 235-268, North-Holland Math. Stud., 99, Ann. Discrete Math., 23, North-Holland, Amsterdam, 1984.

[83] C. Frasnay, *Détermination du degré optimal $d_m$ de monomorphie pour les structures relationnelles au plus m-aires*, Math. Rep. Acad. Sci. Canada **12** (4)(1990), 141-146.

[84] T. Gallai, *Transitiv orientbare graphen*, Acta Math. Acad. Sci. Hungar. **18** (1967), 25-66 (English translation by F. Maffray and M. Preissmann in J.J. Ramirez-Alfonsin and B. Reed (Eds), Perfect graphs, Wiley 2001, 25-66).

[85] M. R. Garey, D. S. Johnson, *The complexity of near-optimal graph coloring*. J. Assoc. Comput. Mach. **23** (1976), 43-49.

[86] C. Geniet, S. Thomassé, *First order logic and twin-width in tournaments and dense oriented graphs*, arXiv:2207.07683v1, 15 July 2022, 28 pp.

[87] P. Gibson, M. Pouzet, and R. Woodrow, *Relational structures having finitely many full-cardinality restrictions*, Discrete Math. **291** (2005), 115-134.

[88] D.H. Gottlieb, *A class of incidence matrices*, Proc. Amer. Math. Soc. **17** (1966), 1233-1237.

[89] G. Grätzer, *General lattice theory, With appendices by B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille*, Reprint of the 1998 second edition. Birkhäuser Verlag, Basel, 2003. xx+663 pp.

[90] G. Hahn, M. Pouzet, R. Woodrow, *Siblings of countable cographs*, to appear in J. Mult.-Valued Logic Soft Comput. (special issue dedicated to Ivo Rosenberg), arXiv:2004.12457, 26 April 2020, 27 pp.

[91] T. Harju, G. Rozenberg, *Decomposition of infinite labeled 2-structures*, Results and trends in theoretical computer science (Graz, 1994), 145-158. Lecture Notes in Comput. Sci., 812, Springer, Berlin, 1994.

[92] H.A. Helfgott, *Isomorphismes de graphes en temps quasi-polynomial* (d'après Babai et Luks, Weisfeiler-Leman), Expository paper associated to Bourbaki seminar (Jan 14, 2017). 43 pages, in French. To appear in Astérisque. Fascicule no 1125 of the Bourbaki seminar (69th year, 2016-2017)arXiv:1701.04372.
[93] P. Hell, J. Nešetřil, *Graphs and homomorphisms*, Oxford Lecture Series in Mathematics and its Applications, 28. Oxford University Press, Oxford, 2004. xii+244 pp.

[94] G. Higman, *Ordering by divisibility in abstract algebras*, Proc. Lond. Math. Soc. (3) 2 (1952), 326–336.

[95] G. Higman, *Homogeneous relations*, Quart. J. Math. Oxford Ser. (2) 28 (1977), 31–39.

[96] W. Hodges, A. H. Lachlan and S. Shelah, *Possible orderings of an indiscernible sequence*, Bull. Lond. Math. Soc. 9 (1977), 212–215.

[97] I.M. Hodkinson, H.D. Macpherson, *Relational structures determined by their finite induced substructures*, J. Symbolic Logic 53 (1988), 222–230.

[98] P. Ille, *Indecomposable graphs*, Discrete Math. 173 (1997), 71–78.

[99] M. Jean, *Relations monomorphes et classes universelles*, C. R. Acad. Sci. Paris Sér. A-B 264 (1967), A591–A593.

[100] P. Jullien, *Contribution à l'étude des types d'ordres dispersés*, Thèse Doctorat d'État, Université de Marseille, 27 June 1968.

[101] M. Kabil, M. Pouzet, *Geometric aspects of generalized metric spaces: Relations with graphs, ordered sets and automata* in New Trends in Analysis and Geometry, Ali Hussain Alkhaldi, Mohammed Kbiri Alaoui and Mohamed Amine Khamsi (eds), Cambridge Scholars Publishing (2020), 319-377

[102] W.M. Kantor, *On incidence matrices of finite projective and affine spaces*, Math. Z. 124 (1972), 315–318.

[103] K. Kearnes, G. Oman, *Jónsson posets and unary Jónsson algebras*, Algebra Universalis 69 (2013), 101–112.

[104] A. Kechris, V. Pestov, S. Todorcevic, *Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups*, Geom. Funct. Anal. 15 (2005), 106–189.

[105] D. Kelly, *The 3-irreducible partially ordered sets*, Canad. J. Math. 29 (1977), 367–383.

[106] D.Kelly, *Comparability graphs*, in Graphs and Orders, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 147 (1985), 3–40.

[107] M. Klazar, *Overview of general results in combinatorial enumeration*, in Permutation patterns, London Math. Soc. Lecture Note Ser. 376 (2010), 3–40.

[108] N. Korpelainen and V. Lozin, *Bipartite induced subgraphs and well-quasi-ordering*, J Graph Theory 67 (2011), 235–249.

[109] N. Korpelainen, V. Lozin and I. Razgon, *Boundary properties of well-quasi-ordered sets of graphs*, Order 30 (2013), 723–735.

[110] P. Krauss, *Universally complete universal theories*, Z. Math. Logik Grundlagen Math. 17 (1971), 351–370.

[111] I. Kříž, J. Sgall, *Well-quasiordering depends on the labels*. Acta Sci. Math. (Szeged) 55 (1991), 59–65.

[112] J.B. Kruskal, *Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture*, Trans. Amer. Math. Soc. 95 (1960), 210–225.

[113] J.B. Kruskal, *The theory of well-quasi-ordering: a frequently discovered concept*, J. Combin. Theory Ser. A 13 (1972), 297–305.

[114] C. Laflamme, M. Pouzet, N. Sauer, *Invariant subsets of scattered trees. An application to the tree alternative property of Bon-ato and Tardif*, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Abh. Math. Sem. Univ. Hamburg) October 2017, 87, 2, 369-408. arXiv:1508.01123, 2015.

[115] C. Laflamme, M. Pouzet, N. Sauer, R. Woodrow, *Siblings of an $\aleph_0$-categorical relational structure*, Contrib. Discrete Math. 16 (2021), no. 2, 90–127. Special Edition, Proceedings of the Banff International Workshop 15w5100 Homogeneous Structures (in honour of Norbert Sauer) Invited editor Lionel Nguyen Van Thé, arXiv:1811.04185.

[116] C. Laflamme, M. Pouzet, R. Woodrow, *Equimorphy – the case of chains*, Arch. Math. Logic 56 (2017), 811-829.

[117] M.C. Laskowski, C.A. Terry, *Jumps in speeds of hereditary properties in finite relational languages*, J. Combin. Theory Ser. B 154 (2022), 93–135.

[118] R. Laver, *On Fraïssé's order type conjecture*, Ann. of Math. (2) 93 (1971), 89–111.

[119] R. Laver, *An order type decomposition theorem*, Ann. of Math. (2) 98 (1973), 96–119.

[120] J.D. Lawson, M. Mislove, H. A. Priestley, *Infinite antichains in semilattices*, Order 2 (1985), 275–290.

[121] J.D. Lawson, M. Mislove, H. A. Priestley, *Ordered sets with no infinite antichains*, Discrete Math. 63 (1987), 225–230.

[122] J.D. Lawson, M. Mislove, H. A. Priestley, *Infinite antichains and duality theories*, Houston J. Math. 14 (1988), 423–441.

[123] M. Lothaire, *Combinatorics on words*. Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, U.K. 1997.

[124] V. Lozin, R. Gábor, *Minimal universal bipartite graphs*, Ars Combin. 84 (2007), 345–356.

[125] V. Lozin, C. Mayhill, *Canonical antichains of unit interval and bipartite permutation graphs*, Order 28 (2011), 513–522.

[126] H.D. Macpherson, *Growth rates in infinite graphs and permutation groups*, Proc. Lond. Math. Soc. (3) 51 (1985), 285–294.

[127] H.D. Macpherson, *Infinite permutation groups of rapid growth*, J. Lond. Math. Soc. (2) 35 (1987), 276–286.

[128] H.D. Macpherson, M. Pouzet, and R.E. Woodrow, *Countable structures of a given age*, J. Symb. Log. 57 (1992), 992–1010.

[129] A.I. Mal'cev, *The metamathematics of algebraic systems*, Collected papers: 1936-1967. Translated, edited, and provided with supplementary notes by Benjamin Franklin Wells, III. Studies in Logic and the Foundations of Mathematics, Vol. 66. North-Holland Publishing Co., Amsterdam-London, 1971. xviii+494 pp.

[130] M. Malliaris, C. Terry, *On unavoidable-induced subgraphs in large prime graphs*, J. Graph Theory 88 (2018), 255–270.

[131] A. Marcone, *Foundations of bqo theory*, Trans. Amer. Math. Soc. 345 (1994), 641–660.

[132] A. Marcus, G. Tardös, *Excluded permutation matrices and the Stanley-Wilf conjecture*, J. Combin. Theory Ser. A 107 (2004), 153–160.

[133] G.A. McKay, *Better-Quasi-Orders: Extensions and Abstractions*, PhD thesis, University of East Anglia, June 15, 2015, 216 pp.
[134] E.C. Milner, *Basic wqo- and bqo-theory*, in Graphs and order, I.Rival Ed. (Banff, Alta., 1984), 487–502. Reidel, Dordrecht, 1985.

[135] M. Mislove, *When are order scattered and topologically scattered the same?*, Orders: description and roles (l'Arbresle, 1982), North Holland Math Stud. **99**, Ann. Discrete Math. **23** (1984), 61-80.

[136] J.D. Monk, *Cardinal invariants on Boolean algebras*, Progress in Mathematics, vol. 142, Birkhäuser, Basel, 1996.

[137] Y. N. Moschovakis, *Descriptive set theory*, Studies in Logic and Foundations of Mathematics, vol. 100, North-Holland Publishing Co., 1980.

[138] C.St.J.A. Nash-Williams, *On well-quasi-ordering finite trees*, Proc. Cambridge Philos. Soc. **59** (1963), 833–835.

[139] C.St.J.A. Nash-Williams, *On well-quasi-ordering infinite trees*, Proc. Cambridge Philos., Soc. **61** (1965), 697-720.

[140] D. Oudrar, *Sur l'énumération de structures discrètes: une approche par la théorie des relations*, Thèse de doctorat, Université d'Alger USTHB à Bab Ezzouar, 28 September 2015, 249 pp., arXiv:1604.05839.

[141] D. Oudrar, *Hereditary classes of ordered binary structures*, Adv. Pure Appl. Math. **11** (2020), 1–33.

[142] D. Oudrar, M. Pouzet, *Profile and hereditary classes of relational structures*, J. Mult.-Valued Logic Soft Comput. **27** (2016), 475–500.

[143] D. Oudrar, M. Pouzet, I. Zaguia, *Minimal prime ages, words and permutation graphs*, arXiv:2206.01557, June 3, 2022, 46 pp.

[144] D. Oudrar, M. Pouzet, *Ordered structures with no finite monomorphic decomposition*. Application to the profile of hereditary classes*, preprint, Oct 2021. 23 pp.

[145] J-F. Pabion, *Relations préhomogènes*, C. R. Acad. Sci. Paris Sér. A-B **274** (1972), A529–A531.

[146] M. Pouzet, *Modèle universel d'une théorie n-complète: Modèle uniformément préhomogène*, C. R. Acad. Sci. Paris Sér. A-B **274** (1972), A695–A698.

[147] M. Pouzet, *Un belordre d'abritement et ses rapports avec les bornes d'une multirelation*, C. R. Acad. Sci. Paris Sér. A-B **274** (1972), A1677–A1680.

[148] M. Pouzet, *Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations*, Math. Z. **150** (1976), 117–134.

[149] M. Pouzet, *Sur la théorie des relations*. Thèse d'état, Université Claude-Bernard, Lyon 1, 1978.

[150] M. Pouzet, *Condition de chaîne en théorie des relations*, Israel J. Math. **30** (1978), 65–84.

[151] M. Pouzet, *Chaînes de théories universelles*, Fund. Math. **103** (1979), 133–149.

[152] M. Pouzet, *Relation minimale pour son âge*, Z. Math. Logik Grundlag. Math. **25** (1979), 315–344.

[153] M. Pouzet, *The asymptotic behavior of a class of counting functions*, Combinatorics 79 Part 2. M.Deza and I.G.Rosenberg Eds., Ann. Discrete Math. **9** (1980), 223–224.

[154] M. Pouzet, *Relation impartible*, Dissertationes **103** (1981), 1–48.

[155] M. Pouzet, *Application de la notion de relation presque-enchaînable au dénombrement des restrictions finies d'une relation*, Z. Math. Logik Grundlag. Math. **27** (1981), 289–332.

[156] M. Pouzet, *Applications of well-quasi-ordering and better quasi-ordering*, In Graphs and order (Banff, Alta., 1984), pp. 503–519. Reidel, Dordrecht, 1985.

[157] M. Pouzet, *The profile of relations*, Glob. J. Pure Appl. Math. **2** (2006), 237–272.

[158] M. Pouzet, *When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron*, Theor. Inform. Appl. **42** (2008), 83–103.

[159] M. Pouzet, *Well-quasi-ordering and bounds of hereditary classes of relational structures*, in preparation, September 2023.

[160] M. Pouzet and I.G. Rosenberg, *Sperner properties for groups and relations*, Europ. J. Combin. **7** (1986), 349–370.

[161] M. Pouzet, N. Sauer, *From well-quasi-ordered sets to better-quasi-ordered sets*. Electron. J. Combin. **13** (2006), no. 1, Research Paper 101, 27 pp.

[162] M. Pouzet, M. Sobrani, *Sandwiches of ages*, Ann. Pure Appl. Logic **108** (2001), 295–326.

[163] M. Pouzet, M. Sobrani, *The order type of the collection of finite series-parallel posets*, Discrete Math. **265** (2003), 189–211.

[164] M. Pouzet, M. Sobrani, *Ordinal invariant of an age*, in preparation.

[165] M. Pouzet, N. Thiéry, *Some relational structures with polynomial growth and their associated algebras I. Quasi-polynomiality of the profile*, Electron. J. Combin. **20** (2013) no. 2, Paper 1, 35pp.

[166] M. Pouzet, N. Thiéry, *Some relational structures with polynomial growth and their associated algebras II. Finite generation, Contrib. Discrete Math. **17** (2022), 70–108.

[167] M. Pouzet, N. Zaguia, *Dimension de Krull des ensembles ordonnés*, Special volume on ordered sets and their applications (L'Arbresle, 1982). Discrete Math. **53** (1985), 173–192.

[168] M. Pouzet, I. Zaguia, *On minimal prime graphs and posets*, Order **26** (2009), 357–375.

[169] M. Pouzet, I. Zaguia, *Graphs containing finite induced paths of unbounded length*, DMTCS special volume edited by Karell Bertet, Miguel Couceiro, Jens Gustedt, Erkko Lehtonen, Nicolas Thiéry. 28pp. Vol 23:2, 3, 2021 ArXiv: 2011.00352v1.

[170] M. Pouzet, I. Zaguia, *Hereditary classes of ordered sets coverable by two chains*, arXiv:2112.02633, 5 December 2021, 39 pp.

[171] H. A. Priestley, *Representation of distributive lattices by means of ordered stone spaces*, Bull. Lond. Math. Soc., **2** (1970) 507–530.
[172] H. A. Priestley, *Ordered topological spaces and the representation of distributive lattices*, Proc. Lond. Math. Soc. (3) **24** (1972), 186-190.

[173] H. A. Priestley, *Ordered sets and duality for distributive lattices*, Ann. Discrete Math. **23** (1984), 39-60.

[174] F.P. Ramsey, *On a problem of formal logic*, Proc. Lond. Math. Soc. **30** (1930), 264-286.

[175] M. Rathjen and A. Weiermann, *Proof-theoretic investigations on Kruskal's theorem*. Ann. Pure Appl. Logic **60** (1993), 49-88.

[176] N. Robertson, P.D. Seymour, *Graph minors. A survey*, Surveys in combinatorics 1985 (Glasgow, 1985), 153-171, London Math. Soc. Lecture Note Ser., 103, Cambridge Univ. Press, Cambridge, 1985.

[177] A. Robinson, *On the metamathematics of algebra*, Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 1951. ix+195 pp.

[178] A. Robinson, *Forcing in model theory*, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 1, pp. 245-250. Gauthier-Villars, Paris, 1971.

[179] J.G. Rosenberg, *Linear orderings*, Pure and Applied Mathematics, 98. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. xvii+487 pp.

[180] C. Ryll-Nardzewski, *On categoricity in power* ≤ κ_α, Bull. Acad. Pol. Sci. Sér. Math. Astr. Phys. **7** (1959), 545-548.

[181] D. Saracino, *Model companions for κ₀-categorical theories*, Proc. Amer. Math. Soc. **39** (1973), 591-598.

[182] E.R. Scheinerman, J. Zito, On the size of hereditary classes of graphs, J. Comb. Theory Ser. B **61** (1994), 16-39.

[183] J. Schmerl, *Coinductive κ₀-categorical theories*, J. Symb. Log. **55** (1990), 1130-1137.

[184] J.H. Schmerl, W.T. Trotter, *Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures*, Discrete Math. **113** (1993), 191-205.

[185] D. Schmidt, *Well-partial orderings and their maximal order types*. Habilitation, University of Heidelberg, Heidelberg, 1978.

[186] W. Sierpinski, *Sur les types d'ordre des ensembles linéaires*, Fund. Math. **37** (1950), 253-264.

[187] M. Slater, *On a class of order-types generalizing ordinals*, Fund. Math. **54** (1964), 259-277.

[188] D. Spielman, M. Bóna, *An infinite antichain of permutations*, Electron. J. Combin. **7** (2000), Note 2, 4 pp.

[189] M. Sobrani, *Structure d'ordre de la collection des âges de relations*, Thèse de doctorat, Université Claude-Bernard, Lyon, 18 déc. 1992.

[190] M. Sobrani, *Sur les âges de relations et quelques aspects homologiques des constructions D+M*. Thèse de doctorat d'état, Université S.M. Ben Abdallah-Fez, Fez, 2002.

[191] R.P. Stanley, *Enumerative combinatorics*. Volume 1, Wadsworth - Brooks/Cole Advanced Books and Software, Belmont, Calif. 1986.

[192] D.P. Sumner, *Graphs indecomposable with respect to the X-join*, Discrete Math. **6** (1973), 281-298.

[193] A. Tarski, *Contributions to the theory of models. III*. Nederl. Akad. Wetensch. Proc. Ser. A. **58** (Indagationes Math. **17**) (1955), 56-64.

[194] A. Tateno, *Mutually embeddable trees and a counterexample to the tree alternative conjecture*, preprint, 2008, 32 pp.

[195] W. Thomas, *Languages, automata, and logic*, Handbook of formal languages, Vol. 3, 389-455, Springer, Berlin, 1997.

[196] S. Thomassé, *On better-quasi-ordering countable series-parallel orders*, Trans. Amer. Math Soc. **352** (1999), 2491-2505.

[197] S. Thomassé, *Conjectures on countable relations*, preprint, 2000, 17 pp., and personal communication, November 2012.

[198] W. T. Trotter, J. I. Moore Jr., *Some theorems on graphs and posets*, Discrete Math. **15** (1976), 79-84.

[199] M. Tyomkyn, *A proof of the rooted tree alternative conjecture*, Discrete Math. **309** (2009), 5963-5967.

[200] V. Vatter. *Permutation classes*. In Handbook of Enumerative Combinatorics, 754-833. CRC Press, 2015.

[201] R.L. Vaught, *Remarks on universal classes of relational systems*, Nederl. Akad. Wetensch. Proc. Ser. A. **57** (Indagationes Math. **16**) (1954), 589-591.

[202] E.S. Wolk, *Partially well-ordered sets and partial ordinals*, Fund. Math. **60** (1967), 175-185.

[203] M. Yannakakis, *The complexity of the partial order dimension problem*, SIAM J. Algebraic Discrete Methods **3** (1982), 351-358.

[204] N. Zaguia, *Chaînes d'idéaux et de sections initiales d'un ensemble ordonné*, Publ. Dép. Math. (Lyon) (N.S.), (7/D) **97**, 1983.

[205] I. Zverovich, *Extension of hereditary classes with substitutions*, Discrete Appl. Math. **128** (2003), 487-509.

ICJ, MATHÉMATIQUES, UNIVERSITÉ CLAUDE-BERNARD LYON1, 43 BD. 11 NOVEMBRE 1918, 69622 VILLEURBANNE CEDEX, FRANCE AND MATHEMATICS & STATISTICS DEPARTMENT, UNIVERSITY OF CALGARY, CALGARY, ALBERTA, CANADA T2N 1N4

Email address: pouzet@univ-lyon1.fr