# An algebraic proof of the graph orientation problem dichotomy for forbidden
tournaments

Roman Feller  Institute of Discrete Mathematics and Geometry
TU Wien
Wiedner Hauptstrasse 8-10/104
1040 Wien
Austria<EMAIL_ADDRESS>and  Michael Pinsker  Institute of Discrete
Mathematics and Geometry
TU Wien
Wiedner Hauptstrasse 8-10/104
1040 Wien
Austria<EMAIL_ADDRESS>
###### Abstract.

Using the theory of smooth approximations, we give a new and algebraic proof
that for any set $\mathcal{F}$ of finite tournaments, the problem of orienting
a finite graph whilst avoiding all members of $\mathcal{F}$ is either in P or
NP-complete. We characterize both cases by algebraic conditions.

Funded by the European Union (ERC, POCOCOP, 101071674). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Research Council Executive
Agency. Neither the European Union nor the granting authority can be held
responsible for them. This research was funded in whole or in part by the
Austrian Science Fund (FWF) [I 5948]. For the purpose of Open Access, the
authors have applied a CC BY public copyright licence to any Author Accepted
Manuscript (AAM) version arising from this submission.

##  1\. Introduction

###  1.1. The graph orientation problem

For a set $\mathcal{F}$ of oriented graphs, the _$\mathcal{F}$ -free
orientation problem_ is the following computational problem: given a finite
undirected graph $G$, can the edges of $G$ be oriented in such a way that the
resulting oriented graph does not contain any member of $\mathcal{F}$?
Recently, Bodirsky and Guzmán-Pro have shown that if $\mathcal{F}$ consists of
tournaments, then this problem is either solvable in polynomial time or NP-
complete [BGP23]. We also refer to the introduction of their work for a nice
exposition of the history of the $\mathcal{F}$-free orientation problem.

The goal of this paper is to provide a new and shorter proof of this
complexity dichotomy which uses the recent algebraic theory of smooth
approximations from [MP22] (see also [MP20]) and lines up smoothly with proofs
of other complexity dichotomies using the same theory, thus making it amenable
to further generalizations. Such generalizations include in particular:

  * •

the $\mathcal{F}$-free orientation problem for sets $\mathcal{F}$ of oriented
graphs which are not necessarily tournaments;

  * •

problems where we are not given a graph, but a list of constraints on vertices
given by quantifier-free formulas over the language of graphs, in the spirit
of Graph-SAT problems studied in [BP15a];

  * •

more general coloring problems as captured by the logic GMSNP introduced in
[BtCLW14].

As a subset of our proof, we also obtain a complexity dichotomy for
_$\mathcal{F}$ -free orientation completion problems_, where we are not given
a finite undirected graph, but a finite undirected graph some of whose edges
are already oriented, and the task remains the same.

###  1.2. Constraint Satisfaction Problems (CSPs)

For any relational structure $\mathbb{A}$, the _Constraint Satisfaction
Problem $\operatorname{CSP}(\mathbb{A})$_ is the class of all finite
structures which have a homomorphism into $\mathbb{A}$; the structure
$\mathbb{A}$ is called a _template_ of the problem. Viewed as a computational
problem, we are given a finite structure $\mathbb{B}$ and have to decide
whether $\mathbb{B}\in\operatorname{CSP}(\mathbb{A})$. We now explain how for
certain $\mathcal{F}$ (including all sets of tournaments), the
$\mathcal{F}$-free orientation problem can be viewed as the CSP of a suitable
template, which is an undirected graph and in general must necessarily be
infinite. The class $\mathcal{K}$ of finite $\mathcal{F}$-free oriented graphs
has the _hereditary property_ , i.e. is closed under (induced) substructures.
Moreover, if all elements of $\mathcal{F}$ are (weakly) connected, then it
also has the _joint embedding property_ , i.e. for any two oriented graphs in
$\mathcal{K}$ there is a graph in $\mathcal{K}$ into which both of them embed.
Thus, there exists an infinite oriented graph $D$ whose induced finite
substructures are precisely the elements of $\mathcal{K}$ up to isomorphism
(obtained basically as the disjoint union of members of $\mathcal{K}$, see
[Hod97]). Let $H$ be the undirected graph reduct of $D$. For any finite
undirected graph $G$ we then have that $G$ embeds into $D$ if and only if it
is a positive instance of the $\mathcal{F}$-free orientation problem. If
$\mathcal{F}$ consists of tournaments (or more generally, is closed under
homomorphic images), this is the case if and only if $G$ has a homomorphism
into $H$. We thus have that the $\mathcal{F}$-free orientation problem is the
same as $\operatorname{CSP}(H)$. This perspective establishes access to the
rich literature on constraint satisfaction problems.

Furthermore, again if $\mathcal{F}$ consists of tournaments, then the class
$\mathcal{K}$ of $\mathcal{F}$-free oriented graphs has the _free amalgamation
property_ , i.e. for any two oriented graphs in $\mathcal{K}$ (with possibly
non-empty intersection) their union is also in $\mathcal{K}$ (for classes of
relational structures this is a strengthening of the joint embedding
property). This implies that the infinite oriented graph $D$ can be chosen to
be _homogeneous_ : any finite isomorphism between finite induced substructures
of $D$ extends to an automorphism of $D$ (see [Hod97]). In fact, there is only
one such structure up to isomorphism which we denote by $D_{\mathcal{F}}$.
Accordingly, we denote the undirected graph reduct of $D_{\mathcal{F}}$ by
$H_{\mathcal{F}}$; thus the $\mathcal{F}$-free orientation problem is equal to
$\operatorname{CSP}(H_{\mathcal{F}})$. The structure $H_{\mathcal{F}}$ has the
advantage that most of the infinite-domain CSP methods apply to it, and in
fact $\operatorname{CSP}(H_{\mathcal{F}})$ falls into the scope of the so-
called Bodirsky-Pinsker conjecture asserting a complexity dichotomy for a more
general class of problems [BPP21], namely CSPs of _first-order reducts of
finitely bounded homogeneous structures_.

##  2\. The Result

To prove our dichotomy result, it will be convenient to make, without loss of
generality, some simplifying assumption on $\mathcal{F}$. If every transitive
tournament is $\mathcal{F}$-free, then every graph $G$ has an
$\mathcal{F}$-free orientation, obtained by orienting its edges along an
arbitrary linear ordering of its vertices. In this case,
$\operatorname{CSP}(H_{\mathcal{F}})$ is trivial. If on the other hand there
is a transitive tournament which is not $\mathcal{F}$-free, then there is a
smallest such tournament, say on $n\geq 1$ vertices. If additionally no
tournament on $n$ vertices is $\mathcal{F}$-free, then a finite graph $G$ has
an $\mathcal{F}$-free orientation precisely when it does not contain a clique
of size $n$: clearly, the existence of such a clique would make an
$\mathcal{F}$-free orientation impossible, and conversely in its absence one
can obtain an $\mathcal{F}$-free orientation using any linear ordering of the
vertices. Therefore, in this situation $\operatorname{CSP}(H_{\mathcal{F}})$
is the computational problem of deciding whether or not a given graph $G$
contains a clique of size $n$, whence
$\operatorname{CSP}(H_{\mathcal{F}})\in\mathrm{P}$. If $\mathcal{F}$ is not of
one of the above forms we say that it is computationally non-trivial: that is,
some transitive tournament is forbidden by $\mathcal{F}$, and for the smallest
such tournament there exists a tournament of the same size that is
$\mathcal{F}$-free.

Before we state our dichotomy in full detail (using technical notions
explained in the preliminaries), let us provide an informal equivalent
description of its two cases. In the first case, $H_{\mathcal{F}}$ can _pp-
interpret_ , i.e. construct in a certain precise way, any finite structure
[BP15b]; it is then follows immediately that
$\operatorname{CSP}(H_{\mathcal{F}})$ is NP-complete. In the second case,
there is a ternary function $f$ acting on the two-element set
$\\{\leftarrow,\to\\}$ whose values are invariant under cyclic permutations of
its arguments, and such that whenever $f$ is applied componentwise to the arcs
of three tuples enumerating $\mathcal{F}$-free graphs (returning no arc
whenever one of the three tuples has no arc), then the resulting tuple also
enumerates an $\mathcal{F}$-free graph. This “symmetry” of
$\operatorname{CSP}(H_{\mathcal{F}})$ implies that it is in P. Note that for
finite $\mathcal{F}$, this tractability condition can be checked
algorithmically.

######  Theorem 1.

Let $\mathcal{F}$ be a finite set of finite tournaments that is
computationally non-trivial. Then precisely one of the following statements
holds.

  * •

The polymorphism clone $\operatorname{Pol}(H_{\mathcal{F}})$ has a uniformly
continuous clone homomorphism to the clone of projections $\mathscr{P}$. In
this case, $\operatorname{CSP}(H_{\mathcal{F}})$ is NP-complete by [BOP18].

  * •

$\operatorname{Pol}(H_{\mathcal{F}})$ contains a ternary operation that is
canonical with respect to $D_{\mathcal{F}}$ and pseudo-cyclic modulo
$\overline{\operatorname{Aut}(D_{\mathcal{F}})}$. In this case,
$\operatorname{CSP}(H_{\mathcal{F}})$ is in P by [BM16].

We obtain the following corollary without the assumption of computational non-
triviality on $\mathcal{F}$.

######  Corollary 2.

Let $\mathcal{F}$ be a finite set of forbidden tournaments. Then precisely one
of the following holds:

  * •

$\operatorname{Pol}(H_{\mathcal{F}})$ has a uniformly continuous clone
homomorphism to $\mathscr{P}$. In this case,
$\operatorname{CSP}(H_{\mathcal{F}})$ is NP-complete.

  * •

$\operatorname{Pol}(H_{\mathcal{F}})$ contains a ternary operation that is
pseudo-cyclic modulo $\overline{\operatorname{Aut}(H_{\mathcal{F}})}$. In this
case, and $\operatorname{CSP}(H_{\mathcal{F}})$ is in $P$.

###### Proof.

If $\mathcal{F}$ is computationally non-trivial, then this is an immediate
consequence of Theorem 1, so let us assume otherwise. Then
$\operatorname{CSP}(H_{\mathcal{F}})$ is in P and equal to the CSP of a graph
$J$ which is either an infinite clique (if every transitive tournament is
$\mathcal{F}$-free, and $\operatorname{CSP}(H_{\mathcal{F}})$ contains all
finite graphs) or the unique homogeneous graph containing all finite
$K_{n}$-free graphs, for some $n\geq 2$ (in the second case of computational
triviality described above). CSPs of structures whose relations can be
expressed (via quantifier-free first-order definitions) in any of these
structures have been completely classified in [BK08, BMPP19]. By a standard
compactness argument, $J$ is in fact a substructure of $H_{\mathcal{F}}$. Now
$J$ is known (and easily seen) to have a pseudo-cyclic polymorphism modulo
$\overline{\operatorname{Aut}(J)}$ [BMPP19]. The proof of [BP20, Corollary
6.2.] shows that also $H_{\mathcal{F}}$ has a pseudo-cyclic polymorphism
modulo $\overline{\operatorname{Aut}(H_{\mathcal{F}})}$. ∎

