# Asymptotic Theories of Classes Defined by
Forbidden Homomorphisms

Manuel Bodirsky111Institut für Algebra, TU Dresden, Colin Jahel222Carnegie
Mellon University

###### Abstract

We study the first-order almost-sure theories for classes of finite structures
that are specified by homomorphically forbidding a set $\mathcal{F}$ of finite
structures. If $\mathcal{F}$ consists of undirected graphs, a full description
of these theories can be derived from the Kolaitis-Prömel-Rothschild theorem,
which treats the special case where $\mathcal{F}=\\{K_{n}\\}$. The
corresponding question for finite sets $\mathcal{F}$ of finite directed graphs
is wide open. We present a full description of the almost-sure theories of
classes described by homomorphically forbidding finite sets $\mathcal{F}$ of
oriented trees; all of them are $\omega$-categorical. In our proof, we
establish a result of independent interest, namely that every constraint
satisfaction problem for a finite digraph has first-order convergence, and
that the corresponding asymptotic theory can be described as a finite linear
combination of $\omega$-categorical theories.

##  1 Introduction

A famous result of Glebskij, Kogan, Ligonskij, and Talanov [22] and Fagin [7]
states that the almost-sure theory $T_{\mathcal{G}}$ of the class
$\mathcal{G}$ of all finite undirected graphs is _complete_ , i.e., every
first-order property of graphs holds asymptotically almost surely, or its
negation holds asymptotically almost surely (this is sometimes referred to as
a _first-order 0-1 law_). Moreover, $T_{\mathcal{G}}$ is _$\omega$
-categorical_, i.e., it has exactly one countable model up to isomorphism, the
so-called _Rado graph_ [20], which is of fundamental importance in model
theory and can be described as the Fraïssé-limit of the class of all finite
graphs [10].

If instead of ${\mathcal{G}}$ we consider the class ${\mathcal{G}}_{3}$ of all
finite _triangle-free_ graphs, i.e., finite graphs that do not contain a
$K_{3}$ subgraph, we still get a first-order 0-1 law, and the resulting
almost-sure theory again has a single countably infinite model $M_{3}$.
However, somewhat surprisingly, this model is _not_ the Fraïssé-limit of the
class of all finite undirected triangle-free graphs: Erdős, Kleitman, and
Rothschild [5] proved that if $n$ tends to infinity, almost all triangle-free
graphs with $n$ vertices are _bipartite_ , i.e., have a homomorphism to
$K_{2}$. Clearly, there are triangle-free graphs $G$ without a homomorphism to
$K_{2}$ (e.g., the cycle with five vertices, $C_{5}$). The structure $M_{3}$
does not contain copies of $G$, and hence $M_{3}$ is not the Fraïssé-limit of
the class of all finite triangle-free graphs.

The mentioned result about triangle-free graphs has been generalised by
Kolaitis, Prömel, and Rothschild [12] to the class of finite graphs without a
copy of $K_{n}$, for every $n\geq 3$. Similarly as in the case of $K_{3}$,
they prove that $K_{n}$-free graphs are asymptotically almost surely
$(n-1)$-partite. In subsequent work, similar results have been obtained by
Prömel and Steger [19] for some classes of finite graphs that that are given
by forbidding some graph $H$ as a _(weak) subgraph_.

If a graph class is specified by forbidding a set $\mathcal{F}$ of finite
graphs _homomorphically_ , rather than forbidding them as (induced or weak)
subgraphs, then the almost-sure theory of the class

$\operatorname{Hom-Forb}(\mathcal{F}):=\\{G\in{\mathcal{G}}\mid\text{no
}F\in{\mathcal{F}}\text{ has a homomorphism to }G\\}$

can be described completely (Theorem 2). The difference between subgraphs and
homomorphisms is irrelevant if $\mathcal{F}=\\{K_{n}\\}$, because $K_{n}$ has
a homomorphism to a graph $G$ if and only if $K_{n}$ is isomorphic to an
(induced) subgraph of $G$. Quite remarkably, one can obtain a complete
description for every set $\mathcal{F}$ of finite graphs (even if
$\mathcal{F}$ is infinite). Let $\chi(G)$ be the _chromatic number_ of $G$,
i.e., the smallest $n$ such that $G$ has a homomorphism to $K_{n}$. If
$\mathcal{F}=\emptyset$ then $\operatorname{Hom-
Forb}(\mathcal{F})=\mathcal{G}$ and the almost-sure theory is the theory of
the Rado graph [20]. For non-empty $\mathcal{F}$, define
$k_{\mathcal{F}}:=\min_{G\in{\mathcal{F}}}\chi(G)$. We show in Section 3 that
the almost-sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$ is
asymptotically almost surely $(k_{\mathcal{F}}-1)$-partite. It then follows
that $\operatorname{Hom-Forb}(\mathcal{F})$ satisfies a first-order 0-1 law
and that the almost-sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$ is
$\omega$-categorical and has an up to isomorphism unique countable model.

The class $\operatorname{Hom-Forb}(\mathcal{F})$ has also been studied in
model theory; Cherlin, Shelah, and Shi [3] showed that there exists an (up to
isomorphism unique) countable model-complete structure $M_{\mathcal{F}}$ whose
_age_ equals $\operatorname{Hom-Forb}(\mathcal{F})$, i.e., a finite graph $G$
embeds into $M_{\mathcal{F}}$ if and only if no structure in $\mathcal{F}$
homomorphically maps to $G$. However, if $k_{\mathcal{F}}>2$ then
$\operatorname{Hom-Forb}(\mathcal{F})$ contains graphs that are not
$(k_{\mathcal{F}}-1)$-colorable, and hence this model is does _not_ satisfy
the almost-sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$ (unless
$\mathcal{F}=\emptyset$).

If $\mathcal{F}$ is a set of finite _directed_ graphs, then must less is known
about the almost-sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$, even
if $\mathcal{F}$ is finite. Some results have been obtained recently by Kühn,
Osthus, Townsend, and Zhao [14] for $\operatorname{Hom-Forb}(T_{3})$ and
$\operatorname{Hom-Forb}(C_{3})$, where $T_{3}$ is the transitive tournament
with three vertices and $C_{3}$ is the directed cycle with three vertices,
answering questions that have been raised in model theory [4]. In particular,
they proved that asymptotically almost surely the graphs in
$\operatorname{Hom-Forb}(T_{3})$ are bipartite. It is easy to come up with
infinite sets ${\mathcal{F}}$ of finite digraphs such that $\operatorname{Hom-
Forb}({\mathcal{F}})$ does not have a 0-1 law (see Example 3).

###  1.1 Our Results

We present a full description of the almost-sure theories of classes of
structures described by forbidding finitely many orientations of finite trees;
all of these classes have a 0-1 law and even an $\omega$-categorical almost-
sure theory (Theorem 3). To prove this, we show a result that is of
independent interest: For every finite digraph $G$ the CSP of $G$ satisfies a
first-order convergence law, and the asymptotic theory of the CSP is linearly
composed from finitely many $\omega$-categorical 0-1 laws. This result and
some others generalise from digraphs to general relational structures. For
concreteness and clarity of presentation, we focus on the case of graphs and
digraphs in this article.

###  1.2 Connection with Database Theory

Note that sets ${\mathcal{F}}$ of finite structures that are homomorphically
forbidden can be interpreted from a database perspective: each structure
$\mathfrak{F}\in{\mathcal{F}}$ can be viewed as a so-called _conjunctive
query_ $\phi$, by turning the elements of the structure into existentially
quantified variables and the relations of the structure into a conjunction of
atomic formulas. Conjunctive queries are the most important class of queries
encountered in database theory. An important and intensively studied subclass
of conjunctive queries are _acyclic_ conjunctive queries; see [16]. It is
well-known and easy to see that a finite structure $\mathfrak{B}$ (i.e., a
_database_) satisfies $\phi$ if and only if $\mathfrak{F}$ has a homomorphism
into $\mathfrak{B}$; see [2]. Results about $\operatorname{Hom-
Forb}({\mathcal{F}})$ can then be interpreted as statements about the uniform
distribution on finite structures that do _not_ satisfy the given set of
conjunctive queries.

###  1.3 Connection with Model Theory

The $\omega$-categorical theories that arise in our main result, Theorem 3, as
almost-sure theories for classes defined by a finite set of homomorphically
forbidden orientations of finite trees, are interesting from a model-theoretic
point of view, since they are _pseudo finite_ : every finite subset of the
theory has a finite model. An example of a pseudo-finite theory is the theory
of the random graph, which follows from the fact that its first-order theory
equals the almost-sure theory of finite undirected graphs. A class of theories
whose pseudo-finiteness can be shown similarly was isolated by Kruckman [13].
Showing that a theory is pseudo finite can be quite challenging. It is a major
open question whether the Fraïssé-limit of the class of all finite triangle-
free graphs has a pseudo-finite theory (see, e.g., [6]). The mentioned result
of Erdős, Kleitman, and Rothschild shows that this problem cannot be
approached via almost sure theories of finite structures in the same way as
for the random graph.

##  2 Preliminaries

A _digraph_ $D$ is a pair $(V,E)$ consisting of a set of _vertices_ $V(D)=V$
and a set $E(D)=E\subseteq V^{2}$ of _edges_. We write

  * •

$T_{k}$ for the transitive tournament on $k$ vertices, i.e., the digraph
$(\\{1,\dots,k\\};<)$ where $<$ denotes the usual strict linear order on
$\\{1,\dots,k\\}$.

  * •

$\vec{P}_{k}$ for the directed path of length $k$, i.e., the digraph

$(\\{1,\dots,k\\};\\{(1,2),(2,3),\dots,(k-1,k)\\}).$

  * •

$\vec{C}_{k}$ for the directed cycle of length $k$, i.e., the digraph

$(\\{0,1,\dots,k-1\\},\\{(u,v)\mid u=v+1\mod k\\}).$

A digraph is _symmetric_ if $(x,y)\in E$ implies $(y,x)\in E$ for all $x,y\in
V$ and _irreflexive_ if $(x,x)\notin E$ for every $x\in V$. If $G$ is a
digraph and $v\in V(G)$, then we write $G-v$ for the digraph
$(V(G)\setminus\\{v\\},E(G)\cap(V(G)\setminus\\{v\\})^{2})$.

An _undirected graph_ $G$ is a pair $(V,E)$ where $V$ is a set of vertices and
$E$ is a set of 2-element subsets of $V$. There is an obvious bijection
between undirected graphs with vertices $V$ and irreflexive symmetric digraphs
with vertices $V$. We write $K_{n}$ for the undirected graph with vertex set
$V=\\{1,\dots,n\\}$ whose edge set consists of _all_ 2-element subsets of $V$.
If $G$ is an undirected graph, then an _orientation of $G$_ is a digraph $O$
such that $(x,y)\in E(O)$ implies $\\{x,y\\}\in E(G)$ and for every
$\\{x,y\\}\in E(G)$ either $(x,y)\in E(O)$ or $(y,x)\in E(O)$, but not both.
An _oriented graph_ is an orientation of some undirected graph (i.e., an
irreflexive digraph whose edge relation is antisymmetric).

###  2.1 Almost Sure Theories

Let $\mathcal{C}$ be an isomorphism-closed class of finite (directed or
undirected) graphs and let $\mathcal{C}_{n}$ be the set of graphs from
$\mathcal{C}$ with vertices $\\{1,\ldots,n\\}$. Graphs with vertex set
$\\{1,\dots,n\\}$ for some $n\in{\mathbb{N}}$ will also be called _labelled_.

We consider _first-order logic over graphs_. An _atomic formula_ is an
expression of the form $E(x,y)$, of the form $x=y$, or of the form $\bot$ (for
_false_) for some variables $x,y$. First-order formulas (over graphs) are
built from atomic formulas by the usual Boolean connectives and universal and
existential quantification. Let $\phi$ be a first-order sentence. We write
$G\models\phi$ if $G$ satisfies $\phi$ in the usual sense. Define

$\phi_{n}^{\mathcal{C}}:=\frac{|\\{G\in{\mathcal{C}}_{n}\mid
G\models\phi\\}|}{|{\mathcal{C}}_{n}|}.$

If $\lim_{n\to\infty}\phi^{\mathcal{C}}_{n}$ exists, we denote the limit by
$\phi_{\omega}^{\mathcal{C}}$. If this limit exists for every first-order
sentence $\phi$, then we say that ${\mathcal{C}}$ has _first-order
convergence_.

If $\phi_{\omega}^{\mathcal{C}}=1$ we say that _$\phi$ holds in
${\mathcal{C}}$ asymptotically almost surely_. More generally, a property $P$
holds _asymptotically almost surely in ${\mathcal{C}}$_ if the fraction of
structures in ${\mathcal{C}}_{n}$ that has the property $P$ tends to one as
$n$ tends to infinity.

The _almost sure theory of ${\mathcal{C}}$_ is the set of first-order
$\tau$-sentences $\phi$ such that $\phi^{\mathcal{C}}_{\omega}=1$ and denoted
by $T_{\mathcal{C}}$. We say that ${\mathcal{C}}$ has a first-order 0-1 law if
$T_{\mathcal{C}}$ is a complete theory, i.e., for every first-order sentence
$\phi$ either $\phi\in T_{\mathcal{C}}$ or $\neg\phi\in T_{\mathcal{C}}$.

###  2.2 Graph Homomorphisms Background

