$\mu_{\restriction\\{j_{3},\ldots,i_{n-3}\\}}=1^{n-5}$. In particular,
$f(G_{w})$ has an induced $P_{n-4}$ and since $f$ is an embedding we infer
that $G_{w}$ has an induced $P_{n-4}$. It follows from Lemma 70 that $w$ has
$1^{n-7}$ as a factor.

∎

######  Proposition 73.

Let $\mu$ be a recurrent word on ${\mathbb{N}}$ such that $l(\mu)$ is finite.
Let $w:=w_{0}\ldots w_{n-1}$ be a finite word such that $n>l(\mu)+7$. If
$G_{w}$ embeds into $G_{\mu}$ and $f$ is such an embedding, then
$f(-1),f(0)<f(1)<f(2)<\ldots<f(n-1)$ and either
$\\{f(-1),f(1),f(2),\ldots,f(n-1)\\}$ or
$\\{f(0),f(1),f(2),\ldots,f(n-1)\\}$is an interval of ${\mathbb{N}}$ and
$w_{2}\ldots w_{n}$ is a factor of $\mu$.

###### Proof.

It follows from Corollary 66 that $G_{w}$ is prime. It follows from our
assumption $n>l(\mu)+7$ and Corollary 68 that $G_{w}\setminus\\{-1\\}$ and
$G_{w}\setminus\\{0\\}$ and $G_{w}\setminus\\{n-1\\}$ are also prime. Since
$f$ is an embedding it follows that in $f(G_{w})$ removal of one of the
vertices $f(-1)$ or $f(0)$ or $f(n-1)$ leaves a prime graph. Since $G_{w}$ is
prime and $f$ is embedding it follows that $f(G_{w})$ is also prime. It
follows from Corollary 57 that $I:=f(V(G_{w}))\setminus\\{\min(f(V(G_{w}))\\}$
is an interval of ${\mathbb{N}}$. It follows from Corollary 59 that
$f(n-1)\in\\{\min(f(V(G_{w})),\min(I),\max(I)\\}$. It follows from Lemma 72
that $f(n-1)=\max(f(V(G_{w})))$. The required conclusion follows then from
Lemma 71. ∎

######  Corollary 74.

Let $\mu$ be a recurrent word on ${\mathbb{N}}$ such that $l(\mu)<4$. Let
$u,v$ be finite words such that $|v|\geq 3$ and $n>l(mu)+4$ and $G_{vu}$ is
prime. If $G_{vu}$ embeds into $G_{\mu}$, then $u\in\operatorname{Fac}(\mu)$.

###### Proof.

Follows from Proposition 73 applied to $w:=vu$. ∎

######  Lemma 75.

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

###### Proof.

We consider several cases.

  1. Case 1.

$\mu$ has $1^{4}$ as a factor.
We can write $\mu=\alpha 1^{4}\mu^{\prime}$ where $\alpha$ is a finite word
and $\mu^{\prime}$ is an infinite $0$-$1$ sequence. Since $\mu$ is recurrent
$\operatorname{Fac}(\mu)=\operatorname{Fac}(1^{4}\mu^{\prime})=\operatorname{Fac}(\mu^{\prime})$.
Hence, we may assume without loss of generality that $\alpha$ is the empty
word. Let $u\in\operatorname{Fac}(\mu^{\prime})$. There exists then
$\beta\in\operatorname{Fac}(\mu^{\prime})$ such that $1^{4}\beta
u\in\operatorname{Fac}(\mu^{\prime})$. It follows from Proposition 65 that
$G_{1^{4}\beta u}$ is prime. Choose $v:=1^{4}\beta$.

  2. Case 2.

$\mu$ has $0^{4}$ as a factor.
We apply Case 1 to $\overline{\mu}$ and $\overline{u}$.

  3. Case 3.

$l(\mu)<4$. Let $u\in\operatorname{Fac}(\mu)$. Since $\mu$ is recurrent there
exists $v\in\operatorname{Fac}(\mu)$ such that $vu\in\operatorname{Fac}(\mu)$
and $|v|\geq 4$ and $|vu|>l(\mu)+4$. It follows from Corollary 66 that
$G_{vu}$ is prime.

∎

######  Lemma 76.

Let $\mu$ be a word on an interval $I$ of ${\mathbb{N}}$ and let
$w:=w_{1}\ldots w_{n}$ be any finite word. If $G_{1^{4}w}$ embeds into
$G_{\mu}$, then $1w$ is a factor of $\mu$.

###### Proof.

We notice at once that it follows from Proposition 65 that $G_{1^{4}w}$ is
prime. Let $f$ be an embedding of $G_{1^{4}w}$ into $G_{\mu}$. Then the image
of $G_{1^{4}w}$ under $f$ is prime. We write
$f(V(G_{1^{4}w}))=\\{i_{0},i_{1},i_{2},i_{3},i_{4},j_{1},\ldots,j_{n}\\}$ so
that $i_{0}<\ldots<i_{4}<j_{1}<\ldots<j_{n}$. It follows from Corollary 57
that $\\{i_{1},i_{2},i_{3},i_{4},j_{1},j_{2},\ldots,j_{n}\\}$ is an interval
of ${\mathbb{N}}$.

We use induction on the length $n\geq 1$ of $w$ to prove the following
statement: $\mu_{\restriction\\{i_{4},j_{1},\ldots,j_{n}\\}}=1w_{1}\ldots
w_{n}$ and if $w\neq 1^{n}$, then for all $i\in\\{1,\ldots,n\\}$, $f$ maps the
vertex of $G_{1^{4}w}$ corresponding to $w_{i}$ to the vertex $v_{i}$.

For the basis case suppose $w\in\\{0,1\\}$. If $w=1$, then
$G_{1^{4}w}=G_{1^{5}}$ is a path on six vertices. Since $f$ is an embedding we
infer that $f(G_{{\bf 1}^{4}w})$ is a path on six vertices. It follows from
Lemma 70 that $\mu(u_{4})=\mu(v_{1})=1$ and hence $1w=11$ is a factor of $\mu$
as required. Now suppose $w=0$ and note that $G_{1^{4}w}$ has exactly one
vertex of degree four. We prove that $\mu(j_{1})=0$. Suppose for a
contradiction that $\mu(j_{1})=1$. Then $\mu(i_{4})=0$ because otherwise
$f(G_{1^{4}w})$ wont have a vertex of degree four and since $f$ is an
embedding neither will $G_{1^{4}w}$ which is impossible. But then in
$f(G_{1^{4}w})$ the vertex $i_{4}$ which has degree four is adjacent to the
vertex $j_{1}$ which has degree one and hence in $G_{1^{4}w}$ the vertex of
degree four is adjacent to a vertex of degree one and this is not possible. A
contradiction. Hence, our supposition that $\mu(v_{1})=1$ is false, that is
$\mu(j_{1})=0$ as required. Now since $f(G_{1^{4}w})\setminus\\{j_{1}\\}$ is a
path on five vertices it follows from Lemma 70 that $\mu(i_{4})=1$ and hence
$1w=10$ is a factor of $\mu$ as required.

Next we consider the inductive case. We first note that if $w=1^{n}$, then
$G_{1^{4}w}$ is a path on $n+5$ vertices. We apply Lemma 70 with $k=n+5$ and
deduce that $\mu_{\restriction\\{i_{3},i_{4},j_{1},\ldots,j_{n}\\}}=1^{n+2}$
and hence $1w$ is a factor of $\mu$. We now assume that $w\neq 1^{n}$. Suppose
that $w_{1}\ldots w_{n-1}=1^{n-1}$. Then $G_{1^{4}w_{1}\ldots w_{n-1}}$ is a
path on $n+4$ vertices. It follows from Lemma 70 that
$\mu_{\restriction\\{i_{3}i_{4},j_{1},\ldots,j_{n-1}\\}}=1^{n+1}$. From our
assumption that $w\neq 1^{n}$ we deduce that $w_{n}=0$. Hence, $G_{1^{4}w}$
has a unique vertex of degree $n+4$ and this vertex is associated to $w_{n}$.
Since $f$ is an embedding and
$\mu_{\restriction\\{i_{3}i_{4},j_{1},\ldots,j_{n-1}\\}}=1^{n+1}$ it follows
that the image under $f$ of the vertex associated to $w_{n}$ must be $j_{n}$
and $j_{n}$ has degree $n+4$. This shows that $\mu(j_{n})=0$ and hence $1w$ is
a factor of $\mu$.

Next we suppose that $w_{1}\ldots w_{n-1}\neq 1^{n-1}$. By the induction
hypothesis $\mu_{\restriction\\{i_{4},j_{1},\ldots,j_{n-1}\\}}=1w_{1}\ldots
w_{n-1}$ and for all $i\in\\{1,\ldots,n-1\\}$, $f$ maps the vertex of
$G_{1^{4}w}$ corresponding to $w_{i}$ to the vertex $j_{i}$. We note that
$j_{n-1}$ is the unique neighbour or the unique non neighbour of $j_{n}$ in
$f(G_{1^{4}w})$. Since $f$ is an embedding it follows that $j_{n}$ is the
image under $f$ of the vertex of $G_{1^{4}w}$ corresponding to $w_{n}$ and
$\mu(j_{n})=w_{n}$. This completes the proof of the lemma. ∎

######  Corollary 77.

Let $\mu$ be a word on an interval $I$ of ${\mathbb{N}}$ and let
$w:=w_{1}\ldots w_{n}$ be any finite word. If $G_{0^{4}w}$ embeds into
$G_{\mu}$, then $0w$ is a factor of $\mu$.

###### Proof.

We apply Lemma 76 to $\overline{\mu}$ and $\overline{w}$ and recall that
$G_{1^{4}\overline{w}}$ embeds into $G_{\overline{\mu}}$ if and only if the
complement of $G_{1^{4}\overline{w}}$, which is $G_{0^{4}w}$, embeds into the
complement of $G_{\overline{\mu}}$, which is $G_{\mu}$. ∎

######  Corollary 78.

Let $\mu$ be a word on ${\mathbb{N}}$.

  1. $(1)$

If $w$ is a bound of $\mu$, then $G_{1^{4}w}$ and $G_{0^{4}w}$ do not embed
into $G_{\mu}$.

  2. $(2)$

If $(w_{i})_{i\in I}$, $I\subseteq{\mathbb{N}}$, is an antichain (with respect
to the factor ordering) of finite words such that no $w_{i}$ starts with $1$,
then $(G_{1^{4}w_{i}})_{i\in I}$ is an antichain of (permutation) graphs.

###### Proof.

  1. $(1)$

The fact that $G_{1^{4}w}$ does not embed into $G_{\mu}$ follows from Lemma
76. The fact that $G_{0^{4}w}$ does not embed into $G_{\mu}$ follows from
Corollary 77.

  2. $(2)$

Suppose for a contradiction that there exists $i\neq j$ be such that
$G_{1^{4}w_{i}}$ embeds into $G_{1^{4}w_{j}}$. It follows from Lemma 76 that
$1w_{i}$ is a factor of $1^{4}w_{j}$. Since $w_{i}$ does not start with $1$ we
infer that $w_{i}$ is a factor of $w_{j}$. This is impossible since by
assumption the sequence $(w_{i})_{i\in I}$ is an antichain of words.

∎

##  9\. A proof of Theorem 37

We prove the following strengthening of Theorem 37. For that we introduce
first the following notation: if $X$ is a set of finite $0$-$1$ words we set
$G_{X}:=\\{G_{w}:w\in X\\}$ and

$\downarrow G_{X}:=\\{H:H\;\text{embeds into some}\;G_{w}\in G_{X}\\}.$

######  Theorem 79.

Let $\mu$ be a recurrent word and $X$ be an initial segment of $\\{0,1\\}^{*}$
for the factor ordering. If $\operatorname{Age}(G_{\mu})\subseteq\downarrow
G_{X}$ then $\operatorname{Fac}(\mu)\subseteq X$.

###### Proof.

Let $u\in\operatorname{Fac}(\mu)$. We prove that $u\in X$. According to Lemma
75, since $\mu$ is recurrent and $u\in\operatorname{Fac}(\mu)$ there is some
$v\in\\{0,1\\}^{*}$ with $|v|\geq 3$ such that $vu\in\operatorname{Fac}(\mu)$
and $G_{vu}$ is prime. Since
$G_{vu}\in\operatorname{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 Corollary
74 that $u$ is a factor of $w$. If $l(\mu)\geq 4$ then there is
$u^{\prime}\in\operatorname{Fac}(\mu)$ such that $u$ is a factor of
$u^{\prime}$ and either $0^{4}u^{\prime}$ or $1^{4}u^{\prime}$ is a factor of
$\mu$. It follows from Lemma 76 and Corollary 77 applied to either $v=0^{4}$
or $v=1^{4}$ that $u^{\prime}$ is a factor of $w$, and so is $u$. Hence, $u\in
X$. ∎

Theorem 37 now follows by observing that
$\operatorname{Age}(G_{\mu^{\prime}})=\downarrow
G_{\operatorname{Fac}({\mu^{\prime}})}$ and then applying Theorem 79 to
$X:=\operatorname{Fac}(\mu^{\prime})$.

##  10\. A proof of Theorem 39

###### Proof.

$(i)\Rightarrow(ii)$. Let $\mu$ be uniformly recurrent. Then trivially, $\mu$
is recurrent. Since for two infinite sequence $\tau$ and $\tau^{\prime}$, the
equality $\operatorname{Fac}(\tau)=\operatorname{Fac}(\tau^{\prime})$ implies
$\operatorname{Age}(G_{\tau})=\operatorname{Age}(G_{\tau^{\prime}})$, it
follows from Theorem 5 that we may assume that $\mu$ is a word on
${\mathbb{N}}$. It follows from Corollary 63 that $G_{\mu}$ is prime. Hence,
from Theorem 10 it follows that the set of prime graphs in
$\operatorname{Age}(G_{\mu})$ is cofinal in $\operatorname{Age}(G_{\mu})$
hence infinite. Now let $\mathcal{C}$ be a proper age of
$\operatorname{Age}(G_{\mu})$. We prove that $\mathcal{C}$ contains only a
finite number of prime graphs. If $\mathcal{C}$ contains restrictions on
intervals of ${\mathbb{N}}$ of arbitrarily large length, then according to
Corollary 66, $\mathcal{C}$ contains finite prime graphs of arbitrarily large
length and therefore $\mathcal{C}=\operatorname{Age}(G_{\mu})$. Else,
$\mathcal{C}$ contains only restrictions to factors of $\mu$ of bounded
length. It follows from Corollary 57 that every prime member of $\mathcal{C}$
of cardinality $m$ induces an interval of ${\mathbb{N}}$ of cardinality $m-1$.
Therefore prime members of $\mathcal{C}$ have bounded cardinality. That is,
there are only finitely many prime members of $\mathcal{C}$.
$(ii)\Rightarrow(i)$. First $\operatorname{Fac}(\mu)$ is infinite since $\mu$
is recurrent. Next, let $X$ be an infinite initial segment of
$\operatorname{Fac}(\mu)$. We claim that $X=\operatorname{Fac}(\mu)$.
Corollary 67 asserts that the set $X^{\prime}:=\\{u\in X:G_{u}\;\text{is
prime}\\}$ is infinite. Since $\downarrow G_{X}$ contains infinitely many
prime and $\operatorname{Age}(G_{\mu})$ is minimal prime, $\downarrow
G_{X}=\operatorname{Age}(G_{\mu})$. Since
$\operatorname{Age}(G_{\mu})\subseteq\downarrow G_{X}$, Theorem 79 asserts
that $\operatorname{Fac}(u) \subseteq X$. This proves our claim. ∎

##  11\. Bounds of $0$-$1$ graphs: a proof of Theorem 47.

Let $\mu$ be a $0$-$1$ sequence. Then every bound of
$\operatorname{Age}(G_{\mu})$ is one of the following types:

  1. $(1)$

Finite graphs that are not comparability graphs and that are minimal with this
property.

  2. $(2)$

Finite comparability graphs of critical posets of dimension three (see
subsection 3.1.2).

  3. $(3)$

Finite comparability graphs of posets of dimension two, that is finite
permutation graphs.

For example if $\mu=11111...$, then the bounds of
$\operatorname{Age}(G_{\mu})$ listed according to their type are:

  1. $(a)$

Odd cycles of length at least 5. These are of type (1).

  2. $(b)$

Even cycles of length at least 6. These are of type (2).

  3. $(c)$

The complete bipartite graph $K_{1,3}$ and the complete graph $K_{3}$. These
are of type (3).

Let $\mu$ be a $0$-$1$ sequence. If $\mu$ contains factors of 1’s of
arbitrarily length, then it follows from Lemma 70 that $G_{\mu}$ embeds
$P_{k}$ for infinitely many $k$’s, hence $\operatorname{Age}(G_{\mu})$
contains the age of an infinite path. The cycles $C_{k}$ are bounds of the
infinite path and form an infinite antichain. Since cycles of length at least
five are not permutation graphs, these cycles are bounds of
$\operatorname{Age}(G_{\mu})$. Now suppose that neither $P_{k}$ nor
$\overline{P_{k}}$ embed in $G_{\mu}$. In particular, $\mu$ has infinitely
many 1’s and 0’s, that is $G_{\mu}$ has an infinite independent set and an
infinite clique. If we put an upper bound on the length of paths and of
complement of paths in members of the lists of Gallai [25] and Kelly [30],
there are only finitely many such members, hence $\operatorname{Age}(G_{\mu})$
has only finitely many bounds of type (1) and finitely many bounds of type
(2). Hence,

######  Theorem 80.

If the age of $G_{\mu}$ does not contain the age of the infinite path nor of
its complement, then it has only finitely many bounds which are not
permutation graphs.

It is tempting to think that candidates for bounds of
$\operatorname{Age}(G_{\mu})$ of type $(3)$ are graphs of the form $G_{w}$
where $w$ is a bound of $\operatorname{Fac}(\mu)$. This is false.

######  Lemma 81.

Let $\mu$ be a recurrent $0$-$1$ sequence on ${\mathbb{N}}$ and
$w:=w_{1}\ldots w_{n}$ be a finite word. If $w_{2}\ldots w_{n}$ is a factor of
$\mu$, then $G_{w}$ embeds into $G_{\mu}$.

###### Proof.

Suppose $w_{2}\ldots w_{n}$ is a factor of $\mu$. Let
$\\{j_{2},\ldots,j_{n}\\}\subseteq{\mathbb{N}}$ be such that
$\mu(j_{k})=w_{k}$ for all $2\leq k\leq n$. Since $\mu$ is recurrent we may
assume that there are at least three elements of ${\mathbb{N}}\cup\\{-1\\}$
before $j_{2}$. Let $j_{1}:=j_{2}-1$ and $w^{\prime}_{1}:=\mu(j_{1})$. If
$w^{\prime}_{1}=w_{1}$, then $w$ is a factor of $\mu$ and hence $G_{w}$ embeds
into $G_{\mu}$. Else if $w^{\prime}_{1}\neq w_{1}$, then we set
$j_{0}:=j_{1}-2$. It follows that $G_{w}$ is isomorphic to
${G_{\mu}}_{\restriction\\{j_{0},j_{1}\ldots,j_{n}\\}}$. ∎

######  Corollary 82.

Let $\mu$ be a recurrent $0$-$1$ sequence on ${\mathbb{N}}$ and $w$ be a
finite word. If $w$ is a bound of $\operatorname{Fac}(\mu)$, then $G_{w}$
embeds into $G_{\mu}$.

###  11.1. Proof of $(1)$ of Theorem 47.

We show first how to construct a bound of $\operatorname{Age}(G_{\mu})$ using
a bound of $\mu$.

######  Lemma 83.

Let $\mu$ be a recurrent $0$-$1$ sequence on ${\mathbb{N}}$ with $l(\mu)$
finite. Let $w=w_{1}\ldots w_{n}$ be a finite word such that $n>l(\mu)+7$.

  1. $(1)$

If $w:=w_{1}\ldots w_{n}$ is a bound of $\mu$ and $w_{0}\in\\{0,1\\}$ is such
that $w_{0}\ldots w_{n-1}$ is a factor of $\mu$ and
$w^{\prime}:=w_{0}w_{1}\ldots w_{n}$, then $G_{w^{\prime}}$ is a bound of
$\operatorname{Age}(G_{\mu})$.

  2. $(2)$

If $G_{w}$ is a bound of $\operatorname{Age}(G_{\mu})$, then $w_{2}\ldots
w_{n}$ is a bound of $\operatorname{Fac}(\mu)$.

###### Proof.

$(1)$ We need to prove that $G_{w^{\prime}}$ does not embed into $G_{\mu}$ and
that deleting any vertex from $G_{w^{\prime}}$ yields a graph that embeds into
$G_{\mu}$. We notice at once that it follows from our assumption $n>l(\mu)+7$
that $G_{w^{\prime}}$ is prime. We first prove that $G_{w^{\prime}}$ does not
embed into $G_{\mu}$. Suppose not and let $f$ be an embedding of
$G_{w^{\prime}}$ into $G_{\mu}$. Then $f(i_{n})=\max(f(V(G_{w^{\prime}})))$
because otherwise it follows from Corollary 68 that $w^{\prime}$ has $0^{n-6}$
or $1^{n-6}$. Hence, $w$ has $0^{n-7}$ or $1^{n-7}$ as a factor. Since
$w_{0}\ldots w_{n-1}$ is a factor of $\mu$ we infer that $n-7<l(\mu)$
contradicting our assumption that $n>l(\mu)+7$. This proves that
$f(i_{n})=\max(f(V(G_{w^{\prime}})))$. It follows then for Lemma 71 that $w$
is a factor of $\mu$ contradicting our assumption that $w$ is a bound of
$\operatorname{Fac}(\mu)$. This proves that $G_{w^{\prime}}$ does not embed
into $G_{\mu}$.
Next we prove that deleting any vertex from $G_{w^{\prime}}$ yields a graph
that embeds into $G_{\mu}$. Set $V(G_{w^{\prime}})=\\{-1,0,\ldots,n\\}$. First
we consider the graph $G_{w^{\prime}}\setminus\\{-1\\}$ and observe that it is
isomorphic to $G_{w}$. It follows from Corollary 82 that $G_{w}$ embeds into
$G_{\mu}$. We now consider the graph $G_{w^{\prime}}\setminus\\{n\\}$ and
observe that it is isomorphic to $G_{w_{0}\ldots w_{n-1}}$. Since $w_{0}\ldots
w_{n-1}$ is a factor of $\mu$ we infer that $G_{w_{0}\ldots w_{n-1}}$ is an
induced subgraph of $G_{\mu}$. Let $k\not\in\\{-1,n\\}$ and consider the graph
$G_{w^{\prime}}\setminus\\{k\\}$. Then
${G_{w^{\prime}}}_{\restriction\\{-1,\ldots,k-1\\}}$ is the graph
$G_{w_{0}\ldots w_{k-1}}$ and
${G_{w^{\prime}}}_{\restriction\\{k+1,\ldots,n\\}}$ is the graph
$G_{w_{k+2}\ldots w_{n}}$. Since $w_{0}\ldots w_{k-1}$ and $w_{k+2}\ldots
w_{n}$ are factors of $\mu$ the graphs $G_{w_{0}\ldots w_{k-1}}$ and
$G_{w_{k+2}\ldots w_{n}}$ are induced subgraphs of $G_{\mu}$, and hence, so is
$G_{w^{\prime}}\setminus\\{k\\}$. This completes the proof of $(1)$.

$(2)$ Suppose $G_{w}$ is a bound of $\operatorname{Age}(G_{\mu})$. Then $w$
cannot be a factor of $\mu$ and it follows from Lemma 81 that $w$ is not a
bound of $\operatorname{Fac}(\mu)$. Hence, $w$ has a factor which is a bound
of $\operatorname{Fac}(\mu)$. We prove that $w_{2}\ldots w_{n}$ is a bound of
$\operatorname{Fac}(\mu)$, that is $w_{2}\ldots w_{n}$ is a not a factor of
$\mu$ and both words $w_{3}\ldots w_{n}$ and $w_{2}\ldots w_{n-1}$ are factors
of $\mu$. The fact that $w_{2}\ldots w_{n}$ is not a factor of $\mu$ follows
from Lemma 81 and the fact that $G_{w}$ does not embed in $G_{\mu}$. Next we
prove that $w_{3}\ldots w_{n}$ and $w_{2}\ldots w_{n-1}$ are factors of $\mu$.
It follows from our assumption $n>l(\mu)+7$ and Corollary 66 that $G_{w}$ is
prime. Next we set $V(G_{w}):=\\{i_{0},i_{1},\ldots,i_{n}\\}$ so that $w$ is a
word on $\\{i_{1},\ldots,i_{n}\\}$. It follows from Corollary 68 that
$G_{w}\setminus\\{i_{0}\\}$ and $G_{w}\setminus\\{i_{n}\\}$ are prime. It
follows from our assumption that $G_{w}$ is a bound of
$\operatorname{Age}(G_{\mu})$ that $G_{w}\setminus\\{i_{0}\\}$ and
$G_{w}\setminus\\{i_{n}\\}$ embed in $G_{\mu}$. It follows from Lemma 72 and
our assumption $n>l(\mu)+7$ that if $f$ and $g$ are such embeddings then
$f(i_{n})=\max(f(G_{w}\setminus\\{i_{0}\\}))$ and
$g(i_{n-1})=\max(g(G_{w}\setminus\\{i_{n}\\}))$. Lemma 71 yields that
$\mu_{\restriction f(\\{i_{3},\ldots,i_{n}\\})}=w_{3}\ldots w_{n}$ and
$\mu_{\restriction g(\\{i_{2},\ldots,i_{n-1}\\})}=w_{2}\ldots w_{n-1}$. This
proves that $w_{3}\ldots w_{n}$ and $w_{2}\ldots w_{n-1}$ are factors of $\mu$
as required. ∎

The proof of $(1)$ of Theorem 47 follows from Theorem 9 and $(1)$ of Lemma 83.

###  11.2. Proof of $(2)$ of Theorem 47

We notice at once that if $\mu$ is periodic and $u$ is a period, then
$\overline{\mu}$ is periodic and $\overline{u}$ is a period.

######  Lemma 84.

Let $\mu$ be a $0$-$1$ word on ${\mathbb{N}}$, let
$I:=\\{i_{0},i_{1},\dots,i_{n-1}\\}\subseteq{\mathbb{N}}\cup\\{-1\\}$ so that
$i_{0}<i_{1}<\dots<i_{n-1}$ and $H:=G_{\mu\restriction I}$ be an induced
subgraph of $G_{\mu}$. Let $j<k<n-1$. If $i_{j}$ is adjacent to all vertices
in $\\{i_{k},\ldots,i_{n-1}\\}$, then $\mu$ is constant on
$\\{i_{k+1},\ldots,i_{n-1}\\}$ and takes the value $0$. In particular, if
$l(\mu)$ is finite and $\\{i_{k+1},\ldots,i_{n-1}\\}$ is an interval of
${\mathbb{N}}$, then $n-l(\mu)-1\leq k$.

###### Proof.

Straightforward. ∎

######  Lemma 85.

Let $\mu$ be a $0$-$1$ word on ${\mathbb{N}}$ such $l(\mu)$ is finite. Let
$J:=\\{j_{0},j_{1},\ldots,j_{k}\\}\subseteq{\mathbb{N}}$ be such that
$j_{0}<j_{1}<\ldots<i_{k}$ and $\\{j_{1},\ldots,j_{k}\\}$ is an interval of
${\mathbb{N}}$ and $k>l(\mu)+5$. Then $G:=G_{\mu}{\restriction J}$ is prime.

###### Proof.

Suppose for a contradiction that $G$ is not prime. Let $M$ be a nontrivial
module of $G$. Then $M\cap\\{j_{1},\ldots,j_{k}\\}$ is a module of
$G\setminus\\{j_{0}\\}$. It follows from our assumption that $k>l(\mu)+5$ and
Corollary 66 that $G\setminus\\{i_{0}\\}$ is prime. Hence,
$M\cap\\{j_{1},\ldots,j_{k}\\}$ is either empty, reduced to a singleton or is
equal to $\\{j_{1},\ldots,j_{k}\\}$. Since $M$ is nontrivial we infer that
$M=\\{j_{1},\ldots,j_{k}\\}$ or $M\cap\\{j_{1},\ldots,j_{k}\\}$ is a
singleton. If $M=\\{j_{1},\ldots,j_{k}\\}$, then $j_{0}$ must be either
adjacent to all elements of $M$ or adjacent to none. Thus $\mu$ is constant on
$M$, that is $k\leq l(\mu)<k-5$. A contradiction. Else if
$M\cap\\{j_{1},\ldots,j_{k}\\}$ is a singleton, then $M=\\{j_{0},j_{m}\\}$ for
some $1\leq m\leq k$. Necessarily $m=k$, because otherwise $j_{m+1}$ separates
$j_{m}$ from $j_{0}$. That is $M=\\{j_{0},j_{k}\\}$. Suppose $\mu(j_{k})=1$.
Then no vertex in $\\{j_{2},\ldots,j_{k-2}\\}$ is adjacent to $j_{k}$. Since
$M$ is a module, no vertex in $\\{j_{2},\ldots,j_{k-2}\\}$ is adjacent to
$j_{0}$ and therefore $\mu$ is constant on $\\{j_{2},\ldots,j_{k-2}\\}$ and
takes the value $1$. Thus $\mu$ has $1^{k-3}$ as factor. If $\mu(j_{k})=0$,
then we obtain that $\mu$ has $0^{k-3}$ as factor. Therefore, $k-3\leq l(\mu)$
and from our assumption $k>l(\mu)+5$ we get $k-3<k-5$ which is impossible. ∎

######  Corollary 86.

Let $\mu$ be a $0$-$1$ word on ${\mathbb{N}}$ such $l(\mu)$ is finite. Let
$J:=\\{j_{0},j_{1},\ldots,j_{k}\\}\subseteq{\mathbb{N}}$ be such that
$j_{0}<j_{1}<\ldots<i_{k}$ and $\\{j_{1},\ldots,j_{k}\\}$ is an interval of
${\mathbb{N}}$ and $k>l(\mu)+6$. Let $G:=G_{\mu}{\restriction J}$ and $x\in
J$. Then $G\setminus\\{x\\}$ is prime if and only if
$x\in\\{j_{0},j_{1},j_{k}\\}$.

######  Lemma 87.

Let $\mu$ be a $0$-$1$ word on ${\mathbb{N}}$ such that $l(\mu)$ is finite.
Let $\\{i_{0},i_{1},\ldots,i_{n-1}\\}\subseteq{\mathbb{N}}$ be such that
$i_{0}<i_{1}<\ldots<i_{n-1}$ and $\\{i_{1},\ldots,i_{n-1}\\}$ is an interval
of ${\mathbb{N}}$ and $n>l(\mu)+8$. Let $x\not\in{\mathbb{N}}$ and $H$ be the
graph whose vertex set is $\\{i_{0},i_{1},\ldots,i_{n-1}\\}\cup\\{x\\}$ and
edge set
$E:=E({G_{\mu}}_{\restriction\\{i_{0},i_{1},\ldots,i_{n-1}\\}})\cup\\{\\{i_{1},x\\},\\{i_{2},x\\},\ldots,\\{i_{n-1},x\\}\\}$.
Then $H$ does not embed into $G_{\mu}$.

###### Proof.

Suppose for a contradiction that $H$ embeds into $G_{\mu}$ and let $f$ be such
an embedding. Then $f$ induces an embedding of $H\setminus\\{x\\}$ into
$G_{\mu}$. It follows from Lemma 85 that $H\setminus\\{x\\}$ is prime.
According to Corollary 57 the image of $H\setminus\\{x\\}$ under $f$
decomposes into a point $y$ and an interval $J$ to its right. It follows from
Corollary 86 that $f(\\{i_{0},i_{1},i_{n}-1\\})=\\{y,\min(J),\max(J)\\}$. It
follows from Lemma 72 that $f(i_{n-1})=\max(J)$. Hence,
$f(\\{i_{0},i_{1}\\})=\\{y,\min(J)\\}$. Now, we argue on the possible position
of $f(x)$. Suppose that $f(x)$ is to the left of $f(i_{n-1})$. Since
$\\{f(i_{2}),\ldots,f(i_{n-1})\\}$ is an interval of ${\mathbb{N}}$ we infer
that $f(x)$ is to the left of $f(i_{2})$. Since $f(x)$ is adjacent to all
vertices in $\\{f(i_{1}),f(i_{2}),\ldots,f(i_{n-1})\\}$ it follows from Lemma
84 that $\mu$ is constant on $\\{f(i_{2}),\ldots,f(i_{n-1})\\}$. Hence,
$n-2\leq l(\mu)$. From our assumption that $n>l(\mu)+8$ we get $n<n-8$ which
is impossible. Now suppose that $f(x)$ is to the right of $f(i_{n-1})$. Since
$f(x)$ is adjacent to all vertices in $\\{f(1),\ldots,f(n-1)\\}$ it is
adjacent to $f(i_{n-2})$ and $f(i_{n-1})$. It follows that $\mu(f(x))=0$. Thus
$f(x)$ is adjacent to $f(i_{0})$, hence $x$ is adjacent to $i_{0}$ in $H$. A
contradiction. This proves that our supposition $H$ embeds into $G_{\mu}$ is
false. ∎

A vertex $x$ of a graph $G$ is $-1$-_extremal_ if either $x$ is not adjacent
to at most one vertex of $V(G)\setminus\\{x\\}$ or if $x$ is adjacent to at
most one vertex of $V(G)\setminus\\{x\\}$. Note that if $x$ is $-1$-extremal
in $G$, then $x$ is also $-1$-extremal in $\overline{G}$.

######  Lemma 88.

Let $\mathcal{C}$ be a hereditary class of finite graphs which is
$1^{-}$-well-quasi-ordered. Then $\mathcal{C}$ has only finitely many bounds
having a $-1$-extremal vertex.

###### Proof.

Since $\mathcal{C}$ is w.q.o. there are only finitely many bounds of
$\mathcal{C}$ having a vertex adjacent to all other vertices. Let
$(G_{n})_{n\in{\mathbb{N}}}$ be a sequence of bounds of $\mathcal{C}$ such
that each $G_{n}$ has a $-1$-extremal vertex $x_{n}$. We may suppose that
there is a unique vertex $y_{n}$ distinct from $x_{n}$ and not adjacent to
$x_{n}$. Let $H_{n}:={G_{n}}_{\restriction V(G_{n})\setminus\\{x_{n}\\}}$.
Since $\mathcal{C}$ is $1^{-}$-well-quasi-ordered from the sequence
$(H_{n},y_{n})$ we can extract an increasing subsequence. Clearly, if
$(H_{n},y_{n})$ embeds into $(H_{m},y_{m})$, then $G_{n}$ embeds into $G_{m}$.
This contradicts the fact that $\\{G_{n}:n\in{\mathbb{N}}\\}$ forms an
antichain. ∎

######  Corollary 89.

Let $\mu$ be a periodic $0$-$1$ sequence on ${\mathbb{N}}$. Then there are
only finitely many bounds of $\operatorname{Age}(G_{\mu})$ having a
$-1$-extremal vertex.

###### Proof.

Follows from Lemma 88 and the fact that $\operatorname{Age}(G_{\mu})$ is
$1^{-}$-well-quasi-ordered. ∎

######  Lemma 90.

Let $\mu$ be a periodic $0$-$1$ sequence on ${\mathbb{N}}$. Then the number of
non prime bounds of $\operatorname{Age}(G_{\mu})$ is finite.

###### Proof.

Let $(G_{n})_{n\in{\mathbb{N}}}$ be a sequence of bounds of
$\operatorname{Age}(G_{\mu})$. Suppose $G_{n}$ is not prime. Let $M_{n}$ be a
nontrivial module of $G_{n}$ and $x_{n}$ any vertex of $M_{n}$. Let
$H_{n}:={G_{n}}_{\restriction(V(G_{n})\setminus M_{n})\cup\\{x_{n}\\}}$. Since
$M_{n}$ is nontrivial and $G_{n}$ is a bound we infer that $H_{n}$ and $M_{n}$
are elements of $\operatorname{Age}(G_{\mu})$. Since
$\operatorname{Age}(G_{\mu})$ is w.q.o there exists an infinite subset $I$ of
${\mathbb{N}}$ so that the sequence $({G_{n}}_{\restriction M_{n}})_{n\in I}$
is increasing with respect to embeddability. Since
$\operatorname{Age}(G_{\mu})$ is $1^{-}$-well-quasi-ordered we infer that we
can extract from the sequence $(H_{n},x_{n})_{n\in I}$ an increasing
subsequence. Then note that if $(H_{n},x_{n})$ embeds into $(H_{m},x_{m})$ and
$M_{n}$ embeds into $M_{m}$, then $G_{n}$ embeds into $G_{m}$. ∎

We now prove $(2)$ of Theorem 47. Let $\mu$ be a non constant and periodic
$0$-$1$ sequence on ${\mathbb{N}}$ and let $H$ be a bound of $G_{\mu}$. It
follows from Lemma 90 that we may assume that $H$ is prime. Since the examples
of critically prime graphs of Schmerl and Trotter [63] split into two totally
ordered sets with respect to embeddability we may assume that $H$ is not
critically prime. There exists then $x\in V(H)$ such that $H\setminus\\{x\\}$
is prime. Since $H$ is a bound of $G_{\mu}$ we infer that $H\setminus\\{x\\}$
embeds into $G_{\mu}$. Let $f_{x}$ be such an embedding. We write
$f_{x}(V(H\setminus\\{x\\}):=\\{i_{0},i_{1},\ldots,i_{n}\\}$ so that
$i_{0}<i_{1}<\ldots<i_{n}$. Since $H\setminus\\{x\\}$ is prime it follows from
Corollary 57 that $\\{i_{1},\ldots,i_{n}\\}$ is an interval of ${\mathbb{N}}$.
Since $\mu$ is periodic $\l(\mu)$ is finite. For $n>l(\mu)+5$,
${G_{\mu}}{\restriction\\{i_{1}<\ldots<i_{n}\\}}$ is prime, hence
$H\setminus\\{x,f_{x}^{-1}(i_{0})\\}$ is prime. We may assume that
$\mu(i_{n})=0$ (if not consider $\overline{G_{\mu}}=G_{\overline{\mu}}$ and
$\overline{H}$ and note that $\overline{\mu}$ is also periodic). By Lemma 88
we may assume that $H$ has no $-1$-extremal vertices. It follows that
$\\{x,f_{x}^{-1}(i_{n})\\}$ is not an edge of $H$ (otherwise
$f_{x}^{-1}(i_{n})$ is $-1$-extremal in $H$). We now consider the graph
$H\setminus\\{f_{x}^{-1}(i_{0})\\}$. Let $g_{i_{0}}$ be an embedding of
$H\setminus\\{f_{x}^{-1}(i_{0})\\}$ into $G_{\mu}$. For $1\leq k\leq n$, we
define $i^{\prime}_{k}:=g_{i_{0}}(f^{-1}_{x}(i_{k}))$.

Suppose $n>l(\mu)+7$. It follows then from Proposition 73 that every embedding
of $H\setminus\\{f_{x}^{-1}(i_{0})\\}$ in $G_{\mu}$ maps
$\\{i^{\prime}_{2},\ldots,i^{\prime}_{n}\\}$ into an interval and in that
order. Hence, such an embedding agree with $f_{x}$ and $g_{i_{0}}$. From our
assumption that $\mu(i_{n})=0$ and $\\{x,f_{x}^{-1}(i_{n})\\}$ is not an edge
of $H$ we deduce that $g_{i_{0}}(x)$ is to the right of $i^{\prime}_{n}$.
Indeed, if $g_{i_{0}}(x)$ is to the left of $i^{\prime}_{n}$, then since
$\mu(i^{\prime}_{n})=\mu(i_{n})=0$ we infer that $g_{i_{0}}(x)$ is on the left
of $i^{\prime}_{3}$. But then $\\{g_{i_{0}}(x),i^{\prime}_{n}\\}$ is an edge,
therefore $\\{x,f_{x}^{-1}(i_{0})\\}$ is an edge of $H$ hence $x$ is
$-1$-extremal, which is not possible . Thus, $g_{i_{0}}(x)$ is to the right of
$i^{\prime}_{n}$. It follows then that $g_{i_{0}}(x)$ is either adjacent to
all vertices in $\\{i^{\prime}_{1},\ldots,i^{\prime}_{n-1}\\}$ or adjacent to
none. This last case is not possible, otherwise $x$ would be $-1$-extremal. So
we are left with the case that $g_{i_{0}}(x)$ is adjacent to all vertices in
$\\{i^{\prime}_{1},\ldots,i^{\prime}_{n-1}\\}$. Since $x$ is not
$-1$-extremal, $x$ is adjacent to all vertices of
$H\setminus\\{f_{x}^{-1}(i_{0}),f_{x}^{-1}(i_{n})\\}$ and not adjacent to
either $f^{-1}(i_{0})$ or $f^{-1}(i_{n})$. It follows from Lemma 87 that
$H\setminus\\{i_{n}\\}$ does not embed into $G_{\mu}$. This contradicts our
assumption that $H$ is a bound of $\operatorname{Age}(G_{\mu})$.

##  12\. Conclusion

This work on hereditary classes of finite graphs containing relatively few
primes put a light on hereditary classes which are well-quasi-ordered and also
on those made of permutation graphs. The result of [18] was crucial in proving
that our list of hereditary classes of graphs which are minimal prime was
complete. Kim [31] obtained for tournaments a result similar to Chudnovski and
al [18]. It remains to see if similar results to ours can be obtained in the
case of tournaments; and also, if they shed light on the case of binary
relations and binary relational structures and allow to solve the problems
mentioned in the text about minimal prime hereditary classes. Among question
which interest us are first the rank of minimal prime classes of permutation
graphs; in this respect note that it is unknown if there are hereditary well-
quasi-ordered classes of graphs with arbitrary countable rank (see [56]).
Next, the question to know wether or not well-quasi- ordered hereditary
classes of finite graphs are better-quasi-ordered.
A consequence of our study is the existence of an uncountable antichain of
well-quasi-ordered ages of permutation graphs. The existence of uncountably
many well-quasi-ordered ages of binary structures was obtained in 1978 [51].
This was obtained by means of a coding via uniformly recurrent sequences. The
same existence for graphs, permutation graphs or posets, is a non trivial fact
which requires work. The same coding than the one we use in this paper was
used first in 1992 [65] and in 2002 [66]. In Chapter 5 of [45] the first
author proved with a simpler coding the existence of uncountably many
hereditary classes of oriented graphs which are minimal prime. We conclude by
mentioning the existence of uncountably many well-quasi-ordered ages of
permutation graphs with distinct enumeration functions (alias profile) due to
Brignall and Vatter [11].

## Acknowledgements

The authors would like to sincerely thank Robert Brignall for bringing to
their attention several informations, notably on pin sequences and labelled
classes of permutations.

## References

  * [1] M.H. Albert and M.D. Atkinson,  Simple permutations and pattern restricted permutations. Discrete Mathematics, 300 (2005) 1–15.
  * [2] M.H. Albert, M.D. Atkinson and M. Klazar,  The enumeration of simple permutations. Journal of integer sequences, Vol. 6 (2003), Article 03.4.4.
  * [3] M.H. Albert, M.D. Atkinson and V. Vatter,  Subclasses of the separable permutations. London Mathematical Society, Volume 43, Issue 5 (2011), Pages 859–870.
  * [4] J.-Paul Allouche and J. Shallit, _Automatic Sequences: Theory, Applications, Generalizations._ Cambridge University Press. (2003). ISBN 978-0-521-82332-6.
  * [5] R. Assous, M. Pouzet, _Jónsson posets,_ Algebra Universalis, 79 (2018) no. 3, Art. 74, 26 pp.
  * [6] Y. Bar-Hillel, M. A. Perles and E. Shamir, _On formal properties of simple phrase structure grammars_ , Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (1961), 143–172.
  * [7] D. Beauquier and M. Nivat, _About rational sets of factors of a bi-infinite word._ Automata, languages and programming (Nafplion, 1985), 33–42, Lecture Notes in Comput. Sci., 194, Springer, Berlin, 1985.
  * [8] V. Berthé and M. Rigo, eds. (2010). _Combinatorics, automata, and number theory._ Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9.
  * [9] Y. Boudabbous, M. Pouzet, _The morphology of infinite tournaments; application to the growth of their profile_. European J. Combin. 31 (2010), no. 2, 461–481.
  * [10] R. Brignall, V. Vatter, _Labelled Well-Quasi-Order for Permutation Classes_ , arXiv:2103.08243 [math.CO] 14 May 2022, 48 pp
  * [11] R. Brignall, V. Vatter, _Uncountably Many Enumerations of Well-Quasi-Ordered Permutation Classes_. In preparation, May 2022.
  * [12] R. Brignall, Private communication, May 20, 2022.
  * [13] R. Brignall, _Simplicity in relational structures and its application to permutation classes_ , PhD Thesis, University of St Andrews, October 25, 2007.
  * [14] R. Brignall, M. Engen and V. Vatter, _A Counterexample Regarding Labelled Well-Quasi-Ordering_ , Graphs and Combinatorics, 34 (2018), 1395–1409.
  * [15] R. Brignall,  A survey of simple permutations. Permutation patterns.  41–65, London Math. Soc. Lecture Note Ser., 376, Cambridge Univ. Press, Cambridge, 2010.
  * [16] P.J. Cameron, _Homogeneous permutations, Permutation patterns_ (Otago, 2003). Electron. J. Combin. 9 (2002/03), no. 2, Research paper 2, 9 pp.
  * [17] R. Carroy, Y. Pequignot, _From well to better, the space of ideals_ , Fund. Math. 227 (2014), no. 3, 247–270.
  * [18] M. Chudnovsky and R. Kim and S. Oum and P. Seymour, _Unavoidable induced subgraphs in large graphs with no homogeneous sets_ , Journal of Combinatorial Theory, Series B 118 (2016), 1–12.
  * [19] B. Dushnik and E.W. Miller, _Partially ordered sets_ , Amer. J. Math. 63 (1941), 600–610.
  * [20] C. Delhommé, _Nicely BQO grounded categories and $2$-structures_, preprint, 2014.
  * [21] 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.
  * [22] R. Fraïssé,  On a decomposition of relations which generalizes the sum of ordering relations. Bull. Amer. Math. Soc., 59:389, 1953.
  * [23] 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.
  * [24] R. Fraïssé, _L’intervalle en théorie des relations, ses généralisations, filtre intervallaires et clôture d’une relation._ , Annals of Discrete Math 23 (1984), 313–341, In ”Orders, description and roles”. Pouzet. M and Richard. D.,éd. (L’Arbresle, 1982), 313–341, North-Holland Math. Stud., 99, North-Holland, Amsterdam, 1984.
  * [25] T. Gallai, _Transitiv orientierbare 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, pp. 25–66).
  * [26] G. Higman, _Ordering by divisibility in abstract algebras_. Proc. London Math. Soc. 3 (1952), 326–336.
  * [27] P. Ille, _Indecomposable graphs_ , Discrete Math, 173 (1997) 71–78.
  * [28] K. Kearnes, G. Oman, _Jónsson posets and unary Jónsson algebras,_ Algebra Universalis 69 (2013), no. 2, 101–112.
  * [29] D. Kelly, _Comparability graphs_ , in Graphs and Orders, I.Rival ed., NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 147 (1985), 3–40.
  * [30] D. Kelly, _The $3$-irreducible partially ordered sets_, Can. J. Math., Vol. XXIX, No. 2 (1977), 367–383.
  * [31] R. Kim, Unavoidable subtournaments in large tournaments with no homogeneous sets. SIAM J. Discrete Math. 31 (2017), no. 2, 714–725.
  * [32] M. Klazar, _Overview of general results in combinatorial enumeration_ , in Permutation patterns, London Math. Soc. Lecture Note Ser., 376, (2010), 3–40, Cambridge Univ. Press, Cambridge.
  * [33] N. Korpelainen, V. Lozin and I. Razgon, _Boundary Properties of Well-Quasi-Ordered Sets of Graphs_ , Order 30 (2013), 723–735.
  * [34] N. Korpelainen and V. Lozin, _Bipartite Induced Subgraphs and Well-Quasi-Ordering_ , J Graph Theory 67 (2011), 235–249.
  * [35] R. Laver, _On Fraïssé’s order type conjecture_ , Ann. of Math. (2) 93 (1971) 89–111.
  * [36] M. Lothaire. _Finite and Infinite Words_. Algebraic Combinatorics on Words. Cambridge University Press. 2002.
  * [37] V. Lozin and R. Gábor, _Minimal universal bipartite graphs_ , Ars Combin. 84 (2007), 345–356.
  * [38] V. Lozin and C. Mayhill, _Canonical Antichains of Unit Interval and Bipartite Permutation Graphs_ , Order 28 (2011), 513–522.
  * [39] E.C. Milner, _Basic wqo- and bqo-theory_ , Graphs and order (Banff, Alta., 1984), 487–502, NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 147, Reidel, Dordrecht, 1985.
  * [40] F. Maffray, M. Preissmann, _A translation of Gallai’s paper: ’Transitiv Orientierbare Graphen’_ , In: Perfect Graphs (J. L. Ramirez-Alfonsin and B. A. Reed, Eds.), Wiley, New York, 2001, pp. 25–-66.
  * [41] A. Marcus, G. Tardös  Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory, Ser. A 107 (2004), 153–160.
  * [42] M. Malliaris, C. Terry, _On unavoidable-induced subgraphs in large prime graphs_. J. Graph Theory 88 (2018), no. 2, 255–270
  * [43] G. A. McKay, _On better-quasi-ordering classes of partial orders_ , 56pp. to appear in part 1 of the special issue of the Journal of Multiple-Valued Logic and Soft Computing dedicated to Ivo Rosenberg and edited by Miguel Couceiro, and Lucien Haddad.
  * [44] C.St.J.A. Nash-Williams,  _On well-quasi-ordering infinite trees_ ,  Proc., Phil, Soc., 61 (1965), 697–720.
  * [45] 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 sept. 2015, ArXiv:1604.05839.
  * [46] D. Oudrar, M. Pouzet,  Profile and hereditary classes of relational structures, Proceedings ISOR’11, International Symposium on Operational Research, Algiers , Algeria , May 30-June 2, 2011, H.Ait Haddadene, I.Bouchemakh, M.Boudar, S.Bouroubi (Eds) LAID3.
  * [47] D. Oudrar, M. Pouzet, _Profile and hereditary classes of relational structures_ , J. of MVLSC Volume 27, Number 5-6 (2016), 475–500.
  * [48] M. Petkovs̆ek, _Letter graphs and well-quasi-order by induced subgraphs_ , Discrete Mathematics 244 (2002), 375–388.
  * [49] 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. (electronic).
  * [50] M. Pouzet, _Un bel ordre d’abritement et ses rapports avec les bornes d’une multirelation_ , C.R. Acad. Sci. Paris Série A-B 274 (1972), A1677–A1680.
  * [51] M. Pouzet,  Sur la théorie des relations, Thèse d’État, Université Claude-Bernard, Lyon 1, 1978.
  * [52] M. Pouzet, _Relation minimale pour son âge_ , Z. Math. Logik Grundlag. Math., 25 (1979), 315–344.
  * [53] M. Pouzet, Relations impartibles, Dissertationnes,  103 (1981), 1–48.
  * [54] 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.
  * [55] M. Pouzet, M. Sobrani, _Sandwiches of ages._ Proceedings of the XIth Latin American Symposium on Mathematical Logic (Mérida, 1998). Ann. Pure Appl. Logic 108 (2001), no. 1-3, 295–326.
  * [56] M. Pouzet, M. Sobrani, _The order type of the collection of finite series-parallel posets._ Discrete Math. 265 (2003), no. 1-3, 189–211.
  * [57] M. Pouzet, H. Si Kaddour, N. Zaguia, _Which posets have a scattered MacNeille completion?_ Algebra Universalis 53 (2005), no. 2-3, 287–299.
  * [58] M. Pouzet, _The profile of relations_. Glob. J. Pure Appl. Math. 2 (2006), no. 3, 237–272.
  * [59] M. Pouzet and I. Zaguia, _Graphs containing finite induced paths of unbounded length_ , Discrete Mathematics and Theoretical Computer Science DMTCS vol. 23 :2, 2021, #3.
  * [60] M. Pouzet and I. Zaguia, _Hereditary classes of ordered sets coverable by two chains_ , arXiv, https://arxiv.org/abs/2112.02633.
  * [61] M. Pouzet and I. Zaguia, _On Minimal Prime Graphs and Posets_ , Order 16 (2009), 357–375.
  * [62] N. Pytheas Fogg, V. Berthé, S. Ferenczi, C. Mauduit, A. Siegel, eds. _Substitutions in dynamics, arithmetics and combinatorics._ Lecture Notes in Mathematics. 1794. Springer-Verlag Berlin Heidelberg 2002. Softcover ISBN 978-3-540-44141-0.
  * [63] J.H. Schmerl, W.T. Trotter,  Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113 (1-3) (1993) 191–205.
  * [64] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A111111.
  * [65] M. Sobrani, _Structure d’ordre de la collection des âges de relations_ , Thèse de doctorat, Université Claude-Bernard, Lyon, 18 déc. 1992.
  * [66] 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, January 2002.
  * [67] E. Szpilrajn, Sur l’extension de l’ordre partiel, Fund. Math., 16 (1930), 386–389.
  * [68] S. Thomassé, _On better quasi ordering countable series-parallel orders_ , Trans. Amer. Math Soc. 352 (no 6) (1999), 2491–2505.
  * [69] W.T. Trotter, and J.I. Moore, Jr., _Characterization problems for graphs, partially ordered sets, lattices, and families of sets_ , Discrete Mathematics 16 (1976)361–381.
  * [70] V. Vatter. _Permutation classes._ In Handbook of Enumerative Combinatorics , pages 754–833. CRC Press, 2015.
  * [71] I. Zverovich, _Extension of hereditary classes with substitutions_ , Discrete Appl.Math., 128(2-3):487–509, 2003.