Recall the $\mathcal{F}$-free orientation completion problem mentioned above.
Bodirsky and Guzmán-Pro in [BGP23] showed that each such problem is equivalent
to the CSP with a 2-element template, and used this fact to obtain their
dichotomy for the $\mathcal{F}$-free orientation problem. We do not take this
approach, but in fact the complexity dichotomy for completion problems is a
subset of our proof. Namely, any such problem is the CSP of the template
$\mathbb{A}$ which has both the (antisymmetric) relation $\to$ of
$D_{\mathcal{F}}$ and the symmetric relation $E$ of $H_{\mathcal{F}}$.
Replacing $H_{\mathcal{F}}$ by $\mathbb{A}$, our proof still works and in fact
significantly simplifies as
$\operatorname{Aut}(\mathbb{A})=\operatorname{Aut}(D_{\mathcal{F}})$.
Similarly, our proof works for any expansion $\mathbb{A}$ of $H_{\mathcal{F}}$
whose relations are invariant under a binary injection as in Lemma 5.

##  3\. Preliminary Facts

All structures appearing in this article are tacitly assumed to be (at most)
countable, and their signatures are assumed to be finite.

###  3.1. Model-theoretic notions

A relational structure $\mathbb{A}$ is homogeneous if every isomorphism
between finite induced substructures of $\mathbb{A}$ extends to an
automorphism of $\mathbb{A}$. If $\mathcal{F}$ is a set of tournaments, then
there exists a homogeneous oriented graph whose (induced) subgraphs are, up to
isomorphism, precisely all $\mathcal{F}$-free oriented graphs (see e.g.
[Hod97]); this oriented graph is unique up to isomorphism and shall be denoted
by $D_{\mathcal{F}}$. It is _$\omega$ -categorical_, i.e. its automorphism
group $\operatorname{Aut}(D_{\mathcal{F}})$ acts on its $k$-tuples
(componentwise) with only finitely many orbits, for all $k\geq 1$. We denote
the underlying set of vertices of $D_{\mathcal{F}}$ by $V$ and its edge
relation by $\to$; the flipped edge relation shall be denoted by $\leftarrow$.

The edge relation $E$ of the undirected graph $H_{\mathcal{F}}$ is defined in
$D_{\mathcal{F}}$ by $\\{(x,y)\;|\;(x\to y)\vee(x\leftarrow y)\\}$. This graph
is not necessarily homogeneous, but $\omega$-categorical since
$\operatorname{Aut}(H_{\mathcal{F}})\supseteq\operatorname{Aut}(D_{\mathcal{F}})$.
In fact, any structure with a first-order definition in $D_{\mathcal{F}}$ is
$\omega$-categorical, for the same reason; such structures are called _first-
order reducts_ of $D_{\mathcal{F}}$. Moreover, $H_{\mathcal{F}}$ is a _model-
complete core_ , i.e. the orbits of the action of
$\operatorname{Aut}(H_{\mathcal{F}})$ on $k$-tuples are _pp-definable_ in
$H_{\mathcal{F}}$, the latter meaning that they are first-order definable
using only conjunction, existential quantification, equality, and the relation
$E$ of $H_{\mathcal{F}}$. The short argument can be found in [BGP23, Theorem
36]. We denote by $N\subseteq V^{2}$ the _non-edges_ of $H_{\mathcal{F}}$,
i.e. injective pairs of vertices which are not adjacent in $H_{\mathcal{F}}$.
Since $N$ is an $\operatorname{Aut}(H_{\mathcal{F}})$-orbit, it is pp-
definable in $H_{\mathcal{F}}$. We say that two tuples $x,y$ of elements of
$V$ of the same length have the same edge-type if the map sending the former
onto the latter is a partial isomorphism on $H_{\mathcal{F}}$. Only if
$H_{\mathcal{F}}$ is homogeneous this is equivalent to $x,y$ belonging to the
same $\operatorname{Aut}(H_{\mathcal{F}})$-orbit.

The class of substructures of $D_{\mathcal{F}}$ has _free amalgamation_ , i.e.
is closed under not necessarily disjoint unions. This implies (see e.g.
[BPP15]) that there exists a linear order $<$ on $V$ such that
$(D_{\mathcal{F}},<):=(V;\to,<)$ is homogeneous and has precisely the class of
linearly ordered $\mathcal{F}$-free graphs as its substructures; it is also
$\omega$-categorical. The order $<$ is isomorphic to the order of the
rationals and the structure $(D_{\mathcal{F}},<)$ is unique up to isomorphism
and called the _free superposition_ of $D_{\mathcal{F}}$ with the order of the
rationals. It enjoys the _Ramsey property_ [HN19], a combinatorial property
whose definition itself will not be needed; we shall make a single reference
to a consequence of it in Section 3.3.

###  3.2. Universal algebraic notions

A _polymorphism_ $f$ of a relational structure $\mathbb{A}$ is a homomorphism
from a finite power $\mathbb{A}^{n}$ of $\mathbb{A}$ to $\mathbb{A}$; here $n$
is said to be the _arity_ of $f$. Polymorphisms are closed under composition
and every coordinate projection $\mathbb{A}^{n}\to\mathbb{A}$ for arbitrary
$n$ is a polymorphism $\mathbb{A}$. This implies that the set
$\operatorname{Pol}(\mathbb{A})$ consisting of all polymorphisms of
$\mathbb{A}$, called the _polymorphism clone_ of $\mathbb{A}$, is a _function
clone_.

In general, a function clone $\mathscr{C}$ on a fixed set $C$, its _domain_ ,
is a set of finitary operations on $C$ containing all projections and closed
under arbitrary composition. For $n\geq 1$, the set of $n$-ary functions of
$\mathscr{C}$ will be denoted by $\mathscr{C}^{(n)}$. We also say that the
clone $\mathscr{C}$ _acts on_ $C$. But $\mathscr{C}$ has various other
actions: on any power $C^{I}$ of $C$, by componentwise evaluation, on any
subset $S$ of $C^{I}$ that is invariant under the action of $\mathscr{C}$, by
restriction, and on $S/\sim$, for an equivalence relation $\sim$ on $S$ that
is invariant under the action of $\mathscr{C}$, by evaluating operations on
representatives of the $\sim$-classes. We write $\mathscr{C}\curvearrowright
C^{I}$, $\mathscr{C}\curvearrowright S$ and $\mathscr{C}\curvearrowright
S/\sim$ for these actions, and call $(S,\sim)$ a _subfactor_ of $\mathscr{C}$.
A subfactor $(S,\sim)$ of $\mathscr{C}$ is said to be _minimal_ if $S/\sim$
consists of at least two elements and any $\mathscr{C}$-invariant subset of
$S$ containing elements from distinct $\sim$-classes equals $S$. A subfactor
$(S,\sim)$ of $\mathscr{C}$ such that $S/\sim$ contains at least two elements
and such that $\mathscr{C}$ acts on $S/\sim$ by projections is called a _naked
set_. Observe that for a minimal naked set $(S,\sim)$, the equivalence
relation $\sim$ has precisely two classes.

For $n\geq 1$, an $n$-ary operation $c$ is called _cyclic_ if it satisfies
$c(a_{1},\ldots,a_{n})=c(a_{2},\ldots,a_{n},a_{1})$ for all elements
$a_{1},\ldots,a_{n}$ of its domain; we indicate this by writing
$c(x_{1},\ldots,x_{n})\approx c(x_{2},\ldots,x_{n},x_{1})$. It is called
_pseudo-cyclic modulo $U$_, where $U$ is a set of unary functions on its
domain, if there exist $u,v\in U$ such that $u\circ
c(x_{1},\ldots,x_{n})\approx v\circ c(x_{2},\ldots,x_{n},x_{1})$. A 6-ary
operation $s$ is called _Siggers_ if $s(x,y,x,z,y,z)\approx s(y,x,z,x,z,y)$.
_Pseudo-Siggers operations modulo $U$_ are defined accordingly. A ternary
operation $m$ is called a _majority_ if $m(x,x,y)\approx m(x,y,x)\approx
m(y,x,x)$. An operation $f$ is _idempotent_ if $f(x,\ldots,x)\approx x$; a
function clone is idempotent if all of its operations are.

A mapping $\xi\colon\mathscr{C}\to\mathscr{D}$ between two function clones is
a _clone homomorphism_ if it preserves arities, maps the $i$th coordinate
projection to the $i$th coordinate projection (of the same arity) and respects
the composition of functions. Spelled out this means, for all $n$ and all
$n$-ary functions $f\in\mathscr{C}$ and all $g_{1},\dots,g_{n}\in\mathscr{C}$
of some arity $k$, it holds
$\xi(f\circ(g_{1},\dots,g_{n}))=\xi(f)\circ(\xi(g_{1}),\dots,\xi(g_{n}))$.
Observe that for a subfactor $(S,\sim)$ of $\mathscr{C}$, the natural mapping
$\xi\colon\mathscr{C}\to(\mathscr{C}\curvearrowright S/\sim)$ is a clone
homomorphism. A clone $\mathscr{C}$ is said to be _equationally trivial_ if it
homomorphically maps into the clone of projections on a two element domain,
which we denote by $\mathscr{P}$. Otherwise it is called _equationally non-
trivial_.

###  3.3. Topology and canonicity

For all $n\geq 1$, the set $V^{V^{n}}$ of all $n$-ary functions on $V$ is
naturally equipped with the _topology of pointwise convergence_ , where for
$f\in V^{V^{n}}$ and $S\subseteq V^{V^{n}}$ we have that $f$ is contained in
the closure $\overline{S}$ of $S$ if for all finite $F\subseteq V^{n}$ there
exists $g_{F}\in S$ which agrees with $f$ on $F$. If $\mathbb{A}$ is any
structure, then $\operatorname{Pol}(\mathbb{A})^{(n)}$ is closed. If
$\mathbb{A}$ is any $\omega$-categorical structure, then
$V^{V^{n}}/\operatorname{Aut}(\mathbb{A})$, defined as the quotient space
where $f,g\in V^{V^{n}}$ are equivalent if $f\in\overline{\\{\alpha
g(x_{1},\ldots,x_{n})\;|\;\alpha\in\operatorname{Aut}(\mathbb{A})\\}}$, is
compact (see e.g. [BP21]).

A function $f\in V^{V^{n}}$ is _canonical_ with respect to $\mathbb{A}$ if $f$
and $f(\beta_{1}(x_{1}),\ldots,\beta_{n}(x_{n}))$ are equivalent in above
factor space for all
$\beta_{1},\ldots,\beta_{n}\in\operatorname{Aut}(\mathbb{A})$; this means that
$f$ preserves the equivalence relations given by the partitions of $k$-tuples
into $\operatorname{Aut}(\mathbb{A})$-orbits, and hence $f$ acts on these
orbits, for all $k\geq 1$. It is called _diagonally canonical_ if this is the
case whenever $\beta_{1}=\cdots=\beta_{n}$. For $f,g\in V^{V^{n}}$, we say
that $g$ locally interpolates $f$ modulo $\operatorname{Aut}(\mathbb{A})$ if
$f\in\overline{\\{\alpha
g(\beta_{1}(x_{1}),\ldots,\beta_{n}(x_{n}))\;|\;\alpha,\beta_{1},\ldots,\beta_{n}\in\operatorname{Aut}(\mathbb{A})\\}}\;.$
_Diagonal interpolation_ is defined similarly, again by requiring
$\beta_{1}=\cdots=\beta_{n}$. Since $(D_{\mathcal{F}},<)$ has the Ramsey
property, every function $g\in V^{V^{n}}$ locally (diagonally) interpolates
modulo $\operatorname{Aut}(D_{\mathcal{F}},<)$ a function which is
(diagonally) canonical with respect to $\operatorname{Aut}(D_{\mathcal{F}},<)$
[BPT13, BP21].