If $G$ and $H$ are digraphs, then a _homomorphism_ from $G$ to $H$ is a map
$h\colon V(G)\to V(H)$ such that for all $(x,y)\in E(G)$ we have
$(h(x),h(y))\in E(H)$. We write $G\to H$ if there exists a homomorphism from
$G$ to $H$, and otherwise we write $G\not\to H$. Two graphs $G$ and $H$ are
called _homomorphically equivalent_ if $G\to H$ and $H\to G$. We write
$\operatorname{CSP}(H)$ (for _constraint satisfaction problem_) for the class
of all finite digraphs $G$ with a homomorphism to $H$. If $\mathcal{F}$ is a
set of graphs, then we write $\operatorname{Hom-Forb}(\mathcal{F})$ for the
class of finite digraphs $G$ such that no digraph in $\mathcal{F}$ maps
homomorphically to $G$. It is easy to see that for every digraph $H$ there
exists a set of finite digraphs ${\mathcal{F}}$ such that
$\operatorname{CSP}(H)=\operatorname{Hom-Forb}({\mathcal{F}})$. We write
$G_{1}\times G_{2}$ for the graph with vertices $V(G_{1})\times V(G_{2})$ and
edges $\\{((a_{1},a_{2}),(b_{1},b_{2}))\mid(a_{1},a_{2})\in
E(G_{1}),(a_{2},b_{2})\in E(G_{2})\\}$. We write $G^{2}$ instead of $G\times
G$.

A homomorphism from $H$ to $H$ is called an _endomorphism of $H$_. Note that
if $H$ is finite and if $h$ is a bijective endomorphism of $H$, then the
inverse $h^{-1}$ of $h$ is also an endomorphism, and $h$ is called an
_automorphism of $H$_. The set of all automorphisms of $H$ forms a group with
respect to composition and is denoted by $\operatorname{Aut}(H)$. An _orbit_
of $\operatorname{Aut}(H)$ is a set of the form
$\\{\alpha(a)\mid\alpha\in\operatorname{Aut}(H)\\}$ for some $a\in V(H)$. A
finite digraph $H$ is called a _core_ if all endomorphisms of $H$ are
automorphisms. It is easy to see that every finite digraph $G$ is
homomorphically equivalent to a finite core digraph $H$, and that this core
digraph is unique up to isomorphism [9], and will be called _the_ core of $H$.

All these definitions work analogously also for undirected graphs instead of
digraphs. Note that the definitions apply in particular to symmetric and
irreflexive digraphs $H$, and the definition for undirected graphs and the
corresponding symmetric and irreflexive digraphs is usually equivalent, via
the mentioned bijection. However, note that if $H$ is a symmetric and
irreflexive digraph, then $\operatorname{CSP}(H)$ might contain digraphs that
are not symmetric, whereas if $H$ is an undirected graph, then
$\operatorname{CSP}(H)$ by definition only contains undirected graphs.
Likewise, if $\mathcal{F}$ is a set of undirected graphs then
$\operatorname{Hom-Forb}(\mathcal{F})$ (defined in the introduction) denotes a
class of undirected graphs.