If $\mathscr{C}$ is any function clone on $V$, then _uniform continuity_ of a
clone homomorphism $\phi$ from $\mathscr{C}$ into $\mathscr{P}$ is understood
with respect to the natural metric from which induces the above topology; it
is equivalent to the existence of a finite set $F\subseteq V$ such that
$\phi(f)$ is already determined by the restriction of $f$ to the appropriate
power of $F$, for any $f\in\mathscr{C}$.

###  3.4. The automorphism group of $H_{\mathcal{F}}$

In [AK18] Agarwal and Kompatscher give a description of
$\operatorname{Aut}(H_{\mathcal{F}})$ in terms of
$\operatorname{Aut}(D_{\mathcal{F}})$ whenever the structure $H_{\mathcal{F}}$
is not homogeneous. This description turns out to be useful for our purposes
(it is crucially used in Lemma 5 and Lemma 9), so we detail the relevant
results. For a set $F\subseteq\operatorname{Sym}(V)$, we write $\langle
F\rangle$ to denote the closed subgroup of $\operatorname{Sym}(V)$ generated
by $F$.

A flip of $D_{\mathcal{F}}$ is any function $fl\in\operatorname{Sym}(V)$
preserving $E$ and $N$ and flipping every arc of $D_{\mathcal{F}}$, i.e. every
pair in $\to$ is sent to a pair in $\leftarrow$. Clearly every flip of
$D_{\mathcal{F}}$ is an element of $\operatorname{Aut}(H_{\mathcal{F}})$, but
their existence depends on the set of tournaments $\mathcal{F}$. It is easy to
see that whenever $fl$ is a flip of $D_{\mathcal{F}}$, then the group
$\langle\operatorname{Aut}(D_{\mathcal{F}})\cup\\{fl\\}\rangle$ contains all
flips of $D_{\mathcal{F}}$, and that the inverse of any flip is again a flip
of $D_{\mathcal{F}}$.

A simple switch of $D_{\mathcal{F}}$ is any $sw\in\operatorname{Sym}(V)$
preserving $E$ and $N$ such that there exists some $a\in V$ such that $sw$
inverts an arc of $D_{\mathcal{F}}$ if and only if it is incident to $a$. Any
simple switch of $D_{\mathcal{F}}$ is an element of
$\operatorname{Aut}(H_{\mathcal{F}})$, but their existence depends on the set
of forbidden tournaments $\mathcal{F}$. Again, if $sw$ is some simple switch
of $D_{\mathcal{F}}$, then the closed subgroup
$\langle\operatorname{Aut}(D_{\mathcal{F}})\cup\\{sw\\}\rangle$ contains all
simple switches of $D_{\mathcal{F}}$, and the inverse of any simple switch is
again a simple switch. As a generalization of a simple switch we define for
any finite set $A\subseteq V$ an $A$-switch of $D_{\mathcal{F}}$ to be any
function $sw_{A}\in\operatorname{Sym}(V)$ that preserves $E$ and $N$ and that
flips an arc of $D_{\mathcal{F}}$ precisely if the arc is incident to a unique
vertex in $A$. If we do not specify $A$, we call any such function a _switch_.

######  Theorem 3.

[AK18, Theorem 2.2] If $H_{\mathcal{F}}$ is not homogeneous, then
$\operatorname{Aut}(H_{\mathcal{F}})$ is among the following groups:
$\operatorname{Aut}(D_{\mathcal{F}})$,
$\langle\operatorname{Aut}(D_{\mathcal{F}})\cup\\{fl\\}\rangle$,
$\langle\operatorname{Aut}(D_{\mathcal{F}})\cup\\{sw\\}\rangle$,
$\langle\operatorname{Aut}(D_{\mathcal{F}})\cup\\{fl,sw\\}\rangle$.

######  Corollary 4.

Suppose that $H_{\mathcal{F}}$ is not homogeneous. Then for every
$\alpha\in\operatorname{Aut}(H_{\mathcal{F}})$ and for every finite set
$F\subseteq V$ there exists a switch $\beta$ and a flip $\gamma$ such that
$\alpha$ agrees with $\beta$ or with $\gamma\circ\beta$ on $F$.

###### Proof.

Note that every automorphism of $D_{\mathcal{F}}$ is a $\emptyset$-switch.
Hence, by Theorem 3, we have that $\alpha$ agrees with some permutation
$\beta_{1}\circ\cdots\circ\beta_{n}$ on $F$, where each $\beta_{i}$ is either
a switch or a flip. Since the composition of two switches is a switch, and the
composition of two flips is an automorphism, we may assume that there are no
two consecutive switches or flips in $\beta_{1}\circ\cdots\circ\beta_{n}$.
Moreover, the composition $\gamma\circ\delta$ of a switch $\gamma$ with a flip
$\delta$ is equal to the composition $\delta^{\prime}\circ\gamma^{\prime}$ of
a flip $\delta^{\prime}$ with a switch $\gamma^{\prime}$. The statement
follows. ∎

##  4\. Preparation to Apply Smooth Approximations

For compactness reasons, we denote the polymorphism clone
$\operatorname{Pol}(H_{\mathcal{F}})$ by $\mathscr{C}$ and define the
following subclones of $\mathscr{C}$:

  * •

$\mathscr{C}_{N}$ is the subclone generated by the $N$-dominated
polymorphisms, where $f\in\mathscr{C}^{(n)}$ is said to be $N$-dominated if
for all $x_{1},\dots,x_{n}\in V^{2}$ we have $f(x_{1},\dots,x_{n})\in N$
whenever one of the $x_{i}$ is in $N$. More generally for any subclone
$\mathscr{D}\subseteq\mathscr{C}$ we write $\mathscr{D}_{N}$ for the subclone
of $\mathscr{D}$ generated by the $N$-dominated functions in $\mathscr{D}$.

  * •

$\mathscr{C}^{D_{\mathcal{F}}}$ is the subclone of polymorphisms in
$\mathscr{C}$ which are canonical with respect to $D_{\mathcal{F}}$.

  * •

$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$ is the subclone of polymorphisms
in $\mathscr{C}$ which preserve the equivalence of
$\operatorname{Aut}(D_{\mathcal{F}})$-orbits of injective tuples.

  * •

$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$ is the subclone of polymorphisms
in $\mathscr{C}$ which preserve the equivalence of
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits of injective tuples.

######  Lemma 5.

For all $n\geq 2$ there is an $n$-ary injective operation $g\in\mathscr{C}$
which

  * •

is $(D_{\mathcal{F}},<)$-canonical

  * •

acts lexicographically with respect to the order $<$

  * •

is $D_{\mathcal{F}}$-canonical

  * •

acts as the first projection on the two
$\operatorname{Aut}(D_{\mathcal{F}})$-orbits $\\{\leftarrow,\to\\}$ of
adjacent pairs

  * •

is $N$-dominated, and in fact satisfies $g(X_{1},\ldots,X_{n})\subseteq N$
whenever $X_{1},\ldots,X_{n}$ are $\operatorname{Aut}(D_{\mathcal{F}})$-orbits
of pairs which are not all ${=}$ and not all contained in $E$.

Any such $g$ is contained in $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$.

###### Proof.

We first construct a binary $g$ with the asserted properties (so $n=2$); the
general case is then obtained by considering
$g(x_{1},g(x_{2},g(\ldots,g(x_{n-1},x_{n})))$.

Let $D$ be the oriented graph with vertex set $V^{2}$ and an arc from $(a,b)$
to $(x,y)$ if and only if there is an arc in $D_{\mathcal{F}}$ from $a$ to $x$
and an edge in $H_{\mathcal{F}}$ between $b$ and $y$. The oriented graph $D$,
equipped with the lexicographic order induced by $<$ on pairs, is a
$\mathcal{F}$-free linearly ordered oriented graph, so by a standard
compactness argument there is an embedding $g$ of this structure into
$(D_{\mathcal{F}},<)$. Clearly, $g$ is as desired.

We will now show that $g$ preserves the
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit equivalence of injective tuples.
Let $s,t,s^{\prime},t^{\prime}$ be injective tuples of equal length $k\geq 1$
with entries in $V$ and such that $s,s^{\prime}$ and $t,t^{\prime}$ lie in the
same $\operatorname{Aut}(H_{\mathcal{F}})$-orbit, respectively. We have to
show that the (injective) tuples $r:=g(s,t)$ and
$r^{\prime}:=g(s^{\prime},t^{\prime})$ belong to the same
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit. As $s,s^{\prime}$ and
$t,t^{\prime}$ have the same edge-type respectively, so do $r,r^{\prime}$, by
the definition of $g$. Hence we are done if $H_{\mathcal{F}}$ is homogeneous,
so let us henceforth assume that this is not the case, and that Theorem 3
applies. Note that if there is an arc between two coordinates of $r$, then $s$
has the same arc between the same coordinates; in other words, the arcs on $r$
are obtained by deleting some (possibly empty) set of arcs from $s$. The same
holds true for $r^{\prime}$ and $s^{\prime}$. Let
$\beta\in\operatorname{Aut}(H_{\mathcal{F}})$ be such that
$\beta(s)=s^{\prime}$. By Corollary 4 there is some finite $A\subseteq V$ such
that $\beta$ agrees with a switch $sw_{A}$, or such a switch composed with a
flip, on $s$. Let $I\subseteq\\{1,\dots,n\\}$ be the set of indices such that
$s_{i}\in A$ and define $B:=\\{r_{i}\mid i\in I\\}$. We then have that
$sw_{B}(r)$ or that tuple composed with a flip (if the flip was present in
$\beta$), belongs to the same $\operatorname{Aut}(D_{\mathcal{F}})$-orbit as
$r^{\prime}$. Since $sw_{B}$ (or its composition with a flip) belongs to
$\operatorname{Aut}(H_{\mathcal{F}})$, this finishes the proof. ∎

######  Lemma 6.

Let $\mathscr{D}$ be a function clone whose functions preserve $N$. If
$\mathscr{D}$ contains a pseudo-cyclic function modulo $\mathscr{D}^{(1)}$, as
well as an $N$-dominated function of the same arity, then $\mathscr{D}_{N}$
also contains a pseudo-cyclic function modulo modulo $\mathscr{D}^{(1)}_{N}$.

###### Proof.

Let $e,f,c\in\mathscr{D}$ be so that $e\circ c(x_{1},\ldots,x_{n})\approx
f\circ c(x_{2},\ldots,x_{n},x_{1})$, and let $h(x_{1},\ldots,x_{n})$ be
$N$-dominated. We have

$e\circ c(h(x_{1},\ldots,x_{n}),\ldots,h(x_{n},x_{1}\ldots,x_{n-1}))\approx
f\circ c(h(x_{2},\ldots,x_{n},x_{1}),\ldots,h(x_{1},\ldots,x_{n}))$

and hence the $n$-ary function
$c(h(x_{1},\ldots,x_{n}),\ldots,h(x_{n},x_{1}\ldots,x_{n-1}))$ is pseudo-
cyclic modulo the unary part of $\mathscr{D}_{N}$ as witnessed by
$e,f\in\mathscr{D}_{N}$. But this function clearly is $N$-dominated as well. ∎

######  Lemma 7.

If one of the following clones
$\mathscr{C}^{D_{\mathcal{F}}}_{N},\mathscr{C}^{D_{\mathcal{F}}},\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N},\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$
is equationally trivial, then all of them are equationally trivial; this is
the case if and only if the action of these clones on $\\{\leftarrow,\to\\}$
is equationally trivial.

###### Proof.

Note that all mentioned clones act on $\\{\leftarrow,\rightarrow\\}$, and
these actions agree. Clearly, if this action is equationally trivial, then so
are all mentioned clones. If it is equationally non-trivial, then it contains
a ternary cyclic function $c$ [BK12]. Composing $c$ in its natural action with
a ternary injection provided by Lemma 5 in the same way as in the previous
lemma yields an element of $\mathscr{C}^{D_{\mathcal{F}}}_{N}$ which is
pseudo-cyclic modulo $\overline{\operatorname{Aut}(D_{\mathcal{F}})}$. Since
$\mathscr{C}^{D_{\mathcal{F}}}_{N}$ is contained in all other mentioned
clones, all of them are equationally non-trivial. ∎

##  5\. Applying Smooth Approximations

###  5.1. The Master Proof

If the clone $\mathscr{C}^{D_{\mathcal{F}}}$ is equationally non-trivial, then
so is the action of $\mathscr{C}^{D_{\mathcal{F}}}_{N}$ on
$\\{\leftarrow,\to\\}$, by Lemma 7. Hence, $\mathscr{C}^{D_{\mathcal{F}}}_{N}$
contains a ternary operation that acts as a cyclic operation on
$\\{\leftarrow,\to\\}$ [BK12]. This operation is a pseudo-cyclic operation
modulo $\overline{\operatorname{Aut}(D_{\mathcal{F}})}$ in its natural action,
by a standard compactness argument.

So assume now that $\mathscr{C}^{D_{\mathcal{F}}}$ is equationally trivial. By
Lemma 7 this is equivalent to $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$
being equationally trivial, and hence so is
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ by Lemma 11. Now Lemma 12
provides a $k\geq 1$ such that the action
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is equationally trivial. We argue
that this in turn implies that
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is equationally trivial. Striving
for a contradiction, suppose otherwise. As $H_{\mathcal{F}}$ is a model-
complete core, the clone
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is idempotent, so it would contain
a cyclic operation $c$ of some arity $n$ by Theorem 4.2 of [BK12]. Using an
$n$-ary function $g\in\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ provided
by Lemma 5 one obtains a cyclic operation

$\displaystyle
c(g(x_{1},\dots,x_{n}),g(x_{2},\dots,x_{n},x_{1}),\dots,g(x_{n},x_{1},\dots,x_{n-1}))$

contained in $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ – a contradiction. Hence
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is indeed equationally trivial and
the assumptions of Theorem 8 are met, providing us with a naked set $(S,\sim)$
of $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright I_{k}$ for
which one of two cases applies. In the first case, $(S,\sim)$ is very smoothly
approximated (with respect to $\operatorname{Aut}(H_{\mathcal{F}})$) by a
$\mathscr{C}$-invariant equivalence relation $\eta$, and Proposition 13
provides the desired uniformly continuous clone homomorphism from
$\operatorname{Pol}(H_{\mathcal{F}})$ to the clone of projections
$\mathscr{P}$. The second case of the theorem, on the other hand, leads to a
contradiction in the following way. Namely, it guarantees a weakly commutative
function $f\in\mathscr{C}$ with respect to $(S,\sim)$. Then Lemma 14 yields a
majority operation contained in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$,
so this clone is equationally non-trivial, which is equivalent to
$\mathscr{C}^{D_{\mathcal{F}}}$ being equationally non-trivial, by Lemma 7.
This contradicts our assumption of equational triviality of
$\mathscr{C}^{D_{\mathcal{F}}}$.

###  5.2. Proofs of all Claims of the Master Proof

The following theorem combines several general theorems from [MP20] and
instantiates them for our purposes.

######  Theorem 8.

Let $k\geq 1$, and suppose that
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is equationally trivial. Then there
is a naked set $(S,\sim)$ of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright I_{k}$ with
$\operatorname{Aut}(H_{\mathcal{F}})$-invariant $\sim$-classes such that one
of the following holds:

  1. (1)

The relation $\sim$ is approximated by a $\mathscr{C}$-invariant equivalence
relation $\eta$ on $I_{k}$ that is very smooth with respect to
$\operatorname{Aut}(H_{\mathcal{F}})$: that is, the restriction of $\eta$ to
$S$ is a refinement of $\sim$, and it is there further refined by the
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits.

  2. (2)

$\mathscr{C}$ contains a _weakly commutative function with respect to
$(S,\sim)$_, i.e. a binary function $f$ such that $f(a,b)\sim f(b,a)$ for all
$a,b\in I_{k}$ such that $f(a,b),f(b,a)$ are in $S$ and disjoint.

###### Proof.

We apply Theorem 10 of [MP20] to the clones
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\subseteq\mathscr{C}$ acting on
$I_{k}$ (so in that theorem, $A=I_{k}$ and $n=1$). We have that $\mathscr{C}$
is a model-complete core, and that the action of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$ on $I_{k}$ is canonical with
respect to the set $\operatorname{Aut}(H_{\mathcal{F}})$ of unary invertibles
in $\mathscr{C}$, by definition. We also have that the action of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$ on
$I_{k}/\operatorname{Aut}(H_{\mathcal{F}})$ is equationally trivial. Mentioned
theorem thus indeed applies, and provides a naked set $(S,\sim)$ and two
possible cases.

In the first case, it asserts the existence of the equivalence relation $\eta$
as in item (1) above, which however is only guaranteed to be _presmooth_ with
respect to $\operatorname{Aut}(H_{\mathcal{F}})$. However, in this case we
also obtain a naked set with a very smooth approximation as follows: first
note that $\operatorname{Aut}(H_{\mathcal{F}})$ is _$\ell$ -“primitive”_ for
all $\ell\geq 1$, i.e. any $\operatorname{Aut}(H_{\mathcal{F}})$-invariant
equivalence relation $\theta$ on an
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit $O$ of $\ell$-tuples relating two
disjoint tuples $s,t$ is full. Indeed, picking any $p\in O$ such that $(s,t)$
and $(p,t)$ belong to the same $\operatorname{Aut}(H_{\mathcal{F}})$-orbit and
such that no element of $p$ is adjacent to any element of $s$, we get that
$s\theta t$ implies $p\theta t$, and hence $s\theta p$. We thus see that if
$u,v\in O$ are arbitrary, then picking $p\in O$ whose entries are not adjacent
to any entry in $u,v$ we get $u\theta p$ and $v\theta p$ and thus $u\theta v$.
Now Lemma 8 of [MP20] states that if $(S,\sim)$ is a minimal naked set (with
respect to inclusion) of $k$-tuples, then since
$\operatorname{Aut}(H_{\mathcal{F}})$ is _$k$ -“primitive”_ and since
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$ preserves the relation $\neq$,
any presmooth approximation $\eta$ of $\sim$ is also very smooth with respect
to $\operatorname{Aut}(H_{\mathcal{F}})$.

In the second case, Theorem 10 of [MP20] guarantees that every
$\mathscr{C}$-invariant binary symmetric relation $R$ on $I_{k}$ that contains
a pair $(a,b)\in S^{2}$ with $a\not\sim b$ and $a,b$ disjoint also contains a
pair $(c,c^{\prime})$, where $c,c^{\prime}$ belong to the same
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit. Then our item (2) above follows
immediately from Lemma 13 of [MP20]. ∎

######  Lemma 9.

If $\mathscr{C}^{D_{\mathcal{F}}}$ is equationally trivial, then
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}\subseteq\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$.

###### Proof.

It suffices to prove that every $N$-dominated function
$f\in\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$ is contained in
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$. Lemma 7 implies that the clone
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$
is equationally trivial, so it consists of essentially unary functions by
Post’s classification [Pos41]. Hence for every $N$-dominated
$f\in\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$ of arity $k\geq 1$, there
exists $i\in\\{1,\dots,k\\}$ such that the action of $f$ on
$\\{\leftarrow,\to\\}$ depends only on the $i$th coordinate. Note that for any
injective tuples $a_{1},\ldots,a_{k}$ of the same length we have that for all
arcs of $f(a_{1},\ldots,a_{k})$, there is the same arc in $a_{i}$; just some
arcs from $a_{i}$ might be missing. Given tuples $b_{1},\ldots,b_{k}$ from the
same $H_{\mathcal{F}}$-orbits as $a_{1},\ldots,a_{k}$, we have that
$f(b_{1},\ldots,b_{k})$ has the same edge-type as $f(a_{1},\ldots,a_{k})$. Let
$\alpha\in\operatorname{Aut}(H_{\mathcal{F}})$ be the automorphism sending
$a_{i}$ onto $b_{i}$. The same argument as in the proof of Lemma 5 shows that
there is $\beta\in\operatorname{Aut}(H_{\mathcal{F}})$ such that $\beta\circ
f(a_{1},\dots,a_{k})$ and $f(b_{1},\dots,b_{k})$ belong to the same
$\operatorname{Aut}(D_{\mathcal{F}})$-orbit. This establishes that $f$
preserves the $\operatorname{Aut}(H_{\mathcal{F}})$-orbit equivalence of
injective tuples. ∎

######  Lemma 10.

Let $\mathcal{F}$ be computationally non-trivial. If
$\mathscr{C}^{(D_{\mathcal{F}},<),\mathrm{inj}}_{N}\nsubseteq\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$,
then the action
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}\curvearrowright\\{\leftarrow,\to\\}$
contains a majority operation.

###### Proof.

Let $f$ be an $N$-dominated function contained in
$\mathscr{C}^{(D_{\mathcal{F}},<),\mathrm{inj}}$ which is not contained in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$, and denote its arity by $n$. As
$f$ preserves the edge relation $E$ and the equivalence of
$\operatorname{Aut}(D_{\mathcal{F}},<)$-orbits of injective tuples, it acts on
the set
$S=\\{({\to}\cap{<}),({\to}\cap{>}),({\leftarrow}\cap{<}),({\leftarrow}\cap{>})\\}$
of $\operatorname{Aut}(D_{\mathcal{F}},<)$-orbits of adjacent pairs.

Firstly we will demonstrate that we may assume that $f$ acts idempotently on
$S$ while maintaining its distinctive properties. To do so, let $\hat{f}$ be
the unary map defined by $x\mapsto f(x,\dots,x)$. By composing $f$ with a
suitable self-embedding of $D_{\mathcal{F}}$ from the outside, we may assume
that $\hat{f}$ preserves the order $<$. Then $\hat{f}$ acts on
$S^{\prime}:=\\{({\to}\cap{<}),({\leftarrow}\cap{<})\\}$, and its action on
$S$ is determined by this action. Suppose that the action of $\hat{f}$ on $S$
is not surjective; then $\hat{f}$ is constant on $S^{\prime}$, and either
every edge in the range of $\hat{f}$ is increasing with respect to $<$, or
every edge in the range of $\hat{f}$ is decreasing with respect to $<$.
Consequently, every tournament in $D_{\mathcal{F}}$ is mapped to a transitive
tournament by the endomorphism $\hat{f}$, as its image agrees with the order
$<$. This observation, applied to any tournament in $D_{\mathcal{F}}$ of a
size for which the transitive tournament is forbidden, which exists by
computational nontriviality of $\mathcal{F}$, yields a contradiction.
Therefore $\hat{f}$ is a permutation on $S$, and as $S$ consists of $4$
elements the function $\tilde{f}:=(\hat{f})^{11}\circ f$ acts idempotently on
$S$. Clearly, $\tilde{f}\in\mathscr{C}^{(D_{\mathcal{F}},<),\mathrm{inj}}$ is
still $N$-dominated, and moreover still not contained in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$, since $\hat{f}$ either flips all
edges or preserves them, none of which alters the non-canonicity of $f$ when
composed with $\hat{f}$. Replacing $f$ with $\tilde{f}$ we may henceforth
assume that $f$ acts idempotently on $S$.