A _tree_ is a connected undirected graph without cycles. We later need the
following result of Nešetřil and Tardif ([18]; see Theorem 2.4.4 in [8].

######  Theorem 1.

For every finite non-empty set of orientations of finite trees $\mathcal{F}$
there exists a finite digraph $D=(V,E)$ such that $\operatorname{Hom-
Forb}({\mathcal{F}})=\operatorname{CSP}(D)$.

Clearly, we may additionally require that the finite digraph $D$ from Theorem
1 is a core, and with this assumption the structure $D$ is unique up to
isomorphism, and called _the dual_ of $\mathcal{F}$.

######  Example 1.

For $k\geq 1$, if $\mathcal{F}=\\{\vec{P}_{k+1}\\}$, then we have
$\operatorname{Hom-Forb}(\mathcal{F})=\operatorname{CSP}(\vec{P}_{k})$.

A first-order formula $\phi(x_{1},\dots,x_{k})$ is called _primitive positive_
if it has the form

$\exists y_{1},\dots,y_{n}(\psi_{1}\wedge\cdots\wedge\psi_{m})$

for some atomic formulas $\psi_{1},\dots,\psi_{m}$ over the variables
$x_{1},\dots,x_{k},y_{1},\dots,y_{n}$. Existential positive formulas are
disjunctions of primitive positive formulas. A first-order formula is called
_existential_ (_universal_) if does not contain universal (existential)
quantifiers and all negation symbols appear in front of atomic formulas; note
that every existential positive formula is existential. The following is well-
known; see, e.g., [1].

######  Lemma 1.

Let $D$ be a finite core digraph and $u\in V(D)$. Then the orbit of $u$ in
$\operatorname{Aut}(D)$ has a primitive positive definition in $D$.

The _conjunctive query_ of a digraph $D$ is the primitive positive formula
$\phi$ defined as follows: the variables of $\phi$ are the vertices of $D$,
and for every edge $(x,y)\in E(D)$ we add a conjunct $E(x,y)$ to $\phi$.

###  2.3 Model Theory Background

Many results about the first-order logic of graphs hold more generally also
for first-order logic over general relational structures; and in fact, this
more general setting of relational structures will also be convenient in some
of our proofs in Section 4.2. For an introduction to model theory of general
relational structures we refer to [11].

A _theory_ is simply a set of first-order sentences. A theory is _satisfiable_
if it has a model. A satisfiable theory $T$ is called _$\omega$ -categorical_
if all countable models of $T$ are isomorphic. A first-order theory $T$ is
_model complete_ if every embedding between models of $T$ preserves all first-
order formulas. A structure is called model complete or $\omega$-categorical
if its first-order theory is. Reducts of $\omega$-categorical structures are
$\omega$-categorical as well (see, e.g., [11]). Note that all finite
structures are model-complete and $\omega$-categorical. Further examples of
structures that are both model-complete and $\omega$-categorical are provided
by structures that are homogeneous in a finite relational signature; a
structure $S$ is called _homogeneous_ if all isomorphisms between finite
substructures can be extended to an automorphism of $S$.

Two theories are called _equivalent_ if they have the same models. Two
theories are called _companions_ if they have the same universal consequences.
A companion of a theory $T$ which is model-complete is called a _model
companion_ of $T$; a model companion might not exist, but if it exists, then
it is unique up to equivalence (see, e.g., [11]).

An _extension axiom_ if a first-order sentence of the form $\forall
x_{1},\dots,x_{n}\exists y.\psi$ where $\psi$ is quantifier-free. The
following well-known fact can be shown by a back-and-forth argument.

######  Lemma 2.

Every first-order theory of a homogeneous structure in a finite relational
language is equivalent to a set of extension axioms.

An _embedding of $G$ into $H$_ is an isomorphism of $G$ with a substructure of
$H$.

######  Lemma 3.

Let $D$ be a finite digraph (or graph) and let

$T:=\\{\neg\phi\mid\phi\text{ is primitive positive and }D\models\neg\phi\\}.$

Then $T$ has an $\omega$-categorical model companion. Its countable model
$U_{D}$ is _universal_ in the sense has the property that a countable digraph
(or graph) $C$ has an embedding into $U_{D}$ if and only if $C$ maps
homomorphically to $D$.

###### Proof.

The first part of the statement follows from Saracino’s theorem [21]. The
second statement follows from a standard compactness argument; see, e.g., [1].
∎

For the special case that $D=K_{n}$, Kolaitis, Prömel, and Rothschild [12]
also proved that the first-order theory of $U_{K_{n}}$ equals precisely the
almost-sure theory of $\operatorname{CSP}(K_{n})$. The graph $U_{K_{n}}$ will
be called the _generic $k$-partite graph_. Note that for $k\geq 2$ this graph
is not homogeneous.

##  3 Forbidden Undirected Graphs

We already mentioned in the introduction that Kolaitis, Prömel, and Rothschild
[12] proved that asymptotically almost all $K_{n}$-free graphs are
$(n-1)$-partite. This theorem has a remarkably general consequence which
provides a complete description of the almost-sure theory of
$\operatorname{Hom-Forb}(\mathcal{F})$ for all sets of finite undirected
graphs $\mathcal{F}$.

######  Theorem 2.

Let $\mathcal{F}$ be a non-empty set of finite undirected graphs. Then the
almost-sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$ equals the first-
order theory of the generic $(k_{\mathcal{F}}-1)$-partite graph.

###### Proof.

Let $k:=k_{\mathcal{F}}$. We claim that no graph $F\in\mathcal{F}$ is
$(k-1)$-partite. By the definition of $k$ we have that $k\leq\chi(F)$. It
follows that there is no homomorphism from $F$ to $K_{k-1}$, which proves the
claim. The claim implies that every $(k-1)$-partite graph is contained in
$\operatorname{Hom-Forb}(\mathcal{F})$.

Next, observe that $\operatorname{Hom-
Forb}(\mathcal{F})\subseteq\operatorname{Hom-Forb}(K_{k})$. To see this, let
$F\in\mathcal{F}$ be such that $k=\min\chi(F)$. Suppose for contradiction that
there is a graph $H\in\operatorname{Hom-
Forb}(\mathcal{F})\setminus\operatorname{Hom-Forb}(K_{k})$. Then there exists
a homomorphism from $K_{k}$ to $H$. But then note that $F$ has a homomorphism
to $K_{k}$ since $\chi(F)\leq k$, and hence $F$ has a homomorphism to $H$, a
contradiction to the assumption that $H\in\operatorname{Hom-
Forb}(\mathcal{F})$.

By the result of Kolaitis, Prömel, and Rothschild, the graphs in
$\operatorname{Hom-Forb}(K_{k})$ are asymptotically almost surely
$(k-1)$-partite, and hence the graphs in $\operatorname{Hom-
Forb}({\mathcal{F}})$ are aymptotically almost surely $(k-1)$-partite as well.
Since $\operatorname{Hom-Forb}(\mathcal{F})$ contains the class of all
$(k-1)$-partite graphs, the almost-sure theory of $\operatorname{Hom-
Forb}(\mathcal{F})$ equals the almost-sure theory of the class of
$(k-1)$-partite graphs, which is the theory of the generic $(k-1)$-partite
graph by the results discussed after Lemma 3. ∎

######  Definition 1.

Let $H$ be a finite undirected graph. Then the _co-chromatic number of $H$_ is
the smallest $k\in{\mathbb{N}}$ such that there exists a graph $G$ such that
$G\not\to H$ and $G\to K_{k}$; note that $K_{\chi(H)+1}\not\to H$ and
$K_{\chi(H)+1}\to K_{\chi(H)+1}$ so $k\leq\chi(H)+1$.

The co-chromatic number of $K_{n}$ is $n+1$. The co-chromatic number of
$C_{2n+1}$, for $n\geq 2$, is $3$ because $C_{2n-1}\not\to H$ and $C_{2n-1}\to
K_{3}$.

######  Corollary 1.

Let $H$ be a finite undirected graph with co-chromatic number $k$. Then the
almost-sure theory of $\operatorname{CSP}(H)$ equals the almost-sure theory of
$\operatorname{CSP}(K_{k-1})$.

###### Proof.

Let $\mathcal{F}$ be the class of all finite undirected graphs that do _not_
have a homomorphism to $H$. Clearly, $\operatorname{CSP}(H)=\operatorname{Hom-
Forb}(\mathcal{F})$. Let $G$ be a graph such that $G\not\to H$ and $G\to
K_{k}$, which exists by the definition of the co-chromatic number $k$. So
$G\in\mathcal{F}$. Also note that $k_{\mathcal{F}}=k$ by the definition of
$k$. By Theorem 2, the almost-sure theory of $\operatorname{Hom-
Forb}(\mathcal{F})$ equals the almost-sure theory of
$\operatorname{CSP}(K_{k-1})$. ∎

######  Example 2.

Let $H$ be the Grötzsch graph, which is the (up to isomorphism unique)
triangle-free graph of chromatic number four with the smallest number of
vertices. The co-chromatic number of $H$ is 3 because $K_{3}\not\to H$ and
$K_{3}\to K_{3}$. By Corollary 1 the almost-sure theory of
$\operatorname{CSP}(H)$ equals the almost-sure theory of
$\operatorname{CSP}(K_{2})$.

##  4 Forbidden Digraphs

There are sets of digraphs ${\mathcal{F}}$ where $\operatorname{Hom-
Forb}({\mathcal{F}})$ does not have a first-order 0-1 law, as the following
example illustrates. If $D=(V;E)$ is a digraph, we also write $x\rightarrow y$
instead of $(x,y)\in E$ (and instead of $E(x,y)$ in logical formulas). We
write $x_{1}\to x_{2}\to x_{3}$ as a shortcut for $x_{1}\to x_{2}\wedge
x_{2}\to x_{3}$ and we write $x_{1}\not\to x_{2}$ as a shortcut for
$(x,y)\notin E$ (and instead of $\neg E(x,y)$ in logical formulas).

######  Example 3.

Let $D$ be the disjoint union of $\vec{C}_{3}$ and $T_{3}$, i.e., we first
rename the vertices of $T_{3}$ so that $V(\vec{C}_{3})$ and $V(T_{3})$ are
disjoint, and then define $V(D):=V(\vec{C}_{3})\cup V(T_{3})$ and
$E(D):=E(\vec{C}_{3})\cup E(T_{3})$. Recall from Section 2.2 that there exists
a finite set of digraphs ${\mathcal{F}}$ such that
${\mathcal{C}}:=\operatorname{CSP}(D)=\operatorname{Hom-Forb}(\mathcal{F})$.
If $\phi$ is the primitive positive sentence

$\exists x_{1},x_{2},x_{3}(x_{1}\rightarrow x_{2}\rightarrow x_{3}\wedge
x_{1}\rightarrow x_{3})$

then $\phi_{\omega}^{\mathcal{C}}$ equals $1/2$ as we will see in Example 4.

In the following we focus on the special case where ${\mathcal{F}}$ is a
finite set of orientations of trees.

###  4.1 Forbidden Orientations of Trees

We will provide an explicit description of the almost-sure theory of
$\operatorname{Hom-Forb}(\mathcal{F})$ for finite sets $\mathcal{F}$ of
orientations of trees.

######  Theorem 3.

Let $\mathcal{F}$ be a finite set of finite oriented trees. Then the almost-
sure theory of $\operatorname{Hom-Forb}(\mathcal{F})$ is (pseudo-finite and)
$\omega$-categorical; in particular, it has a first-order 0-1 law.

Our proof uses Theorem 1 which asserts the existence of a digraph $D$ such
that $\operatorname{CSP}(D)=\operatorname{Hom-Forb}({\mathcal{F}})$. The
following properties of the digraph $D$ will be useful.

######  Proposition 1 ([15]).

For every finite non-empty set of orientations of finite trees $\mathcal{F}$
the dual digraph $D$ of $\mathcal{F}$ (see Theorem 1) has no directed cycles,
and has no non-trivial automorphisms.

###### Proof.

If $D$ contains a directed cycle, then all orientations of trees
homomorphically map to $D$, a contradiction. The fact that it has no non-
trivial automorphisms is stated in Lemma 4.1 in [15]. ∎

We first study the almost sure theory of the class of finite digraphs equipped
with a fixed homomorphism to $D$; the computations are easier in this setting.
From the results we then derive results about $\operatorname{CSP}(D)$ in
Section 4.5.

###  4.2 Model theory of D-coloured digraphs

In this section we study the first-order theories that will eventually be
relevant for describing our almost-sure theories.

######  Definition 2.

Let $D$ be a finite digraph. A _$D$ -coloured digraph_ is a digraph $G$
equipped with unary predicates $P_{u}$ for each $u\in V(D)$ such that each
$x\in V(G)$ is contained in $P_{u}$ for precisely one $u\in V(D)$, and such
that the map $p$ that sends $x$ to $u$ is a homomorphism from $G$ to $D$.

The proof of the following lemma can be shown by a straightforward application
of Fraïssé’s theorem [10].

######  Lemma 4.

There exists an (up to isomorphism unique) countable homogeneous $D$-coloured
digraph $C_{D}$ such that the finite structures that embed into $C_{D}$ are
precisely the $D$-coloured digraphs.

######  Lemma 5.

Suppose that $D$ is a finite digraph without non-trivial automorphisms. Then
the reduct of $C_{D}$ in the signature of digraphs is isomorphic to the
structure $U_{D}$ introduced in Lemma 3.

###### Proof.

A finite digraph embeds into $C^{\prime}_{D}$ if and only if it maps
homomorphically to $D$ if and only if it embeds into $U_{D}$, so the theory
$T$ of $C_{D}^{\prime}$ is a companion of the theory of $U_{D}$. We claim that
$C_{D}^{\prime}$ is model complete. By Theorem 4.5.8 (2) in [1] it suffices to
verify that each of the unary predicates $P_{v}$ for $v\in V(D)$ and their
negations have existential positive definitions in $C_{D}^{\prime}$. Let
$\phi_{v}$ be the primitive positive that defines the orbit of $v$ in $D$,
which exists by Lemma 1. Since $D$ has no non-trivial automorphisms, the only
element that satisfies $\phi_{v}$ in $D$ is the vertex $v$. The expansion of
$D$ in the signature of $C_{D}$ where $P_{u}$ denotes $\\{u\\}$, for each
$u\in V(D)$, has an embedding $e$ into $C_{D}$ be the definition of $C_{D}$.
Note that $e(v)$ satisfies $\phi_{v}$ in $C_{D}^{\prime}$. Moreover, every
vertex in $P_{v}^{C_{D}}$ satisfies $\phi_{v}$ by the homogeneity of $C_{D}$.
Vertices outside $P^{C_{D}}_{v}$, on the other hand, do not satisfy
$\phi_{v}$. To see this, note that every element $x$ of $C_{D}$ must be in
$P^{C_{D}}_{u}$ for some $u\in V(D)$, which in turn implies by the homogeneity
of $C_{D}$ that $x$ satisfies the primitive positive definition of $\\{u\\}$
in $D$. But then if $x$ satisfies $\phi_{v}$, then this implies that $u=v$. So
indeed, $P_{v}$ has the existential positive (even primitive positive)
definition $\phi_{v}$. The negation of $P_{v}$ then has the existential
positive definition $\bigvee_{u\neq v}\phi_{u}$. Since the model companion is
unique up to equivalence of theories, and both $C_{D}^{\prime}$ and $U_{D}$
are model-complete and companions of each other, this implies that
$C_{D}^{\prime}$ and $U_{D}$ have the same first-order theory. Since $C_{D}$
is $\omega$-categorical, so is the $\\{E\\}$-reduct $C_{D}^{\prime}$ of
$C_{D}$; this implies that $C_{D}^{\prime}$ and $U_{D}$ are even isomorphic. ∎

###  4.3 Density

The key to studying random $D$-colored digraph is a certain notion of density,
which has already been studied for undirected graphs [17] and which we also
use for directed graphs.

######  Definition 3.

Let $D$ be a digraph. Then the _density of $D$_ is defined to be the maximum
of

$\displaystyle\sum_{(u,v)\in E(D)}\delta(u)\delta(v)$ (1)

over all probability distributions $\delta\colon V(D)\to[0,1]$ (satisfying
$\sum_{v\in V(D)}d(v)=1$). If $\delta$ realizes this maximum, we call it a
_density function of $D$_, and the _support $\\{v\in V(D)\mid\delta(v)>0\\}$
of $\delta$_ is called a _densest subgraph of $D$_.

The following is a reformulation of a result of Motzkin and Straus [17] for
oriented graphs.333The authors thank Oleg Pikhurko for pointing this out to
us.

######  Lemma 6 ([17]).

Let $D$ be a finite oriented graph. Then the density of $D$ equals

$\frac{1}{2}(1-1/k)=\frac{k-1}{2k}$

where $k$ is largest such that $D$ has a subgraph which is an orientation of a
$K_{k}$.

######  Definition 4 (Blow-up graphs and digraphs).

Let $G$ be an undirected graph. A _blow-up of $G$_ is a graph obtained from
$G$ by adding for each vertex $u\in V(G)$ arbitrarily many ‘copies’ of $u$,
i.e., vertices with the same neighbourhood as $u$; among the different copies
of $u$ there are no edges. Blow-ups of digraphs $D$ are defined analogously.

######  Lemma 7.

Let $D$ be a finite oriented graph and let $\delta$ be a density function of
$D$. Then the subgraph of $D$ induced by the support of $\delta$ is an
orientation of a blow-up of $K_{k}$, for some $k\geq 2$, such that the sum
over $\delta(u)$ for all the copies $u$ of the same vertex of $K_{k}$ equals
$1/k$.

###### Proof.

We prove the statement by induction on $n:=|V(D)|$. If $n=1$ then the
statement is trivial. If $n>1$ we distinguish three cases.

  * •

for some $u\in V(D)$ we have $\delta(u)=0$; in this case, we apply the
inductive assumption for the oriented graph $D-u$ and are done.

  * •

for all $u\in V(D)$ we have that $\delta(u)>0$, and $D$ is not an orientation
of $K_{n}$. Let $v_{1},\dots,v_{n}$ be the vertices of $D$ and assume without
loss of generality that neither $(v_{1},v_{2})$ nor $(v_{2},v_{1})$ is an edge
in $D$. We will write $v_{1},\ldots,v_{n}$ for the vertices of $D$. For
$x_{1},\ldots,x_{n}\in\mathbb{R}$, define

$f(x_{1},\dots,x_{n}):=\sum_{(v_{i},v_{j})\in E(D)}x_{i}x_{j}.$

Suppose that $x_{1},\dots,x_{n}\geq 0$ are chosen such that
$x_{1}+\cdots+x_{n}=1$ and $f(x_{1},\dots,x_{n})$ is maximal. Note that if
$\sum_{(v_{1},v_{i})\in E(D)}x_{i}\neq\sum_{(v_{2},v_{i})\in E(D)}x_{i}$ then
we do not have a maximum of $f$ at $(x_{1},\ldots,x_{n})$. Indeed, if
$\sum_{(v_{1},v_{i})\in E(D)}x_{i}>\sum_{(v_{2},v_{i})\in E(D)}x_{i}$, then

$f(x_{1}+t,x_{2}-t,x_{3},\ldots,x_{n})>f(x_{1},\ldots,x_{n})$

for all $t\in[0,x_{2}]$, which contradicts our assumption. Therefore, we have

$\sum_{(v_{1},v_{i})\in E(D)}x_{i}=\sum_{(v_{2},v_{i})\in E(D)}x_{i}$

and for all $t\in[0,x_{2}]$

$f(x_{1}+t,x_{2}-t,x_{3},\dots,x_{n})=f(x_{1},x_{2},x_{3},\dots,x_{n}).$

Applied to $x_{i}:=\delta(v_{i})$ for $i\in\\{1,\dots,n\\}$, this means that

$(\delta(v_{1})+\delta(v_{2}),0,\delta(v_{3}),\ldots,\delta(v_{n}))$

also maximises $f$, and hence defines another density function
$\delta^{\prime}$ of $D$. We may apply the inductive assumption to the graph
$D-v_{2}$ and the density function $\delta^{\prime}$, and obtain that
$D-v_{2}$ has a subgraph $H$ which is an orientation of a blow-up of $K_{k}$,
for some $k\geq 2$, such that the sum over $\delta^{\prime}(u)$ for all the
copies $u$ of a vertex of $K_{k}$ equals $1/k$.

We claim that the subgraph $H^{\prime}$ of $D$ with vertices
$V(H)\cup\\{v_{2}\\}$ is a blow-up of $K_{k}$ as well. We first notice that
for any $v_{3}\in V(H)$, if $(v_{1},v_{3})\notin E(D)$ then
$(v_{2},v_{3})\notin E(D)$, because otherwise $\sum_{(v_{1},v_{i})\in
E(D)}\delta(v_{i})=\sum_{(v_{3},v_{i})\in E(D)}\delta(v_{i})-\delta(v_{2})$,
so $\sum_{(v_{1},v_{i})\in E(D)}\delta(v_{i})<\sum_{(v_{3},v_{i})\in
E(D)}\delta(v_{i})$, in contradiction to $\delta$ being a density function of
$D$. Moreover, since $\sum_{(v_{1},v_{i})\in
E(D)}\delta(v_{i})=\sum_{(v_{2},v_{i})\in E(D)}\delta(v_{i})$, necessarily
$v_{2}$ has an edge with every other vertex in $V(H)$ connected to $v_{1}$,
otherwise $\sum_{(v_{2},v_{i})\in E(D)}\delta(x_{i})<\sum_{(v_{1},v_{i})\in
E(D)}\delta(x_{i})$ and which again leads to a contradiction to the maximality
of $\delta$.

So $H^{\prime}$ is indeed a blow-up of $K_{k}$; note that the sum over
$\delta(u)$ for all the copies $u$ of the same vertex of $K_{k}$ equals $1/k$,
which proves the statement of the lemma.

  * •

$D$ is an orientation of $K_{n}$. Note that in this case the probability
distribution $\delta$ on $\\{v_{1},\dots,v_{n}\\}$ maximises

$\displaystyle\frac{(\delta(v_{1})+\cdots+\delta(v_{n}))^{2}-\delta(v_{1})^{2}-\cdots-\delta(v_{n})^{2}}{2}=\frac{1-(\delta(v_{1})^{2}+\cdots+\delta(v_{n})^{2})}{2}.$
(2)

The expression $\delta(v_{1})^{2}+\cdots+\delta(v_{n})^{2}$ is minimised if
$\delta(v_{1})=\cdots=\delta(v_{n})=1/n$. To see this, suppose that
$\delta(v_{1})>1/n>\delta(v_{2})$. Then the family

$(y_{1},\ldots,y_{n}):=(\delta(v_{1})-1/n+\delta(v_{2}),1/n,\delta(v_{3}),\ldots,\delta(v_{n}))$

is such that $\sum_{i}y_{i}=1$ and
$y_{1}^{2}+\cdots+y_{n}^{2}<\delta(v_{1})^{2}+\cdots+\delta(v_{n})^{2}$.
Indeed, for all $x>y\in[0,1]$,
$x^{2}+y^{2}\geq(x-\varepsilon)^{2}+(y+\varepsilon)^{2}$ for all
$\varepsilon\in(0,x-y)$. We can reason analogously if
$\delta(v_{i})>1/n>\delta(v_{j})$, for $i,j\in\\{1,\dots,n\\}$, and therefore
we can modify the family finitely many times to obtain a family $x_{i}$
satisfying $x_{1}=\cdots=x_{n}=1/n$. Hence, the maximum of (2) is attained if
all the $\delta(v_{i})$ are equal.

This concludes the inductive step and the lemma is proven. ∎

###  4.4 Random D-coloured digraphs

In the following, we consider $D$-coloured graphs drawn uniformly at random
from the set of all labelled $D$-coloured digraphs, i.e., $D$-coloured
digraphs with vertex set $\\{1,\dots,n\\}$.

######  Theorem 4.

Let $D$ be a finite oriented graph. Let $\ell$ be largest so that $D$ contains
an orientation of $K_{\ell}$. Then asymptotically almost surely a labelled
$D$-coloured digraph is such that the image of the homomorphism to $D$ is
contained in a blow-up of an orientation of $K_{\ell}$.

###### Proof.

Let $v_{1},\dots,v_{k}$ be the vertices of $D$. To construct a $D$-coloured
digraph with vertex set $\\{1,\dots,n\\}$, we have to

  * •

choose a partition $P_{v_{1}}\cup\dots\cup P_{v_{k}}=\\{1,\dots,n\\}$, and

  * •

if $(u,v)$ is an edge in $D$ we may arbitrarily choose for each $a\in P_{u}$
and $b\in P_{v}$ whether to put an edge from $a$ to $b$ or not.

Hence, the number of all $D$-coloured digraphs equals

$\displaystyle c_{n}:=\sum_{s_{1},\dots,s_{k}\in{\mathbb{N}}\text{ and
}s_{1}+\cdots+s_{k}=n}{n\choose s_{1},\dots,s_{k}}\;\prod_{(v_{i},v_{j})\in
E(D)}2^{s_{i}s_{j}}.$ (3)

Let $d$ be the density of $D$ (Definition 3). We will need a sharper notion of
density to obtain a bound on $c_{n}$. We may suppose without loss of
generality that the subgraph of $D$ induced on $v_{1},\dots,v_{\ell}$ is
$T_{\ell}$. We define

$d_{n}=\frac{1}{n^{2}}\max_{x_{1}+\cdots+x_{\ell}=n}\sum_{1\leq
i<j\leq\ell}x_{i}x_{j}.$

There are integers $s_{i}\in\\{\lfloor n/\ell\rfloor,\lceil n/\ell\rceil\\}$,
for $i\in\\{1,\dots,\ell\\}$, such that $s_{1}+\cdots+s_{\ell}=n$ and

$\sum_{1\leq i<j\leq\ell}s_{i}s_{j}\geq{\ell\choose 2}\lfloor
n/\ell\rfloor^{2}.$

Recall from Lemma 7 that $d={\ell\choose 2}\frac{1}{\ell^{2}}$, and since
$d_{n}\geq\frac{1}{n^{2}}{\ell\choose 2}\lfloor n/\ell\rfloor^{2}$ by the
squeeze theorem we get that $d_{n}\to_{n}d$. Also note that $d_{n}$ can be
used to get a lower bound on $c_{n}$:

$c_{n}\geq 2^{n^{2}d_{n}}.$

Now take $s_{1},\dots,s_{k}\in{\mathbb{N}}$ such that $s_{1}+\dots+s_{k}=n$
and assume that the subgraph $S$ of $D$ induced on $\\{v_{i}\in V(D)\mid
s_{i}\neq 0\\}$ is not an orientation of a blow-up of $K_{\ell}$. We want to
show that for sufficiently large $n\in{\mathbb{N}}$

$d_{n}-\left(\frac{1}{n^{2}}\sum_{(v_{i},v_{j})\in E(D)}s_{i}s_{j}\right)\geq
1/n-1/n^{2}.$

The central part of the proof is dealing with the case that $S$ has a subgraph
that is an orientation of $K_{\ell}$. We first discuss the case where such a
subgraph does not exist. In this case, the density of $S$ is $d^{\prime}<d$.
In particular, by the definition of the density, we have
$\frac{1}{n^{2}}\sum_{(v_{i},v_{j})\in E(D)}s_{i}s_{j}\leq d^{\prime}$. Since
$d^{\prime}<d$, for any $\varepsilon\in(0,d-d^{\prime})$ we have

$\frac{1}{n^{2}}\sum_{(v_{i},v_{j})\in
E(D)}s_{i}s_{j}<d-\varepsilon<d_{n}-1/n$

for $n$ large enough.

We now work under the assumption that there exists a subgraph $C$ of $S$ that
is an orientation of $K_{\ell}$. Up to renaming the vertices, we assume that
$V(C)=\\{v_{1},\ldots,v_{\ell}\\}.$ Let $\delta$ be a function realizing
$d_{n}$ on $C$, i.e., $\sum_{i\in\\{1,\ldots,\ell\\}}\delta(v_{i})=1$ and
$\sum_{(v_{i},v_{j})\in E(C)}\delta(v_{i})\delta(v_{j})=d_{n}$. For
$i\in\\{1,\dots,k\\}$, we write $\beta_{i}=s_{i}/n$ and
$\delta_{i}=\delta(v_{i})$, and for $j\in\\{1,\dots,\ell\\}$ we write
$\alpha_{j}=\delta_{j}-\beta_{j}$. Note that since
$\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}+\beta_{i}=\sum_{i\in\\{1,\dots,\ell\\}}\delta_{i}=1=\sum_{i\in\\{1,\dots,k\\}}\beta_{i}$,
we have

$\displaystyle\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}=\sum_{j\in\\{\ell+1,\dots,k\\}}\beta_{j}.$
(4)

Note that $\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}\notin\\{0,1\\}$, which is
true since we assumed that $C$ is a subgraph of $S$ and that $S$ itself is not
an orientation of $K_{\ell}$. Indeed, if
$\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}=0$, then this would mean that
$\sum_{j\in\\{\ell+1,\dots,k\\}}\beta_{j}=0$ which is the same as saying that
$S$ is contained is $C$. On the other hand
$\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}=1=\sum_{j\in\\{\ell+1,\dots,k\\}}\beta_{j}$
means that $S$ and $C$ are disjoint. Finally, remark that
$\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i}$ not being $0$ or $1$ it is at least
$1/n$ and at most $1-1/n$. The map $x\mapsto x(1-x)$ being smallest around $1$
and $0$, we have

$\displaystyle\sum_{j\in\\{1,\dots,\ell\\}}\alpha_{j}(1-\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i})\geq
1/n(1-1/n).$ (5)

We can now start the main computation of the proof. The simplification for the
equality in line (8) will be explained below.

$\displaystyle\sum_{(v_{i},v_{j})\in E(D)}\beta_{i}\beta_{j}$
$\displaystyle=\sum_{(v_{i},v_{j})\in
E(C)}(\delta_{i}-\alpha_{i})(\delta_{j}-\alpha_{j})$
$\displaystyle\quad+\sum_{v_{i}\in V(C),v_{j}\notin V(C),(v_{i},v_{j})\in
E(D)}(\delta_{i}-\alpha_{i})\beta_{j}+\sum_{v_{i},v_{j}\notin
V(C),(v_{i},v_{j})\in E(D)}\beta_{i}\beta_{j}$
$\displaystyle\leq\sum_{(v_{i},v_{j})\in
E(C)}(\delta_{i}-\alpha_{i})(\delta_{j}-\alpha_{j})$
$\displaystyle\quad+\sum_{v_{i}\in V(C),v_{j}\notin
V(C)}(\delta_{i}-\alpha_{i})\beta_{j}+\sum_{v_{i},v_{j}\notin
V(C)}\beta_{i}\beta_{j}$ $\displaystyle=\sum_{(v_{i},v_{j})\in
E(C)}\delta_{i}\delta_{j}\ -\sum_{(v_{i},v_{j})\in
E(C)}\delta_{j}\alpha_{i}+\sum_{(v_{i},v_{j})\in E(C)}\alpha_{i}\alpha_{j}$
$\displaystyle\quad\underbrace{-\sum_{(v_{i},v_{j})\in
E(C)}\delta_{i}\alpha_{j}+\sum_{v_{i}\in V(C),v_{j}\notin
V(C)}\delta_{i}\beta_{j}}_{=0}$ (6)
$\displaystyle\quad\underbrace{-\sum_{v_{i}\in V(C),v_{j}\notin
V(C)}\alpha_{i}\beta_{j}+\sum_{v_{i},v_{j}\notin
V(C)}\beta_{i}\beta_{j}}_{=0}$ (7) $\displaystyle=d_{n}-\sum_{(v_{i},v_{j})\in
E(C)}(\delta_{i}-\alpha_{i})\alpha_{j}$ (8) $\displaystyle\leq
d_{n}-\sum_{i,j\in\\{1,\dots,\ell\\}}(\delta_{i}-\alpha_{i})\alpha_{j}$ (9)
$\displaystyle=d_{n}-\sum_{j\in\\{1,\dots,\ell\\}}\alpha_{j}(1-\sum_{i\in\\{1,\dots,\ell\\}}\alpha_{i})$
$\displaystyle\leq d_{n}-1/n(1-1/n)=d_{n}-1/n+1/n^{2}$ (by (5))

Let us now deal with the terms in line (6).

$\displaystyle\sum_{v_{i},v_{j}\notin V(C)}\beta_{i}\beta_{j}-\sum_{v_{i}\in
V(C),v_{j}\notin V(C)}\alpha_{i}\beta_{j}=\sum_{v_{j}\notin
V(C)}\beta_{j}(\sum_{v_{r}\notin V(C)}\beta_{r}-\sum_{v_{l}\in
V(C)}\alpha_{l})$

We can use (4) to get that this sum is zero. Analogously one can show that the
terms in line (7) cancel out. The inequality in line (9) holds because $C$ is
an orientation of a complete graph.

We can now conclude. Let $b_{n}$ be the number of labelled $D$-coloured graphs
of size $n$ where the homomorphism to $D$ has an image that is not contained
in a blow-up of $K_{\ell}$. Let $S_{n}$ be the set of
$s_{1},\dots,s_{k}\in{\mathbb{N}}$ such that $s_{1}+\dots+s_{k}=n$ and such
that $v_{i}\mapsto\frac{s_{i}}{n}$ is not a density function.

$\displaystyle b_{n}$ $\displaystyle=\sum_{s_{1},\ldots,s_{n}\in
S_{n}}{n\choose{s_{1},\ldots,s_{k}}}2^{\sum_{v_{i},v_{j}\in E(D)}s_{i}s_{j}}$
$\displaystyle\leq 2^{n^{2}d(1-1/n+1/n^{2})}\sum_{s_{1},\ldots,s_{n}\in
S_{n}}{n\choose{s_{1},\ldots,s_{k}}}\leq 2^{n^{2}d_{n}(1-1/n+1/n^{2})}n^{k}$

Since $c_{n}\geq 2^{n^{2}d_{n}}$, we get $b_{n}/c_{n}\to 0$. In other words,
asymptotically almost surely a labelled $D$-coloured digraph has a
homomorphism to $D$ whose image is contained in an orientation of a blow-up of
$K_{\ell}$. ∎

######  Proposition 2.

Let $D$ be $T_{\ell}$. Then asymptotically almost surely, the number of
vertices of color $v$, where $v$ is a vertex of $D$, in a $D$-colored directed
graph of size $n$ has size at least $\lfloor n/\ell\rfloor$.

###### Proof.

We use the notation from the proof of Theorem 4. If
$(s_{i})_{i\in\\{1,\ldots,\ell\\}}$ is such that $\sum_{i}s_{i}=n$ and there
is $i\in\\{1,\ldots,\ell\\}$ such that $s_{i}<\lfloor n/\ell\rfloor$, then
there must be $j\neq i$ such that $s_{j}\geq\lfloor n/\ell\rfloor+1$. Then

$\displaystyle\sum_{r,q}s_{r}s_{q}=$
$\displaystyle\sum_{r,q\notin\\{i,j\\}}s_{r}s_{q}+s_{i}\sum_{r\notin\\{i,j\\}}s_{r}+s_{j}\sum_{r\notin\\{i,j\\}}s_{r}+s_{i}s_{j}$
$\displaystyle<$
$\displaystyle\underbrace{\sum_{r,q\notin\\{i,j\\}}s_{r}s_{q}+(s_{i}+1)\sum_{r\notin\\{i,j\\}}s_{r}+(s_{j}-1)\sum_{r\notin\\{i,j\\}}s_{r}+(s_{i}+1)(s_{j}-1)}_{=A}-1.$