Next we claim that for $i\in\\{1,\dots,n\\}$ there exist $o_{i}\in S^{\prime}$
and $q_{i}\in S$ belonging to distinct
$\operatorname{Aut}(D_{\mathcal{F}})$-orbits such that $f(o_{1},\dots,o_{n})$
and $f(q_{1},\dots,q_{n})$ belong to the same
$\operatorname{Aut}(D_{\mathcal{F}})$-orbit. Indeed, otherwise we would have
that for any $p_{1},\dots,p_{n}\in S$, the
$\operatorname{Aut}(D_{\mathcal{F}})$-orbit of $f(p_{1},\dots,p_{n})$ would be
determined by the value of $f(o_{1},\dots,o_{n})$, where $o_{i}$ would be the
unique element of $S^{\prime}$ which is disjoint from $p_{i}$, for all
$i\in\\{1,\dots,n\\}$. Hence, $f$ would act on the
$\operatorname{Aut}(D_{\mathcal{F}})$-orbits in $E$, and being $N$-dominated,
would therefore be an element of $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$,
a contradiction.

Without loss of generality we may assume that
$f(o_{1},\dots,o_{n})\subseteq\to$. By induction on $m\geq 2$ we now prove
that for any $a,b,c\in E^{m}$ such that for every $i\in\\{1,\dots,m\\}$ at
most one of the edges $a_{i},b_{i},c_{i}$ is in $\leftarrow$, there is a
ternary polymorphism $h$ of $H_{\mathcal{F}}$ with $h(a,b,c)\in(\to)^{m}$.

A standard compactness argument, which we now present for the convenience of
the reader then implies the existence of a ternary function
$h\in\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$ acting like a majority
operation on $\\{\leftarrow,\to\\}$. Let $T$ be the set of finite subsets of
$V^{3}$, partially ordered by $\subseteq$. For every $F\in T$ there is a
ternary function $h^{F}\in\operatorname{Pol}(H_{\mathcal{F}})$ which acts like
a majority operation on the edges within $F$. Replacing $h^{F}$ by the
function $(x,y,z)\mapsto
h^{F}\big{(}p^{3}_{1}(x,y,z),p^{3}_{2}(x,y,z),p^{3}_{3}(x,y,z)\big{)}$, where
each $p^{3}_{i}$ is a ternary $N$-dominated function whose existence is
stipulated in Lemma 5 with the $i$th coordinate taking the role of the first
one, we may moreover assume that $h^{F}$ is $N$-dominated within $F$, and
hence $h^{F}$ preserves the $\operatorname{Aut}(D_{\mathcal{F}})$-orbit
equivalence of injective tuples within $F$. Now the net $(h^{F})_{F\in T}$,
yields the desired function $h$. More precisely, recall that
$\operatorname{Pol}(H_{\mathcal{F}})^{(3)}/\operatorname{Aut}(D_{\mathcal{F}})$
is compact. It follows that the net $([h^{F}]_{\theta})_{F\in T}$ has an
accumulation point and we show that any
$h\in\operatorname{Pol}(H_{\mathcal{F}})$ contained in such an accumulation
point preserves the equivalence of
$\operatorname{Aut}(D_{\mathcal{F}})$-orbits of injective tuples and acts as a
majority operation on $\\{\leftarrow,\to\\}$. Observe that $h$ has those
desired properties, whenever it has the desired properties within every $F\in
T$ and let $F\in T$ be such a finite set of triples. As $[h]_{\theta}$ is an
accumulation point of $([h^{F}]_{\theta})_{F\in T}$ the definitions of the
topology of pointwise convergence and of the quotient topology
straightforwardly imply that there is $F^{\prime}\in T$ with $F\subseteq
F^{\prime}$ and $\alpha\in\operatorname{Aut}(D_{\mathcal{F}})$ such that
$\alpha\circ h^{F^{\prime}}|_{F}=h|_{F}$. By construction $h^{F^{\prime}}$ has
the desired properties within $F^{\prime}$, so in particular within $F$, and
since the application of an automorphism of $D_{\mathcal{F}}$ from the outside
preserves the properties in question, also $h$ has the desired properties
within $F$.

We now return to the inductive proof of the statement made before the
compactness argument. In the base case $m=2$ we can take $h$ to be a suitable
projection. In the induction step let $m\geq 3$. By the induction hypothesis
there are ternary
$h,h^{\prime},h^{\prime\prime}\in\operatorname{Pol}(H_{\mathcal{F}})$ such
that within $x:=h(a,b,c)$ all but possibly the first coordinate $x_{1}$,
within $y:=h^{\prime}(a,b,c)$ all but possibly $y_{2}$, and within
$z:=h^{\prime\prime}(a,b,c)$ all but possibly $z_{3}$ are elements of $\to$.
As we are done otherwise, we may assume that $x_{1}$, $y_{2}$, and $z_{3}$
indeed belong to $\leftarrow$. Let $g$ be an injective binary function as in
Lemma 5 acting as the the first projection on $\\{\leftarrow,\to\\}$. This
function allows us to assume that $x,y$ and $z$ have the same equality type,
that is, two elements appearing in pairs in $x$ are equal precisely if the
corresponding elements in $y$ and $z$ are equal: this is achieved by replacing
$x$ by $g(x,g(y,z))$, $y$ by $g(y,g(x,z))$, and $z$ by $g(z,g(x,y))$. We may
assume that there are no repetitions in $x$ (nor in $y$ or $z$), i.e.,
$x_{i}\neq x_{j}$ for all distinct $i,j\in\\{1,\dots,m\\}$, as otherwise we
are done by the induction hypothesis. Moreover, it is impossible that $x_{i}$
is obtained by flipping the entries of $x_{j}$: this is clear if $i,j\neq 1$,
and if $i,j\neq 2$ by the same argument with $y$ (which is of the equality
type as $x$), and if $i,j\neq 3$ by the same argument with $z$.

This ensures that on $x$, viewed as subsets of $V$, there are two linear
orders $\prec,\prec^{\prime}$, which agree everywhere except on the entries of
$x_{1}$, where they disagree. So the assumptions on the equality type of $x$
imply that $\prec$ and $\prec^{\prime}$ in particular agree on $x_{i}$, for
$i\in\\{2,\dots,m\\}$. Simply define a linear order on $x$ that makes the
entries of $x_{1}$ the two largest elements. Then we can flip the order
between the entries of $x_{1}$ without changing the order between the entries
of $x$ that are not contained in $x_{1}$ to obtain $\prec$ and
$\prec^{\prime}$. By possibly flipping both $\prec$ and $\prec^{\prime}$ we
may furthermore assume that the first entry of $x_{2}$ is smaller than the
second entry of $x_{2}$ with respect to $\prec$ and $\prec^{\prime}$. As $x$
and $y$ have the same equality type the same applies to $y$.

By the above discussion there are $u^{k}\in\\{x,y\\}$ as well as
$\alpha_{k}\in\operatorname{Aut}(D_{\mathcal{F}})$ for all
$k\in\\{1,\dots,n\\}$, such that $\alpha_{k}(u^{k}_{1},u^{k}_{2})\in
q_{k}\times o_{k}$ and such that for a fixed $i\in\\{3,\dots,m\\}$ the tuples
$\alpha_{1}(u^{1}_{i}),\dots,\alpha_{n}(u^{n}_{i})$ belong to the same
$\operatorname{Aut}(D_{\mathcal{F}},<)$-orbit. The choice of
$o_{1},\dots,o_{n}$ and $q_{1},\dots,q_{n}$ as well as the fact that $f$ acts
idempotently on $S$ imply that $f(\alpha_{1}u^{1},\dots,\alpha_{n}u^{n})$ is
an element of $(\to)^{m}$, establishing the induction step and the result. ∎

######  Lemma 11.

Let $\mathcal{F}$ be computationally non-trivial. If
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$ is equationally trivial, then
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ is equationally trivial as
well.

###### Proof.

Suppose that $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ is equationally
non-trivial; we prove that $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$
acts non-trivially on $\\{\leftarrow,\rightarrow\\}$. The lemma then follows
by Lemma 7.

First observe that the action of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ on
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits of injective $k$-tuples is
equationally non-trivial for every $k\geq 2$; moreover, it is idempotent since
$H_{\mathcal{F}}$ is a model-complete core. Hence, for each $k\geq 2$ there is
a function $s_{k}\in\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ satisfying
the 6-ary Siggers identity in this action. Any accumulation point $s$ of the
sequence $(s_{k})_{k\geq 2}$ in the 6-ary part of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}/\operatorname{Aut}(H_{\mathcal{F}})$
then satisfies the Siggers identity in all of these actions; such an
accumulation point exists by compactness. In its standard action, the function
$s$ then satisfies the pseudo-Siggers identity on injective tuples, i.e., for
all injective tuples $t_{1},t_{2},t_{3}$ of equal length we have that
$s(t_{1},t_{2},t_{1},t_{3},t_{2},t_{3})$ and
$s(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2})$ belong to the same
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit.

An application of Corollary 6 of [BP21] shows that there exists
$s^{\prime}\in\mathscr{C}^{(D_{\mathcal{F}},<),\mathrm{inj}}_{N}$ which is
locally interpolated by $s$ modulo $\operatorname{Aut}(D_{\mathcal{F}})$.
Suppose $s^{\prime}$ is not contained in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$. Since $\mathcal{F}$ is
computationally non-trivial, Lemma 10 yields a majority operation contained in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$,
which is equivalent to $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$ acting
non-trivially on $\\{\leftarrow,\to\\}$ by Lemma 7. Henceforth we may assume
that $s^{\prime}\in\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$. We claim that
$s^{\prime}$ still satisfies the pseudo-Siggers identity on injective tuples,
as above. Let injective tuples $t_{1},t_{2},t_{3}$ of equal length be given.
On the finite set $S$ consisting of all entries of these tuples, we have

$s^{\prime}(x_{1},\ldots,x_{6})\approx\beta
s(\alpha_{1}x_{1},\ldots,\alpha_{6}x_{6})$

for suitable
$\alpha_{1},\ldots,\alpha_{6},\beta\in\operatorname{Aut}(D_{\mathcal{F}})$.
Moreover, since $s$ acts on $\operatorname{Aut}(H_{\mathcal{F}})$-orbits of
injective tuples, we have

$\displaystyle\gamma s(t_{1},t_{2},t_{1},t_{3},t_{2},t_{3})$
$\displaystyle=s(\alpha_{1}t_{1},\alpha_{2}t_{2},\alpha_{3}t_{1},\alpha_{4}t_{3},\alpha_{5}t_{2},\alpha_{6}t_{3}),$
$\displaystyle\gamma^{\prime}s(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2})$
$\displaystyle=s(\alpha_{1}t_{2},\alpha_{2}t_{1},\alpha_{3}t_{3},\alpha_{4}t_{1},\alpha_{5}t_{3},\alpha_{6}t_{2}),$

for suitable $\gamma,\gamma^{\prime}\in\operatorname{Aut}(H_{\mathcal{F}})$.
Picking $\delta\in\operatorname{Aut}(H_{\mathcal{F}})$ such that

$s(t_{1},t_{2},t_{1},t_{3},t_{2},t_{3})=\delta
s(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2}),$

we get

$\displaystyle s^{\prime}(t_{1},t_{2},t_{1},t_{3},t_{2},t_{3})$
$\displaystyle=\beta
s(\alpha_{1}t_{1},\alpha_{2}t_{2},\alpha_{3}t_{1},\alpha_{4}t_{3},\alpha_{5}t_{2},\alpha_{6}t_{3})$
$\displaystyle=\beta\gamma s(t_{1},t_{2},t_{1},t_{3},t_{2},t_{3})$
$\displaystyle=\beta\gamma\delta s(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2})$
$\displaystyle=\beta\gamma\delta(\beta\gamma^{\prime})^{-1}\beta\gamma^{\prime}s(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2})$
$\displaystyle=\beta\gamma\delta(\beta\gamma^{\prime})^{-1}\beta
s(\alpha_{1}t_{2},\alpha_{2}t_{1},\alpha_{3}t_{3},\alpha_{4}t_{1},\alpha_{5}t_{3},\alpha_{6}t_{2})$
$\displaystyle=\beta\gamma\delta(\beta\gamma^{\prime})^{-1}s^{\prime}(t_{2},t_{1},t_{3},t_{1},t_{3},t_{2}),$

so
$\beta\gamma\delta(\beta\gamma^{\prime})^{-1}\in\operatorname{Aut}(H_{\mathcal{F}})$
proves our claim.

Suppose that $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$ was equationally
trivial. Then its action on $\\{\leftarrow,\rightarrow\\}$ would be
equationally trivial as well by Lemma 7, and hence it would be an action by
essentially unary functions – this follows from Post’s classification of
function clones on a 2-element domain [Pos41]. In particular, this would be
true for $s^{\prime}$. The function $f(x):=s^{\prime}(x,\ldots,x)$ then must
be a permutation of $\\{\leftarrow,\rightarrow\\}$ in this action, by the
assumed non-triviality of $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}_{N}$.
Composing $s^{\prime}$ with $f$ from the outside, we may then assume that
$s^{\prime}$ acts as a projection on $\\{\leftarrow,\rightarrow\\}$, without
loss of generality the first one. Pick injective tuples $a,b$ of equal length
but in different $\operatorname{Aut}(H_{\mathcal{F}})$-orbits. Then
$s^{\prime}(a,b,a,b,b,b)$ and $s^{\prime}(b,a,b,a,b,b)$ belong to the same
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit by the previous paragraph. On the
other hand, since $s^{\prime}$ acts as a projection on
$\\{\leftarrow,\rightarrow\\}$ and is $N$-dominated, $s^{\prime}(a,b,a,b,b,b)$
belongs to the same $\operatorname{Aut}(D_{\mathcal{F}})$-orbit as $a$ and
$s^{\prime}(b,a,b,a,b,b)$ tot he same
$\operatorname{Aut}(D_{\mathcal{F}})$-orbit as $b$, a contradiction. ∎

The following lemma holds for all model-complete cores which have a ternary
injection and which act on orbits of injective tuples.

######  Lemma 12.

If $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ is equationally trivial,
then there is some $k\geq 2$ such that the action of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ on
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits of injective $k$-tuples is
equationally trivial.

###### Proof.

Suppose that the action of $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ on
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits of injective $k$-tuples is
equationally non-trivial for every $k\geq 2$. Since each of this actions is
idempotent, and the underlying set of the action finite, it follows that for
every $k\geq 2$ there is a function $s_{k}$ in
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ which acts as a 6-ary Siggers
operation. Similarly as in Lemma 10, we consider the factor space
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}/\operatorname{Aut}(H_{\mathcal{F}})$,
whose 6-ary part is compact. Thus, the sequence $([s_{k}])_{k\geq 2}$, where
$[f]$ denotes the class of any function $f$ in the factor, has an accumulation
point $[s]$. We then have that $s$ acts as a 6-ary Siggers operation on
$\operatorname{Aut}(H_{\mathcal{F}})$-orbits of injective $k$-tuples for all
$k\geq 2$.

Let $g\in\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ be any ternary
injection provided by Lemma 5 and set $u(x,y,z):=g(x,y,z)$,
$v(x,y,z):=g(y,z,x)$, and $w(x,y,z):=g(z,x,y)$. We have that
$s(u,v,u,w,v,w)(t_{1},t_{2},t_{3})$ and
$s(v,u,w,u,w,v)(t_{1}^{\prime},t_{2}^{\prime},t_{3}^{\prime})$ belong to the
same $\operatorname{Aut}(H_{\mathcal{F}})$-orbits whenever
$t_{1},t_{2},t_{3},t_{1}^{\prime},t_{2}^{\prime},t_{3}^{\prime}$ are finite
tuples of equal length such that $t_{i},t_{i}^{\prime}$ belong to the same
$\operatorname{Aut}(H_{\mathcal{F}})$-orbit for all $1\leq i\leq 3$. This
implies that there exist
$e,f\in\overline{\operatorname{Aut}(H_{\mathcal{F}})}$ such that the identity

$e\circ s(u,v,u,w,v,w)(x,y,z)\approx f\circ s(v,u,w,u,w,v)(x,y,z)$

holds in the standard action of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$. This identity, when written
using $g$ rather than $u,v,w$ (along with $e,f,s$), is non-trivial, hence
showing that $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}_{N}$ is indeed
equationally non-trivial. ∎

######  Proposition 13.

Let $\mathcal{F}$ be a finite set of finite tournaments that is
computationally non-trivial. If $\mathscr{C}^{D_{\mathcal{F}}}$ is
equationally trivial and we are in situation (1) of Theorem 8, then there is a
uniformly continuous clone homomorphism $\mathscr{C}\to\mathscr{P}$.

###### Proof.

It suffices to construct a uniformly continuous clone homomorphism
$\mathscr{C}\to\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
S/\sim$, since $(S,\sim)$ is a naked set of
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright I_{k}$.

First we will demonstrate that we can assume that all tuples in $S$ have the
same edge-type. To do so, pick any $x,y\in S$ with $x\not\sim y$, and set
$x^{\prime}:=g(x,y)$ and $y^{\prime}:=g(y,x)$, where $g$ is as in Lemma 5.
Then $x^{\prime},y^{\prime}\in S$ have equal edge-type and $x\not\sim y$ since
$g$, being an element of $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$, acts as
a projection on $\sim$-classes. Since $\mathscr{C}$ preserves $E$ and $N$, the
set of all $k$-tuples of the same edge-type as $x^{\prime},y^{\prime}$ is
$\mathscr{C}$-invariant; hence, restricting $S$ to such tuples yields a naked
set with the desired property.

By Lemma 5, for every $n\geq 1$ and every $1\leq i\leq n$ there is an $n$-ary
$(D_{\mathcal{F}},<)$-canonical injection $p^{n}_{i}$ which follows the $i$th
coordinate for the order $<$, acts like the $i$th projection on
$\\{\leftarrow,\rightarrow\\}$, and such that $p^{n}_{i}(a_{1},\ldots,a_{n})$
belongs to $N$ whenever $a_{1}\ldots,a_{n}$ are pairs not all belonging to $E$
and not all belonging to ${=}$. Note that in particular, $p^{n}_{i}$ then acts
as the $i$th projection on $S/\operatorname{Aut}(D_{\mathcal{F}})$.

We now construct the clone homomorphism
$\phi\colon\operatorname{Pol}(H_{\mathcal{F}})\to\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright
S/\sim$ as follows. Given an $n$-ary $f\in\operatorname{Pol}(H_{\mathcal{F}})$
we let $f^{\prime}$ be a $(D_{\mathcal{F}},<)$-canonical function which is
locally interpolated by $f$ modulo $\operatorname{Aut}(D_{\mathcal{F}},<)$.
The existence of such a function $f^{\prime}$ follows from Corollary 6 of
[BP21] together with the fact that $(D_{\mathcal{F}},<)$ is a Ramsey structure
implying that its automorphism group is extremely amenable [Kec95]. We then
set $f^{\prime\prime}=f^{\prime}(p^{n}_{1},\dots,p^{n}_{n})$ which is an
$N$-dominated $(D_{\mathcal{F}},<)$-canonical function. Moreover,
$f^{\prime\prime}$ is injective: if $(a_{1},\ldots,a_{n})$ is a tuple of pairs
in $V^{2}$ which do not all belong to $=$, then, independently of $i$, we have
that $p^{n}_{i}(a_{1},\ldots,a_{n})$ belongs to $E$ if and only if all of the
$a_{j}$ do, and to $N$ otherwise. Hence, further application of $f$ yields
either an element of $E$ or of $N$, since these two sets are invariant under
$f$. We next claim that
$f^{\prime\prime}\in\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$. Otherwise,
Lemma 10 implies that
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$
contains a majority operation, so by Lemma 7, $\mathscr{C}^{D_{\mathcal{F}}}$
would be equationally non-trivial, contradicting the assumption of this
proposition. An application of Lemma 9 shows that $f^{\prime\prime}$, being
$N$-dominated, is contained in $\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$,
so it acts on the set $S/\sim$.

We now let $\phi(f)$ be the action of $f^{\prime\prime}$ on $S/\sim$, and
claim that this assignment is well-defined. To see this, we will first argue
that for any $u_{1},\dots,u_{n}\in S$ we have

$\displaystyle
f^{\prime\prime}(u_{1},\dots,u_{n})\,\sim\,f^{\prime}(u_{1},\dots,u_{n})\,({\sim}\circ\eta)\,f(u_{1},\dots,u_{n})\;.$

Indeed, for the first equivalence observe that since all elements of $S$ are
of the same edge-type, we have that $u_{i}$ and
$p^{n}_{i}(u_{1},\ldots,u_{n})$ belong to the same $(D_{\mathcal{F}},<)$-orbit
and hence to the same $\sim$-class for all $i$; since $f^{\prime}$ is
$(D_{\mathcal{F}},<)$-canonical, its application to the $u_{i}$ and the
$p_{i}(u_{1},\ldots,u_{n})$ therefore yields tuples in the same
$(D_{\mathcal{F}},<)$-orbit, and hence in the same $\sim$-class; in particular
we see that $f^{\prime}(u_{1},\ldots,u_{n})\in S$. For the second equivalence,
note that $f^{\prime}(u_{1},\ldots,u_{n})=\alpha
f(\beta_{1}u_{1},\ldots,\beta_{n}u_{n})$ for some
$\alpha,\beta_{1},\ldots,\beta_{n}\in\operatorname{Aut}(D_{\mathcal{F}},<)$.
Since the approximation $\eta$ is very smooth with respect to
$\operatorname{Aut}(H_{\mathcal{F}})$, we have that $u_{i}$ and
$\beta_{i}u_{i}$ are $\eta$-related for all $i$. With $f$ preserving $\eta$,
this implies that $f(\beta_{1}u_{1},\ldots,\beta_{n}u_{n})$ and
$f(u_{1},\ldots,u_{n})$ are $\eta$-related, and since $\sim$-classes are
$\operatorname{Aut}(H_{\mathcal{F}})$-invariant we moreover get that
$f^{\prime}(u_{1},\dots,u_{n})$ and $f(\beta_{1}u_{1},\dots,\beta_{n}u_{n})$
are $\sim$-related, proving the the claim.