The inequality holds because $s_{j}-s_{i}\geq 2$. We define
$(s^{\prime}_{r})_{r\in\\{1,\ldots,\ell}$ by

$s^{\prime}_{r}=\left\\{\begin{array}[]{ll}s_{r}&\text{ if
}r\notin\\{i,j\\}\\\ s_{i+1}&\text{ if }r=i\\\ s_{j+1}&\text{ if
}r=j.\end{array}\right.$

Note that

$A=\sum_{r,q}s^{\prime}_{r}s^{\prime}_{q}\leq n^{2}d_{n}.$

This allows us to conclude that
$\frac{1}{n^{2}}\sum_{m,n}s_{n}s_{m}<d_{n}-1/n^{2}$. Let us call $R_{n}$ the
set of $D$-colored digraphs on $\\{1,\ldots,n\\}$ such that there exists a
vertex $d$ of $D$ such that the number of vertices of color $d$ is less than
$\lfloor n/\ell\rfloor$. Then $|R_{n}|$ is less than
$n^{k}2^{n^{2}(d_{n}-1/n)}$. As we argued in the proof of Theorem 4, the total
number of $D$-colored graphs is greater than $2^{n^{2}d_{n}}$, hence the
probability of being in $R_{n}$ goes to $0$. ∎

######  Proposition 3.

Let $D$ be a digraph vertices $v_{1},\dots,v_{l}$ which is a $T_{\ell}$ for
some $\ell\geq 1$. Then a $D$-coloured digraph $G$ with vertex set
$\\{1,\dots,n\\}$ from the uniform distribution can equivalently be obtained
by

  * •

distributing the $n$ vertices into $\ell$ bags, denoted by $P_{v_{i}}$ where
$v_{i}$ is a vertex of $T_{\ell}$, with probability $1/\ell$ independently for
each bag;

  * •

adding edges $(u,v)$, for $u\in P_{v_{i}}$ and $v\in P_{v_{j}}$, $i<j$,
independently at random with probability $1/2$.

###### Proof.

The proof of the statement is straightforward from the particular shape of
$D$. ∎

######  Corollary 2.

Let $D$ be a $T_{k}$. Then the almost-sure theory of the class of all finite
$D$-coloured digraphs equals the theory of $C_{D}$.

###### Proof.

Let $V(D)=\\{v_{1},\dots,v_{k}\\}$. To prove the statement of the lemma, then
by Lemma 2 it suffices to check that every extension axiom that holds in
$U_{D}$ holds asymptotically almost surely for $D$-coloured digraphs. Let
$\phi$ be such an extension axiom of the form $\forall
x_{1},\dots,x_{m}\exists y.\,\psi(x_{1},\dots,x_{m},y)$, and let $G$ be a
$D$-coloured structure which is drawn uniformly at random from the set of all
$D$-coloured structures with vertices $\\{1,\dots,n\\}$, produced according to
Proposition 3. Let $a_{1},\dots,a_{m}$ be elements of $G$. Then the
probabilities that a given element $b\in V(G)\setminus\\{a_{1},\dots,a_{m}\\}$
satisfies $\psi(a_{1},\dots,a_{m},b)$ are independent and larger than some
positive constant, and the probability that such an element $b$ exists tends
to $1$ exponentially fast if $|V(G)|$ tends to infinity. We may then use the
union bound to derive that $\phi$ satisfies $\phi$ asymptotically almost
surely. ∎

###  4.5 Getting rid of the colors

In this section we use our results about $D$-coloured graphs to derive
statements about the almost-sure theory of $\operatorname{CSP}(D)$.

######  Lemma 8.

Let $D$ be a core digraph without non-trivial automorphisms such that the
almost-sure theory of the class of $D$-coloured digraphs equals $C_{D}$. Then
asymptotically almost surely, a graph from $\operatorname{CSP}(D)$ has exactly
one homomorphism to $D$.

###### Proof.

If we draw a $D$-coloured digraph with vertex set $\\{1,\dots,n\\}$ uniformly
at random and then remove the colours, the digraphs $G$ with many
homomorphisms to $D$ are more likely to be drawn than those with few
homomorphisms to $D$. Clearly, $G$ has a homomorphism $h$ to $D$. We claim
that asymptotically almost surely $h$ is the only homomorphism from $G$ to
$D$. To see this, note that $C_{D}$ contains the sentence $\psi=\forall
x(\phi_{1}(x)\vee\cdots\vee\phi_{k}(x))$ where $\phi_{i}$ is a primitive
positive definition of the orbit of $v_{i}$ in $D$, for every
$i\in\\{1,\dots,k\\}$; such definitions exist by the assumption that $D$ is a
core and by Lemma 1. Note that by the assumption that $D$ does not have non-
trivial automorphisms, the orbit of $v_{i}$ in $\operatorname{Aut}(D)$ equals
$\\{v_{i}\\}$.

Let $f$ be a homomorphism from $G$ to $D$; we claim that $f=h$. Let $u\in
V(G)$ and $h(u)=v_{i}$. Then $v_{i}$ satisfies $\phi_{i}$ and does not satisfy
$\phi_{j}$ for every $j\neq i$. By assumption, $G$ asymptotically almost
surely satisfies $\psi$. The vertex $u$ cannot satisfy $\phi_{j}$, for $j\neq
i$, since homomorphisms preserve $\phi_{j}$ but $h(u)$ does not satisfy
$\phi_{j}$. So asymptotically almost surely, $u$ must satisfy $\phi_{i}$. For
every homomorphism $f$ from $G$ to $D$ the vertex $f(u)$ must satisfy
$\phi_{i}$. But $\phi_{i}$ defines $v_{i}=h(u)$; this shows that $f(u)=h(u)$
and proves the claim.

The probability that a random digraph in $\operatorname{CSP}(D)$ with vertex
set $\\{1,\dots,n\\}$ has only one satisfying assignment is even greater, and
hence also tends to 1 when $n$ tends to infinity. ∎

######  Corollary 3.

Asymptotically almost surely, a labelled digraph from
$\operatorname{CSP}(T_{\ell})$ has exactly one homomorphism to $D$. Moreover,
asymptotically almost surely, the preimage of a vertex of $T_{\ell}$ under the
unique homomorphism has size at least $\lfloor n/\ell\rfloor$.

###### Proof.

The digraph $D$ is a core and has no non-trivial automorphisms. Moreover,
Corollary 2 implies that the almost-sure theory of $D$-coloured graphs equals
the theory of $C_{D}$. Therefore, the statement follows from Lemma 8. The
second statement is then an immediate consequence of Proposition 2. ∎

######  Proposition 4.

The almost-sure theory of $\operatorname{CSP}(T_{\ell})$ equals the theory of
$U_{T_{\ell}}$.

###### Proof.

By Corollary 3, asymptotically almost surely every graph with a homomorphism
to $D$ has exactly one homomorphism to $D$, so the almost-sure theory of
$\operatorname{CSP}(D)$ equals the theory of the reduct of $C_{D}$ in the
signature of graphs. By Lemma 5, we obtain that the almost-sure theory of
$\operatorname{CSP}(D)$ equals $U_{D}$. ∎

######  Example 4.

We revisit the digraph $D$ from Example 3, which was the disjoint union of
$\vec{C}_{3}$ and $T_{3}$. We still have to prove that the probability of the
sentence $\phi$ which states that a given graph admits a homomorphism from
$T_{3}$ asymptotically holds in $\operatorname{CSP}(D)$ with probability
$1/2$. Note that the number $c_{n}$ of digraphs with vertex set
$\\{1,\dots,n\\}$ that map homomorphically to $T_{3}$ equals the number of
digraphs that map homomorphically to $\vec{C}_{3}$. A density argument shows
that the number of digraphs that map homomorphically to neither $T_{3}$ nor
$\vec{C}_{3}$ is negligible in comparison to $c_{n}$ (similarly as in the
proof of Theorem 4. By Proposition 4, a graph that homomorphically maps to
$T_{3}$ satisfies $\phi$ asymptotically almost surely; conversely, a graph
that satisfies $\phi$ has no homomorphism to $\vec{C}_{3}$, and by what we
have stated above it must have a homomorphism to $T_{3}$. This shows that
$\phi$ holds asymptotically with probability $1/2$.

###  4.6 Blow-ups of $K_{k}$

In the previous section we have seen that we can get rid of the colours if $D$
is a core digraph without non-trivial automorphisms. However, the densest
parts of $D$ might not satisfy these assumptions. We therefore make use of the
additional assumption that $D$ is a finite dual.

######  Lemma 9.

Let $D$ be the dual of a finite set of oriented trees. Assume that there are
$x_{1},x_{2},x_{3}\in V(D)$ such that $x_{1}\to x_{2}\to x_{3}$ and $x_{1}\to
x_{3}$ and $D$ contains subgraphs $L_{n}$ and $L_{m}$ that are oriented
cliques of size $n$ and $m$, respectively, such that for all $l_{1}\in L_{n}$,
$l_{2}\in L_{m}$, and $i\in\\{1,2,3\\}$ we have $l_{1}\to x_{i}\to l_{2}$.
Suppose $L_{n}$ and $L_{m}$ are chosen so that $n+m$ is largest possible. Then
there cannot be $x_{4}\in V(D)$ such that $x_{4}\to x_{1}$, $x_{4}\to x_{3}$,
$x_{4}\nrightarrow x_{2}$ and $x_{4}\to l$ for all $l\in L_{n}\cup L_{m}$.

###### Proof.

This proof requires some elements from [15]. Let $A$ be a directed graph and
$B$ a subgraph of $A$. We say that $A$ dismantles into $B$ if there is an
enumeration $y_{1},\ldots,y_{r}$ of $V(A)\backslash V(B)$ such that for every
$i\leq r$ there is a homomorphism $\phi_{i}$ from the induced subgraph of $B$
with vertex set $B\cup\\{y_{i},\ldots,y_{n}\\}$ to the induced subgraph of $B$
with vertex set $B\cup\\{y_{i+1},\ldots,y_{r}\\}$ which extends the identity
map.

Let us assume $A$ dismantles to $B$ and that $y_{1},\ldots,y_{r}$ and
$(\phi_{1},\ldots,\phi_{r})$ are witnesses of this dismantlement. In this
case, say that $y_{i}$ is “sent to” $\phi_{i}(y_{i})$ and, since vertices of
$A\setminus B$ are sent in an one by one, we say that $y_{i}$ is “sent before”
$y_{j}$ when $j>i$. Remark that, under those assumptions, up to modifying
$(\phi_{i})_{i\leq r}$, we can always assume that $y_{i}$ is sent to a vertex
in $B$. Indeed, for $i\leq r$ set
$\psi(y_{i})=\phi_{r}(\phi_{r-1}(\ldots\phi_{i}(y_{i}))\in B$, we can replace
$\phi_{i}$ by the extension of the identity on
$B\cup\\{y_{i+1},\dots,y_{n}\\}$ which sends $y_{i}$ to $\psi(y_{i})$ and we
still get a dismantlement from $A$ to $B$. Let us now state the result from
[15] that we need: if $D$ is the dual of a finite set of oriented trees, then
$D^{2}$ dismantles into $\triangle_{D^{2}}$, where $\triangle_{D^{2}}$ denotes
the subgraph of $D^{2}$ induced on the diagonal $\\{(a,a)\mid a\in V(D)\\}$.
This follows from the proof of Theorem 5.7 in [15].

Let $L$ be the subgraph of $D$ induced on $L_{m}\cup
L_{n}\cup\\{x_{1},x_{2},x_{3}\\}$. We assume for contradiction that there
exists $x_{4}\in V(D)$ as in the statement of the lemma, and use the fact that
$D^{2}$ dismantles into $\triangle_{D^{2}}$. In particular, we need to send
$(x_{4},x_{1})$ and $(l,x_{2})$ for each $l\in L$ to some vertex in
$\triangle_{D^{2}}$. We argue that the first of those vertices that is sent to
$\triangle_{D^{2}}$ cannot be sent to a vertex of $\triangle_{L^{2}}$. Indeed,
if $(x_{4},x_{1})$ is sent to a vertex of $\triangle_{L^{2}}$ before
$(l,x_{2})$ for every $l\in L$, it needs to be sent to
$(u,u)\in\triangle_{L^{2}}$ such that $(u,u)\to(x_{1},x_{2})$, so $u\to
x_{1}$, meaning that $u\in L_{n}$. Since we also have
$(x_{4},x_{1})\to(u,x_{2})$ and $(u,x_{2})$ has not been sent to
$\triangle_{L^{2}}$, this would imply $(u,u)\to(u,x_{2})$ which is impossible.
On the other hand, if some $l\in L_{n}$ is such that $(l,x_{2})$ is sent to
$(u,u)\in\triangle_{L^{2}}$ first, then we would have $(x_{4},x_{1})\to(u,u)$
and thus $x_{1}\to u$ and $x_{4}\to u$, implying that $u\in
L\setminus(L_{n}\cup\\{x_{2}\\})$. In this case $(l,x_{2})\to(u,u)$ which is
impossible. Therefore, whichever vertex of
$\\{(x_{4},x_{1})\\}\cup\\{(l,x_{2})\mid l\in L_{n}\\}$ is sent first, it must
be sent to $(x_{5},x_{5})$ for some $x_{5}\in D\backslash V(L)$.

We have two cases: either $(x_{4},x_{1})$ is sent first, or $(l,x_{2})$ for
some $l\in L_{n}$ is sent first. If $(x_{4},x_{1})$ is sent first, then since
$(x_{4},x_{1})\to(l,x_{2})$ for all $l\in V(L)$, necessarily $x_{5}\to l$,
therefore $V(L)\cup\\{x_{5}\\}$ forms an oriented clique that is larger than
$L$. If there is $l$ such that $(l,x_{2})$ is sent first, then
$(x_{4},k)\to(x_{5},x_{5})$ for $k\in L_{n}\cup\\{x_{1}\\}$ and $x_{5}\to
k^{\prime}$ for $k^{\prime}\in L_{m}$. Therefore, $V(L)\cup\\{x_{5}\\}$ forms
an oriented clique than is larger than $L$. In both cases we have reached a
contradiction to the assumption that $n+m$ is largest possible. ∎

######  Lemma 10.

Let $D$ be the dual of a finite set of oriented trees. Assume that there are
$x_{1},x_{2},x_{3}\in V(D)$ such that $x_{1}\to x_{2}\to x_{3}$ and $x_{1}\to
x_{3}$ and $D$ has a subgraph $L_{n}$ that is an oriented clique of size $n$
such that for all $l\in L_{n}$ and $i\in\\{1,2,3\\}$ we have $l\to x_{i}$.
Choose $L_{n}$ so that $n$ is maximal. Then there cannot be $x_{4}\in V(D)$
such that $x_{4}\to x_{1}$, $x_{4}\to x_{2}$, $x_{4}\nrightarrow x_{3}$ and
$x_{4}\to l$ for all $l\in V(L_{n})$.

###### Proof.

Assume for contradiction that there exists $x_{4}\in V(D)$ as in the lemma.
Let $L$ be the subgraph of $D$ induced on $L_{n}\cup\\{x_{1},x_{2},x_{3}\\}$.
We use the fact that $D^{2}$ dismantles into $\triangle_{D^{2}}$ as in the
proof of the previous lemma. In particular, we need to send $(x_{4},x_{2})$
and $(l,x_{3})$ for each $l\in L_{n}\cup\\{x_{1},x_{2}\\}$ somewhere. Looking
at which one needs to be sent first, we can argue that they cannot be sent to
a vertex from $\triangle_{L^{2}}$. Indeed, if $(x_{4},x_{2})$ is sent to a
vertex from $\triangle_{L^{2}}$ before $(l,x_{3})$ for each $l\in
L_{n}\cup\\{x_{1},x_{2}\\}$, then it needs to be sent to
$(u,u)\in\triangle_{L^{2}}$ such that $(u,u)\to(x_{1},x_{3})$, so $u\to
x_{1}$, meaning that $u\in V(L_{n})$. Since we also have
$(x_{4},x_{2})\to(u,x_{3})$ and $(u,x_{3})$ has not been sent to the diagonal,
this is impossible. But if for some $l\in V(L_{n})$ the vertex $(l,x_{3})$ is
sent to $(u,u)\in\triangle_{L^{2}}$ first, then we would have
$(x_{4},x_{2})\to(u,u)$. The only possible $u$ is $x_{3}$, however if that is
the case, $(l,x_{3})$ can not be sent to $(u,u)$, we have a contradiction.

Therefore, there must be $x_{5},x^{l}_{6}\in D\backslash V(L_{n+3})$ such that
$(x_{4},x_{1})$ is sent to $(x_{5},x_{5})$ and $(x_{1},x_{2})$ is sent to
$(x^{l}_{6},x^{l}_{6})$. We have two cases: either $(x_{4},x_{2})$ is sent
first, or one of the $(l,x_{3})$ is sent first. If $(x_{4},x_{2})$ is sent
first, then since $(x_{4},x_{2})\to(l,x_{2})$ for all $l\in V(L_{n})$,
necessarily $x_{5}\to l$, Therefore, $V(L)\cup\\{x_{5}\\}$ forms a larger
oriented clique than $L$. If there is $l$ such that $(l,x_{2})$ is sent first,
then $(x_{4},k)\to(x_{6}^{l},x_{6}^{l})$ for $k\in L_{n}\cup\\{x_{1}\\}$.
Therefore, $V(L)\cup\\{x_{6}^{l}\\}$ forms a larger oriented clique than $L$.
Both cases are in contradiction to the maximal choice of $n$. ∎

######  Lemma 11.

Let $D$ be the dual of a finite set of oriented trees, let $\delta$ be a
density function of $D$, and let $k$ be the size of the largest oriented
clique in $D$. Then the subgraph $S$ of $D$ induced by $\\{v\in
V(D)\mid\delta(v)>0\\}$ is isomorphic to $T_{k}$, and $\delta(u)=1/k$ for
every $u\in V(D)$.

###### Proof.

By Lemma 7 we have that $S$ induces an orientation of a blow-up of $K_{k}$,
for some $k$. Lemma 9 and 10 ensure us that the only orientation of blow-up of
$K_{k}$ contained in $S$ is an orientation of $K_{k}$ itself. Indeed, assume
that there is a subgraph $R$ of $D$ that is a proper blow-up of $K_{k}$,
meaning it strictly contains a copy of $K_{k}$ that we denote by $Q$, in
particular we would get $u\in Q$ and $v\notin Q$ such that $u$ and $v$ have
the same edges and non-edges with the other vertices of $Q$. This, by
maximally of $k$, contradicts either Lemma 9 or Lemma 10 respectively
depending on if $u$ both sends and receives edges from $Q$ or if only receives
edges from the other vertices of $Q$. Therefore, $S$ can only be an
orientation of $K_{k}$ with no vertices blown-up. Hence, by the acyclicity of
$D$ (Proposition 1), we obtain that $S$ is isomorphic to $T_{k}$. The
statement about $\delta$ then follows from Lemma 7. ∎

######  Theorem 5.

Let $D$ be the dual of a finite set of oriented trees. Then there exists an
$\ell\in{\mathbb{N}}$ such that the almost-sure theory of
$\operatorname{CSP}(D)$ equals the almost-sure theory of
$\operatorname{CSP}(T_{\ell})$.

###### Proof.

Theorem 4 implies that asymptotically almost surely a random $D$-coloured
graph is such that all colours come from a copy $H$ of a blow-up of an
orientation of $K_{\ell}$, for some $\ell\in{\mathbb{N}}$. By Lemma 11, $H$ is
in fact isomorphic to $T_{\ell}$. Corollary 3 implies that a labelled digraph
from $\operatorname{CSP}(T_{\ell})$ has exactly one homomorphism to
$T_{\ell}$.

∎

###  4.7 Proofs of the main results

We can finally prove Theorem 3: if $\mathcal{F}$ is a finite set of
orientations of finite trees, the almost-sure theory of $\operatorname{Hom-
Forb}({\mathcal{F}})$ is $\omega$-categorical.

###### Proof of Theorem 3.

Let ${\mathcal{F}}$ be a finite set of orientations of finite trees. By
Theorem 1 there is a finite digraph $D$ such that $\operatorname{Hom-
Forb}(\mathcal{F})=\operatorname{CSP}(D)$. Theorem 5 implies that the almost-
sure theory $T$ of $\operatorname{CSP}(D)$ equals the almost-sure theory of
$\operatorname{CSP}(T_{\ell})$ for some $\ell\geq 1$. By Proposition 4, the
theory $T$ equals $U_{T_{\ell}}$, and $U_{B}$ is $\omega$-categorical by Lemma
3. ∎

As we mentioned, we believe that our results about classes of the form
$\operatorname{CSP}(D)$ where $D$ is a finite digraphs are of independent
interest. As demonstrated in Example 4, these classes do not always have a
first-order 0-1 law. However, our proofs show that their asymptotic behaviour
is composed linearly from finitely many $\omega$-categorical first-order
theories in a sense that we introduce now.

A class ${\mathcal{C}}$ of finite digraphs has a _finite linear combination of
0-1 laws_ if there exists $k\in{\mathbb{N}}$ and classes
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ with first-order $0-1$ laws and
$\lambda_{1},\ldots,\lambda_{k}\in[0,1]$ such that $\sum_{i}\lambda_{i}=1$ and
for all first-order $\tau$-sentences $\phi$

$\phi_{\omega}^{\mathcal{C}}=\sum_{i=1}^{k}\lambda_{i}\phi_{\omega}^{\mathcal{D}_{i}}.$

The following result can be shown by adapting the proof of Theorem 4 to the
setting where we allow double edges, and by performing the arguments in
Section 4.5 for the densest subgraphs. The main argument is that we are able
to define a similar notion of density, where double edges are counted twice,
and use it in the same way. It is to be noted that a double edge has higher
density that any orientation of $K_{\ell}$. The results stating that
$\operatorname{CSP}(D)$ concentrates on its densest parts remains true and so
we obtain the following.

######  Theorem 6.

For every finite digraph $D$, the class $\operatorname{CSP}(D)$ has a finite
linear combination of 0-1 laws.

##  5 Concluding Remarks and Open Problems

Many of the results for digraphs can be generalised to general relational
structures. For the appropriate notion of acyclicity for general structures,
see [18]. Theorem 1 has been generalized to general structures [18] and
therefore, the same approach as we have taken here can be applied to study
$\operatorname{Hom-Forb}({\mathcal{F}})$ where ${\mathcal{F}}$ is a finite set
of acyclic structures. However, we do not know of any elegant characterisation
of the densest substructure for general structures. We conclude with a series
of open questions.

######  Question 1.

Determine the almost-sure theory of $\operatorname{Hom-
Forb}(\\{\vec{C}_{3}\\})$. Is it complete? Is it $\omega$-categorical?

######  Question 2.

Let $\tau$ be a finite relational signature and let ${\mathcal{F}}$ be a
finite set of finite $\tau$-structures. Does $\operatorname{Hom-
Forb}({\mathcal{F}})$ have first-order convergence?

## References

  * [1] M. Bodirsky.  Complexity of Infinite-Domain Constraint Satisfaction.  Lecture Notes in Logic (52). Cambridge University Press, 2021.
  * [2] A. K. Chandra and P. M. Merlin.  Optimal implementation of conjunctive queries in relational data bases.  In Proceedings of the Symposium on Theory of Computing (STOC), pages 77–90, 1977.
  * [3] G. Cherlin, S. Shelah, and N. Shi.  Universal graphs with forbidden subgraphs and algebraic closure.  Advances in Applied Mathematics, 22:454–491, 1999.
  * [4] G. L. Cherlin.  The classification of countable homogeneous directed graphs and countable homogeneous $n$-tournaments.  AMS Memoir, 131(621), January 1998.
  * [5] P. Erdős, D. J. Kleitman, and B. L. Rothschild.  Asymptotic enumeration of ${K}_{n}$-free graphs.  In International Colloquium on Combinatorial Theory, volume Vol. 2, pages 19–27, 1976.  Atti dei Convegni Lincei, Roma.
  * [6] C. Even-Zohar and N. Linial.  Triply existentially complete triangle-free graphs.  Journal of Graph Theory, 78(4):305–317, 2015.
  * [7] R. Fagin.  Generalized first-order spectra and polynomial-time recognizable sets.  Complexity of Computation, 7:43–73, 1974.
  * [8] J. Foniok.  Homomorphisms and structural properties of relational systems.  Doctoral Thesis, Charles University Prague, Faculty of Mathematics and Physics, 2007.
  * [9] P. Hell and J. Nešetřil.  Graphs and Homomorphisms.  Oxford University Press, Oxford, 2004.
  * [10] W. Hodges.  Model theory.  Cambridge University Press, Cambridge, 1993.
  * [11] W. Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [12] P. G. Kolaitis, H. J. Prömel, and B. L. Rothschild.  $K_{l+1}$-free graphs: asymptotic structure and a $0{-}1$ law.  TAMS, 303:637–671, 1987.
  * [13] A. Kruckman.  Disjoint $n$-amalgamation and pseudofinite countably categorical theories.  Notre Dame Journal of Formal Logic, 60(1):139–160, 2019.
  * [14] D. Kühn, D. Osthus, T. Townsend, and Y. Zhao.  On the structure of oriented graphs and digraphs with forbidden tournaments or cycles.  J. Comb. Theory, Ser. B, 124:88–127, 2017.
  * [15] B. Larose, C. Loten, and C. Tardif.  A characterisation of first-order constraint satisfaction problems.  Logical Methods in Computer Science, 3(4:6), 2007.
  * [16] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello.  The DLV system for knowledge representation and reasoning.  CoRR, cs.AI/0211004, 2002.
  * [17] T. Motzkin and E. Straus.  Maxima for graphs and a new proof of a theorem of Turán.  Canadian Journal of Mathematics, 17:533–540, 1965.
  * [18] J. Nešetřil and C. Tardif.  Duality theorems for finite structures.  Journal of Combinatorial Theory, Series B, 80:80–97, 2000.
  * [19] H. J. Prömel and A. Steger.  The asymptotic number of graphs not containing a fixed color-critical subgraph.  Comb., 12(4):463–473, 1992.
  * [20] Rado.  Universal graphs and universal functions.  Acta Arith., 9:331–340, 1964.
  * [21] D. Saracino.  Model companions for $\aleph_{0}$-categorical theories.  Proceedings of the American Mathematical Society, 39:591–598, 1973\.
  * [22] M. L. Y. V. Glebskij, D.I. Kogan and V. Talanov.  Range and degree of realizability of formulas in the restricted predicate calculus.  Kibernetika, 2:17–28, 1969.


# Convex Combinations of Pauli Semigroups: Geometry, Measure and an
Application

Vinayak Jagadish  Quantum Research Group, School of Chemistry and Physics,
University of KwaZulu-Natal, Durban 4001, South Africa  National Institute for
Theoretical Physics (NITheP), KwaZulu-Natal, South Africa  R. Srikanth
Poornaprajna Institute of Scientific Research, Bangalore-560 080, India
Francesco Petruccione  Quantum Research Group, School of Chemistry and
Physics, University of KwaZulu-Natal, Durban 4001, South Africa  National
Institute for Theoretical Physics (NITheP), KwaZulu-Natal, South Africa

###### Abstract

Finite-time Markovian channels, unlike their infinitesimal counterparts, do
not form a convex set. As a particular instance of this observation, we
consider the problem of mixing the three Pauli channels, conservatively
assumed to be quantum dynamical semigroups, and fully characterize the
resulting “Pauli simplex.” We show that neither the set of non-Markovian
(completely positive indivisble) nor Markovian channels is convex in the Pauli
simplex, and that the measure of non-Markovian channels is about 0.87. All
channels in the Pauli simplex are P divisible. A potential application in the
context of quantum resource theory is also discussed.

##  I Introduction

Memory effects in open quantum systems Breuer and Petruccione (2002); Breuer
_et al._ (2016) have become a potential experimental area of research in
quantum information science. At the same time, the theoretical study of non-
Markovian dynamics of open quantum systems continues to gain wide interest and
poses newer conceptual challenges and surprises Li  _et al._ (2018). The
dynamics of open quantum systems are described by time-dependent positive
trace preserving maps, referred to as dynamical maps. If the maps are
completely positive (CP) as well, they are called quantum channels Sudarshan
_et al._ (1961); Jagadish and Petruccione (2018). Interestingly, the question
of what constitutes quantum non-Markovianity has remained elusive. Among
various approaches are that based on CP divisibility Rivas  _et al._ (2010);
Hall  _et al._ (2014), on the distinguishability of states Breuer  _et al._
(2009), and on the operationally motivated process-tensor formulation Pollock
_et al._ (2018).

Recently, there has been an interest in convex combinations of quantum
channels. An example of mixing two Markovian evolutions to create a non-
Markovian one was reported in Chruściński and Wudarski (2015). The idea in a
more rudimentary form (before the divisibility and distinguishability criteria
for quantum non-Markovianity were developed) appears in an earlier paper Wolf
_et al._ (2008). In Breuer  _et al._ (2018), the counterintuitive behavior was
explained in terms of correlations and the information flow between the system
and environment. An example of a convex combination of two non-Markovian
channels leading to a memoryless evolution was discussed in Wudarski and
Chruściński (2016). In Megier  _et al._ (2017), it was also shown that a
master equation with an always negative decay rate arises from a mixture of
Markovian semigroups.

Here, we generalize the idea of mixing channels to the case of three-way
mixing, and discuss the convexity of sets of quantum (non-)Markovian dynamical
maps. For simplicity, we restrict ourselves to the case of Pauli channels,
whose geometrical structure is well understood Bengtsson and Życzkowski
(2017). We show that for finite mixing of two channels, the resultant channel
is non-Markovian throughout, whereas for the case of mixing three channels, a
more complex picture emerges, which we fully characterize. We discuss the
implications of our result and give a measure of the sets of Markovian and
non-Markovian channels. Earlier papers Chruściński and Wudarski (2015);
Wudarski and Chruściński (2016) have noted specific examples of nonconvexity
of Markovian channels. However, this would leave open the question of whether
such examples constitute a zero-measure set. Here, we characterize the full
set of mixing Pauli channels (i.e., evolutions over finite time) and show that
the subset of non-Markovian channels is highly convex and that such examples
have a finite (nonzero) measure. With this demonstration, the implication of
the convexity of Markovian channels is significant for a quantum resource
theoretic approach to non-Markovianity, which is our main result.

Briefly, the framework for a quantum resource theory (QRT) is as follows. A
QRT involves classifying all quantum states into two groups, one consisting of
resource states and the other of free states Chitambar and Gour (2019).
Associated with the free states is a set of free quantum operations that are
naturally motivated and such that the set of free states is closed under the
action of free operations. Further, there must be a measure of resourcefulness
that must be contractive (nonincreasing) under the free operations. A QRT can
address the question of what information processing tasks are (im)possible
using free operations Chitambar and Gour (2019). In a QRT of entanglement, the
resource states are the entangled states, the free states are the separable
states, while free operations are conveniently stochastic local operations and
classical communication.

In the context of studying the properties of sets of quantum channels, the
Choi-Jamiołkowski isomorphism Jamiołkowski (1972) can be conveniently used to
represent channels acting on $d$-dimensional quantum systems as states of
$d^{2}$-dimensional systems. This has been used to show that in contrast to
the case of quantum channels, the set of generators of CP-divisible evolutions
(or equivalently, that Markovian evolutions over small-time intervals) indeed
forms a convex set. This forms a basis for a convex QRT for non-Markovianity,
with resource objects effectively identified with generators of CP-indivisible
channels Bhattacharya  _et al._ (2018); Anand and Brun (2019). Interestingly,
Berk  _et al._ (2019) surveys a variety of potential QRTs for quantum non-
Markovianity based on various identifications of free operations, with
Markovianity defined according to the process tensor approach Pollock  _et
al._ (2018), and identifies one of them as being the appropriate one for
quantum non-Markovianity.

In our framework for a QRT of quantum non-Markovianity, the CP-divisible
channels correspond to the free states and the CP-indivisible channels to the
resource states. The issue then is, what would be the appropriate free
operations in this context, and is studied here. One might consider
compositions of channels as a candidate for free operations. It is not hard to
show that CP-divisible channels are closed under composition, denoted $\circ$.

However, the operation $\circ$ as a free operation acting on CP indivisibility
is not well defined. CP-indivisible channels can lead to entanglement with an
environment, and hence their compositions will generally not lead to quantum
channels. In this light, a natural candidate for free operations on the free
states representing channels can be taken to be the action of forming convex
combinations (i.e., mixing). Quantum channels are closed under mixing: given
CP maps $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ mixed with fractions $\alpha$
and $(1-\alpha)$, the state
$(\alpha\mathcal{E}_{1}+(1-\alpha)\mathcal{E}_{2})(\rho)=\alpha\mathcal{E}_{1}(\rho)+(1-\alpha)\mathcal{E}_{2}(\rho)$,
which is clearly a valid state throughout the domain of validity of
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. All the same, the above results on
nonconvexity suggest that a QRT for non-Markovianity identified with CP
divisibility and free operations with convex combinations would not be
possible.

In a convex QRT, the free states form a convex set. One may consider nonconvex
QRTs corresponding to situations where the mixing is not available due to
physical restrictions or such mixing is easily implementable and leads to
resource states. A pertinent example here would be a QRT of non-Gaussianity,
in the area of continuous-variable quantum information theory, where free
operations taken to be Gaussian operations with adaptive feed-forward, can
produce a convex combination of Gaussian states, which is in general non-
Gaussian Chitambar and Gour (2019).

Alternatively, one might enlarge the set of free states to the convex hull of
Gaussian states, which leads to a convex QRT of non-Gaussianity, where states
outside the hull are considered as “genuinely non-Gaussian” Takagi and Zhuang
(2018). In the present context, one might ask whether a suitable enlargement
of the set of free states can lead to a convex QRT of non-Markovian channels,
or whether a suitable restriction on free operations would lead to a non-
convex QRT for non-Markovian channels.

In this light, one might consider whether other free operations may be
considered to obtain a nonconvex QRT of CP indivisibility, such as local
operations on the system, but their physical motivation is not clear. In the
context of using convex combinations as free operations, one could still
recover a QRT in this scenario, provided all the cases of nonconvexity could
be “quarantined” into a zero-measure set. Thus, the main technical part of our
paper is devoted to studying the geometric structure of the “Pauli simplex,”
obtained by mixing the dynamical semigroup realizations of the three Pauli
channels. This will be seen to be a simple yet nontrivial instance suitable to
answer the above question.

##  II Convex Combination of Two Channels

Consider the channel $\mathcal{E}$ acting on a qubit, represented by the
density matrix

$\rho=\frac{1}{2}(\mathbbm{1}+a_{i}\sigma_{i})=\frac{1}{2}\left(\begin{array}[]{cc}1+a_{3}&a_{1}-\imath
a_{2}\\\ a_{1}+\imath a_{2}&1-a_{3}\end{array}\right).$ (1)

The vector ${\bf a}=(a_{1}\,,\,a_{2}\,,\,a_{3})$, with $|{\bf a}|\leq 1$, is
the Bloch vector. Here, we consider Pauli channels which are unital, as
defined by $\mathcal{E}(\sigma_{I})=\sigma_{I},$ and
$\mathcal{E}(\sigma_{i})=x_{i}\sigma_{i},$ where $\sigma_{I}=\mathbbm{1}$ and
$\sigma_{i}$’s are the Pauli matrices.

Consider the two Pauli channels
$\mathcal{E}_{y}^{p}(\rho)=(1-p)\rho+p\sigma_{y}\rho\sigma_{y}$ and
$\mathcal{E}_{z}^{p}(\rho)=(1-p)\rho+p\sigma_{z}\rho\sigma_{z},$ where $p$ is
the decoherence parameter, where $p=p(t)$ is any monotonically increasing
function such that $p(0)=0$ and $p(\infty)=\frac{1}{2}$. Conservatively, we
choose $p$ to be $[1-\mathrm{exp}(-rt)]/2$, where $r$ is a constant. This
corresponds to a quantum dynamical semigroup (QDS), with a time-independent
Lindblad generator. This choice of $p$ ensuring a QDS is taken since a QDS is
arguably the “most Markovian” according to many criteria, and would thus serve
to emphasize the non-convexity result that we obtain. Note that we use the
same $p$ for each of the Pauli channels, making our study and analysis simple
and interesting.

######  Theorem 1.

Any finite degree of mixing of two Markovian (QDS) Pauli channels results in
non-Markovianity.

For the case of $a=1$, the channel is Markovian corresponding to the two
positive eigenvalues $1\pm\nu$ where $\nu=\frac{1-2q}{1-2p}$. Theorem 1 can be
proven by an argument based on generators, as discussed below.

Proof. Let us consider the convex combination of two channels as

$\displaystyle\mathcal{E}_{\ast}(p)=a\mathcal{E}_{z}^{p}+(1-a)\mathcal{E}_{y}^{p}.$
(2)

The time-local generator $L$ of a channel $\mathcal{E}$, is defined by
$\dot{\mathcal{E}}=L\mathcal{E}$. Quite generally (barring the existence of
non-invertibility), maps and generators for the channel are equivalent and
interconvertible Hall  _et al._ (2014).

The differential form of the channel can be evaluated to be

$L(\rho)=\sum_{k=X,Y,Z}\gamma_{k}(\sigma_{k}\rho\sigma_{k}-\rho),$ (3)

where $\gamma_{k}$’s are the decay rates. Note that we work in the Pauli basis
$\\{\mathbbm{1},\sigma_{i}\\}$. The decay rate, $\gamma_{X}$ turns out to be

$\gamma_{X}=-\left[\frac{(1-a)a(1-p)p}{(1-2p)[1-2(1-a)p](1-2ap)}\right]\dot{p}.$
(4)

For any choice of $a\in(0,1)$, it is clear that $\gamma_{X}$ is always
negative, since expression with the square brackets and $\dot{p}$ in the
right-hand side of this equation are positive. This implies that the mixing of
any two Markovian Pauli channels produces a channel which is non-Markovian. A
similar result follows for the other convex combinations of any other pair of
Pauli channels as well. $\blacksquare$

##  III Convex Combination of Three Channels

Here, we consider the simplex obtained by arbitrary convex combinations of the
three Pauli channels, which are assumed to have a QDS form and the same decay
rate $c$. A general three-way mixture is described by

$\tilde{\mathcal{E}}_{\ast}(p)=a\mathcal{E}_{x}^{p}+b\mathcal{E}_{y}^{p}+c\mathcal{E}_{z}^{p},$
(5)

with $a+b+c=1$ and
$\mathcal{E}_{x}^{p}(\rho)=(1-p)\rho+p\sigma_{x}\rho\sigma_{x}.$ We shall call
this the Pauli simplex. This is an equilateral triangle, whose vertices are
QDS Pauli channels having a constant decay rate.

The differential form of the channel follows to be of the same form as in Eq.
(3), with the decay rates being

$\displaystyle\gamma_{X}$ $\displaystyle=$
$\displaystyle\left(\frac{1-b}{1-2(1-b)p}+\frac{1-c}{1-2(1-c)p}-\frac{1-a}{1-2(1-a)p}\right)\frac{\dot{p}}{2}$
$\displaystyle\gamma_{Y}$ $\displaystyle=$
$\displaystyle\left(\frac{1-a}{1-2(1-a)p}+\frac{1-c}{1-2(1-c)p}-\frac{1-b}{1-2(1-b)p}\right)\frac{\dot{p}}{2}$
$\displaystyle\gamma_{Z}$ $\displaystyle=$
$\displaystyle\left(\frac{1-a}{1-2(1-a)p}+\frac{1-b}{1-2(1-b)p}-\frac{1-c}{1-2(1-c)p}\right)\frac{\dot{p}}{2}.$

For arbitrary choices of $a,$ $b$ and $c$, it can be seen that in general one
or more of the decay rates can become negative, implying the CP indivisibility
(and thus non-Markovian nature) of the channel. The following result holds.

######  Theorem 2.

In the Pauli simplex, (a) neither the set of Markovian channels nor that of
non-Markovian (CP-indivisble) maps is convex; (b) all channels are P
divisible, i.e., Markovian according to the distinguishability criterion.

Proof. The proof of (a) follows readily from Fig. 1, derived in the following
section. Here, the Markovian set is seen to constitute a curved-edge (horn)
triangle within the Pauli simplex and having its vertex angles of
$0^{\degree}$. To prove (b), we note that in Eq. (LABEL:ratesdecaythree), the
decay rate expressions have the form

$\displaystyle\gamma_{X}(a,b,c)$ $\displaystyle=$
$\displaystyle-f(a,p)+f(b,p)+f(c,p)$ $\displaystyle\gamma_{Y}(a,b,c)$
$\displaystyle=$ $\displaystyle f(a,p)-f(b,p)+f(c,p)$
$\displaystyle\gamma_{Z}(a,b,c)$ $\displaystyle=$ $\displaystyle
f(a,p)+f(b,p)-f(c,p),$ (7)

where $f(\alpha,p)\geq 0$ for all $p\in[0,\frac{1}{2})$ and
$\alpha\in\\{a,b,c\\}$. The the sum $\gamma_{i}+\gamma_{j},$ $i,$ $j=X,Y,Z,$
$i\neq j$ is always positive, even though an individual rate may be negative.
For example, $\gamma_{X}+\gamma_{Y}=2f(c,p)\geq 0$. This implies that the
dynamics obtained by the mixing is P divisible and in the qubit context, is
equivalent to Markovianity according to the Breuer-Laine-Piilo
distinguishability criterion Chruściński and Wudarski (2015). $\blacksquare$

##  IV Measure of (non-)Markovian maps in the Pauli triangle

The inherent three-way symmetry in the problem helps simplify the analysis.

######  Lemma 1.

If a channel obtained as a mixture of the three Pauli (QDS) channels is non-
Markovian, then precisely one of the three rates $\gamma_{j}$ is negative.

Proof. It follows from Eq. (7) at most one of the three decay rates can be
negative. Next, note that
$\frac{df(\alpha,p)}{dp}=\frac{2(1-\alpha)^{2}}{(1-2(1-\alpha)p)^{2}}>0$ for
all $p,\alpha$. Thus, in a given rate $\gamma_{j}$ ($j\in\\{X,Y,Z\\}$), two of
the terms will produce a monotonic increase in rate, whereas the negative term
will produce a monotonic decrease. Further, all rate components $\gamma_{j}$
start at a positive value. For example, $\gamma_{Y}(a,b,1-a-b,p=0)=2b$.

Now, suppose $\gamma_{Y}$ is negative in some region, it follows from the
considerations of the preceding paragraph that there is a $p_{0}$ such that
$\gamma_{X}$ is negative for $p\geq p_{0}$ and positive otherwise. That is,
for $p>p_{0}$, we have $f(b,p)>f(a,p)+f(c,p)$, and it remains so for
$p\in[p_{0},\frac{1}{2})$. But, by that token, notice that $\gamma_{Y}$ and
$\gamma_{Z}$ will always be positive throughout. $\hfill\blacksquare$

It follows from Lemma 1 that the regions $\mathcal{R}_{X}$, $\mathcal{R}_{Y},$
and $\mathcal{R}_{Z}$ in the $(a,b,c)$ parameter space, where $\gamma_{X}$,
$\gamma_{Y},$ and $\gamma_{Z}$ turn negative, will be non-overlapping. In Fig.
1, the (convex) regions of negative rates are indicated by the corresponding
symbol.

######  Theorem 3.

The measure of non-Markovian maps in the Pauli simplex is about 0.867.

Proof. As noted, by virtue of the monotony of $f(\alpha,p)$, if a given rate
(say) $\gamma_{Y}(a,b,c,p)$ turns negative at $p=p_{0}$, then it remains
negative throughout the remaining range of $p$, and in particular at
$p=\frac{1}{2}$.

Thus, $\gamma_{Y}(a,b,p)$ will turn negative if and only if

$\displaystyle\gamma_{Y}\left(a,b,\frac{1}{2}\right)$ $\displaystyle=$
$\displaystyle\frac{a+b}{1-a-b}+\frac{1-a}{a}-\frac{1-b}{b}$ (8)
$\displaystyle\equiv$ $\displaystyle\Gamma_{Y}(a,b)<0.$

We wish to determine the set of all points $(a,b)$ that yield negative
$\gamma_{Y}$ at $p=\frac{1}{2}$. To this end, we solve
$\gamma_{Y}(a,b,\frac{1}{2}-x)=0$ for $a$ in terms of $b$, which yields

$a_{\pm}^{Y}(b,x)=\frac{1}{2}\left(\pm\frac{\sqrt{(b-\frac{-2x-1}{2x-1})(b-\frac{2x+1}{2x-1})(b-\frac{2-\sqrt{4x^{2}-4x+5}}{2x-1})(b-\frac{\sqrt{4x^{2}-4x+5}+2}{2x-1})}}{4(b-1)x^{2}-4bx+b+1}-b+1\right).$
(9)

From this, one finds that for $b\in[0,\beta(x)]$, where
$\beta(x)\equiv\frac{2-\sqrt{4x^{2}-4x+5}}{2x-1}$ is the region for which
$\gamma_{Y}(a,b,0.5-x)=0$. In this range, points $(a,b)$ such that
$a\in(a_{-}^{Y}(b,x),a_{+}^{Y}(b,x))$ (respectively,
$[0,a_{-}^{Y}(b,x)]\cup[a_{+}^{Y}(b,x)),1]$) represent those for which
$\gamma_{Y}(a,b,0.5-x)$ is negative (respectively, positive). Regions of
$b>\beta(x)$ are those for which $\gamma_{X}(a,b)$ is still positive for
$p=0.5-x$. Thus, we fully determine $\mathcal{R}_{Y}$, by setting $x:=0$.
Accordingly,

$\displaystyle|\mathcal{R}_{Y}|$ $\displaystyle=$ $\displaystyle
2\int_{b=0}^{\beta(0)}[a_{+}(b,0)-a_{-}(b,0)]db$ (10) $\displaystyle=$
$\displaystyle
2\int_{b=0}^{-2+\sqrt{5}}\frac{\sqrt{b^{4}+4b^{3}-2b^{2}-4b+1}}{b+1}db$
$\displaystyle\approx$ $\displaystyle 0.2898,$

where the pre-factor comes from the normalization
$\int_{a=0}^{1}\int_{b=0}^{1-a}da~{}db=\frac{1}{2}$.

Since the three non-Markovian regions are nonoverlapping, the measure of all
non-Markovian channels in the Pauli simplex is 3$|\mathcal{R}_{Y}|$ which is
0.867. Thus, the measure of Markovian channels in the Pauli triangle is about
0.133. $\blacksquare$

Figure 1: (Color online) The Pauli simplex (outer triangle), whose vertices
are the Pauli QDS channels, and represented in convex coordinates in the
Pauli-neutral representation (see text). The curved-edge (horn) triangle, with
its interior colored magenta, represents the Markovian region, tapering to 0∘
at each vertex. The three convex regions marked $\mathcal{R}_{j}$
$(j\in\\{X,Y,Z\\})$ correspond to non-Markovian (CP indivisible).The
corresponding edges of the horn triangle are described by the equations
$\gamma_{X}(p=\frac{1}{2})=0$, $\gamma_{Y}(p=\frac{1}{2})=0,$ and
$\gamma_{Z}(p=\frac{1}{2})=0$. The area of the horn triangle is about 0.87 of
the Pauli simplex.

Eq. (9) is the equation of $\gamma_{Y}$ in the representation where the
coordinates $(a,b)$ are used. The diagrammatic depiction of the Pauli simplex
in the $(a,b)$ representation, and analogously in the $(a,c)$ or $(b,c)$
representation, is a right angle triangle. With a suitable linear
transformation, one can shift to the “Pauli neutral” representation, which
depicts the Pauli simplex as an equilateral triangle, as shown in Fig. 1.

The curved-edge (horn) triangle in Fig. 1, colored in magenta, encloses the
nonconvex Markovian region. The vertex angles for this triangle are all
$0^{\degree}$. The convex region $\mathcal{R}_{Y}$, of area about 28.98% that
of the Pauli simplex, represents the set of maps where $\gamma_{Y}$ alone
turns negative after a sufficiently long time; similarly for $\mathcal{R}_{X}$
and $\mathcal{R}_{Z}$. However, the union of these three non-Markovian regions
is clearly not convex. Also, while the Markovian region is a connected region,
the non-Markovian region is not, being the union of three disjoint regions.

##  V Discussion and conclusions

The measure of the non-Markovian region in the Pauli simplex being 0.87 means
that if the three channels are mixed in a random proportion, then the
probability that the resulting channel will be non-Markovian is about 0.87.
The measure of CP-indivisible channels in the Pauli simplex can be considered
as a quantification of the nonconvexity of the set of CP-divisible channels in
this example. This unequivocally answers in the negative the question posed
earlier, of whether the instances of nonconvexity are confined to a zero-
measure set. We point out that this strongly constrains any QRT of non-
Markovianity wherein CP-divisible maps correspond to free states.

##  VI Acknowledgements:

V.J. thanks Namit Anand for useful comments on the paper. The work of V.J. and
F.P. is based upon research supported by the South African Research Chair
Initiative of the Department of Science and Technology and National Research
Foundation. R.S. thanks the Defense Research and Development Organization
(DRDO), India for the support provided through Project No.
ERIP/ER/991015511/M/01/1692.

##  Appendix A Intermediate Maps of Convex Combinations of Channels and non-
Markovianity

Consider the convex combination of two channels as in Eq. (2). To check the
non-Markovianity of the channel $\mathcal{E}_{\ast}$ according to the Rivas-
Huelga-Plenio (RHP) criterion Rivas  _et al._ (2010), we consider the
intermediate map $\mathcal{E}_{\ast}(q,p)$ defined by
$\mathcal{E}_{\ast}(q)=\mathcal{E}_{\ast}(q,p)\mathcal{E}_{\ast}(p)$, with
$p\leq q<\frac{1}{2}$ and $a\in(0,1)$. For this, we use the $A$-matrix
representation of the map following Sudarshan  _et al._ (1961); Jagadish and
Petruccione (2018). The $A$ matrix acts on the density matrix expressed as a
column vector. The $A$ matrix for the intermediate map is therefore readily
obtained by $A_{\ast}(a,q,p)=A_{\ast}(a,q)A_{\ast}(a,p)^{-1}$. By rearranging
the entries of $A_{\ast}(a,q,p)$, one obtains the dynamical (or Choi Choi
(1975)) matrix

$\mathfrak{B}_{\ast}(a,q,p)=\frac{1}{2}\left(\begin{array}[]{cccc}1+x_{3}&0&0&x_{1}+x_{2}\\\
0&1-x_{3}&x_{1}-x_{2}&0\\\ 0&x_{1}-x_{2}&1-x_{3}&0\\\
x_{1}+x_{2}&0&0&1+x_{3}\end{array}\right),$ (11)

with $x_{1}=\frac{1-2q}{1-2p},x_{2}=\frac{1-2aq}{1-2ap}$ and
$x_{3}=\frac{2aq-2q+1}{2ap-2p+1}$. For complete positivity of the dynamical
matrix Eq. (11), and hence the Markovianity of $\mathcal{E}_{\ast}$, all
eigenvalues of $\mathfrak{B}_{\ast}(a,q,p)$ must be positive. The conditions
for that can be evaluated to be $\absolutevalue{1\pm
x_{3}}\geq\absolutevalue{x_{1}\pm x_{2}}.$ For $\mathcal{E}_{\ast}(p)$, the
corresponding dynamical matrix is of the form of Eq. (11), with $x_{1}=1-2p,$
$x_{2}=1-2ap,$ and $x_{3}=2ap-2p+1.$ One can easily see that the map
$\mathcal{E}_{\ast}(p)$ is CP irrespective of $a$. However, the intermediate
map is not-completely positive (NCP) [indicative of a negative eigenvalue for
$\mathfrak{B}_{\ast}(a,q,p)$] and hence non-Markovian for all $a\in(0,1)$. For
instance, consider $\mathfrak{B}_{\ast}(0.1,0.45,0.4)$, which has a negative
eigenvalue, $\approx-0.0839$, indicative of the NCP nature of the intermediate
map and hence non-Markovianity. Thus, any nonzero mixing of two Pauli channels
produces non-Markovianity, which generalizes the result of Wudarski and
Chruściński (2016) (corresponding to $a=\frac{1}{2})$. This is an alternate
approach to Theorem 1 making use of the RHP criterion at the level of
intermediate maps.

## References

  * Breuer and Petruccione (2002) H.-P. Breuer and F. Petruccione,  _The Theory of Open Quantum Systems_ (Oxford University Press, New York, 2002).
  * Breuer  _et al._ (2016) H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini, Rev. Mod. Phys. 88, 021002 (2016).
  * Li  _et al._ (2018) L. Li, M. J. W. Hall, and H. M. Wiseman, Phys. Rep. 759, 1 (2018).
  * Sudarshan  _et al._ (1961) E. C. G. Sudarshan, P. M. Mathews, and J. Rau, Phys. Rev. 121, 920 (1961).
  * Jagadish and Petruccione (2018) V. Jagadish and F. Petruccione, Quanta 7, 54 (2018).
  * Rivas  _et al._ (2010) A. Rivas, S. F. Huelga, and M. B. Plenio, Phys. Rev. Lett. 105, 050403 (2010).
  * Hall  _et al._ (2014) M. J. W. Hall, J. D. Cresser, L. Li, and E. Andersson, Phys. Rev. A 89, 042120 (2014).
  * Breuer  _et al._ (2009) H.-P. Breuer, E.-M. Laine, and J. Piilo, Phys. Rev. Lett. 103, 210401 (2009).
  * Pollock  _et al._ (2018) F. A. Pollock, C. Rodríguez-Rosario, T. Frauenheim, M. Paternostro, and K. Modi, Phys. Rev. A 97, 012127 (2018).
  * Chruściński and Wudarski (2015) D. Chruściński and F. A. Wudarski, Phys. Rev. A 91, 012104 (2015).
  * Wolf  _et al._ (2008) M. M. Wolf, J. Eisert, T. S. Cubitt, and J. I. Cirac, Phys. Rev. Lett. 101, 150402 (2008).
  * Breuer  _et al._ (2018) H.-P. Breuer, G. Amato, and B. Vacchini, New J. Phys. 20, 043007 (2018).
  * Wudarski and Chruściński (2016) F. A. Wudarski and D. Chruściński, Phys. Rev. A 93, 042120 (2016).
  * Megier  _et al._ (2017) N. Megier, D. Chruściński, J. Piilo, and W. T. Strunz, Sci. Rep. 7, 1 (2017).
  * Bengtsson and Życzkowski (2017) I. Bengtsson and K. Życzkowski,  _Geometry of Quantum States: An Introduction to Quantum Entanglement_ , 2nd ed. (Cambridge University Press, Cambridge, UK, 2017).
  * Chitambar and Gour (2019) E. Chitambar and G. Gour, Rev. Mod. Phys. 91, 025001 (2019).
  * Jamiołkowski (1972) A. Jamiołkowski, Rep. Math. Phys. 3, 275 (1972).
  * Bhattacharya  _et al._ (2018) S. Bhattacharya, B. Bhattacharya, and A. S. Majumdar, arXiv:1803.06881 [quant-ph] (2018).
  * Anand and Brun (2019) N. Anand and T. A. Brun, arXiv:1903.03880 [quant-ph] (2019).
  * Berk  _et al._ (2019) G. D. Berk, A. J. P. Garner, B. Yadin, K. Modi, and F. A. Pollock, 1907.07003 [quant-ph] (2019).
  * Takagi and Zhuang (2018) R. Takagi and Q. Zhuang, Phys. Rev. A 97, 062337 (2018).
  * Choi (1975) M.-D. Choi, Linear Algebra Appl. 10, 285 (1975).