It follows from the above that
$\phi(f)([u_{1}]_{\sim},\dots,[u_{n}]_{\sim})=[f^{\prime\prime}(u_{1},\dots,u_{n})]_{\sim}=[f(u_{1},\dots,u_{n})]_{\eta\circ\sim}$
implying that $\phi(f)$ does not depend on the choice of $f^{\prime}$. Observe
moreover that since $S/\sim$ is finite, $\phi$ is a uniformly continuous
mapping; it remains to show that it is a clone homomorphism. Clearly, $\phi$
preserves arities and projections, so we are left showing that it preserves
composition. Let $f\in\mathscr{C}$ be $n$-ary, $g_{1},\dots,g_{n}$ be $m$-ary
and $c_{1},\dots,c_{m}\in S/\sim$. We calculate setwise

$\displaystyle\phi(f(g_{1},\dots,g_{n}))(c_{1},\dots,c_{m})$
$\displaystyle=\big{[}f\big{(}g_{1}(c_{1},\dots,c_{m}),\dots,g_{n}(c_{1},\dots,c_{m})\big{)}\big{]}_{\eta\circ\sim}$
$\displaystyle=\big{[}f\big{(}[g_{1}(c_{1},\dots,c_{m})]_{\eta},\dots,[g_{n}(c_{1},\dots,c_{m})]_{\eta}\big{)}\big{]}_{\eta\circ\sim}$
$\displaystyle=\big{[}f\big{(}[g_{1}(c_{1},\dots,c_{m})]_{\eta}\cap
S,\dots,[g_{n}(c_{1},\dots,c_{m})]_{\eta}\cap S\big{)}\big{]}_{\eta\circ\sim}$
$\displaystyle\subseteq\big{[}f\big{(}[g_{1}(c_{1},\dots,c_{m})]_{\eta\circ\sim},\dots,[g_{n}(c_{1},\dots,c_{m})]_{\eta\circ\sim}\big{)}\big{]}_{\eta\circ\sim}$
$\displaystyle=\phi(f)(\phi(g_{1}),\dots,\phi(g_{n}))(c_{1},\dots,c_{m}),$

and since $\phi(f(g_{1},\dots,g_{n}))(c_{1},\dots,c_{m})$ and
$\phi(f)(\phi(g_{1}),\dots,\phi(g_{n}))(c_{1},\dots,c_{m})$ are both
$\sim$-classes they have to be equal, proving that $\phi$ preserves
composition. ∎

######  Lemma 14.

Let $\mathcal{F}$ be computationally non-trivial. Suppose that $k\geq 1$ and
that $(S,\sim)$ is a naked set for
$\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}\curvearrowright I_{k}$ with
$\operatorname{Aut}(H_{\mathcal{F}})$-invariant classes. If $\mathscr{C}$
contains a binary function $f$ which is weakly commutative with respect to
$(S,\sim)$, then
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$
contains a majority operation.

###### Proof.

Let $g$ be a binary polymorphism of $H_{\mathcal{F}}$ as in Lemma 5. Observe
that the binary polymorphism $h$ defined by $(x,y)\mapsto f(g(x,y),g(y,x))$ is
injective since $g$ is and since $\not=$ is preserved by all polymorphisms of
$H_{\mathcal{F}}$, in particular by $f$. Moreover, $h$ is still weakly
commutative: if for $a,b\in I_{k}$ we have $h(a,b),h(b,a)\in S$, then setting
$a^{\prime}:=g(a,b)$ and $b^{\prime}:=g(b,a)$ we obtain
$f(a^{\prime},b^{\prime}),f(b^{\prime},a^{\prime})\in S$, and hence
$h(a,b)=f(a^{\prime},b^{\prime})\sim f(b^{\prime},a^{\prime})=h(b,a)$. Hence
replacing $f$ by $h$ we can assume that $f$ is itself injective. As the
distinctive property of $f$ is stable under diagonal interpolation, we can
also assume that $f$ is diagonally canonical with respect to
$\operatorname{Aut}(D_{\mathcal{F}},<)$.

Let $O=(N\cap{<})$ and $O^{\prime}=(N\cap{>})$. Diagonal canonicity of $f$
implies that within $O$ the function $f$ acts on the set
$\\{({\leftarrow}\cap{<}),({\leftarrow}\cap{>}),({\to}\cap{<}),({\to}\cap{<})\\}$
of $\operatorname{Aut}(D_{\mathcal{F}},<)$-orbits of adjacent pairs, i.e.
whenever $x,y\in E$ with $(x_{i},y_{j})\in O$ for $i,j\in\\{1,2\\}$, then the
$\operatorname{Aut}(D_{\mathcal{F}},<)$-orbit of $f(x,y)$ only depends on the
$\operatorname{Aut}(D_{\mathcal{F}},<)$-orbits of $x$ and $y$. The same holds
true for $O^{\prime}$. An application of Lemma 10 shows that we may assume
that within $O$ and $O^{\prime}$, $f$ also acts on the set
$\\{\leftarrow,\to\\}$ of $\operatorname{Aut}(D_{\mathcal{F}})$-orbits of
adjacent pairs: otherwise, let $e_{1},e_{2}$ be self-embeddings of
$(D_{\mathcal{F}},<)$ such that $(e_{1}(x),e_{2}(y))\in O$ for all $x,y\in V$
(or in $O^{\prime}$ for the other case). Then the function
$f(e_{1}(x),e_{2}(y))$ is $N$-dominated and contained in
$\mathscr{C}^{(D_{\mathcal{F}},<),\mathrm{inj}}$ but not in
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$, so Lemma 10 implies that
$\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}\curvearrowright\\{\leftarrow,\to\\}$
contains a majority and we are done.

So we may henceforth assume that within $O$ and $O^{\prime}$, the function $f$
acts on $\\{\leftarrow,\to\\}$. It is easy to see that this action is
necessarily essentially unary in both cases as no other function
$\\{\leftarrow,\to\\}$ can be induced by a function on $D_{\mathcal{F}}$.
Similarly, one sees that the two actions on $\\{\leftarrow,\to\\}$ cannot be
constant, and hence are either by a projection, or by a projection composed
with the unique non-trivial permutation of $\\{\leftarrow,\to\\}$. Moreover,
if one of the actions is not by a projection, then
$\overline{\operatorname{Aut}(H_{\mathcal{F}})}$ contains a function which
acts as the non-trivial permutation on $\\{\leftarrow,\to\\}$, obtained as
$x\mapsto f(e_{1}(x),e_{2}(x))$, where $e_{1}$ and $e_{2}$ are self-embeddings
as above. In this case $\operatorname{Aut}(H_{\mathcal{F}})$-orbits are
invariant under flipping all edges of the underlying oriented graph structure.

We will now demonstrate that the actions within $O$ and $O^{\prime}$ on
$\\{\leftarrow,\to\\}$ cannot depend on the same argument. Striving for a
contradiction, suppose without loss of generality that both actions depend on
the first argument. Then for any $a,b\in S$ of the same edge-type and with
$(a_{i},b_{j})\in O$ for all $i,j\in\\{1,\dots,k\\}$, we have that $f(a,b)$
belongs to the $\operatorname{Aut}(H_{\mathcal{F}})$-orbit of $a$, and in
particular is an element of $S$; similarly, since $(b_{j},a_{i})\in
O^{\prime}$ for all $i,j\in\\{1,\dots,k\\}$, we see that $f(b,a)$ belongs to
the $\operatorname{Aut}(H_{\mathcal{F}})$-orbit of $b\in S$. This immediately
contradicts $f(a,b)\sim f(b,a)$ whenever $a\not\sim b$. But such $a,b$ meeting
our assumptions above exist, as they can be obtained by taking any
$\sim$-inequivalent $a^{\prime},b^{\prime}\in S$, and setting $a=e_{1}\circ
g(a^{\prime},b^{\prime})$ and $b=e_{2}\circ g(b^{\prime},a^{\prime})$, with
$g,e_{1},e_{2}$ as above; here we use that
$g\in\mathscr{C}^{H_{\mathcal{F}},\mathrm{inj}}$ acts as a projection on
$\sim$-classes. Henceforth we may therefore assume that $f$ depends on the
first argument on $O$ and on the second argument on $O^{\prime}$.

We now consider the atomic diagonal $(H_{\mathcal{F}},<)$-type $B$ of two non-
adjacent edges $x,y$, i.e. of $(x,y)\in E^{2}$ with $(x_{i},y_{j})\in N$ for
$i,j\in\\{1,2\\}$. More precisely $B$ consists of all pairs of tuples $(u,v)$
such that $uv$ is the the range of a partial isomorphism of
$(H_{\mathcal{F}},<)$ with domain $xy$. Diagonal canonicity of $f$ implies
that within each such type $B$, $f$ acts on the set $\\{\leftarrow,\to\\}$. We
can moreover assume that the action of $f$ on $\\{\leftarrow,\to\\}$ within
each such type is idempotent or constant, by replacing $f$ with $f(e_{1}\circ
f(x,y),e_{2}\circ f(x,y))$, where $e_{1},e_{2}$ are self-embeddings of
$D_{\mathcal{F}}$ ensuring that the atomic diagonal $(H_{\mathcal{F}},<)$-type
of $(a,b)$ is the same as the atomic diagonal $(H_{\mathcal{F}},<)$-type of
$(e_{1}\circ f(a,b),e_{2}\circ f(a,b))$ for all pairs of non-adjacent edges
$(a,b)$. For the convenience of the reader, we give the elementary argument
showing the existence of such $e_{1}$ and $e_{2}$. Let $D$ be the oriented
graph obtained as the disjoint union of two copies $D_{1},D_{2}$ of
$D_{\mathcal{F}}$, i.e. there are no edges between $D_{1}$ and $D_{2}$. Let
$s,t$ be sequences in $V$ such that $(s,t)$ is an enumeration of $V^{2}$. We
consider the sequence $f(s,t)$ as a sequence $x$ in $D_{1}$ (via some
isomorphism $q_{1}$ from $D_{\mathcal{F}}$ onto $D_{1}$), and also similarly
as a sequence $y$ in $D_{2}$ (via some isomorphism $q_{2}$). Now $f$ being
injective implies that there is a linear order $<_{D}$ on $D$ such that all
inequalities witnessed on the pair of sequences $(s,t)$ with respect to $<$
are also witnessed on $(x,y)$ with respect to $<_{D}$, i.e. for all natural
numbers $i,j$ we have that $s_{i}<s_{j}$ implies $x_{i}<_{D}x_{j}$, that
$t_{i}<t_{j}$ implies $y_{i}<_{D}y_{j}$, that $s_{i}<t_{j}$ implies
$x_{i}<_{D}y_{j}$, and that $t_{i}<s_{j}$ implies $y_{i}<_{D}x_{j}$. The
ordered oriented graph $(D,<_{D})$ embeds into $(D_{\mathcal{F}},<)$ via an
embedding $e$ and we can set $e_{i}=e\circ q_{i}$ for $i=1,2$.

Suppose that the action of $f$ on $\\{\leftarrow,\to\\}$ within the atomic
diagonal $(H_{\mathcal{F}},<)$-type $B$ of a pair of non-adjacent edges was
constant. Without loss of generality we may assume that within $B$ it holds
$f(\to,\to)=f(\leftarrow,\leftarrow)={\to}$. We now demonstrate that this
implies that every tournament in $D_{\mathcal{F}}$ induced by an injective
tuple $a$, is mapped by some unary function in $\mathscr{C}$ to a tuple all of
whose edges point forward within the tuple, contradicting the assumption that
$\mathcal{F}$ is computationally non-trivial. This is achieved by induction on
the length of $a$. If the length of $a$ is $2$, we pick
$\alpha,\beta\in\operatorname{Aut}(D_{\mathcal{F}})$ so that
$(\alpha(a),\beta(a))$ is in $B$ implying that $x\mapsto
f(\alpha(x),\beta(x))$ is the desired function. For the inductive step assume
that the length of $a$ is $n+1$, for some $n\geq 2$. By the induction
hypothesis we may assume that all edges within the first $n$ entries of $a$
point forward. Assume first that for $(u,v)\in B$ it holds $u_{1}<v_{1}$. Let
$\alpha,\beta\in\operatorname{Aut}(D_{\mathcal{F}})$ so that for
$a^{\prime}=\alpha(a)$ and $a^{\prime\prime}=\beta(a)$ it holds
$(a^{\prime}_{i},a^{\prime\prime}_{j})\in O$, for $1\leq i,j\leq n$ and
$((a^{\prime}_{i},a^{\prime}_{n+1}),(a^{\prime\prime}_{i},a^{\prime\prime}_{n+1}))\in
B$, for $1\leq i\leq n$; this is possible since the imposed conditions do not
force a cycle on the tuple $a^{\prime}a^{\prime\prime}$ with respect to the
order $<$. Then , $x\mapsto f(\alpha(x),\beta(x))$ is the desired unary
function in $\mathscr{C}$. If for $(u,v)\in B$ it holds $u_{1}>v_{1}$ the same
argument with $O^{\prime}$ instead of $O$ yields the desired conclusion.

In summary, we now know that within the atomic diagonal
$(H_{\mathcal{F}},<)$-type of every pair of non-adjacent edges, $f$ acts on
$\\{\leftarrow,\to\\}$ as a projection or as a semilattice operation, setting
the stage for the final step in the proof, the construction of a ternary
function in $\mathscr{C}^{D_{\mathcal{F}},\mathrm{inj}}$ acting like a
majority on $\\{\leftarrow,\to\\}$.

Just like in the proof of Lemma 10 it suffices to show by induction on $m\geq
2$ that for all tuples $a,b,c\in E^{m}$ such that for every $1\leq i\leq m$ at
most one of the pairs $a_{i},b_{i},c_{i}$ is in $\leftarrow$, there exists a
ternary $h\in\mathscr{C}$ such that $h(a,b,c)\in\to^{m}$. For the base case
$m=2$ we can take $h$ to be a suitable ternary projection. For the induction
step let $m\geq 3$ and $a,b,c\in E^{m}$. Clearly we can assume that there are
no repetitions, i.e. $(a_{i},b_{i},c_{i})\not=(a_{j},b_{j},c_{j})$ for all
$1\leq i<j\leq m$. Using the same trick as in the proof of Lemma 10 we may
also assume that the kernels of $a,b$ and $c$ are identical. This implies that
there cannot be $i,j\in\\{1,\dots,m\\}$ such that flipping the pair $a_{i}$
yields $a_{j}$, as otherwise the same would be true for $b_{i}$ and $b_{j}$ as
well as for $c_{i}$ and $c_{j}$, contradicting the fact that for all $1\leq
i\leq m$ at most one of the pairs $a_{i},b_{i},c_{i}$ is in $\leftarrow$. By
the induction hypothesis we may assume that all but the second component of
$a$ are in $\to$ and all but the first component of $b$ are in $\to$, while
the assumptions about the kernels of $a$ and $b$ are still true. By applying
suitable automorphisms of $D_{\mathcal{F}}$ to $a$ and $b$ respectively, we
can moreover assume that no element of a pair in $a$ is adjacent to any
element of a pair in $b$.

If no equalities hold between $a_{1}$ and $a_{2}$ then there is
$\alpha\in\operatorname{Aut}(H_{\mathcal{F}})$ with
$(\alpha(a_{1}),\alpha(b_{1}))\in O$ and $(\alpha(a_{2}),\alpha(b_{2}))\in
O^{\prime}$. Moreover, $(\alpha(a_{i}),\alpha(b_{i}))$ is a pair of non-
adjacent edges for $3\leq i\leq m$, and so $f$ acts oidempotently on
$\\{\leftarrow,\to\\}$ within its order type. Hence we obtain
$f(\alpha(a),\alpha(b))\in(\to)^{m}$ proving the existence of the desired
polymorphism.

If there are equalities between $a_{1}$ and $a_{2}$ we only demonstrate how to
deal with the case in which the second coordinate of $a_{1}$ equals the first
coordinate of $a_{2}$ as the other cases may be treated similarly. Note that
by our assumptions on the kernel of $a$ we know that the first coordinate of
$a_{1}$ and the second coordinate of $a_{2}$ are distinct elements. In the
following, call an atomic diagonal $(H_{\mathcal{F}},<)$-type $B$ of a pair of
non-adjacent edges which is crossing if for $(u,v)\in B$ the order $<$ between
$u_{1}$ and $v_{1}$ is opposite of the order $<$ between $u_{2}$ and $v_{2}$.

If $f$ acts as a semilattice operation on $\\{\leftarrow,\to\\}$ within a
crossing $B$, then by flipping all order relations that hold in $B$, obtain a
crossing type where $f$ acting on $\\{\leftarrow,\to\\}$ prefers $\to$ over
$\leftarrow$; hence without loss of generality we may assume this is the case
on $B$. First assume $B$ demands $u_{1}<v_{1}$ for a pair $(u,v)$, and hence
$u_{2}>v_{2}$. Let $\alpha\in\operatorname{Aut}(D_{\mathcal{F}})$ so that
$(\alpha(a_{1}),\alpha(b_{1}))\in B$ and such that $(p,q)\in O^{\prime}$
whenever $p$ is an entry of $a_{2}$ and $q$ is an entry of $b_{2}$. Then
$f(\alpha(a),\alpha(b))\in(\to)^{m}$ and we are done. If on the other hand $B$
demands $u_{1}>v_{1}$, and hence $u_{2}<v_{2}$, for a pair $(u,v)$, then we
pick $\alpha\in\operatorname{Aut}(D_{\mathcal{F}})$ so that
$(\alpha(b_{1}),\alpha(a_{1}))\in B$ and $(\alpha(b_{2}),\alpha(a_{2}))\in O$.
Again, $f(\alpha(b),\alpha(a))\in(\to)^{m}$, finishing the induction step.

It remains to consider the case in which $f$ acts as a projection on
$\\{\leftarrow,\to\\}$ within each crossing type of non-adjacent edges. If $f$
behaves like the first projection within some crossing type that demands
$u_{1}<v_{1}$, and hence $u_{2}>v_{2}$, for a pair $(u,v)$, we may choose
$\alpha\in\operatorname{Aut}(D_{\mathcal{F}})$ so that
$(\alpha(a_{1}),\alpha(b_{1}))\in B$ and $(\alpha(a_{2}),\alpha(b_{2}))\in
O^{\prime}$ to again conclude $f(\alpha(a),\alpha(b))\in(\to)^{m}$. Otherwise
$f$ behaves like the second projection on $\\{\leftarrow,\to\\}$ within each
crossing type demanding $u_{1}<v_{1}$ for a pair $(u,v)$. Take such a crossing
type $B$ and let $\alpha\in\operatorname{Aut}(D_{\mathcal{F}})$ such that
$(\alpha(a_{1}),\alpha(b_{1}))\in O$ and $(\alpha(a_{2}),\alpha(b_{2}))\in B$.
Again $f(\alpha(a),\alpha(b))\in(\to)^{m}$. ∎

## References

  * [AK18] Lovkush Agarwal and Michael Kompatscher.  $2^{\aleph_{0}}$ pairwise nonisomorphic maximal-closed subgroups of Sym($\mathbb{N}$) via the classification of the reducts of the Henson digraphs.  Journal of Symbolic Logic, 83(2):395–415, 2018.
  * [BGP23] Manuel Bodirsky and Santiago Guzmán-Pro.  Forbidden tournaments and the orientation completion problem, 2023.
  * [BK08] Manuel Bodirsky and Jan Kára.  The complexity of equality constraint languages.  Theory of Computing Systems, 3(2):136–158, 2008.  A conference version appeared in the proceedings of Computer Science Russia (CSR’06).
  * [BK12] Libor Barto and Marcin Kozik.  Absorbing subalgebras, cyclic terms and the constraint satisfaction problem.  Logical Methods in Computer Science, 8/1(07):1–26, 2012.
  * [BM16] Manuel Bodirsky and Antoine Mottet.  Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction.  In Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science (LICS), pages 623–632, 2016.  Preprint available at ArXiv:1601.04520.
  * [BMPP19] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz.  Constraint satisfaction problems for reducts of homogeneous graphs.  SIAM Journal on Computing, 48(4):1224–1264, 2019.  A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1-119:14.
  * [BOP18] Libor Barto, Jakub Opršal, and Michael Pinsker.  The wonderland of reflections.  Israel Journal of Mathematics, 223(1):363–398, 2018.
  * [BP15a] Manuel Bodirsky and Michael Pinsker.  Schaefer’s theorem for graphs.  Journal of the ACM, 62(3):52 pages (article number 19), 2015.  A conference version appeared in the Proceedings of STOC 2011, pages 655-664.
  * [BP15b] Manuel Bodirsky and Michael Pinsker.  Topological Birkhoff.  Transactions of the American Mathematical Society, 367:2527–2549, 2015.
  * [BP20] Libor Barto and Michael Pinsker.  Topology is irrelevant.  SIAM Journal on Computing, 49(2):365–393, 2020.
  * [BP21] Manuel Bodirsky and Michael Pinsker.  Canonical functions: a proof via topological dynamics.  Homogeneous Structures, A Workshop in Honour of Norbert Sauer’s 70th Birthday, Contributions to Discrete Mathematics, 16(2):36–45, 2021.
  * [BPP15] Manuel Bodirsky, Michael Pinsker, and András Pongrácz.  The 42 reducts of the random ordered graph.  Proceedings of the LMS, 111(3):591–632, 2015.  Preprint available from arXiv:1309.2165.
  * [BPP21] Manuel Bodirsky, Michael Pinsker, and András Pongrácz.  Projective clone homomorphisms.  Journal of Symbolic Logic, 86(1):148–161, 2021.
  * [BPT13] Manuel Bodirsky, Michael Pinsker, and Todor Tsankov.  Decidability of definability.  Journal of Symbolic Logic, 78(4):1036–1054, 2013.  A conference version appeared in the Proceedings of the Twenty-Sixth Annual IEEE Symposium on. Logic in Computer Science (LICS 2011), pages 321-328.
  * [BtCLW14] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter.  Ontology-based data access: A study through disjunctive datalog, csp, and MMSNP.  ACM Trans. Database Syst., 39(4):33:1–33:44, 2014.
  * [HN19] Jan Hubička and Jaroslav Nešetřil.  All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms).  Advances in Mathematics, 356:106791, 2019.
  * [Hod97] Wilfrid Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [Kec95] Alexander Kechris.  Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics.  Springer, 1995.
  * [MP20] Antoine Mottet and Michael Pinsker.  Smooth approximations and CSPs over finitely bounded homogeneous structures.  2020\.  Preprint arXiv:2011.03978.
  * [MP22] Antoine Mottet and Michael Pinsker.  Smooth approximations and CSPs over finitely bounded homogeneous structures.  In Proceedings of the Symposium on Logic in Computer Science (LICS), 2022.  Preprint arXiv:2011.03978.
  * [Pos41] Emil L. Post.  The two-valued iterative systems of mathematical logic, volume 5.  Princeton University Press, Princeton, 1941.