# A Complexity Dichotomy in Spatial Reasoning
via Ramsey Theory

Manuel Bodirsky and Bertalan Bodor  Institut für Algebra, Fakultät für
Mathematik, TU Dresden and Department of Algebra, Faculty of Mathematics and
Physics, Charles University, Prague

###### Abstract.

Constraint satisfaction problems (CSPs) for first-order reducts of finitely
bounded homogeneous structures form a large class of computational problems
that might exhibit a complexity dichotomy, P versus NP-complete. A powerful
method to obtain polynomial-time tractability results for such CSPs is a
certain reduction to polynomial-time tractable finite-domain CSPs defined over
$k$-types, for a sufficiently large $k$. We give sufficient conditions when
this method can be applied and apply these conditions to obtain a new
complexity dichotomy for CSPs of first-order expansions of the basic relations
of the well-studied spatial reasoning formalism RCC5. We also classify which
of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory;
we prove that RCC5 has a Ramsey order expansion.

The authors have received funding from the European Research Council (Grant
Agreement no. 681988, CSP-Infinity).

###### Contents

  1. 1 Introduction
  2. 2 Countably Categorical Structures
  3. 3 Ramsey Theory
  4. 4 Oligomorphic Clones
  5. 5 Canonical Functions
    1. 5.1 Behaviours
    2. 5.2 Canonicity
    3. 5.3 Canonisation
    4. 5.4 Complexity
  6. 6 Results
    1. 6.1 The Unique Interpolation Property
    2. 6.2 Other Characterisations of the UIP
  7. 7 Proof of the Extension Lemma
    1. 7.1 Diagonal Interpolation
    2. 7.2 Rich subsets
    3. 7.3 Interpolation invariance
    4. 7.4 Proofs of main results
  8. 8 Verification of the UIP
  9. 9 First-order expansions of the basic relations of RCC5
    1. 9.1 A Ramsey order expansion of $\mathfrak{R}$
    2. 9.2 Polymorphisms of $\mathfrak{R}$ that are canonical with respect to $(\mathfrak{R},\prec)$
    3. 9.3 Independent substructures
    4. 9.4 Uniformly continuous minor-preserving maps
      1. 9.4.1 Cyclic polymorphisms
      2. 9.4.2 Factoring $\prec$
      3. 9.4.3 Restricting to $\smash{{}^{\bot}_{\prec}}$
      4. 9.4.4 Canonical pseudo-cyclic polymorphisms
    5. 9.5 Verifying the UIP
    6. 9.6 Proof of the complexity classification
  10. 10 Expressibility in Datalog and Extensions
  11. 11 Future Work

##  1\. Introduction

The _Constraint satisfaction problem (CSP)_ of a relational structure
$\mathfrak{B}$ is the computational problem of deciding whether a given finite
structure $\mathfrak{A}$ has a homomorphism to $\mathfrak{B}$. If the
structure $\mathfrak{B}$ is finite, then $\operatorname{CSP}(\mathfrak{B})$ is
in P or NP-complete; this was conjectured by Feder and Vardi [FV99] and proved
by Bulatov [Bul17] and, independently, by Zhuk [Zhu17]. Both approaches use
concepts and methods from universal algebra; in particular, they use that the
computational complexity of $\operatorname{CSP}(\mathfrak{B})$ is fully
determined by the set $\operatorname{Pol}(\mathfrak{B})$ of _polymorphisms_ of
$\mathfrak{B}$, which is the set of homomorphisms from $\mathfrak{B}^{n}$ to
$\mathfrak{B}$ for $n\in{\mathbb{N}}$. In fact,
$\operatorname{CSP}(\mathfrak{B})$ is NP-complete if
$\operatorname{Pol}(\mathfrak{B})$ has a minor-preserving map to the clone
$\operatorname{Proj}$ of projections on a two-element set, and is in P
otherwise.

Some of the results about finite structures can be lifted to countably
infinite structures whose automorphism group satisfies a certain finiteness
condition, called _oligomorphicity_ : the requirement is that for every
$n\in{\mathbb{N}}$ the componentwise action of the automorphism group on
$n$-tuples has only finitely many orbits. Examples of such structures arise
systematically in model theory: every homogeneous structure $\mathfrak{B}$
with a finite relational signature is of this type; such structures will be
called _finitely homogeneous_. An additional finiteness condition is to
require that the class of finite substructures of $\mathfrak{B}$ is described
by finitely many forbidden substructures, in which case $\mathfrak{B}$ is
called _finitely bounded_. The class of reducts of finitely bounded
homogeneous structures is a huge generalisation of the class of all finite
structures.

There is also a generalisation of the Feder-Vardi dichotomy conjecture, which
is still open, to reducts of finitely bounded homogeneous structures. In fact,
there is a known NP-hardness condition for the CSPs of such structures which
is conjectured to be at the border between polynomial-time tractable and NP-
complete CSPs [BPP21, BOP18, BKO+17]. The _infinite-domain tractability
conjecture_ states that the CSP for every structure that does not satisfy the
mentioned hardness condition is in P (details can be found in Section 4).
There are many classes of infinite-domain structures where the infinite-domain
tractability conjecture has been verified. Often, these classes consist of the
_first-order reducts_ of some fixed underlying structure $\mathfrak{B}$. By a
_first-order reduct of $\mathfrak{B}$_ we mean a reduct of the expansion of
$\mathfrak{B}$ by all relations that are first-order definable in
$\mathfrak{B}$. For example, the infinite-domain tractability conjecture has
been verified for

  1. (1)

all CSPs of structures preserved by all permutations [BK08], which is
precisely the class of first-order reducts of pure sets (structures with no
relations);

  2. (2)

all CSPs of structures with a highly set-transitive automorphism group [BK09b]
(i.e., for all finite subsets $X,Y$ with $|X|=|Y|$ there exists an
automorphism which maps $X$ to $Y$), which is precisely the class of first-
order reducts of unbounded dense linear orders;

  3. (3)

all CSPs of first-order reducts of the homogeneous universal poset [KP18];

  4. (4)

all CSPs of first-order reducts of the binary branching C-relation [BJP17];

  5. (5)

all CSPs of first-order reducts of homogeneous graphs [BMPP19];

  6. (6)

all CSPs of first-order reducts of _unary structures_ , i.e., structures with
a signature that consists of finitely many unary relation symbols [BM18];

  7. (7)

all CSPs expressible in MMSNP [BMM18]; MMSNP is a fragment of existential
second-order logic introduced by Feder and Vardi [FV99].

In some, but not in all cases above the polynomial-time tractability results
for $\operatorname{CSP}(\mathfrak{B})$ can be obtained by reducing
$\operatorname{CSP}(\mathfrak{B})$ to $\operatorname{CSP}(\mathfrak{T})$ where
$\mathfrak{T}$ is a certain finite structure whose domain is the set of
complete $k$-types of $\mathfrak{B}$, for a sufficiently large $k$; this
method works if the _clone of canonical polymorphisms of $\mathfrak{B}$_ does
not have a minor-preserving map to the projections [BM18]. In this case,
$\operatorname{Pol}(\mathfrak{T})$ does not have a minor-preserving map to
$\operatorname{Proj}$, and hence satisfies the condition for the algorithms of
Bulatov and of Zhuk. The polynomial-time tractability of
$\operatorname{CSP}(\mathfrak{T})$ then implies the polynomial-time
tractability of $\operatorname{CSP}(\mathfrak{B})$, by a reduction from
[BM18]. The publications cited above show that the canonical polymorphisms
determine the complexity of the CSPs in (1), (3), (5), (6), and (7), but not
for the CSPs in (2) and (4).

We introduce a property, which is implicit in [BM18, BMM18], and which we call
the _unique interpolation property (UIP)_. We present equivalent
characterisations of the unique interpolation property; in particular, we show
that it suffices to verify the unique interpolation property for binary
polymorphisms. For our characterisation we need an additional assumption,
which holds in all the mentioned examples that appear in (1)-(7) above, and
which makes the connection between CSPs and universal algebra particularly
strong: we require that $\mathfrak{B}$ is a reduct of a finitely homogeneous
_Ramsey structure_ $\mathfrak{A}$. While the assumption to be Ramsey is quite
strong, the assumption that a finitely homogeneous structure is a reduct of a
finitely homogeneous Ramsey structure is weak: in fact, it might be that
_every_ finitely bounded homogeneous structure has a finitely bounded
homogeneous Ramsey expansion (see [Bod15, BPT13]).

We use our general results to prove a new complexity dichotomy for qualitative
spatial reasoning. A fundamental formalism in spatial reasoning is RCC5
[Ben94], which involves five binary relations defined on some general set of
_regions_ ; a formal definition can be found in Section 9. Renz and Nebel
[RN01] showed that the CSP for RCC5 is NP-complete, and Nebel [Neb95] showed
that the CSP for the five basic relations of RCC5 is in P (via a reduction to
2SAT111The proof of Nebel was formulated for RCC8 instead of RCC5, but the
result for RCC5 can be shown analogously.). Renz and Nebel [RN01] have
extended the polynomial-time tractability result to a superclass of the basic
relations, and they showed that their expansion is _maximal_ in the sense that
every larger subset of the RCC5 relations has an NP-hard CSP. Drakengren and
Jonsson [JD97] classified the computational complexity of the CSP for all
subsets of the RCC5 relations. We classify the complexity of the CSP for
expansions of the basic relations of RCC5 by first-order definable relations
of arbitrary finite arity, solving the essential part of Problem 4 in [BJ17].
In particular, we verify the tractability conjecture for these CSPs, and show
that the tractable cases can be solved by reducing them to polynomial-time
tractable finite-domain CSPs using the reduction from [BM18]. For our method,
we need a homogeneous Ramsey expansion of RCC5; to prove the Ramsey property
of the expansion that we construct we apply a recent Ramsey transfer result of
Mottet and Pinsker [MP21], using the well-known fact that a certain ordered
version of the atomless Boolean algebra has the Ramsey property [KPT05].

The results mentioned so far have been announced in the proceedings of LICS
2021 [BB21a], but most proofs were omitted because of space restrictions. We
additionally show that if the condition of the infinite-domain tractability
conjecture applies to a first-order expansion $\mathfrak{B}$ of the basic
relations of RCC5, then $\operatorname{CSP}(\mathfrak{B})$ can be solved by
Datalog [FV99] (in polynomial time); otherwise, it cannot be expressed in the
much stronger _fixed-point logic with counting (FPC)_ [ABD09].

### Related Work

There exists another powerful approach to CSP complexity classification under
similar conditions, the theory of _smooth approximations_ [MP22, MNPW21]. The
theory of smooth approximations also gives a sufficient condition for the UIP
in certain cases (see the discussion at the end of Section 3.2 in [MP22]); but
the machinery and the general statements there do not seem to directly relate
to the statements that we prove here. The smooth approximations approach
proved to be very efficient in re-deriving existing classifications and
proving new classifications where a surprisingly large proportion of the work
follows from the general results of smooth approximations, and only relatively
few arguments are needed to adapt to the classes under consideration. However,
we do not know how to apply their approach to derive our spatial reasoning
classification. We believe that also the general results presented here will
be useful in other settings; one example of a different setting where the
present approach has been applied is the class of monadically stable
$\omega$-categorical structures, for which the second author confirmed the
infinite-domain tractability conjecture in his PhD thesis [Bod22], using
results of this article. In contrast to the present article, the smooth
approximations approach also provides a systematic approach to Datalog
expressibility [MNPW21]; but also here we do not know how to obtain the
particular results about Datalog expressibility in spatial reasoning from
their general theorems.

### Outline

In Section 2, Section 3, and Section 4 we introduce some fundamental notions
and results from model theory, Ramsey theory, and universal algebra,
respectively, that we need to state our results. In Section 3 we also need a
consequence of the Ramsey property of an $\omega$-categorical structure
$\mathfrak{A}$ for the existence of independent elementary substructures of
$\mathfrak{A}$ (Theorem 3.2); this result might be of independent interest in
model theory. The formal definition of the unique interpolation property and
our first general main result about the UIP with an application to complexity
classification is presented in Section 6.1. We then present two results that
facilitate the verification of the UIP in concrete settings (Section 6.2). The
applications of the general results to the spatial reasoning formalism RCC5
are in Section 9, and the classification of the respective CSPs in Datalog in
Section 10.

##  2\. Countably Categorical Structures

All structures considered in this text are assumed to be relational unless
stated otherwise. If $\mathfrak{A}$ is a structure, then $A$ denotes the
domain of $\mathfrak{A}$. A structure $\mathfrak{A}$ is called _$\omega$
-categorical_ if the set of all first-order sentences that hold in
$\mathfrak{A}$ has exactly one countable model up to isomorphism. This concept
has an equivalent characterisation based on the automorphism group
$\operatorname{Aut}(\mathfrak{A})$ of $\mathfrak{A}$. For $l\in{\mathbb{N}}$,
the _$l$ -orbit_ of $a=(a_{1},\dots,a_{l})\in A^{l}$ in
$\operatorname{Aut}(\mathfrak{A})$ is the set

$\\{\alpha(a)\colon\alpha\in\operatorname{Aut}(\mathfrak{A})\\}\text{ where
}\alpha(a)\coloneqq(\alpha a_{1},\dots,\alpha a_{l}).$

We write ${\mathcal{O}}_{l}(\mathfrak{A})$ for the set of $l$-orbits of
$\operatorname{Aut}(\mathfrak{A})$. Engeler, Svenonius, and Ryll-Nardzewski
(see, e.g., Theorem 6.3.1 in [Hod97]) proved that a countable structure is
$\omega$-categorical if and only if $\operatorname{Aut}(\mathfrak{A})$ is
_oligomorphic_ , i.e., if ${\mathcal{O}}_{l}(\mathfrak{A})$ is finite for
every $l\in{\mathbb{N}}$. In fact, $a,b\in A^{l}$ have the same $l$-orbit if
and only if they satisfy the same first-order formulas over $\mathfrak{A}$; we
write $\operatorname{typ}^{\mathfrak{A}}(a)$ for the set of all first-order
formulas satisfied by $a$ over $\mathfrak{A}$, called the _type of $a$ over
$\mathfrak{A}$_. For $B\subseteq A$, we write
$\operatorname{typ}^{\mathfrak{A}}(a/B)$ for the set of all first-order
formulas with parameters from $B$ (i.e., formulas over an expanded signature
that also contains constant symbols denoting elements from $B$) satisfied by
$a$ over $\mathfrak{A}$.

Homogeneous structures. Many examples of $\omega$-categorical structures arise
from structures $\mathfrak{A}$ that are _homogeneous_. A relational structure
is _homogeneous_ if every isomorphism between finite substructures of
$\mathfrak{A}$ can be extended to an automorphism of $\mathfrak{A}$. It
follows from the above that if $\mathfrak{A}$ is finitely homogeneous, then
$\mathfrak{A}$ is $\omega$-categorical. If $a\in A^{n}$, we write
$\operatorname{qf-typ}^{\mathfrak{A}}(a)$ for the set of all quantifier-free
formulas that hold on $a$ over $\mathfrak{A}$. Clearly, in homogeneous
structures $\mathfrak{A}$ the quantifier-free type of $a$ determines the type
of $a$. Also note that every $\omega$-categorical structure can be turned into
a homogeneous $\omega$-categorical structure by expanding it by all first-
order definable relations.

Every homogeneous structure $\mathfrak{A}$ is uniquely given (up to
isomorphism) by its _age_ , i.e., by the class
$\operatorname{Age}(\mathfrak{A})$ of all finite structures that embed into
$\mathfrak{A}$ (see, e.g., Lemma 6.1.4 in [Hod97]). Conversely, every class
$\mathcal{C}$ of structures with finite relational signature which is an
_amalgamation class_ , i.e., is closed under isomorphism, substructures, and
which has the _amalgamation property_ , is the age of a homogeneous structure,
which we call the _Fraïssé-limit of ${\mathcal{C}}$_ (see, e.g., Theorem 6.1.2
in [Hod97]). We say that $\mathfrak{B}$ is _finitely bounded_ if there exists
a finite set of finite structures $\mathcal{F}$ such that the age of
$\mathfrak{B}$ equals the class of all finite structures $\mathfrak{A}$ such
that no structure from $\mathcal{F}$ embeds into $\mathfrak{A}$.

Model-complete cores. An $\omega$-categorical structure $\mathfrak{C}$ is
_model-complete_ if every self-embedding
$e\colon\mathfrak{C}\hookrightarrow\mathfrak{C}$ preserves all first-order
formulas. An $\omega$-categorical structure $\mathfrak{C}$ is called a _core_
if every endomorphism of $\mathfrak{C}$ is a self-embedding of $\mathfrak{C}$.
If there is a homomorphism from a structure $\mathfrak{A}$ to a structure
$\mathfrak{B}$ and vice versa, then $\mathfrak{A}$ and $\mathfrak{B}$ are
called _homomorphically equivalent_. Every $\omega$-categorical structure
$\mathfrak{A}$ is homomorphically equivalent to a model-complete core, which
is unique up to isomorphism, and again $\omega$-categorical, and which is
called _the_ model-complete core of $\mathfrak{A}$ [Bod07, BHM12].

##  3\. Ramsey Theory

For $\tau$-structures $\mathfrak{A},\mathfrak{B}$ we write
${\mathfrak{B}\choose\mathfrak{A}}$ for the set of all embeddings of
$\mathfrak{A}$ into $\mathfrak{B}$. If
$\mathfrak{A},\mathfrak{B},\mathfrak{C}$ are $\tau$-structures and
$r\in{\mathbb{N}}$ then we write

$\mathfrak{C}\to(\mathfrak{B})^{\mathfrak{A}}_{r}$

if for every function
$\chi\colon{\mathfrak{C}\choose\mathfrak{A}}\to\\{1,\dots,r\\}$ (also referred
to as a _colouring_ , where $\\{1,\dots,r\\}$ are the different colours) there
exists $e\in{\mathfrak{C}\choose\mathfrak{B}}$ such that $\chi$ is constant on

$\left\\{e\circ f\colon
f\in{\mathfrak{B}\choose\mathfrak{A}}\right\\}\subseteq{\mathfrak{C}\choose\mathfrak{A}}.$

######  Definition 1.

A class of finite $\tau$-structures has the _Ramsey property_ if for all
$\mathfrak{A},\mathfrak{B}$ and $r\in{\mathbb{N}}$ there exists $\mathfrak{C}$
such that $\mathfrak{C}\to(\mathfrak{B})^{\mathfrak{A}}_{r}$. A homogeneous
structure has the Ramsey property if its age has the Ramsey property.

Let $r\in{\mathbb{N}}$. We write $\mathfrak{C}\to(\mathfrak{B})_{r}$ if for
every $\chi\colon C^{|B|}\to\\{1,\dots,r\\}$ there exists
$e\colon\mathfrak{B}\hookrightarrow\mathfrak{C}$ such that if
$\operatorname{qf-typ}^{\mathfrak{B}}(s)=\operatorname{qf-
typ}^{\mathfrak{B}}(t)$ for $s,t\in B^{|B|}$, then $\chi(e(s))=\chi(e(t))$.
The Ramsey property has the following well-known consequence (see, e.g.,
Proposition 2.21 in [Bod15]).

######  Lemma 3.1.

Let $\mathcal{C}$ be a Ramsey class. Then for every $r\in{\mathbb{N}}$ and
$\mathfrak{B}\in\mathcal{C}$ there exists $\mathfrak{C}\in\mathcal{C}$ such
that $\mathfrak{C}\to(\mathfrak{B})_{r}$.

Another important consequence of the Ramsey property is presented in Section
5.3. We also need the following consequence of the Ramsey property (in the
proof of Proposition 7.3), which appears to be new. Let $\mathfrak{D}$ be a
structure and let $A,B\subseteq D$. We say that $A$ is _independent from $B$
in $\mathfrak{D}$_ if for all $\bar{a},\bar{b}\in A^{n}$, if
$\operatorname{typ}^{\mathfrak{D}}(\bar{a})=\operatorname{typ}^{\mathfrak{D}}(\bar{b})$,
then
$\operatorname{typ}^{\mathfrak{D}}(\bar{a}/B)=\operatorname{typ}^{\mathfrak{D}}(\bar{b}/B)$.
Two substructures $\mathfrak{A},\mathfrak{B}$ of $\mathfrak{D}$ are called
_independent_ if $A$ is independent from $B$ in $\mathfrak{D}$ and $B$ is
independent from $A$ in $\mathfrak{D}$. A substructure $\mathfrak{B}$ of a
$\tau$-structure $\mathfrak{A}$ is called _elementary_ if the identity mapping
from $\mathfrak{B}$ to $\mathfrak{A}$ preserves all first-order
$\tau$-formulas.

######  Theorem 3.2.

Let $\mathfrak{A}$ be a countable homogeneous $\omega$-categorical Ramsey
structure. Then $\mathfrak{A}$ contains two independent elementary
substructures.

In the proof of Theorem 3.2 we use the following consequence of the
compactness theorem of first-order logic.

######  Proposition 3.3.

Let $\mathfrak{A}$ be a countable $\omega$-categorical homogeneous structure.
Then the following are equivalent.

  1. (1)

$\mathfrak{A}$ contains two independent elementary substructures.

  2. (2)

For all $\mathfrak{B}_{1},\mathfrak{B}_{2}\in\operatorname{Age}(\mathfrak{A})$
there exists embeddings
$e_{i}\colon\mathfrak{B}_{i}\hookrightarrow\mathfrak{A}$, for $i\in\\{1,2\\}$,
such that $e_{1}(B_{1})$ and $e_{2}(B_{2})$ are independent in $\mathfrak{A}$.

###### Proof.

The forward implication is immediate from the definitions. For the converse
implication, let $a_{1},a_{2},\dots$ be an enumeration of $A$ and let
$B=\\{b_{1},b_{2},\dots\\}$ and $C=\\{c_{1},c_{2},\dots\\}$ be sets of new
constant symbols. Let $\Phi$ be the set of all sentences that express that for
all $n\in{\mathbb{N}}$, $\bar{b},\bar{b}^{\prime}\in B^{n}$, and
$\bar{c},\bar{c}^{\prime}\in C^{n}$

  * •

if
$\operatorname{typ}^{\mathfrak{A}}(\bar{b})=\operatorname{typ}^{\mathfrak{A}}(\bar{b}^{\prime})$
then
$\operatorname{typ}^{\mathfrak{A}}(\bar{b},\bar{c})=\operatorname{typ}^{\mathfrak{A}}(\bar{b}^{\prime},\bar{c})$.

  * •

if
$\operatorname{typ}^{\mathfrak{A}}(\bar{c})=\operatorname{typ}^{\mathfrak{A}}(\bar{c}^{\prime})$
then
$\operatorname{typ}^{\mathfrak{A}}(\bar{c},\bar{b})=\operatorname{typ}^{\mathfrak{A}}(\bar{c}^{\prime},\bar{b})$.

For $n\in{\mathbb{N}}$ let $\phi_{n}(x_{1},\dots,x_{n})$ be a formula that
expresses that
$\operatorname{typ}^{\mathfrak{A}}(x_{1},\dots,x_{n})=\operatorname{typ}^{\mathfrak{B}}(a_{1},\dots,a_{n})$.
By assumption, all finite subsets of

$T\coloneqq\operatorname{Th}(\mathfrak{A})\cup\Phi\cup\\{\phi_{n}(b_{1},\dots,b_{n})\wedge\phi_{n}(c_{1},\dots,c_{n}):n\in{\mathbb{N}}\\}$

are satisfiable. By compactness of first-order logic, it follows that $T$ has
a model $\mathfrak{A}^{\prime}$. By the downward Löwenheim-Skolem theorem, we
may assume that $\mathfrak{A}^{\prime}$ is countably infinite. The reduct of
$\mathfrak{A}^{\prime}$ with the same signature as $\mathfrak{A}$ satisfies
$\operatorname{Th}(\mathfrak{A})$, and since $\mathfrak{A}$ is
$\omega$-categorical this reduct is isomorphic to $\mathfrak{A}$, so that we
may assume that $\mathfrak{A}^{\prime}$ is an expansion of $\mathfrak{A}$. Let
$\mathfrak{B}$ be the substructure of $\mathfrak{A}$ induced by the constants
from $B$. Since
$\mathfrak{A}^{\prime}\models\\{\phi_{n}(b_{1},\dots,b_{n}):n\in{\mathbb{N}}\\}$
and by the homogeneity of $\mathfrak{A}$ we have that $\mathfrak{B}$ is an
elementary substructure of $\mathfrak{A}$. Likewise, the substructure
$\mathfrak{C}$ of $\mathfrak{A}$ induced by the constants from $C$ is an
elementary substructure of $\mathfrak{A}$. Since
$\mathfrak{A}^{\prime}\models\Phi$ the two substructures $\mathfrak{B}$ and
$\mathfrak{C}$ are independent. ∎

To find independent sets, we use the Ramsey property via the following lemma.

######  Lemma 3.4.

Let $\mathfrak{A}$ be a countable homogeneous $\omega$-categorical Ramsey
structure, $C\subseteq A$ finite, and
$\mathfrak{B}\in\operatorname{Age}(\mathfrak{A})$. Then there exists
$\mathfrak{D}\in\operatorname{Age}(\mathfrak{A})$ such that for every
$e\colon\mathfrak{D}\hookrightarrow\mathfrak{A}$ there exists
$f\colon\mathfrak{B}\hookrightarrow\mathfrak{A}$ such that $f(B)\subseteq
e(D)$ and for all $\bar{a},\bar{b}\in B^{|B|}$, if
$\operatorname{typ}^{\mathfrak{A}}(f(\bar{a}))=\operatorname{typ}^{\mathfrak{A}}(f(\bar{b}))$
then
$\operatorname{typ}^{\mathfrak{A}}(f(\bar{a})/C)=\operatorname{typ}^{\mathfrak{A}}(f(\bar{b})/C)$.

###### Proof.

Let $C=\\{c_{1},\dots,c_{n}\\}$. Let $r$ be the number of types of
$|B|+n$-tuples in $\mathfrak{A}$. Since $\mathfrak{A}$ is homogeneous Ramsey
there exists $\mathfrak{D}\in\operatorname{Age}(\mathfrak{A})$ such that
$\mathfrak{D}\to(\mathfrak{B})_{r}$. We claim that $\mathfrak{D}$ satisfies
the statement of the lemma. Let
$e\colon\mathfrak{D}\hookrightarrow\mathfrak{A}$ be an embedding. We color
$e(D)^{|B|}$ as follows: the colour of $t\in e(D)^{|B|}$ is the orbit of
$(t_{1},\dots,t_{|B|},c_{1},\dots,c_{n})$. There are at most $r$ such orbits.
Since $\mathfrak{D}\to(\mathfrak{B})_{r}$ we get that there exists an
$f\colon\mathfrak{B}\hookrightarrow\mathfrak{A}$ such that $f(B)\subseteq
e(D)$ and if $\bar{a},\bar{b}\in B^{|B|}$ are such that
$\operatorname{typ}^{\mathfrak{A}}(f(\bar{a}))=\operatorname{typ}^{\mathfrak{A}}(f(\bar{b}))$,
then
$\operatorname{typ}^{\mathfrak{A}}(f(\bar{a})/C)=\operatorname{typ}^{\mathfrak{A}}(f(\bar{b})/C)$.
∎

###### Proof of Theorem 3.2.

We use Proposition 3.3. Let
$\mathfrak{B}_{1},\mathfrak{B}_{2}\in\operatorname{Age}(\mathfrak{A})$; we may
assume that $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ are substructures of
$\mathfrak{A}$. Then Lemma 3.4 implies that there exists
$\mathfrak{D}_{1}\in\operatorname{Age}(\mathfrak{A})$ such that for every
embedding $e_{1}\colon\mathfrak{D}_{1}\hookrightarrow\mathfrak{A}$ there
exists an embedding $f_{1}\colon\mathfrak{B}_{1}\hookrightarrow\mathfrak{A}$
such that $f_{1}(B_{1})\subseteq e_{1}(D_{1})$ and for all $n\in{\mathbb{N}}$,
$b,b^{\prime}\in(B_{1})^{n}$

(1) $\displaystyle\text{ if
}\operatorname{typ}^{\mathfrak{A}}(f_{1}(b))=\operatorname{typ}^{\mathfrak{A}}(f_{1}(b^{\prime}))$
$\displaystyle\text{ then
}\operatorname{typ}^{\mathfrak{A}}(f_{1}(b)/B_{2})=\operatorname{typ}^{\mathfrak{A}}(f_{1}(b^{\prime})/B_{2}).$

We may assume that $\mathfrak{D}_{1}$ is a substructure of $\mathfrak{A}$.
Another application of Lemma 3.4 gives us an embedding
$f_{2}\colon\mathfrak{B}_{2}\hookrightarrow\mathfrak{A}$ such that for all
$n\in{\mathbb{N}}$, $b,b^{\prime}\in(B_{2})^{n}$, if
$\operatorname{typ}^{\mathfrak{A}}(f_{2}(b))=\operatorname{typ}^{\mathfrak{A}}(f_{2}(b^{\prime}))$
then
$\operatorname{typ}^{\mathfrak{A}}(f_{2}(b)/D_{1})=\operatorname{typ}^{\mathfrak{A}}(f_{2}(b^{\prime})/D_{1})$.
By the homogeneity of $\mathfrak{A}$, there exists
$\alpha\in\operatorname{Aut}(\mathfrak{A})$ extending $f_{2}$. The property of
$\mathfrak{D}_{1}$ implies that there exists an embedding
$f_{1}\colon\mathfrak{B}_{1}\hookrightarrow\mathfrak{A}$ such that
$f_{1}(B_{1})\subseteq\alpha^{-1}(D_{1})$ such that (1) holds for all
$b,b^{\prime}\in(B_{1})^{n}$.

We claim that $f_{1}(B_{1})$ and $B_{2}$ are independent. Clearly,
$f_{1}(B_{1})$ is independent from $B_{2}$. To show that $B_{2}$ is
independent from $f_{1}(B_{1})$, let $n\in{\mathbb{N}}$ and
$b,b^{\prime}\in(B_{2})^{n}$ be such that
$\operatorname{typ}^{\mathfrak{A}}(b)=\operatorname{typ}^{\mathfrak{A}}(b^{\prime})$.
Then
$\operatorname{typ}^{\mathfrak{A}}(\alpha(b))=\operatorname{typ}^{\mathfrak{A}}(\alpha(b^{\prime}))$,
and hence that
$\operatorname{typ}^{\mathfrak{A}}(\alpha(b)/D_{1})=\operatorname{typ}^{\mathfrak{A}}(\alpha(b^{\prime})/D_{1})$
by the choice of $f_{2}$. This in turn implies that
$\operatorname{typ}^{\mathfrak{A}}(b/\alpha^{-1}(D_{1}))=\operatorname{typ}^{\mathfrak{A}}(b^{\prime}/\alpha^{-1}(D_{1}))$
which implies the statement since $f_{1}(B_{1})\subseteq\alpha^{-1}(D_{1})$. ∎

##  4\. Oligomorphic Clones

In this section we introduce fundamental concepts and results about
polymorphism clones of finite and countably infinite $\omega$-categorical
structures that are needed for the statement of our results.

The _$k$ -th direct power_ of a structure $\mathfrak{A}$ (also called the
_categorical power_), denoted by $\mathfrak{A}^{k}$. It is the
$\tau$-structure with domain $A^{k}$ such that

$((a_{1,1},\dots,a_{1,k}),\dots,(a_{n,1},\dots,a_{n,k}))\in
R^{\mathfrak{A}^{k}}$

if and only if $(a_{1,i},\dots,a_{n,i})\in R^{\mathfrak{A}}$ for every
$i\in\\{1,\dots,k\\}$. A _polymorphism_ of $\mathfrak{A}$ is a homomorphism
from a finite direct power $\mathfrak{A}^{k}$ to $\mathfrak{A}$. The set of
all polymorphisms of $\mathfrak{A}$, denoted by
$\operatorname{Pol}(\mathfrak{A})$, forms a _clone (over $A$)_, i.e., it is
closed under composition and contains for every $k$ and $i\leq k$ the
projection $\pi^{k}_{i}$ of arity $k$ that always returns the $i$-th argument.
Moreover, $\operatorname{Pol}(\mathfrak{A})$ is closed with respect to the
_topology of pointwise convergence_ , i.e., if $f\colon A^{k}\to A$ is such
that for every finite $F\subseteq A$ there exists
$g\in\operatorname{Pol}(\mathfrak{A})$ such that
$g(a_{1},\dots,a_{k})=f(a_{1},\dots,a_{k})$ for all $a_{1},\dots,a_{k}\in F$,
then $f\in\operatorname{Pol}(\mathfrak{A})$. If ${\mathscr{S}}$ is a set of
operations over $A$, then $\overline{\mathscr{S}}$ denotes the smallest closed
set that contains ${\mathscr{S}}$. If ${\mathscr{S}}$ is a set of operations,
we write ${\mathscr{S}}^{(k)}$ for the set of operation in ${\mathscr{S}}$ of
arity $k$. The clone of all projections on $\\{0,1\\}$ is denoted by
$\operatorname{Proj}$.

######  Definition 2.

A function $\zeta\colon{\mathscr{C}}_{1}\to{\mathscr{C}}_{2}$ between two
clones over a countably infinite set $A$ is called

  * •

_minor-preserving_ if

$\zeta\big{(}f(\pi^{k}_{i_{1}},\dots,\pi^{k}_{i_{n}})\big{)}=\zeta(f)(\pi^{k}_{i_{1}},\dots,\pi^{k}_{i_{n}})$

for all $f\in{\mathscr{C}}^{(n)}_{1}$ and
$i_{1},\dots,i_{n}\in\\{1,\dots,k\\}$.

  * •

_uniformly continuous_ if and only if for any finite $G\subseteq A$ there is a
finite $F\subseteq A$ such that for all $n\in{\mathbb{N}}$ and
$f,g\in{\mathscr{C}}_{1}^{(n)}$, if $f|_{F^{n}}=g|_{F^{n}}$ then
$\zeta(f)|_{G^{n}}=\zeta(g)|_{G^{n}}$.

The set ${\mathscr{O}}_{A}\coloneqq\bigcup_{k\in{\mathbb{N}}}(A^{k}\to A)$ of
all operations on $A$ can be equipped with a complete metric such that the
closed clones with respect to this metric are precisely the polymorphism
clones of relational structures with domain $A$, and such that the uniformly
continuous maps are precisely the maps that are uniformly continuous with
respect to this metric in the standard sense, justifying our terminology; see,
e.g., [Bod21]. Now suppose that $\mathfrak{B}$ is a finite structure with a
finite relational signature; the following results imply that the existence of
a minor-preserving map from $\operatorname{Pol}(\mathfrak{B})$ to
$\operatorname{Proj}$ describes the border between containment in P and NP-
completeness.

######  Theorem 4.1 (follows from [BKJ05, BOP18]).

Let $\mathfrak{B}$ be a structure with a finite domain and a finite relational
signature. If there is a minor-preserving map
$\operatorname{Pol}(\mathfrak{B})\to\operatorname{Proj}$ then
$\operatorname{CSP}(\mathfrak{B})$ is NP-hard.

######  Theorem 4.2 ([MM08]).

Let $\mathfrak{B}$ be a structure with a finite domain. If there is no minor-
preserving map $\operatorname{Pol}(\mathfrak{B})\to\operatorname{Proj}$ then
$\operatorname{Pol}(\mathfrak{B})$ contains a _weak near unanimity (WNU)
operation_ , i.e., an operation $f$ of some arity $k\geq 2$ that satisfies for
all $a,b\in B$ that

$f(a,\dots,a,b)=f(a,\dots,b,a)=\dots=f(b,a,\dots,a).$

######  Theorem 4.3 (Bulatov [Bul17], Zhuk [Zhu17]).

Let $\mathfrak{B}$ be a structure with a finite domain and a finite relational
signature. If $\mathfrak{B}$ has a WNU polymorphism, then
$\operatorname{CSP}(\mathfrak{B})$ is in P.

The hardness result in Theorem 4.1 can be generalised to a large class of
countable structures $\mathfrak{B}$.

######  Theorem 4.4 ([BOP18]).

Let $\mathfrak{B}$ be a countable $\omega$-categorical structure with finite
relational signature such that $\operatorname{Pol}(\mathfrak{B})$ has a
uniformly continuous minor-preserving map to $\operatorname{Proj}$. Then
$\operatorname{CSP}(\mathfrak{B})$ is NP-hard.

The present paper is motivated by the following conjecture from [BPP21], in a
reformulation from [BKO+17], which generalises the Bulatov-Zhuk dichotomy
(Theorem 4.3).

######  Conjecture 4.5.

Let $\mathfrak{B}$ be a reduct of a countable finitely bounded homogeneous
structure such that there is no uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{B})$ to $\operatorname{Proj}$. Then
$\operatorname{CSP}(\mathfrak{B})$ is in P.

##  5\. Canonical Functions

Some of the strongest partial results towards Conjecture 4.5 is based on the
concept of _canonical_ polymorphisms. Let $\mathfrak{A}$ be an
$\omega$-categorical structure. An operation $f\colon A^{k}\to A$ is called
_canonical over ${\mathfrak{A}}$_ if for all $n\in{\mathbb{N}}$ and
$a_{1},\dots,a_{k},b_{1},\dots,b_{k}\in A^{n}$, if
$\operatorname{typ}^{\mathfrak{A}}(a_{i})=\operatorname{typ}^{\mathfrak{A}}(b_{i})$
for all $i\in\\{1,\dots,k\\}$, then
$\operatorname{typ}^{\mathfrak{A}}(f(a_{1},\dots,a_{k}))=\operatorname{typ}^{\mathfrak{A}}(f(b_{1},\dots,b_{k}))$
(the function is applied to the tuples componentwise). Note that if
$\mathfrak{A}$ is a finitely homogeneous structure, and $m$ is the maximal
arity of (the relations of) $\mathfrak{A}$, then $f$ is canonical with respect
to $\mathfrak{A}$ if and only if it is satisfies the condition above for
$n=m$. The set of all canonical operations over $\mathfrak{A}$ is denoted by
$\operatorname{Can}(\mathfrak{A})$; note that
$\operatorname{Can}(\mathfrak{A})$ is a clone and closed.

###  5.1. Behaviours

To conveniently work with canonical functions and with functions that locally
resemble canonical functions, we need the concept of a _behaviour_ of
functions $f\colon A^{k}\to A$ over a structure $\mathfrak{A}$, following
[BP11, BP21]. In order to have some flexibility when using the terminology, we
work in the setting of _partial functions_ from $A^{k}\to A$, i.e., functions
that are only defined on a subset of $A^{k}$.

######  Definition 3 (Behaviours).

Let $n,k\in{\mathbb{N}}$. Then an _$n$ -behaviour over $\mathfrak{A}$ (of a
$k$-ary partial map from $A^{k}$ to $A$)_ is a partial function from
${\mathcal{O}_{n}(\mathfrak{A})}^{k}$ to ${\mathcal{O}}_{n}(\mathfrak{A})$. A
_behaviour over $\mathfrak{A}$_ is a partial function $\mathcal{B}$ from
$\bigcup_{i=1}^{\infty}{\mathcal{O}_{i}(\mathfrak{A})}^{k}$ to
$\bigcup_{i=1}^{\infty}{\mathcal{O}}_{i}(\mathfrak{A})$ so that for every $i$
we have
$\mathcal{B}({\mathcal{O}}_{i}(\mathfrak{A})^{k})\subseteq{\mathcal{O}}_{i}(\mathfrak{A})$.
An $n$-behaviour (behaviour) is called _complete_ if it is defined on all of
${\mathcal{O}}_{n}(\mathfrak{A})^{k}$ (on all of
$\bigcup_{i=1}^{\infty}{\mathcal{O}_{i}(\mathfrak{A})^{k}}$).

Note that every $n$-behaviour is in particular a behaviour.

######  Definition 4 (Behaviours of functions).

Let $\mathfrak{A}$ be a structure and $k\in{\mathbb{N}}$. A partial function
$f\colon A^{k}\to A$ _realises_ a behaviour $\mathcal{B}$ over $\mathfrak{A}$
if for all $a^{1}_{1},\dots,a^{k}_{n}\in A$, if $O_{i}$ is the orbit of
$(a^{i}_{1},\dots,a^{i}_{n})$ for $i\in\\{1,\dots,k\\}$, then
${\mathcal{B}}(O_{1},\dots,O_{k})$ is the orbit of
$(f(a^{1}_{1},\dots,a^{k}_{1}),\dots,f(a^{1}_{n},\dots,a^{k}_{n}))$.

If $S\subseteq A^{k}$ and $\mathcal{B}$ is a behaviour over $\mathfrak{A}$,
then we say that $f\colon A^{k}\to A$ _realises $\mathcal{B}$ on $S$_ if the
restriction $f|_{S}$ realises $\mathcal{B}$. The following proposition can be
shown by a standard compactness argument.

######  Proposition 5.1.

Let $\mathfrak{A}$ be an $\omega$-categorical structure and
$k,n\in{\mathbb{N}}$. Then an $n$-behaviour over $\mathfrak{A}$ is realised by
some $f\in\operatorname{Pol}(\mathfrak{A})^{(k)}$ if and only if it is
realised by some $f\in\operatorname{Pol}(\mathfrak{A})^{(k)}$ on $F^{k}$ for
every finite subset $F\subseteq A$.

###  5.2. Canonicity

Let $n,k\in{\mathbb{N}}$. A partial function $f\colon A^{k}\to A$ is called
_$n$ -canonical over $\mathfrak{A}$_ if it realises a complete $n$-behaviour
over $\mathfrak{A}$, and _canonical over $\mathfrak{A}$_ if it realises some
complete behaviour over $\mathfrak{A}$; note that this is consistent with the
definition given in Section 4. If $S\subseteq A$, then we say that $f$ is _(
$n$-) canonical on $S$_ if the restriction $f|_{S}$ is ($n$-) canonical.

Suppose that $\mathfrak{B}$ is a homogeneous relational structure with maximal
arity $m$. If $f\colon B\to C$ realises some complete $m^{\prime}$-behaviour
over $(\mathfrak{B},\mathfrak{C})$ for $m^{\prime}=\max(m,2)$, then $f$ is
canonical over $(\mathfrak{B},\mathfrak{C})$ (in other words, in this
situation a complete $m$-behaviour uniquely determines a complete behaviour;
the requirement $m^{\prime}\geq 2$ is necessary so that the
$m^{\prime}$-behaviour allows, for instance, to distinguish constant functions
from injective functions). Hence, if $\mathfrak{B}$ is finitely homogeneous,
then there are only finitely many complete behaviours for functions of arity
$k$.

Note that the binary relation $\\{(u,\alpha(u))\colon u\in
A^{n},\alpha\in\operatorname{Aut}(\mathfrak{A})\\}$ is a congruence of
$\operatorname{Can}(\mathfrak{A})$, and so there is a uniformly continuous
clone homomorphism $\xi^{\mathfrak{A}}_{n}$ from
$\operatorname{Can}(\mathfrak{A})$ to a clone whose domain
${\mathcal{O}}_{n}(\mathfrak{A})$ is the (finite) set of congruence classes,
and which we denote by
$\xi^{\mathfrak{A}}_{n}(\operatorname{Can}(\mathfrak{A}))$. If
${\mathscr{C}}\subseteq\operatorname{Can}(\mathfrak{A})$, then we write
$\xi^{\mathfrak{A}}_{n}({\mathscr{C}})$ for the subclone of
$\xi^{\mathfrak{A}}_{n}(\operatorname{Can}(\mathfrak{A}))$ induced by the
image of $\mathscr{C}$ under $\xi^{\mathfrak{A}}_{n}$. Note that if
$f\in\operatorname{Can}(\mathfrak{A})$, then $g\colon A^{k}\to A$ has the same
behaviour as $f$ over $\mathfrak{A}$ if and only if $f$ interpolates $g$ and
$g$ interpolates $f$ over $\mathfrak{A}$.

######  Lemma 5.2 (Proposition 6.6 in [BPP21]).

Let $\mathfrak{A}$ be a finitely homogeneous structure. Let $m$ be the maximal
arity of $\mathfrak{A}$ and suppose that
$f,g\in\operatorname{Can}(\mathfrak{A})$ are such that
$\xi^{\mathfrak{A}}_{m}(f)=\xi^{\mathfrak{A}}_{m}(g)$. Then there are
$e_{1},e_{2}\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that
$e_{1}\circ f=e_{2}\circ g$.

The following proposition can be shown by a compactness argument.

######  Lemma 5.3.

Let $\mathfrak{B}$ be a first-order reduct of an $\omega$-categorical
structure $\mathfrak{A}$. Let $k,n,m\in{\mathbb{N}}$ and let
${\mathcal{B}}_{1},\dots,{\mathcal{B}}_{m}$ be $n$-behaviours over
$(\mathfrak{A}^{(k)},\mathfrak{A})$. Suppose that for every finite $F\subseteq
A$ and $i\in\\{1,\dots,m\\}$ there exist $\alpha_{i,1},\dots,\alpha_{i,k}$ and
$f\in\operatorname{Pol}(\mathfrak{B})$ such that
$f(\alpha_{i,1},\dots,\alpha_{i,k})$ realises ${\mathcal{B}}_{i}$ on $F^{k}$.
Then there exist
$e_{1,1},\dots,e_{m,k}\in\overline{\operatorname{Aut}(\mathfrak{A})}$ and
$f\in\operatorname{Pol}(\mathfrak{B})$ such that for every
$i\in\\{1,\dots,m\\}$ the operation $f(e_{i,1},\dots,e_{i,k})$ realises
${\mathcal{B}}_{i}$ on all of $A^{k}$. Moreover, if
$I\subseteq\\{1,\dots,k\\}$ and $\alpha_{i,j}=\operatorname{id}$ for all $j\in
I$ and every finite $X\subseteq A$ then we can guarantee
$e_{i,j}=\operatorname{id}$ for all $j\in I$.

###  5.3. Canonisation

The following is from [BPT13]; also see [BP21].

######  Lemma 5.4 (Canonisation lemma).

Let $\mathfrak{A}$ be a countable $\omega$-categorical homogeneous Ramsey
structure and let $f\colon A^{k}\to A$. Then there is a canonical function
over $\mathfrak{A}$ which is interpolated by $f$ over
$\operatorname{Aut}(\mathfrak{A})$.

In some situations it is practical to use a finite version of the canonisation
lemma (e.g. in the proof of Lemma 7.5 or Lemma 8.1), which can be derived
easily from Lemma 5.4 by a compactness argument, or directly from Lemma 3.1.

######  Lemma 5.5.

Let $\mathfrak{A}$ be a homogeneous $\omega$-categorical Ramsey structure and
$B\subseteq A$ finite. Then there exists a finite $C\subseteq A$ such that for
every $f\colon A^{k}\to A$ there are
$\alpha_{1},\dots,\alpha_{k}\in\operatorname{Aut}(\mathfrak{A})$ such that
$\alpha_{1}(B)\subseteq C,\dots,\alpha_{k}(B)\subseteq C$ and
$f(\alpha_{1},\dots,\alpha_{k})$ is canonical on $B^{k}$.

###  5.4. Complexity

The following theorem is essentially from [BM18] and uses [Bul17, Zhu17];
since we are not aware of a formulation of the result in the form below, which
is the form that is most useful for the purposes of this article, we added a
guide to the literature in the proof.

######  Theorem 5.6 ([BM18]).

Let $\mathfrak{B}$ be a reduct of a countable finitely bounded homogeneous
structure $\mathfrak{A}$ such that there is no uniformly continuous minor-
preserving map from
$\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{A})$ to
$\operatorname{Proj}$. Then $\operatorname{CSP}(\mathfrak{B})$ is in P.

###### Proof.

Let $m$ be the maximal arity of the relations of $\mathfrak{B}$. If
$\xi_{m}^{\mathfrak{A}}$ has a (uniformly continuous) minor-preserving map to
$\operatorname{Proj}$ then so has $\operatorname{Pol}(\mathfrak{B})$ by
composing the maps, contrary to our assumptions. Therefore,
$\xi_{m}^{\mathfrak{A}}$ contains a _Siggers operation_ [Sig10]. Lemma 5.2
implies that
$\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{A})$ has a
_Siggers operation modulo $\overline{\operatorname{Aut}(\mathfrak{A})}$_
[BP20]. The polynomial-time tractability of $\operatorname{CSP}(\mathfrak{B})$
then follows from Corollary 4.13 in [BM18], which uses [Bul17, Zhu17]. ∎

For many classes of reducts of finitely bounded homogeneous structures, the
conditions given in Theorem 4.4 and in Theorem 5.6 cover all the cases. The
next section presents a condition from [BM18] that turned out to be highly
relevant to understand this phenomenon.

##  6\. Results

In this section we state the main results of the paper that we then prove in
Section 7 and in Section 8. The applications to RCC5 in spatial reasoning can
be found in Section 9.

###  6.1. The Unique Interpolation Property

Let $\mathscr{M}$ be a set of function from $A$ to $A$ and let $f,g\colon
A^{k}\to A$ be operations. We say that _$f$ interpolates $g$ over
${\mathscr{M}}$_ if for every finite $F\subseteq A$ there are
$u,v_{1},\dots,v_{k}\in{\mathscr{M}}$ such that
$g(a_{1},\dots,a_{k})=u(f(v_{1}(a_{1}),\dots,v_{k}(a_{k})))$ for all
$a_{1},\dots,a_{k}\in F$.

######  Definition 5.

Let $\mathfrak{A}$ be a structure and let $\mathscr{C}$ be an operation clone
that contains $\operatorname{Aut}(\mathfrak{A})$. A function $\zeta$ defined
on $\mathscr{D}\subseteq\mathscr{C}$ has the _unique interpolation property
(UIP) with respect to ${\mathscr{C}}$ over $\mathfrak{A}$_ if
$\zeta(g)=\zeta(h)$ for all $g,h\in\mathscr{D}$ that are interpolated by the
same operation $f\in{\mathscr{C}}$ over $\operatorname{Aut}(\mathfrak{A})$.

The main result of this section, Lemma 6.1, gives a sufficient condition for
the existence of an extension of a minor-preserving map defined on the
canonical polymorphisms of a structure $\mathfrak{B}$ to a uniformly
continuous minor-preserving map defined on all of
$\operatorname{Pol}(\mathfrak{B})$. The statement is inspired by Theorem 5.5
in [BM18], and similar statements played an important role in [BMM18].
However, the original proof in [BM18] contains a mistake (in the proof the
mashup theorem, Theorem 5.5 in [BM18], more specifically in the claim that
$\phi$ is a minor-preserving map) and fixing this with a general approach is
one of the contributions of the present article.

######  Lemma 6.1 (The extension lemma).

Let $\mathfrak{B}$ be a reduct of a countable finitely homogeneous Ramsey
structure $\mathfrak{A}$ and let $\mathscr{D}$ be an operation clone. Suppose
that
$\zeta\colon\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{A})\to\mathscr{D}$
is minor-preserving and has the UIP with respect to
$\operatorname{Pol}(\mathfrak{B})$ over $\mathfrak{A}$. Then $\zeta$ can be
extended to a uniformly continuous minor-preserving map
$\tilde{\zeta}\colon\operatorname{Pol}(\mathfrak{B})\to\mathscr{D}$.

The extension lemma motivates the study of the UIP in the context of
complexity classification of CSPs, and we obtain the following in Section 7.4.

######  Corollary 6.2.

Let $\mathfrak{C}$ be a reduct of a finitely bounded homogeneous structure
$\mathfrak{B}$, which is itself a reduct of a finitely homogeneous Ramsey
structure $\mathfrak{A}$. Suppose that whenever there is a uniformly
continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{B})$ to
$\operatorname{Proj}$ then there is also a minor-preserving map from
$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{A})$ to
$\operatorname{Proj}$ which has the UIP with respect to
$\operatorname{Pol}(\mathfrak{C})$ over $\mathfrak{A}$. Then
$\operatorname{CSP}(\mathfrak{C})$ is in P or NP-complete.

###  6.2. Other Characterisations of the UIP

To verify the UIP, the following characterisation of the UIP is helpful, since
it allows us to focus on binary polymorphisms. Let ${\mathscr{C}}$ be an
operation clone and let ${\mathscr{M}}\subseteq{\mathscr{C}}^{(1)}$. If
$v_{1},\dots,v_{k}\in{\mathscr{M}}$ we write $f(v_{1},\dots,v_{k})$ for the
operation that maps $(a_{1},\dots,a_{k})$ to
$f(v_{1}(a_{1}),\dots,v_{k}(a_{k}))$. We say that a function $\zeta$ defined
on $\mathscr{C}$ is _$\mathscr{M}$ -invariant_ if for all
$f\in{\mathscr{C}}^{(k)}$ and $u,v_{1},\dots,v_{k}\in\mathscr{M}$ we have

(2) $\displaystyle\zeta(f)=\zeta\big{(}u(f(v_{1},\dots,v_{k}))\big{)}.$

It follows from known results (see Proposition 7.7) that if $\mathfrak{A}$ is
a finitely homogeneous structure and
$\mathscr{C}\subseteq\operatorname{Can}(\mathfrak{A})$ is a closed clone, then
there exists a uniformly continuous minor-preserving map from $\mathscr{C}$ to
$\operatorname{Proj}$ if and only if there exists a minor-preserving map
$\zeta\colon{\mathscr{C}}\to\operatorname{Proj}$ which is
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant.

######  Theorem 6.3 (Binary UIP verification).

Let $\mathfrak{A}$ be a countable finitely homogeneous Ramsey structure and
let $\mathfrak{C}$ be a reduct of $\mathfrak{A}$. Let $\mathscr{C}$ be the
clone of all polymorphisms of $\mathfrak{C}$ that are canonical over
$\mathfrak{A}$ and let $\zeta\colon{\mathscr{C}}\to\operatorname{Proj}$ be an
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant minor-preserving map.
Then the following are equivalent.

  1. (1)

$\zeta$ has the UIP with respect to $\operatorname{Pol}(\mathfrak{C})$ over
$\mathfrak{A}$.

  2. (2)

for all $f\in\operatorname{Pol}(\mathfrak{C})^{(2)}$ and
$u_{1},u_{2}\in{\overline{\operatorname{Aut}(\mathfrak{A})}}$, if
$f(\operatorname{id},u_{1})$ and $f(\operatorname{id},u_{2})$ are canonical
over $\mathfrak{A}$ then

$\zeta(f(\operatorname{id},u_{1}))=\zeta(f(\operatorname{id},u_{2})).$

Theorem 6.3 can be strengthened further. We have already seen that every
homogeneous $\omega$-categorical Ramsey structure contains two independent
elementary substructures. The idea of the following theorem is that it
suffices to verify the UIP on such a pair of substructures.

######  Theorem 6.4.

Let $\mathfrak{A}$ be a countable finitely homogeneous Ramsey structure and
let $\mathfrak{C}$ be a reduct of $\mathfrak{A}$. Let ${\mathscr{C}}$ be the
clone of all polymorphisms of $\mathfrak{C}$ that are canonical over
$\mathfrak{A}$ and let $\zeta\colon{\mathscr{C}}\to\operatorname{Proj}$ be an
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant minor-preserving map.
Then the following are equivalent.

  1. (1)

$\zeta$ has the UIP with respect to $\operatorname{Pol}(\mathfrak{C})$ over
$\mathfrak{A}$.

  2. (2)

for every pair $(\mathfrak{A}_{1},\mathfrak{A}_{2})$ of independent elementary
substructures of $\mathfrak{A}$ such that for all
$f\in\operatorname{Pol}(\mathfrak{C})^{(2)}$,
$u_{1},u_{2}\in{\overline{\operatorname{Aut}(\mathfrak{A})}}$ with
$u_{1}(A)\subseteq A_{1},u_{2}(A)\subseteq A_{2}$, if
$f(\operatorname{id},u_{1})$ and $f(\operatorname{id},u_{2})$ are canonical
over $\mathfrak{A}$ then

$\zeta(f(\operatorname{id},u_{1}))=\zeta(f(\operatorname{id},u_{2})).$

##  7\. Proof of the Extension Lemma

This section contains the proof of Lemma 6.1; Corollary 6.2 about the
complexity of CSPs is then an easy consequence.

###  7.1. Diagonal Interpolation

In our proofs we need the concept of _diagonal interpolation_ , which is a
more restricted form of interpolation, and was already used in [BMM18].

######  Definition 6.

Let $\mathscr{M}$ be a set of functions from $A$ to $A$. We say that $f\colon
A^{k}\to A$ _diagonally interpolates $g\colon A^{k}\to A$ over
${\mathscr{M}}$_ if for every finite $F\subseteq A$ there are
$u,v\in{\mathscr{M}}$ such that
$g(a_{1},\dots,a_{k})=u(f(v(a_{1}),\dots,v(a_{k})))$ for all
$a_{1},\dots,a_{k}\in F$.

Diagonal interpolation is well-behaved with respect to minor identities.

######  Lemma 7.1.

Let $\mathscr{M}$ be a set of functions from $A$ to $A$, let $f\colon A^{k}\to
A$ be an operation, and let $\pi=(\pi^{n}_{i_{1}},\dots,\pi^{n}_{i_{k}})$ be a
vector of $k$ projections, each of arity $n$. Suppose that $f$ diagonally
interpolates $g$ over $\mathscr{M}$. Then $f\circ\pi$ diagonally interpolates
$g\circ\pi$ over ${\mathscr{M}}$.

###### Proof.

By assumption $g\in\overline{\\{u(f(v,\dots,v))\colon u,v\in\mathscr{M}\\}}$.
Since composition with $\pi$ is continuous,

$\displaystyle g\circ\pi$
$\displaystyle\in\overline{\\{u(f(v,\dots,v))\circ\pi\colon
u,v\in\mathscr{M}\\}}$
$\displaystyle=\overline{\\{u(f\circ\pi)(v,\dots,v)\colon
u,v\in\mathscr{M}\\}}$

and thus $f\circ\pi$ diagonally interpolates $g\circ\pi$ over ${\mathscr{M}}$.
∎

We want to stress that the innocent-looking Lemma 7.1 fails for interpolation
instead of diagonal interpolation: the following example shows that Lemma 7.1
fails for interpolation instead of diagonal interpolation.

######  Example 7.2.

Let $\mathfrak{A}$ be a structure with countable domain and two disjoint
infinite unary relations $U_{1}$ and $U_{2}$. Let $f\colon A^{3}\to A$ be an
injective function such that for every $i\in\\{1,2\\}$

  * •

$f(a,b,c)\in U_{i}$ if $a\in U_{i}$ and $b\neq c$,

  * •

$f(a,b,c)\in U_{i}$ if $b\in U_{i}$ and $b=c$.

Let $e_{1},e_{2}$ be two self-embeddings of $\mathfrak{A}$ with disjoint
images and let $g\colon A^{3}\to A$ be given by

$g(x,y,z)\coloneqq f(x,e_{1}(y),e_{2}(z)).$

Then $g$ is injective and for each $i\in\\{1,2\\}$ we have
$g(U_{i},A,A)\subseteq U_{i}$. Hence, $g$ is canonical and
$\xi_{1}(g)=\pi^{3}_{1}$. We claim that $f^{\prime}\coloneqq
f\circ(\pi^{2}_{1},\pi^{2}_{2},\pi^{2}_{2})$ does not interpolate
$g^{\prime}\coloneqq g\circ(\pi^{2}_{1},\pi^{2}_{2},\pi^{2}_{2})$. For each
$i\in\\{1,2\\}$ we have $f^{\prime}(A,U_{i})\subseteq U_{i}$, so $f^{\prime}$
is canonical and $\xi_{1}(f^{\prime})=\pi^{2}_{2}$. On the other hand

$\xi_{1}(g^{\prime})=\xi_{1}(g)(\pi^{2}_{1},\pi^{2}_{2},\pi^{2}_{2})=\pi^{3}_{1}(\pi^{2}_{1},\pi^{2}_{2},\pi^{2}_{2})=\pi^{2}_{1}$

which proves the claim.

The next lemma plays an important role in the proof of Lemma 6.1.

######  Lemma 7.3.

Let $\mathfrak{B}$ be a reduct of a countable finitely homogeneous Ramsey
structure $\mathfrak{A}$. Let $f\in\operatorname{Pol}(\mathfrak{B})$. Then
there exists $g\in\operatorname{Pol}(\mathfrak{B})$ that diagonally
interpolates both $f$ and an operation in $\operatorname{Can}(\mathfrak{A})$
over $\operatorname{Aut}(\mathfrak{A})$.

###### Proof.

Let $k$ be the arity of $f$. We first show a local version of the statement,
and then derive the statement by a compactness argument. The local version is
that for every finite $X\subseteq A$ there exists
$g\in\operatorname{Pol}(\mathfrak{B})$ and
$e\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that $g(e,\dots,e)$ is
canonical on $X^{k}$ over $\mathfrak{B}$ and $g$ agrees with $f$ on $X^{k}$.

Let $c=(c_{1},\dots,c_{n})$ be such that $\\{c_{1},\dots,c_{n}\\}=X$. By
Theorem 3.2 there are two independent elementary substructures
$\mathfrak{C}_{1}$ and $\mathfrak{C}_{2}$ of $\mathfrak{A}$. Since
$\mathfrak{A}$ is $\omega$-categorical, for $i\in\\{1,2\\}$ there exists an
isomorphism $e_{i}$ from $\mathfrak{A}$ to $\mathfrak{C}_{i}$; by the
homogeneity of $\mathfrak{A}$ we have
$e_{i}\in\overline{\operatorname{Aut}(\mathfrak{A})}$. The restriction of
$e_{1}$ to $X$ can be extended to an automorphism
$\delta\in\operatorname{Aut}(\mathfrak{A})$. Then $\delta^{-1}(C_{1})$ and
$\delta^{-1}(C_{2})$ induce independent elementary substructures of
$\mathfrak{A}$, and $X\subseteq\delta^{-1}(C_{1})$. So we may assume without
loss of generality that $X\subseteq C_{1}$.

Since $\mathfrak{A}$ is Ramsey, $f(e,\dots,e)$ interpolates a canonical
function over $\operatorname{Aut}(\mathfrak{A})$; so there are
$\delta_{1},\dots,\delta_{k}\in\operatorname{Aut}(\mathfrak{A})$ such that
$f(e\circ\delta_{1},\dots,e\circ\delta_{k})$ is canonical on $X^{k}$. In other
words, for $Y_{i}\coloneqq e\circ\delta_{1}(X)$, the map $f$ is canonical on
$Y_{1}\times\cdots\times Y_{k}$ over $\mathfrak{A}$. Since $X\subseteq C_{1}$
and $Y_{i}\subseteq C_{2}$, the tuples
$e\circ\delta_{1}(c),\dots,e\circ\delta_{k}(c)$ all have the same type over
$c$. Hence, there exist $\alpha_{i}\in\operatorname{Aut}(\mathfrak{A})$ such
that $\alpha_{i}(Y_{1})=Y_{i}$ and $\alpha(c)=c$. Define $g\coloneqq
f(\alpha_{1},\dots,\alpha_{k})$. Then $f$ and $g$ agree on $X^{k}$. We claim
that $h\coloneqq g(e\delta_{1},\dots,e\delta_{1})$ is canonical on $X^{k}$
over $\mathfrak{A}$. This follows from $f$ being canonical on

$\displaystyle Y_{1}\times\cdots\times Y_{k}$
$\displaystyle=\alpha_{1}(Y_{1})\times\cdots\times\alpha_{k}(Y_{1})$
$\displaystyle=\alpha_{1}e\delta_{1}(X)\times\cdots\alpha_{k}e\delta_{k}(X)$

since $h$ equals $f(\alpha_{1}e\delta_{1},\dots,\alpha_{k}e\delta_{k})$ on
$X^{k}$.

To show how the local version implies the statement of the lemma, let $\sigma$
be the signature of $\mathfrak{B}$ and let $\mathfrak{C}$ be an expansion of
$\mathfrak{B}$ by countably many constants such that every element of
$\mathfrak{C}$ is named by a constant symbol.

Let $\rho$ be the signature of $\mathfrak{C}$ together with a new a $k$-ary
function symbol $g$. Consider the $\rho$-theory $T$ consisting of the union of
the following first-order sentences:

  1. (1)

$\operatorname{Th}(\mathfrak{C})$;

  2. (2)

A first-order sentence which asserts that $g$ preserves all relations from
$\sigma$;

  3. (3)

For all $l\in{\mathbb{N}}$ and constant symbols
$c_{0},c_{1},\dots,c_{k}\in\rho$ such that
$f(c_{1}^{\mathfrak{C}},\dots,c_{k}^{\mathfrak{C}})=c_{0}^{\mathfrak{C}}$ the
sentence $g(c_{1},\dots,c_{k})=c_{0}$.

  4. (4)

for all constant symbols $c_{1},\dots,c_{l}\in\sigma$ the sentence
$\psi_{c_{1},\dots,c_{l}}$ which expresses that there exist
$y_{1},\dots,y_{l}$ such that
$\operatorname{typ}^{\mathfrak{A}}(y_{1},\dots,y_{l})=\operatorname{typ}^{\mathfrak{A}}(c_{1},\dots,c_{l})$
and $g$ is canonical on $\\{y_{1},\dots,y_{l}\\}^{k}$.

It follows from the basic facts about $\omega$-categorical structures from
Section 2 that such sentences exist.

Claim. Every finite subset $S$ of $T$ has a model. Let $X$ be the (finite) set
of all constants $c$ such that the respective constant symbol appears in a
sentence of $S$ or in $\\{c_{1},\dots,c_{l}\\}$ for some
$\psi_{c_{1},\dots,c_{l}}\in S$. Let $d_{1},\dots,d_{n}$ be some enumeration
of $X$. Then $\psi_{d_{1},\dots,d_{n}}$ implies every sentence in $S^{\prime}$
from item (4). By the local version of the statement there exists
$g\in\operatorname{Pol}(\mathfrak{B})$ and
$e\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that

  * •

$g(e,\dots,e)$ is canonical on $X^{k}$ over $\mathfrak{A}$, and

  * •

$g$ agrees with $f$ on $X^{k}$.

Let $\mathfrak{D}$ be the $\rho$-expansion of $\mathfrak{C}$ where
$g^{\mathfrak{D}}\coloneqq g$. Then $\mathfrak{D}$ satisfies $S$. This is
clear for the sentences from item (1), (2), and (3). Finally, since
$g(e,\dots,e)$ is canonical on $X^{k}$ over $\mathfrak{A}$ the sentences of
$S^{\prime}$ from item (4) can be satisfied by setting $y_{i}\coloneqq
e(c_{i})$.

By the compactness theorem of first-order logic, $T$ has a model
$\mathfrak{D}$. By the downward Löwenheim-Skolem theorem we may also assume
that $\mathfrak{D}$ is countable. Then the $\sigma$-reduct of $\mathfrak{D}$
satisfies $\operatorname{Th}(\mathfrak{B})$ and hence is isomorphic to
$\mathfrak{B}$ by the $\omega$-categoricity of $\mathfrak{B}$. We may
therefore identify the element of $\mathfrak{D}$ with the elements of
$\mathfrak{B}$ along this isomorphism and henceforth assume that
$\mathfrak{D}$ is an expansion of $\mathfrak{A}$. Because of the sentences
under (2) we have that $g^{\mathfrak{D}}$ is a polymorphism of $\mathfrak{B}$.
The map $e\colon B\to B$ given by $c^{\mathfrak{C}}\mapsto c^{\mathfrak{D}}$
is an elementary self-embedding. The sentences under (3) imply that
$g(e,\dots,e)$ equals $e(f)$, so $g$ diagonally interpolates $f$. Finally, the
sentences under (4) imply that $g$ diagonally interpolates some function from
$\operatorname{Can}(\mathfrak{B})$. ∎

###  7.2. Rich subsets

To prove the existence of canonical functions it is useful to introduce a
notion of _rich_ substructures of a structure; this will be needed in the full
version of the proofs for Lemma 6.1, but also explicitly in Section 9 (e.g.,
in Lemma 9.18) when we apply the general results to the spatial reasoning
formalism RCC5.

######  Definition 7.

Let $\mathfrak{A}$ be a countable finitely homogeneous structure and let $m$
be the maximal arity of $\mathfrak{A}$. Let
${\mathscr{C}}\subseteq{\mathscr{O}}_{A}$ be a closed clone containing
$\operatorname{Aut}(\mathfrak{A})$ and let $k\in{\mathbb{N}}$. Then we say
that $X\subseteq A$ is _$k$ -rich with respect to ${\mathscr{C}}$_ if

  * •

every $m$-orbit of $\mathfrak{A}^{(k)}$ contains a tuple from $(X^{k})^{m}$;

  * •

every behaviour over $\mathfrak{A}$ which is realised on $X^{k}$ by some
operation in $\mathscr{C}$ is also realised on $A^{k}$ by some operation in
$\mathscr{C}$.

Note that if $X$ is $k$-rich then every behaviour which is realisable on
$X^{k}$ is complete. It is clear from the definition that if $X\subseteq A$ is
$k$-rich, and $X\subseteq Y$, then $Y$ is also $k$-rich.

######  Lemma 7.4.

Let $\mathfrak{A}$ be a countable finitely homogeneous structure. Let
$\mathscr{C}$ be a closed clone containing $\operatorname{Aut}(\mathfrak{A})$
and let $k\in{\mathbb{N}}$. Then there exists a finite $X\subseteq A$ which is
$k$-rich with respect to ${\mathscr{C}}$.

###### Proof.

Let $m$ be the maximal arity of $\mathfrak{A}$. The structure
$\mathfrak{A}^{(k)}$ is $\omega$-categorical and hence has finitely many
$m$-orbits. Therefore, we can choose a finite subset $X_{0}$ of $A$ such that
every orbit of $m$-tuples in $\operatorname{Aut}(\mathfrak{A}^{(k)})$
intersects $(X_{0}^{k})^{m}$. Let $X_{0}\subset X_{1}\subset\cdots$ be finite
subsets of $A$ such that $\bigcup_{i=1}^{\infty}X_{i}=A$. Let
$\mathcal{B}_{i}$ denote the (finite) set of all $m$-behaviours which are
realised on $X^{k}_{i}$ by some operation of ${\mathscr{C}}$. Then
${\mathcal{B}}_{0}\supseteq{\mathcal{B}}_{1}\supseteq\cdots$ and hence there
exists an $N$ such that ${\mathcal{B}}_{N}={\mathcal{B}}_{N+1}=\cdots$. Then
Proposition 5.1 implies that every behaviour in ${\mathcal{B}}_{N}$ is
realised on $A^{k}$ by some operation in ${\mathscr{C}}$. This proves that
$X_{N}$ is $k$-rich: the first item is satisfied because $X_{0}\subseteq
X_{N}$, and the second item because every behaviour that is realised in
$X^{k}_{N}$ is also realised on $A^{k}$. ∎

######  Definition 8.

Let $\mathfrak{A}$ and $\mathscr{C}$ be as in Definition 7, let $\eta$ be a
function defined on ${\mathscr{C}}\cap\operatorname{Can}(\mathfrak{A})$, let
$F$ be $k$-rich with respect to ${\mathscr{C}}$ for some $k\geq 1$, and let
$f\in\mathscr{C}^{(k)}$. Suppose that $f$ has on $F^{k}$ the same complete
behaviour as $g\in\operatorname{Can}(\mathfrak{A})$. Then we will also write
$\eta(f|_{F^{k}})$ for $\eta(g)$.

###  7.3. Interpolation invariance

It has been shown in [BP15] (see Theorem 6.4 in [BOP18]) that if
$\mathscr{C}\subseteq{\mathscr{O}_{B}}$ is a closed clone and $\mathscr{G}$ an
oligomorphic permutation group over the same base set $B$, then every
$\mathscr{G}$-invariant continuous map $\zeta$ defined on $\mathscr{C}$ is
uniformly continuous. In Lemma 7.5 we present a sufficient condition for
uniform continuity which does not require that the map $\zeta$ we start from
is continuous, for the special case that
$\mathscr{G}=\operatorname{Aut}(\mathfrak{C})$ for a finitely homogeneous
Ramsey structure $\mathfrak{C}$.

######  Definition 9.

Let $\mathscr{C}$ be a closed operation clone on a set $B$ and let
$\mathscr{M}$ be a set of functions from $B$ to $B$. A function $\zeta$
defined on ${\mathscr{C}}$ is called _interpolation invariant over
$\mathscr{M}$_ if $\zeta(f)=\zeta(g)$ whenever $f\in{\mathscr{C}}$
interpolates $g\in{\mathscr{C}}$ over $\mathscr{M}$.

Clearly, interpolation invariance over $\mathscr{M}$ implies
${\mathscr{M}}$-invariance; see 2.

######  Lemma 7.5.

Let $\mathfrak{B}$ be a first-order reduct of a countable finitely homogeneous
Ramsey structure $\mathfrak{A}$. Let $\zeta$ be a function defined on
$\operatorname{Pol}(\mathfrak{B})$ which is interpolation invariant over
$\operatorname{Aut}(\mathfrak{A})$. Then $\zeta$ is uniformly continuous.

###### Proof.

Let $m$ be the maximal arity of $\mathfrak{A}$. Suppose for contradiction that
$\zeta$ is not uniformly continuous. Then there exists a $k\in{\mathbb{N}}$ so
that for every finite $X\subseteq A$ there exist
$f_{X},g_{X}\in\operatorname{Pol}(\mathfrak{B})$ such that
$(f_{X})|_{X^{k}}=(g_{X})|_{X^{k}}$, but $\zeta(f_{X})\neq\zeta(g_{X})$. By
Lemma 7.4, there exists a finite $A_{0}\subseteq A$ which is $k$-rich with
respect to $\operatorname{Pol}(\mathfrak{B})$.

Claim. For every finite $F\subseteq A$ that contains $A_{0}$ there exists an
$h\in\operatorname{Pol}(\mathfrak{B})^{(k)}$ and
$h^{\prime}\in\operatorname{Pol}(\mathfrak{B})^{(k)}\cap\operatorname{Can}(\mathfrak{A})$
such that $h$ and $h^{\prime}$ have the same complete behaviour on $F^{k}$ and
$\zeta(h)\neq\zeta(h^{\prime})$. By Lemma 5.5 there exists a finite
$C\subseteq A$ such that for every $h\colon A^{k}\to A$ there are
$\alpha_{1},\dots,\alpha_{k}\in\operatorname{Aut}(\mathfrak{A})$ such that
$\alpha_{1}(F)\subseteq C,\dots,\alpha_{k}(F)\subseteq C$ and
$h(\alpha_{1},\dots,\alpha_{k})$ is canonical on $F^{k}$. In particular, this
holds for the operations $f_{C},g_{C}$ introduced above, so that
$f^{\prime}\coloneqq f_{C}(\alpha_{1},\dots,\alpha_{k})$ and
$g^{\prime}\coloneqq g_{C}(\alpha_{1},\dots,\alpha_{k})$ are canonical on
$F^{k}$. We have $(f_{C})|_{C^{k}}=(g_{C})|_{C^{k}}$ and
$\zeta(f_{C})\neq\zeta(g_{C})$, and $\zeta(f_{C})=\zeta(f^{\prime})$ and
$\zeta(g_{C})=\zeta(g^{\prime})$ because $f_{C}$ interpolates $f^{\prime}$ and
$g_{C}$ interpolates $g^{\prime}$ over $\operatorname{Aut}(\mathfrak{A})$.
Since $A_{0}\subseteq F$ is $k$-rich there exist
$h^{\prime}\in\operatorname{Pol}^{(k)}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{A})$
such that $h^{\prime}$ has the same complete behaviour as $f^{\prime}$ on
$F^{k}$, and therefore also the same complete behaviour as $g^{\prime}$ on
$F^{k}$. Hence, we must have $\zeta(h^{\prime})\neq\zeta(f^{\prime})$ or
$\zeta(h^{\prime})\neq\zeta(g^{\prime})$, and hence either
$(f^{\prime},h^{\prime})$ or $(g^{\prime},h^{\prime})$ provide us witnesses
for the claim.

Let $A_{0}\subseteq A_{1}\subseteq\cdots$ be finite such that
$\bigcup_{l\in{\mathbb{N}}}A_{l}=A$. By the claim above, for each
$l\in{\mathbb{N}}$ we can find a function
$h\in\operatorname{Pol}(\mathfrak{B})$ and
$h^{\prime}\in\operatorname{Pol}(\mathfrak{B})^{(k)}\cap\operatorname{Can}(\mathfrak{A})$
such that $h$ and $h^{\prime}$ have the same $m$-behaviour ${\mathcal{H}}_{l}$
on $F^{k}$ and $\zeta(h)\neq\zeta(h^{\prime})$. By Lemma 5.4 the operation $h$
interpolates an operation $g$ with a complete behaviour ${\mathcal{B}}_{l}$
over $\mathfrak{A}$, and $\zeta(g)=\zeta(h)\neq\zeta(h^{\prime})$. Since there
are finitely many $m$-behaviours over $\mathfrak{A}$, there exists
$({\mathcal{H}},{\mathcal{B}})$ such that
$({\mathcal{H}}_{l},{\mathcal{B}}_{l})=({\mathcal{H}},{\mathcal{B}})$ for
infinitely many $l\in{\mathbb{N}}$.

Lemma 5.3 shows that there exists $f\in\operatorname{Pol}(\mathfrak{B})$ and
$e_{1},e^{\prime}_{1},\dots,e_{k},e_{k}^{\prime}\in\overline{\operatorname{Aut}(\mathfrak{A})}$
such that $f\circ(e_{i},\dots,e_{k})$ has behaviour ${\mathcal{H}}$ and
$f\circ(e^{\prime}_{i},\dots,e^{\prime}_{k})$ has behaviour ${\mathcal{B}}$.
Hence, $f$ interpolates two functions that $\zeta$ maps to different values,
contradicting interpolation invariance of $\zeta$. ∎

######  Lemma 7.6.

Let $\mathfrak{A}$ be a finitely related homogeneous structure and let
$\mathscr{C}$ be a subclone of $\operatorname{Can}(\mathfrak{A})$. Let
$\zeta\colon{\mathscr{C}}\to\operatorname{Proj}$ be
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant. Then $\zeta$ is
uniformly continuous.

###### Proof.

Let $m$ be the maximal arity of $\mathfrak{A}$, and let $X\subseteq A$ be
finite so that every orbit of $m$-tuples contains a witness in $X^{m}$. Let
$k\in{\mathbb{N}}$ and $f,g\in{\mathscr{C}}^{(k)}$ be such that
$f|_{X^{k}}=g|_{X^{k}}$. Then $\zeta(f)=\zeta(g)$ by the choice of $X$. By
Lemma 5.2, there are
$e_{1},e_{2}\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that
$e_{1}\circ f=e_{2}\circ g$. The
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariance of $\zeta$ implies
that $\zeta(f)=\zeta(e_{1}\circ f)=\zeta(e_{2}\circ g)=\zeta(g)$, proving the
uniform continuity of $\zeta$. ∎

The following can be obtained by combining known results in the literature.

######  Proposition 7.7.

Let $\mathfrak{B}$ be finitely related homogeneous with maximal arity
$m\in{\mathbb{N}}$. Let $\mathfrak{C}$ be a first-order reduct of
$\mathfrak{B}$ which is a model-complete core. Suppose that
${\mathscr{C}}\coloneqq\operatorname{Pol}(\mathfrak{C})\subseteq\operatorname{Can}(\mathfrak{B})$.
Then the following are equivalent.

  1. (1)

There is no uniformly continuous minor-preserving map from
${\mathscr{C}}\to\operatorname{Proj}$.

  2. (2)

There is no $\overline{\operatorname{Aut}(\mathfrak{B})}$-invariant minor-
preserving map ${\mathscr{C}}\to\operatorname{Proj}$.

  3. (3)

$\xi^{\mathfrak{B}}_{m}({\mathscr{C}})$ has no minor-preserving map to
$\operatorname{Proj}$.

  4. (4)

$\xi^{\mathfrak{B}}_{m}({\mathscr{C}})$ has a cyclic operation.

###### Proof.

$(1)\Rightarrow(2)$: An immediate consequence of Lemma 7.6.

$(2)\Rightarrow(3)$: If $\xi^{{\mathfrak{C}}}_{m}({\mathscr{C}})$ has a minor-
preserving map to $\operatorname{Proj}$, then we can compose it with
$\xi^{{\mathfrak{C}}}_{m}$ and obtain a
$\overline{\operatorname{Aut}(\mathfrak{B})}$-invariant minor-preserving map
from ${\mathscr{C}}$ to $\operatorname{Proj}$, and $(2)$ does not hold.

$(3)\Rightarrow(4)$ has been shown in [BOP18, BK12].

$(4)\Rightarrow(1)$. Since ${\mathfrak{C}}$ is finitely homogeneous, it has
less than doubly exponential growth. Therefore, $\mathfrak{B}$ has less than
doubly exponential growth as well, and the statement follows from results in
[BKO+19]. ∎

###  7.4. Proofs of main results

###### Proof of Lemma 6.1.

Let $f\in\operatorname{Pol}(\mathfrak{B})^{(k)}$. Since $\mathfrak{A}$ is a
finitely homogeneous Ramsey structure, we can apply the canonisation lemma
(Lemma 5.4), which implies that $f$ interpolates a function
$g\in\operatorname{Can}(\mathfrak{A})$ over
$\operatorname{Aut}(\mathfrak{A})$. Define $\bar{\zeta}(f)\coloneqq\zeta(g)$;
this is well-defined because $\zeta$ has the UIP with respect to
$\operatorname{Pol}(\mathfrak{B})$. Note that if
$f\in\operatorname{Can}(\mathfrak{A})$, then $\bar{\zeta}(f)=\zeta(f)$, so
$\bar{\zeta}$ extends $\zeta$.

Claim 1. $\bar{\zeta}$ is
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant. Suppose that
$f,g\in\operatorname{Pol}(\mathfrak{B})$ are such that $f$ interpolates $g$
over $\operatorname{Aut}(\mathfrak{A})$. Lemma 5.4 implies that $g$
interpolates over $\operatorname{Aut}(\mathfrak{A})$ an operation
$h\in\operatorname{Can}(\mathfrak{A})$. Then $f$ interpolates $h$ over
$\operatorname{Aut}(\mathfrak{A})$, too, and we have
$\bar{\zeta}(f)=\zeta(h)=\bar{\zeta}(g)$.

Claim 2. $\bar{\zeta}$ is uniformly continuous. This follows from Claim 1 by
Lemma 7.5.

Claim 3. $\bar{\zeta}$ is minor-preserving. Arbitrarily choose
$f\in\operatorname{Pol}(\mathfrak{B})^{(k)}$ and a vector
$\pi=(\pi^{n}_{i_{1}},\dots,\pi_{i_{k}}^{n})$ of projections of arity
$n\in{\mathbb{N}}$. We have to show that
$\bar{\zeta}(f\circ\pi)=\bar{\zeta}(f)\circ\pi$. By Lemma 7.3, there exists
$g\in\operatorname{Pol}(\mathfrak{B})^{(k)}$ that diagonally interpolates $f$
and diagonally interpolates
$h\in\operatorname{Pol}(\mathfrak{B})^{(k)}\cap\operatorname{Can}(\mathfrak{A})$.
We obtain

$\displaystyle\bar{\zeta}(f\circ\pi)$
$\displaystyle=\bar{\zeta}(g\circ\pi)\quad\quad\quad\quad\text{(Lem.~{}\ref{lem:diag-
minor} and interpol.-inv.\ of $\bar{\zeta}$)}$
$\displaystyle=\bar{\zeta}(h\circ\pi)\quad\quad\quad\quad\text{(Lem.~{}\ref{lem:diag-
minor} and interpol.-inv.\ of $\bar{\zeta}$)}$
$\displaystyle=\zeta(h\circ\pi)\quad\quad\quad\quad\text{($h\circ\pi\in\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{A})$)}$
$\displaystyle=\zeta(h)\circ\pi\quad\quad\quad\quad\text{($\zeta$ is minor
preserving)}$
$\displaystyle=\bar{\zeta}(h)\circ\pi=\bar{\zeta}(g)\circ\pi=\bar{\zeta}(f)\circ\pi.$

Claim 2 and 3 imply the statement of the theorem. ∎

###### Proof of Corollary 6.2.

Let $\mathfrak{C}\in{\mathcal{C}}$. First suppose that
$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{B})$ does
not have a uniformly continuous minor-preserving map to the projections.
Theorem 5.6 implies that $\operatorname{CSP}(\mathfrak{C})$ is in P. Now
suppose that
$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{B})$ has a
uniformly continuous minor-preserving map to $\operatorname{Proj}$. Then the
assumptions imply that there is also a uniformly continuous minor-preserving
map
$\zeta\colon\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{A})\to\operatorname{Proj}$
that has the UIP with respect to $\operatorname{Pol}(\mathfrak{C})$ over
$\mathfrak{A}$. Lemma 6.1 shows that $\zeta$ can be extended to a uniformly
continuous minor-preserving map
$\bar{\zeta}\colon\operatorname{Pol}(\mathfrak{C})\to\operatorname{Proj}$.
Then $\operatorname{CSP}(\mathfrak{C})$ is NP-hard by Theorem 4.4. Since CSPs
of reducts of finitely bounded structures are in NP, this concludes the proof.
∎

Note that the proof of Corollary 6.2 shows that Conjecture 4.5 holds for all
structures $\mathfrak{C}\in{\mathcal{C}}$.

##  8\. Verification of the UIP

In this section we show that if a minor-preserving map to the clone of
projections does not have the UIP, then this is witnessed by binary operations
of a very special form, proving Theorem 6.3 and its strengthening Theorem 6.4.
We need the following ‘higher-dimensional checker board’ canonisation lemma.

######  Lemma 8.1.

Let $\mathfrak{A}$ be a countable finitely homogeneous Ramsey structure and
$f\colon A^{k}\to A$. Suppose that $f$ interpolates over $\mathfrak{A}$ the
operations $h_{1},\dots,h_{m}\in\operatorname{Can}(\mathfrak{A})$. Then for
every finite $X\subseteq A$ there exist
$\alpha_{1,1},\dots,\alpha_{m,k}\in\operatorname{Aut}(\mathfrak{A})$ such that

  * •

for every $i\in\\{1,\dots,m\\}$ the operation
$f(\alpha_{i,1},\dots,\alpha_{i,k})$ has the same behaviour as $h_{i}$ on
$X^{k}$, and

  * •

for all $u_{1},\dots,u_{k}\in\\{1,\dots,m\\}$ the operation
$f(\alpha_{u_{1},1},\dots,\alpha_{u_{k},k})$ is canonical on $X^{k}$.

###### Proof.

Let $u^{1},\dots,u^{p}$ be an enumeration of $\\{1,\dots,m\\}^{k}$. We show by
induction on $q\in\\{1,\dots,p\\}$ that for every finite $X\subseteq A$ there
exist $\alpha_{1,1},\dots,\alpha_{m,k}\in\operatorname{Aut}(\mathfrak{A})$
such that for every $i\in\\{1,\dots,m\\}$ the operation
$f(\alpha_{i,1},\dots,\alpha_{i,k})$ has the same behaviour as $h_{i}$ on
$X^{k}$, and for all $l\in\\{1,\dots,q\\}$ the operation
$f(\alpha_{u^{l}_{1},1},\dots,\alpha_{u^{l}_{k},k})$ is canonical on $X^{k}$.
For $q=p$ we obtain the statement of the lemma.

If $q=0$ the statement of the claim follows from the assumptions of the lemma.
For the inductive step, we assume that the statement holds for $q-1$ and prove
the statement for $q$. Let $X\subseteq A$ be finite. Lemma 5.5 asserts the
existence of a finite $C\subseteq A$ such that for every $f\colon A^{k}\to A$
there are $\beta_{1},\dots,\beta_{k}\in\operatorname{Aut}(\mathfrak{A})$ such
that $\beta_{1}(X)\subseteq C,\dots,\beta_{k}(X)\subseteq C$ and
$f(\beta_{1},\dots,\beta_{k})$ is canonical on $X^{k}$. We apply the induction
hypothesis to $C$, and obtain $\gamma_{1,1},\dots,\gamma_{m,k}$ such that for
every $i\in\\{1,\dots,m\\}$ the operation $f(\gamma_{i,1},\dots,\gamma_{i,k})$
has the same behaviour as $h_{i}$ on $C^{k}$ and
$f(\gamma_{u^{l}_{1},1},\dots,\gamma_{u^{l}_{k},k})$ is canonical on $C^{k}$
for every $l\in\\{1,\dots,q-1\\}$. Let $f^{\prime}\coloneqq
f(\gamma_{u^{q}_{1},1},\dots,\gamma_{u^{q}_{k},k})$. The property of $C$
implies that there are
$\beta_{1},\dots,\beta_{k}\in\operatorname{Aut}(\mathfrak{A})$ such that
$\beta_{1}(X)\subseteq C,\dots,\beta_{k}(X)\subseteq C$ and
$f^{\prime}(\beta_{1},\dots,\beta_{k})$ is canonical on $X^{k}$. For
$i\in\\{1,\dots,m\\}$ and $j\in\\{1,\dots,k\\}$ define
$\alpha_{i,j}\coloneqq\gamma_{i,j}\circ\beta_{j}$. Observe
$\alpha_{i,j}(X)\subseteq\gamma_{i,j}(C)$ and hence

  * •

$f(\alpha_{u^{l}_{1},1},\dots,\alpha_{u^{l}_{k},k})$ is canonical on $X^{k}$
for $l\in\\{1,\dots,q-1\\}$: this follows from the inductive assumption that
$f(\gamma_{u^{l}_{1},1},\dots,\gamma_{u^{l}_{k},k})$ is canonical on $C^{k}$;

  * •

$f(\alpha_{u^{q}_{1},1},\dots,\alpha_{u^{q}_{k},k})$ is canonical on $X^{k}$:
this follows from the property of $\beta_{1},\dots,\beta_{k}$ that

$f^{\prime}(\beta_{1},\dots,\beta_{k})=f(\alpha_{u^{q}_{1},1},\dots,\alpha_{u^{q}_{k},k})$

is canonical on $X^{k}$;

  * •

for every $i\in\\{1,\dots,m\\}$, the operation
$f(\alpha_{i,1},\dots,\alpha_{i,k})$ has the same behaviour as $h_{i}$ on
$X^{k}$ because for every $j\in\\{1,\dots,k\\}$ and
$f(\gamma_{i,1},\dots,\gamma_{i,k})$ has the same behaviour as $h_{i}$ on
$C^{k}$ by the inductive assumption.

This concludes the proof that $\alpha_{1,1},\dots,\alpha_{m,k}$ satisfy the
inductive statement. ∎

We introduce useful notation for the proofs of Theorem 6.3 and Theorem 6.4. If
$f\colon B^{k}\to B$, $u\colon B\to B$, and $\ell\in\\{1,\dots,k\\}$, we write
$f^{u}_{\ell}$ for the $k$-ary operation defined by

$(x_{1},\dots,x_{k})\mapsto
f(x_{1},\dots,x_{\ell-1},u(x_{\ell}),x_{\ell+1},\dots,x_{k}).$

###### Proof of Theorem 6.3.

The forward implication is trivial. For the converse implication, suppose that
$\zeta$ does not have the UIP with respect to
$\operatorname{Pol}(\mathfrak{C})$ over $\mathfrak{A}$. That is, there are
operations $g,g_{1},g_{2}\in{\mathscr{C}}^{(k)}$ such that $g$ interpolates
both $g_{1}$ and $g_{2}$ over $\operatorname{Aut}(\mathfrak{A})$ and
$\zeta(g_{1})\neq\zeta(g_{2})$. By Lemma 7.4 there exists a finite
$X_{0}\subseteq A$ which is $k$-rich with respect to
$\operatorname{Pol}(\mathfrak{B})$. By Lemma 8.1 applied to $g$ and $X_{0}$
there exist
$\alpha_{1,1},\dots,\alpha_{2,k}\in\operatorname{Aut}(\mathfrak{A})$ such that

  * •

for all $u_{1},\dots,u_{k}\in\\{1,2\\}$ the operation
$g(\alpha_{u_{1},1},\dots,\alpha_{u_{k},k})$ is canonical on $X_{0}^{k}$ over
$\mathfrak{A}$, and

  * •

for $i\in\\{1,2\\}$ the operation $g(\alpha_{i,1},\dots,\alpha_{i,k})$ has the
same behaviour as $g_{i}$ on $X_{0}^{k}$.

Let $i\in\\{1,\dots,k\\}$ be the smallest index such that

$\displaystyle\zeta\big{(}g(\alpha_{1,1},\dots,\alpha_{1,i-1},\alpha_{1,i},\alpha_{2,{i+1}},\dots,\alpha_{2,k})\big{)}$
$\displaystyle\neq\;$
$\displaystyle\zeta\big{(}g(\alpha_{1,1},\dots,\alpha_{1,i-1},\alpha_{2,i},\alpha_{2,{i+1}},\dots,\alpha_{2,k})\big{)}.$

We know that such an index exists since

$\zeta\big{(}g(\alpha_{1,1},\dots,\alpha_{1,k})\big{)}=\zeta(g_{1})\neq\zeta(g_{2})=\zeta\big{(}g(\alpha_{2,1},\dots,\alpha_{2,k})\big{)}.$

Let $h\coloneqq
g(\alpha_{1,1},\dots,\alpha_{1,i-1},\operatorname{id},\alpha_{2,{i+1}},\dots,\alpha_{2,k})$.
So we have shown the following.

Claim. For every finite $X\subseteq A$ that contains $X_{0}$ there exist
$i\in\\{1,\dots,k\\}$, $h\in\operatorname{Pol}(\mathfrak{B})^{(k)}$,
$\alpha,\beta\in\operatorname{Aut}(\mathfrak{A})$, and
$h,h^{\prime}\in\operatorname{Pol}(\mathfrak{B})^{(k)}\cap\operatorname{Can}(\mathfrak{A})$
such that

  * •

$f^{\alpha}_{\ell}$ has the same behaviour as $h$ on $X^{k}$,

  * •

$f^{\beta}_{\ell}$ has the same behaviour as $h^{\prime}$ on $X^{k}$, and

  * •

$\zeta(h)\neq\zeta(h^{\prime})$.

Let $X_{0}\subset X_{1}\subset\cdots$ be finite subsets of $A$ such that
$\bigcup_{i=0}^{\infty}X_{i}=A$. Then the claim applied to $X=X_{i}$, for
$i\in{\mathbb{N}}$, asserts the existence of $f_{i}$, $\alpha_{i}$,
$\beta_{i}$, and $\ell_{i}$ such that $(f_{i})_{\ell_{i}}^{\alpha_{i}}$ and
$(f_{i})_{\ell_{i}}^{\beta_{i}}$ are canonical on $X_{i}^{k}$ and
$\zeta((f_{i})^{\alpha_{i}}_{\ell_{i}})\neq\zeta((f_{i})^{\beta_{i}}_{\ell_{i}})$.
By thinning out the sequences $(f_{i})_{i\in\mathbb{N}}$,
$(\alpha_{i})_{i\in{\mathbb{N}}}$, $(\beta_{i})_{i\in{\mathbb{N}}}$, and
$(\ell_{i})_{i\in{\mathbb{N}}}$ we can assume that all $\ell_{i}$ are equal,
say $\ell$, and that the complete behaviour ${\mathcal{B}}_{1}$ of
$f_{i}^{\alpha_{i}}$ on $X_{0}$ and ${\mathcal{B}}_{2}$ of $f_{i}^{\beta_{i}}$
on $X_{0}$ does not depend on $i$. Note that we must have
${\mathcal{B}}_{1}\neq{\mathcal{B}}_{2}$. By Lemma 5.3 (and in particular the
statement at the end starting with “moreover”) there exist
$g\in\operatorname{Pol}(\mathfrak{B})$ and
$u,v\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that $g^{u}_{\ell}$
has behaviour ${\mathcal{B}}_{1}$ on all of $A$, and $g^{v}_{\ell}$ has
behaviour ${\mathcal{B}}_{2}$ on all of $A$. So they are canonical over
$\mathfrak{A}$ and $\zeta(g^{u}_{\ell})\neq\zeta(g^{v}_{\ell})$. Suppose that
$\zeta(g^{u}_{\ell})=\pi^{k}_{r}$ and $\zeta(g^{v}_{\ell})=\pi^{k}_{s}$. Let

$f(x,y)\coloneqq f(\underbrace{y,\dots,y}_{r-1},x,y,\dots,y).$

Then note that

(3) $\displaystyle\zeta\big{(}f(\pi^{2}_{1},u(\pi^{2}_{2}))\big{)}=\;$
$\displaystyle\zeta\big{(}g(\underbrace{u(\pi^{2}_{2}),\dots,u(\pi^{2}_{2})}_{r-1},\pi^{2}_{1},u(\pi^{2}_{2}),\dots,u(\pi^{2}_{2}))\big{)}$
(4) $\displaystyle=\;$
$\displaystyle\zeta\big{(}g^{u}_{\ell}(\underbrace{\pi^{2}_{2},\dots,\pi^{2}_{2}}_{r-1},\pi^{2}_{1},\pi^{2}_{2},\dots,\pi^{2}_{2})\big{)}$
(5) $\displaystyle=\;$
$\displaystyle\pi^{k}_{r}(\underbrace{\pi^{2}_{2},\dots,\pi^{2}_{2}}_{r-1},\pi^{2}_{1},\pi^{2}_{2},\dots,\pi^{2}_{2})$
(6) $\displaystyle=\;$ $\displaystyle\pi^{2}_{1}$

where equality of (3) and (4) holds since $\zeta$ is
$\overline{\operatorname{Aut}(\mathfrak{A})}$-invariant, and equality of (4)
and (6) holds since $\zeta$ is minor-preserving. Similarly, since $r\neq s$

$\displaystyle\zeta\big{(}f(\pi^{2}_{1},v(\pi^{2}_{2}))\big{)}$
$\displaystyle=\pi^{k}_{s}(\underbrace{\pi^{2}_{2},\dots,\pi^{2}_{2}}_{r-1},\pi^{2}_{1},\pi^{2}_{2},\dots,\pi^{2}_{2})=\pi^{2}_{2}$

Therefore, $f,u,v$ show that item $(2)$ from the statement does not hold,
concluding the proof that $(2)\Rightarrow(1)$. ∎

We finally prove Theorem 6.4, which shows that it suffices to verify the UIP
on independent elementary substructures.

###### Proof of Theorem 6.4.

The forward implication holds trivially. We now show the converse,
$(2)\Rightarrow(1)$. It suffices to verify $(2)$ in Theorem 6.3. Let
$f\in\operatorname{Pol}(\mathfrak{C})^{(2)},u_{1},u_{2}\in\overline{\operatorname{Aut}(\mathfrak{A})}$
be such that $f^{u_{1}}_{2},f^{u_{2}}_{2}\in\operatorname{Can}(\mathfrak{A})$.
Let $F\subseteq A$ be 2-rich with respect to
$\operatorname{Pol}(\mathfrak{C})$. We have to verify that $f^{u_{1}}_{2}$ and
$f^{u_{2}}_{2}$ have the same complete behaviour on $F^{2}$.

Let $(\mathfrak{A}_{1},\mathfrak{A}_{2})$ be a pair of independent elementary
substructures of $\mathfrak{A}$; such a pair exists by Theorem 3.2. For
$j\in\\{1,2\\}$ let $e_{j}$ be an embedding of $\mathfrak{A}$ into
$\mathfrak{A}_{j}$. Since $\mathfrak{A}$ is homogeneous there exists
$\epsilon\in\operatorname{Aut}(\mathfrak{A})$ such that $e_{1}$ and $\epsilon$
agree on $u_{1}(F)\cup u_{2}(F)$. By Lemma 5.4 applied to
$f(\operatorname{id},\epsilon^{-1}e_{2})$ there are
$\beta_{1},\beta_{2}\in\operatorname{Aut}(\mathfrak{A})$ such that
$f(\beta_{1},\epsilon^{-1}e_{2}\beta_{2})$ is canonical on $F^{2}$. Let
$v_{i}\coloneqq\epsilon u_{i}$ and $w\coloneqq e_{2}\beta_{2}$. Note that
$v_{i}(F)\subseteq A_{1}$ and $w(F)\subseteq A_{2}$. Let $h\coloneqq
f(\beta_{1},\epsilon^{-1})\in\operatorname{Pol}(\mathfrak{C})$, and note that

$h_{2}^{v_{i}}=f(\beta_{1},\epsilon^{-1}\epsilon u_{i})=f(\beta_{1},u_{i})$

is canonical since $f_{2}^{u_{i}}=f(\operatorname{id},u_{i})$ is canonical,
and that

$h_{2}^{w}=f(\beta_{1},\epsilon^{-1}e_{2}\beta_{2})$

is canonical on $F^{2}$ as we have seen above. We thus apply (2) two times to
obtain that $\zeta(h_{2}^{v_{1}})=\zeta(h_{2}^{w})=\zeta(h_{2}^{v_{2}})$.
Finally, note that

$\zeta(f(\operatorname{id},u_{i}))=\zeta(f(\beta_{1},u_{i}))=\zeta(f(\beta_{1},\epsilon^{-1}\epsilon
u_{i}))=\zeta(h_{2}^{v_{i}}).$

We conclude that
$\zeta(f(\operatorname{id},u_{1}))=\zeta(f(\operatorname{id},u_{2}))$. ∎

##  9\. First-order expansions of the basic relations of RCC5

RCC5 is a fundamental formalism for spatial reasoning, and may be viewed as an
$\omega$-categorical structure $\mathfrak{R}$ (see, e.g., [BC09, BJ17]). There
are many equivalent ways of formally introducing RCC5; we follow the
presentation in [BC09] and refer to [BJ17] for other definitions and their
equivalence. Let $\mathfrak{S}$ be the structure with domain $S\coloneqq
2^{\mathbb{N}}\setminus\\{\emptyset\\}$, i.e., the set of all non-empty
subsets of the natural numbers ${\mathbb{N}}$. The signature of $\mathfrak{S}$
consists of the five binary relation symbols
$\mathtt{EQ},\mathtt{PP},\mathtt{PPI},\mathtt{DR},\mathtt{PO}$ where for
$x,y\subseteq\mathbb{N}$ we have

(7) $\displaystyle(x,y)\in\mathtt{EQ}$ $\displaystyle\text{ iff }x=y,$ “$x$
and $y$ are equal” (8) $\displaystyle(x,y)\in\mathtt{PP}$ $\displaystyle\text{
iff }x\subset y,$ “$x$ is strictly contained in $y$” (9)
$\displaystyle(x,y)\in\mathtt{PPI}$ $\displaystyle\text{ iff }x\supset y,$
“$x$ strictly contains $y$” (10) $\displaystyle(x,y)\in\mathtt{DR}$
$\displaystyle\text{ iff }x\cap y=\emptyset,$ “$x$ and $y$ are disjoint” (11)
$\displaystyle(x,y)\in\mathtt{PO}$ $\displaystyle\text{ iff }x\not\subset
y\wedge y\not\subset x\wedge x\cap y\neq\emptyset,$ “$x$ and $y$ properly
overlap”.

Note that by definition every pair $(x,y)\in S^{2}$ is contained in exactly
one of the relations
$\mathtt{DR}^{\mathfrak{S}},\mathtt{PO}^{\mathfrak{S}},\mathtt{PP}^{\mathfrak{S}},\mathtt{PPI}^{\mathfrak{S}},\mathtt{EQ}^{\mathfrak{S}}$.
Note that the structure $\mathfrak{S}$ is not $\omega$-categorical; however,
$\operatorname{Age}(\mathfrak{S})$ is an amalgamation class (Theorem 30 in
[BC09]), and hence there exists a countable homogeneous structure
$\mathfrak{R}$ with the same age as $\mathfrak{S}$. We refer to the relations
$\mathtt{EQ}^{\mathfrak{R}},\mathtt{PP}^{\mathfrak{R}},\mathtt{PPI}^{\mathfrak{R}},\mathtt{DR}^{\mathfrak{R}},\mathtt{PO}^{\mathfrak{R}}$
as the _basic relations of RCC5_.

The _composition_ of two binary relations $R_{1}$ and $R_{2}$ is the binary
relation $R_{1}\circ R_{2}\coloneqq\big{\\{}(x,y):\exists
z\big{(}R_{1}(x,z)\wedge R_{2}(z,y)\big{)}\big{\\}}$. The _converse_
(sometimes also called _inverse_) of a relation $R$ is the relation
$\\{(y,x)\colon(x,y)\in R\\}$, and denoted by $R^{\smile}$. The converse of
$\mathtt{PP}$ is $\mathtt{PPI}$, and $\mathtt{EQ}^{\mathfrak{R}}$,
$\mathtt{DR}^{\mathfrak{R}}$, and $\mathtt{PO}^{\mathfrak{R}}$ are their own
converse. The full binary relation containing all pairs of elements of
$\mathfrak{R}$ is denoted by $\bf 1$. It is straightforward to verify that the
relations
$\mathtt{EQ}^{\mathfrak{R}},\mathtt{PP}^{\mathfrak{R}},\mathtt{PPI}^{\mathfrak{R}},\mathtt{DR}^{\mathfrak{R}},\mathtt{PO}^{\mathfrak{R}}$
compose as shown in Table 1.

######  Lemma 9.1.

$\mathfrak{R}$ is finitely bounded.

###### Proof.

A finite structure embeds into $\mathfrak{R}$ if and only if all three-element
substructures of the structure embed into $\mathfrak{R}$. For details we refer
to [BJ17], implication $2\Rightarrow 3$ in Proposition 15. ∎

######  Remark 9.2.

As a _relation algebra_ , RCC5 is given by the composition table and the data
about the converses. Our structure $\mathfrak{R}$ introduced above is a
_representation_ of RCC5. We do not introduce relation algebras formally,
because they will not be needed in the following, and rather refer to [BJ17].

∘ DR PO PP PPI EQ DR 1 PP∪DR∪PO PP∪DR∪PO DR DR PO PPI∪DR∪PO 1 PP∪PO PPI∪PO PO
PP DR PP∪DR∪PO PP 1 PP PPI PPI∪DR∪PO PPI∪PO 1 ∖DR PPI PPI EQ DR PO PP PPI EQ

Figure 1. The composition table for the relations of $\mathfrak{R}$.

A _first-order expansion_ of a structure $\mathfrak{A}$ is an expansion of
$\mathfrak{A}$ by relations that are first-order definable over
$\mathfrak{A}$.

######  Theorem 9.3.

For every first-order expansion $\mathfrak{C}$ of $\mathfrak{R}$ either

  * •

$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{R})$ does
not have a uniformly continuous minor-preserving map to $\operatorname{Proj}$,
in which case $\operatorname{CSP}(\mathfrak{C})$ is in P, or

  * •

$\operatorname{Pol}(\mathfrak{C})$ has a uniformly continuous minor-preserving
map to $\operatorname{Proj}$, in which case $\operatorname{CSP}(\mathfrak{C})$
is NP-complete.

We prove Theorem 9.3 using Corollary 6.2 and hence first need to introduce a
Ramsey expansion $(\mathfrak{R};\prec)$ of $\mathfrak{R}$ (Section 9.1); we
use a recent Ramsey transfer result of Mottet and Pinsker [MP21]. Every first-
order expansion $\mathfrak{C}$ of $\mathfrak{R}$ is clearly a model-complete
core. We verify the remaining assumption in Corollary 6.2 in two steps.
Assuming that there exists a uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{R})$ to
$\operatorname{Proj}$, we construct Section 9.4 either

  * •

a minor-preserving map
$\eta\colon\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{R},\prec)\to\operatorname{Proj}$
which arises from the action of the canonical polymorphisms on the two
relations $\mathtt{PP}$ and $(\mathtt{DR}\cup\mathtt{PO})\,\cap\prec$, or

  * •

a minor-preserving map
$\rho\colon\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{R},\prec)\to\operatorname{Proj}$
which arises from the action of the canonical polymorphisms on the two
relations $\mathtt{DR}\,{\cap}\,{\prec}$ and $\mathtt{PO}\,{\cap}\,{\prec}$.

In the second step, we prove that if such a map
$\eta,\rho\colon\operatorname{Pol}(\mathfrak{C})\cap\operatorname{Can}(\mathfrak{R},\prec)\to\operatorname{Proj}$
exists, then it has the UIP with respect to $\operatorname{Pol}(\mathfrak{C})$
over $(\mathfrak{R},\prec)$ (Section 9.5); here we use Theorem 6.4. The
statement then follows from Corollary 6.2.

###  9.1. A Ramsey order expansion of $\mathfrak{R}$

The structure $\mathfrak{R}$ is not Ramsey, but it has a homogeneous Ramsey
expansion by a linear order. Let $\mathcal{C}$ be the class of all expansions
of structures from $\operatorname{Age}(\mathfrak{S})$ with the signature
$\\{\mathtt{EQ},\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI},\prec\\}$
such that $\prec$ denotes a linear extension of $\mathtt{PP}$.

######  Proposition 9.4.

The class $\mathcal{C}$ defined above is an amalgamation class.

###### Proof.

It is clear from the definition that $\mathcal{C}$ is closed under
isomorphisms and substructures. It is well-known that in order to prove the
amalgamation property, it suffices to verify the 1-point amalgamation property
(see, e.g., [Bod21]): for all structures
$\mathfrak{A},\mathfrak{B}_{1},\mathfrak{B}_{2}\in{\mathcal{C}}$ such that
$A=B_{1}\cap B_{2}$ and $B_{i}=A\cup\\{b_{i}\\}$, for $i\in\\{1,2\\}$ and
$b_{1}\neq b_{2}$, there exists $\mathfrak{C}\in{\mathcal{C}}$ with
$C=B_{1}\cup B_{2}=A\cup\\{b_{1},b_{2}\\}$ such that $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$ are substructures of $\mathfrak{C}$. It is easy to see that
such a structure $\mathfrak{C}$ can be determined by specifying which
relations of $\mathfrak{C}$ contain the pair $(b_{1},b_{2})$.

Bodirsky and Chen [BC09] (also see [Bod21]) proved that there exists
$R\in\\{\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI}\\}$ such that

  * •

if we add the pair $(b_{1},b_{2})$ to $R^{\mathfrak{C}}$ and the pair
$(b_{2},b_{1})$ to $(R^{\mathfrak{C}})^{\smile}$, then the
$\\{\mathtt{EQ},\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI}\\}$-reduct of
the resulting structure $\mathfrak{C}$ is in
$\operatorname{Age}(\mathfrak{S})$, and

  * •

$(b_{1},b_{2})\in\mathtt{PP}^{\mathfrak{C}}$ only if there exists $a\in A$
such that $(b_{1},a)\in\mathtt{PP}^{\mathfrak{B}_{1}}$ and
$(a,b_{2})\in\mathtt{PP}^{\mathfrak{B}_{2}}$.

If $R$ equals $\mathtt{PP}$ we add $(b_{1},b_{2})$ to $\prec^{\mathfrak{C}}$;
if $R$ equals $\mathtt{PPI}$ we add $(b_{2},b_{1})$ to $\prec^{\mathfrak{C}}$.
If $R$ is from $\\{\mathtt{DR},\mathtt{PO}\\}$, then we add $(b_{1},b_{2})$ or
$(b_{2},b_{1})$ to $\prec^{\mathfrak{C}}$ according to an order-amalgam of the
$\\{\prec\\}$-reducts of $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ over
$\mathfrak{A}$. In each of these cases, $\prec^{\mathfrak{C}}$ is a linear
order that extends $\mathtt{PP}^{\mathfrak{C}}$, and hence $\mathfrak{C}$ is
in ${\mathcal{C}}$. ∎

One can check by an easy back-and-forth argument that the
$\\{\mathtt{EQ},\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI}\\}$-reduct of
the Fraïssé-limit of ${\mathcal{C}}$ is isomorphic to $\mathfrak{R}$; hence,
we may denote this Fraïssé-limit by $(\mathfrak{R},\prec)$. To show that
$(\mathfrak{R},\prec)$ has the Ramsey property, we use a recent Ramsey
transfer result.

######  Definition 10 (Mottet and Pinsker [MP21]).

Let $\mathscr{G}$ be a permutation group on a set $X$. A function $g\colon
X\to X$ is called _range-rigid with respect to $\mathscr{G}$_ if for every
$k\in{\mathbb{N}}$, every orbit of $k$-tuples in the range of $g$ is preserved
by $g$.

Mottet and Pinsker [MP21] proved that if $\mathfrak{B}$ is a homogeneous
structure and $g\colon B\to B$ is range-rigid with respect to
$\operatorname{Aut}(\mathfrak{B})$, then the age of the structure induced by
$\mathfrak{B}$ on the image of $g$ has the amalgamation property; we denote
the Fraïssé-limit of this class by $\mathfrak{B}_{g}$.

######  Theorem 9.5 (Lemma 10 in [MP21]).

Let $\mathfrak{B}$ be a homogeneous structure and let $g\colon B\to B$ be
range-rigid with respect to $\operatorname{Aut}(\mathfrak{B})$. If
$\mathfrak{B}$ is Ramsey, then so is $\mathfrak{B}_{g}$.

Let $\mathfrak{A}=(A;\cap,\cup,\overline{\cdot},0,1)$ be the countable
atomless Boolean algebra [Hod97], which we view as a subalgebra of
$(2^{\mathbb{N}};\cap,\cup,\overline{\cdot},0,1)$. We use the usual shortcuts:

  * •

$x\subseteq y$ stands for $x\cap y=x$,

  * •

$x\subset y$ stands for $x\subseteq y$ and $x\neq y$, and

  * •

$x+y$ stands for $(x\cap\overline{y})\cup(y\cap\overline{x})$.

Let $\mathfrak{A}^{\prime}$ be the ($\omega$-categorical) relational structure
with the same domain as $\mathfrak{A}$ carrying all relations that are first-
order definable in $\mathfrak{A}$. Kechris, Pestov, and Todorčević described a
linear order $\prec$ on $A$ so that the expanded structure
$(\mathfrak{A}^{\prime},\prec)$ is a homogeneous $\omega$-categorical Ramsey
structure [KPT05]. The age of $(\mathfrak{A}^{\prime},\prec)$ can be described
as follows. If $\mathfrak{F}$ is a finite substructure of $\mathfrak{A}$, then
$\mathfrak{F}$ is a finite Boolean algebra and there exists an enumeration
$a_{1},\dots,a_{n}$ of the atoms of $\mathfrak{F}$ such that for all $u,v\in
F$ with $u=\bigcup_{i=1}^{n}(d_{i}\cap a_{i})$ and
$v=\bigcup_{i=1}^{n}(e_{i}\cap a_{i})$ for $d,e\in\\{0,1\\}^{n}$ we have
$u\prec v$ if and only if there exists some $j\in\\{1,\dots,n\\}$ such that
$d_{j}<e_{j}$ and $d_{i}=e_{i}$ for all $i>j$; such an ordering is called an
_antilexicographical ordering_.

Let $\mathfrak{B}$ be the relational structure with domain $B\coloneqq
A\setminus\\{0\\}$ and for all $k,l\geq 1$ the relation

$\displaystyle
R_{k,l}\coloneqq\big{\\{}(a_{1},\dots,a_{k},b_{1},\dots,b_{l})\mid\bigcap_{i=1}^{k}a_{i}\subseteq\bigcup_{j=1}^{l}b_{j}\big{\\}}$

and for all $k\geq 1$ and $e,d\in\\{0,1\\}^{k}$ the relation

$\displaystyle
O_{k,d,e}\coloneqq\big{\\{}(a_{1},\dots,a_{k})\mid\bigcap_{i=1}^{k}(a_{i}+d_{i})\prec\bigcap_{i=1}^{k}(a_{i}+e_{i})\big{\\}}.$

Note that $x\prec y$ has the definition $O_{2,(0,1),(1,0)}(x,y)$ in
$\mathfrak{B}$, which holds precisely if
$x\cap\overline{y}\prec{\overline{x}}\cap y$.

######  Lemma 9.6.

The structure $\mathfrak{B}$ is homogeneous.

###### Proof.

Let $i$ be an isomorphism between finite induced substructures of
$\mathfrak{B}$. We claim that $i$ preserves all quantifier-free formulas of
$\mathfrak{A}$. To see this, it suffices to show that for every Boolean term
$f$ of arity $n$ and every Boolean term $g$ of arity $k$, the function $i$
preserves the formula $f(x_{1},\dots,x_{n})=g(y_{1},\dots,y_{k})$. Since
$f(x_{1},\dots,x_{n})=g(y_{1},\dots,y_{k})$ if and only if
$f(x_{1},\dots,x_{n})+g(y_{1},\dots,y_{k})=0$, it suffices to show the
statement for the special case $f(x_{1},\dots,x_{n})=0$. Every Boolean term
can be rewritten as a finite union of finite intersections of arguments and
complements of arguments. Therefore, $f(x_{1},\dots,x_{n})=0$ is equivalent to
a conjunction of formulas of the form $x_{i_{1}}\cap\cdots\cap
x_{i_{r}}\subseteq x_{j_{1}}\cup\cdots\cup x_{j_{s}}$. These formulas are
preserved by $i$, because $i$ preserves $R_{r,s}$.

We claim that $i$ also preserves all quantifier-free formulas of
$(\mathfrak{A},\prec)$. The definition of $\prec$ implies that it suffices to
show that $i$ preserves $\prec$ for the atoms of the Boolean algebra generated
by the domain $\\{a_{1},\dots,a_{m}\\}$ of $i$. Let $b$ and $c$ be two such
atoms with $b\prec c$. Then $b=\bigcap_{i=1}^{m}(a_{i}+d_{i})$ and
$c=\bigcap_{i=1}^{m}(a_{i}+e_{i})$ for some $d,e\in\\{0,1\\}^{m}$, and hence
$i(b)\prec i(c)$, because $i$ preserves the relation $O_{m,d,e}$. By the
homogeneity of $(\mathfrak{A},\prec)$, the map $i$ has an extension to an
automorphism of $(\mathfrak{A},\prec)$. The restriction of this map to $B$ is
an automorphism of $\mathfrak{B}$, concluding the proof. ∎

######  Lemma 9.7.

The structure $\mathfrak{B}$ is Ramsey.

###### Proof.

The structure $(\mathfrak{A}^{\prime},\prec)$ and its homogeneous substructure
$\mathfrak{A}^{\prime\prime}$ with domain $B$ have topologically isomorphic
automorphism groups; since the Ramsey property only depends on the topological
automorphism group (see, e.g., [KPT05]), it follows that
$\mathfrak{A}^{\prime\prime}$ is Ramsey. It is easy to see that
$\mathfrak{A}^{\prime\prime}$ and $\mathfrak{B}$ have the same automorphism
group, even as permutation groups, which implies the statement. ∎

Consider the
$\\{\mathtt{EQ},\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI}\\}$-structure
with domain $A$ whose relations are defined over $\mathfrak{A}$ by the
expressions in (7), (8), (9), (10), (11); let $\mathfrak{D}$ be the
substructure of this structure with domain $B$.

######  Lemma 9.8.

There exists a self-embedding $e$ of $(\mathfrak{D},\prec)$ such that

  1. (1)

for all $k,l\in{\mathbb{N}}$ and $a_{1},\dots,a_{k},b_{1},\dots,b_{l}\in B$ we
have that

$(e(a_{1}),\dots,e(a_{k}),e(b_{1}),\dots,e(b_{l}))\in R_{k,l}$

if and only if $(a_{i},b_{j})\in\mathtt{PP}\cup\mathtt{EQ}$ or
$(a_{i},a_{j})\in\mathtt{DR}$ for some $i,j\leq\max(k,l)$, and

  2. (2)

for every $k\in{\mathbb{N}}$ and $d,e\in\\{0,1\\}^{k}$ there exists a
quantifier-free formula $\phi_{k,d,e}$ in the signature of
$(\mathfrak{D},\prec)$ that defines $O_{k,d,e}$.

The function $e$ is range-rigid with respect to
$\operatorname{Aut}(\mathfrak{B})$.

###### Proof.

First note that any function $e$ that satisfies the first statement of the
lemma must be range-rigid. By the homogeneity of $\mathfrak{B}$, orbits of
$k$-tuples in $\mathfrak{B}$ can be described by conjunctions of relations of
the form $R_{k,l}$ and of the form $O_{k,d,e}$. Therefore, every orbit of
$k$-tuples in the range of $e$ has by items (1) and (2) of the statement a
quantifier-free definition over the relations of $(\mathfrak{D},\prec)$. Since
$e$ preserves these relations, $e$ preserves all orbits of $k$-tuples in the
range of $e$.

To prove the first part of the statement, by a standard compactness argument
it suffices to prove that for every finite substructure $\mathfrak{F}$ of
$\mathfrak{B}$ there exists a finite substructure $(\mathfrak{G},\prec)$ of
$(\mathfrak{A},\prec)$ and a map $f\colon F\to G\setminus\\{0\\}$ that
preserves the relations of $(\mathfrak{D},\prec)$ and satisfies the property
of $e$ formulated in items (1) and (2) in the statement. Let

$\displaystyle I\coloneqq\big{\\{}$
$\displaystyle\\{a_{1},\dots,a_{k}\\}\mid\;k\in{\mathbb{N}},a_{1},\dots,a_{k}\in
F,(a_{i},a_{j})\in\mathtt{PO}^{\mathfrak{F}}\text{ for all }1\leq i<j\leq
k\\}\big{\\}}$

and let $f\colon F\to 2^{I}$ be the map given by

$f(a)\coloneqq\\{X\in I\mid\exists a^{\prime}\in X.\,a^{\prime}\subseteq
a\\}.$

Define the relation $\sqsubset$ on $I$ so that $X\sqsubset Y$ holds for
$X,Y\in I$ if and only if the smallest element of $X+Y=(X\cup
Y)\setminus(X\cap Y)$ with respect to $\prec$ is contained in $X$.

Claim 1. $\sqsubset$ defines a linear order on $I$. It is clear from the
definition of $\sqsubset$ that for all $X,Y\in I$ exactly one of $X=Y$,
$X\sqsubset Y$, and $Y\sqsubset X$ holds. To show that $\sqsubset$ is
transitive it suffices to show that $\sqsubset$ does not contain a directed
3-cycle. Let $X,Y,Z\in I$ be pairwise distinct. Let $a$ be the smallest
element in $(X\cup Y\cup Z)\setminus(X\cap Y\cap Z)$ and suppose that $a\in
X\setminus Y$, so that $X\sqsubset Y$.

  * •

If $a\in Z$ then $a$ is the the smallest element in $Z+Y$, and thus
$Z\sqsubset Y$.

  * •

If $a\notin Z$ then $a$ is the smallest element in $X+Z$, and thus $X\sqsubset
Z$.

In either case the restriction of $\sqsubset$ to $X,Y,Z$ does not form a
directed 3-cycle. By symmetry, the assumption that $x\in X\setminus Y$ can be
made without loss of generality; this proves the claim.

Let $\mathfrak{G}$ be the Boolean algebra on $2^{I}$, and let $\prec$ denote
the linear order on $G$ such that $S\prec T$ if the largest element of the
symmetric difference $S+T$ with respect to the linear order $\sqsubset$ is
contained in $T$. Note that $\prec$ is an antilexicographic linear order on
$G$ and hence $(\mathfrak{G};\prec)$ embeds into $(\mathfrak{A};\prec)$. Also
note that the image of $f$ lies in $G\setminus\\{0\\}$.

Claim 2. Every $X\in I$ equals the largest element of $I$ with respect to
$\sqsubset$ which is contained in $\bigcap_{a\in X}f(a)$. By construction,
$X\in f(a)$ for all $a\in X$, that is, $X\in\bigcap_{a\in X}f(a)$. Assume that
there exists $Y\in\bigcap_{a\in X}f(a)$. We have to show that $Y=X$ or
$Y\sqsubset X$. If $X\subseteq Y$ then we are done. Otherwise, let $a$ be the
smallest element of $X\setminus Y$ with respect to $\prec$. Since $Y\in f(a)$
there exists some $a^{\prime}\in Y$ such that $a^{\prime}\subseteq a$ by the
definition of $f(a)$. Since $a\notin Y$, it follows that $a^{\prime}\neq a$.
So $a^{\prime}\subset a$ and thus $a$ and $a^{\prime}$ cannot both be in $X$.
Since $a\in X$ we conclude that $a^{\prime}\notin X$. Hence, $a^{\prime}\in
Y\setminus X$. Since $\prec$ extends $\subset$ it follows that
$a^{\prime}\prec a$. Since $a$ was chosen to be minimal in $X\setminus Y$ with
respect to $\prec$ this implies that $Y\sqsubset X$.

To prove that $f$ preserves the relations of $\mathfrak{D}$, it suffices to
show that $f$ preserves $\mathtt{PP}$, $\mathtt{DR}$, and $\mathtt{PO}$.

  * •

Suppose that $a,b\in F$ satisfy $\mathtt{PP}(a,b)$ in $\mathfrak{F}$. Let us
assume that $X\in f(a)$ for some $X\in I$. By definition we know that
$a^{\prime}\in X$ for some $a^{\prime}\subseteq a$. Then we also have
$a^{\prime}\subseteq b$, and thus by definition $X\in f(b)$. This concludes
the proof that $f(a)\subseteq f(b)$. On the other hand $\\{b\\}\in
f(b)\setminus f(a)$, thus in fact $\mathtt{PP}(f(a),f(b))$ holds in
$\mathfrak{G}$.

  * •

Suppose that $a,b\in F$ satisfy $\mathtt{DR}(a,b)$ in $\mathfrak{F}$. If $X\in
f(a)$ then by definition there exists $a^{\prime}\in X$ such that
$a^{\prime}\subseteq a$. Since $X\in I$ and $a^{\prime}\cap b=0$ this implies
that $b^{\prime}\notin X$ for every $b^{\prime}\subseteq b$. Therefore,
$X\notin f(b)$. This implies that $\mathtt{DR}(f(a)\cap f(b))$ holds in
$\mathfrak{G}$.

  * •

Suppose that $a,b\in F$ satisfy $\mathtt{PO}(a,b)$ in $\mathfrak{F}$. Then
$\\{a\\}\in f(a)\setminus f(b)$, $\\{b\\}\in f(b)\setminus f(a)$, and
$\\{a,b\\}\in\gamma(a)\cap\gamma(b)$. Therefore, $\mathtt{PO}(f(a),f(b))$
holds in $\mathfrak{G}$.

We now show that $f$ preserves $\prec$. Let $a,b\in F$ be such that $a\prec
b$. Then by definition $\\{a\\}\sqsubset\\{b\\}$. Claim 2 implies that the
largest elements contained in $f(a)$ and $f(b)$ are $\\{a\\}$ and $\\{b\\}$,
respectively. It follows that $f(a)\prec f(b)$.

To prove that $f$ satisfies items (1) and (2) of the statement, the following
notation will be convenient. For $X\subseteq F$, we write $M(X)$ for the
minimal elements in $S$ with respect to $\subset$, i.e.,

$M(X)\coloneqq\\{a\in X\mid\neg\exists b\in X.\,b\subset a\\}.$

Note that for every $a\in X$ there exists an $a^{\prime}\in M(X)$ such that
$a^{\prime}\subseteq a$, because $X\subseteq F$ is finite.

Claim 3. Let $a_{1},\dots,a_{k},b_{1},\dots,b_{l}\in F$. Then the following
are equivalent.

  1. (1)

$(f(a_{1}),\dots,f(a_{k}),f(b_{1}),\dots,f(b_{l}))\notin R_{k,l}$;

  2. (2)

$c\coloneqq\bigcap_{i=1}^{k}f(a_{i})\cap\bigcap_{i=1}^{l}\overline{f(b_{i})}\neq\emptyset$;

  3. (3)

$a_{i}\cap a_{j}\neq 0$ and $a_{i}\not\subseteq b_{j}$ for all $1\leq
i<j\leq\max(k,l)$.

  4. (4)

The $\sqsubset$-maximal element of
$c=\bigcap_{i=1}^{k}f(a_{i})\cap\bigcap_{i=1}^{k}\overline{f(b_{i})}$ is
$M(\\{a_{1},\dots,a_{k}\\})$.

(1) and (2) are equivalent by definition.
(2) implies (3): if there are $i,j\in\\{1,\dots,k\\}$ such that $a_{i}\cap
a_{j}=\emptyset$, then $f(a_{i})\cap f(a_{j})=\emptyset$ since $f$ preserves
$\mathtt{DR}$, and hence $c=\emptyset$. If there are $i\leq k$ and $j\leq l$
such that $a_{i}\subseteq b_{j}$ then $a\cap\overline{b_{j}}=\emptyset$ and
hence $c=\emptyset$.
(3) implies (4): Let $X\coloneqq M(\\{a_{1},\dots,a_{k}\\})$. Then by
assumption $X\in I$, and by Claim 2 we know that $X$ is the maximal element of
$\bigcap_{i=1}^{k}f(a_{i})$ with respect to $\sqsubset$. Suppose for
contradiction that $X\in f(b_{j})$ for some $j\in\\{1,\dots,l\\}$. The
definition of $f$ implies that there exists $b_{j}^{\prime}\subseteq b_{j}$
such that $b_{j}^{\prime}\in X$. In other words, $b_{j}^{\prime}=a_{i}$ for
some $i\in\\{1,\dots,k\\}$, and therefore we have $a_{i}\subseteq b_{j}$, a
contradiction.
(4) implies (2): trivial.

Note that the equivalence of (1) and (3) in Claim 3 immediately implies that
$f$ satisfies item (1) of the statement. To prove that $f$ satisfies item (2),
let $a_{1},\dots,a_{k}\in F$ and $d,e\in\\{0,1\\}^{k}$. Let $X\coloneqq
M(\\{a_{i}\mid d_{i}=0\\})$ and $Y\coloneqq M(\\{a_{i}\mid e_{i}=0\\})$. We
will prove that $(f(a_{1}),\dots,f(a_{k}))\in O_{k,d,e}$ if and only if
$\bigcap_{i=1}^{k}(f(a_{i})+e_{i})\neq 0$ and either

  1. (1)

$\bigcap_{i=1}^{k}(f(a_{i})+d_{i})=0$, or

  2. (2)

$\bigcap_{i=1}^{k}(f(a_{i})+d_{i})\neq 0$ and $X\sqsubset Y$.

If $\bigcap_{i=1}^{k}(f(a_{i})+e_{i})=0$ then clearly

(12)
$\displaystyle\bigcap_{i=1}^{k}(f(a_{i})+d_{i})\prec\bigcap_{i=1}^{k}(f(a_{i})+e_{i})$

is false and hence $(f(a_{1}),\dots,f(a_{k}))\notin O_{k,d,e}$ and we are
done. So suppose that $\bigcap_{i=1}^{k}(f(a_{i})+e_{i})\neq 0$. If
$\bigcap_{i=1}^{k}(f(a_{i})+d_{i})=0$ then $(\ref{eq:order})$ holds. In this
case $(f(a_{1}),\dots,f(a_{k}))\in O_{k,d,e}$ and we are again done. So
suppose that $\bigcap_{i=1}^{k}(f(a_{i})+d_{i})\neq 0$.

Then by Claim 3 we know that $X,Y\in I$ and $X$ and $Y$ are the
$\sqsubset$-maximal elements in $\bigcap_{i=1}^{k}(f(a_{i})+d_{i})$ and
$\bigcap_{i=1}^{k}(f(a_{i})+e_{i})$, respectively. Thus, if $X\sqsubset Y$
then $\bigcap_{i=1}^{k}(f(a_{i})+d_{i})\prec\bigcap_{i=1}^{k}(f(a_{i})+e_{i})$
and so $(f(a_{1}),\dots,f(a_{k}))\in O_{k,d,e}$ and we are done. If
$Y\sqsubset X$ then
$\bigcap_{i=1}^{k}(f(a_{i})+e_{i})\prec\bigcap_{i=1}^{k}(f(a_{i})+d_{i})$ and
hence $(f(a_{1}),\dots,f(a_{k}))\notin O_{k,d,e}$ and we are also done. If
$X=Y$, let $i\in\\{1,\dots,k\\}$. If $d_{i}=0$ then by the definition of $X$
there exists an $a_{j}\in X$ such that $a_{j}\subseteq a_{i}$. Then $a_{j}\in
Y$ and thus $e_{j}=0$. Since $\bigcap_{l=1}^{k}(f(a_{l})+e_{l})\neq 0$ is
follows that in particular
$f(a_{j})\cap(f(a_{i})+e_{i})=(\gamma(a_{j})+e_{j})\cap(f(a_{i})+e_{i})\neq\emptyset$.
Since $f$ preserves $\mathtt{DR}$ this implies that $a_{j}\cap(a_{i}\cap
e_{i})\neq 0$. Since $a_{j}\subseteq a_{i}$ this is only possible if
$e_{i}=0$. Similarly one can show that $e_{i}=0$ implies $d_{i}=0$. Therefore,
$d=e$, and thus $O_{k,d,e}=\emptyset$. In particular,
$(f(a_{1}),\dots,f(a_{k}))\notin O_{k,d,e}$.

Claim 3 implies that $\bigcap_{i=1}^{k}(f(a_{j})+e_{i})\neq 0$ and
$\bigcap_{i=1}^{k}(f(a_{i})+d_{i})=0$ can be defined by quantifier-free
$\\{\mathtt{PP},\mathtt{EQ},\mathtt{DR}\\}$-formulas. Note that condition (2)
above can be expressed (assuming for simplicity of notation that
$X=\\{a_{i}\mid d_{i}=0\\}$ and $Y=\\{a_{i}\mid e_{i}=0\\}$; the general case
is similar) by the quantifier-free $\\{\prec\\}$-formula

$\bigvee_{i:d_{i}=0,e_{i}=1}\bigwedge_{j:d_{j}\neq e_{j}}a_{i}\prec a_{j}$

which concludes the proof. ∎

######  Proposition 9.9.

$\operatorname{Age}(\mathfrak{D},\prec)=\operatorname{Age}(\mathfrak{R},\prec)$.

###### Proof.

Note that $\mathfrak{D}$ has the same age as $\mathfrak{S}$ and hence the same
age as $\mathfrak{R}$. Also, $\prec$ is a linear extension of
$\mathtt{PP}^{\mathfrak{D}}$, and hence every finite substructure of
$(\mathfrak{D},\prec)$ is also a substructure of $(\mathfrak{R},\prec)$.

Conversely, let $(\mathfrak{F},\prec)$ be a finite substructure of
$(\mathfrak{R},\prec)$. Let $g$ be an embedding of $\mathfrak{F}$ into
$\mathfrak{D}$. Let $u_{1},\dots,u_{k}$ be an enumeration of $F$ such that
$u_{1}\prec\cdots\prec u_{k}$. Let $v_{1},\dots,v_{k}\in B$ be such that
$(v_{i},g(u_{j}))\in\mathtt{DR}^{\mathfrak{D}}$ for all
$i,j\in\\{1,\dots,k\\}$ and such that
$(v_{i},v_{j})\in\mathtt{DR}^{\mathfrak{D}}$ for $i\neq j$. Then we define
$f\colon F\to B$ by

$b(u)\coloneqq g(u)\cup\bigcup_{(u_{i},u)\in\mathtt{PP}^{\mathfrak{F}}}v_{i}.$

Note that $v_{1},\dots,v_{k}$ are atoms in the Boolean algebra generated by
the elements $g(F)\cup\\{v_{1},\dots,v_{n}\\}$ in $\mathfrak{A}$, and let
$w_{1},\dots,w_{\ell}$ be the other atoms. We may assume that $\prec$ is
defined on this Boolean algebra according the enumeration
$w_{1},\dots,w_{\ell},v_{1},\dots,v_{k}$ of the atoms. We prove that $f$ is an
embedding of $(\mathfrak{F},\prec)$ into $(\mathfrak{D},\prec)$. Let
$u,u^{\prime}\in F$. If $(u,u^{\prime})\in\mathtt{PP}^{\mathfrak{F}}$, then
$g(u)\subset g(v)$ and
$\\{i\colon(u_{i},u)\in\mathtt{PP}^{\mathfrak{F}}\\}\subset\\{i\colon(u_{i},u^{\prime})\in\mathtt{PP}^{\mathfrak{F}}\\}$
by the transitivity of $\mathtt{PP}^{\mathfrak{F}}$, so
$(b(u),b(u^{\prime}))\in\mathtt{PP}^{\mathfrak{D}}$. It is also clear that $b$
preserves $\mathtt{EQ}$, $\mathtt{PPI}$, $\mathtt{DR}$. To see that $b$
preserves $\mathtt{PO}$, note that if
$(u,u^{\prime})\in\mathtt{PO}^{\mathfrak{F}}$, then
$(g(u),g(u^{\prime}))\in\mathtt{PO}^{\mathfrak{D}}$, so $g(u)\cap
g(u^{\prime})$, $g(u)\cap\overline{g(u^{\prime})}$, and $\overline{g(u)}\cap
g(u^{\prime})$ are non-empty. Note that $g(u)\cap g(u^{\prime})\subseteq
b(u)\cap b(u^{\prime})$, $g(u)\cap\overline{g(u^{\prime})}\subseteq
b(u)\cap\overline{b(u^{\prime})}$, and $\overline{g(u)}\cap
g(u^{\prime})\subseteq\overline{b(u)}\cap b(u^{\prime})$, so
$(b(u),b(u^{\prime}))\in\mathtt{PO}^{\mathfrak{D}}$.

To prove that $b$ preserves $\prec$, let $i,j\in\\{1,\dots,k\\}$ be such that
$i<j$ and $u_{i}\prec u_{j}$. Then
$\mathtt{PP}^{\mathfrak{D}}(v_{j},b(u_{j}))$,
$\mathtt{DR}^{\mathfrak{D}}(v_{j},b(u_{i}))$, and for every
$m\in\\{j+1,\dots,k\\}$ we have $\mathtt{DR}^{\mathfrak{D}}(v_{m},b(u_{i}))$
and $\mathtt{DR}^{\mathfrak{D}}(v_{m},b(u_{j}))$. Indeed, if
$\mathtt{DR}^{\mathfrak{D}}(v_{m},b(u_{i}))$ does not hold, then
$\mathtt{PP}^{\mathfrak{D}}(v_{m},b(u_{i}))$ and hence
$\mathtt{PP}^{\mathfrak{F}}(u_{m},u_{i})$ by the definition of $b$. This in
turn implies that $u_{m}\prec u_{i}$ and hence $m<i$, a contradiction. By the
definition of $\prec$ on $A$ this implies that $b(u_{i})\prec b(u_{j})$ and
finishes the proof of the claim. ∎

Every relation of $(\mathfrak{D},\prec)$ has a quantifier-free definition in
the homogeneous structure $\mathfrak{B}$; let $(\mathfrak{C},\prec)$ be the
$\\{\mathtt{EQ},\mathtt{DR},\mathtt{PO},\mathtt{PP},\mathtt{PPI},\prec\\}$-structure
defined over $\mathfrak{B}_{e}$ via these quantifier-free definitions.

######  Proposition 9.10.

$(\mathfrak{C},\prec)$ is homogeneous.

###### Proof.

It suffices to show that $(\mathfrak{C},\prec)$ and $\mathfrak{B}_{e}$ are
quantifier-free interdefinable. By definition, every relation of
$(\mathfrak{C},\prec)$ has a quantifier-free definition in $\mathfrak{B}_{e}$.
Conversely, let $R$ be a relation of $\mathfrak{B}_{e}$. If $R$ is of the form
$R_{k,l}$ then item (1) of Lemma 9.8 implies that $R$ has a quantifier-free
definition over $(\mathfrak{C},\prec)$. If $R$ is of the form $O_{k,d,e}$ then
item (2) of Lemma 9.8 implies that $R$ has a quantifier-free definition over
$(\mathfrak{C},\prec)$. ∎

######  Corollary 9.11.

$(\mathfrak{C},\prec)$ and $(\mathfrak{R},\prec)$ are isomorphic.

###### Proof.

It suffices to prove that the homogeneous structures $(\mathfrak{C},\prec)$
and $(\mathfrak{R},\prec)$ have the same age. By Proposition 9.9, the age of
$(\mathfrak{R},\prec)$ equals the age of $(\mathfrak{D},\prec)$. ∎

######  Theorem 9.12.

$(\mathfrak{R},\prec)$ is Ramsey.

###### Proof.

We apply the Ramsey transfer (Theorem 9.5) to the homogeneous Ramsey structure
$\mathfrak{B}$ from Lemma 9.6 and the map $e$ from Lemma 9.8 which is range-
rigid with respect to $\operatorname{Aut}(\mathfrak{B})$. Theorem 9.5 states
that the homogeneous structure $\mathfrak{B}_{e}$ is Ramsey. The structure
$\mathfrak{B}_{e}$ has the same automorphism group as the homogeneous
structure $(\mathfrak{R};\prec)$; it follows that $(\mathfrak{R};\prec)$ is
Ramsey as well. ∎

###  9.2. Polymorphisms of $\mathfrak{R}$ that are canonical with respect to
$(\mathfrak{R},\prec)$

From now on, we identify the symbols
$\mathtt{EQ},\mathtt{PP},\mathtt{PPI},\mathtt{DR},\mathtt{PO}$ with the
respective relations of $\mathfrak{R}$, and we write $\succ$ for the converse
of $\prec$. Note that $\mathtt{PP}\cup\mathtt{DR}\cup\mathtt{PO}$ and
$\mathtt{PPI}\cup\mathtt{DR}\cup\mathtt{PO}$ are primitively positively
definable in $\mathfrak{R}$, since they are entries in Table 1. Hence, their
intersection $\mathtt{DR}\cup\mathtt{PO}$ is primitively positively definable
in $\mathfrak{R}$, too. We also write $\bot$ instead of
$\mathtt{DR}\cup\mathtt{PO}$, and $\smash{{}^{\bot}_{\prec}}$ for the relation
$\bot\,\cap\prec$.

The composition table for the binary relations with a first-order definition
over $(\mathfrak{R};\prec)$ can be derived from the composition table of
$\mathfrak{R}$ (Table 1) using the following lemma.

######  Lemma 9.13.

Let
$R_{1},R_{2}\in\\{\mathtt{EQ},\mathtt{PP},\mathtt{PPI},\mathtt{DR},\mathtt{PO}\\}$
and let $O_{1},O_{2}$ be two orbits of pairs of $(\mathfrak{R};\prec)$ such
that $O_{i}\subseteq R_{i}$. Then

$O_{1}\circ O_{2}=\begin{cases}(R_{1}\circ R_{2})\,\cap\prec&\text{ if
}O_{1},O_{2}\subseteq\;\prec\\\ (R_{1}\circ R_{2})\,\cap\succ&\text{ if
}O_{1},O_{2}\subseteq\;\succ\\\ R_{1}\circ R_{2}&\text{ otherwise.
}\end{cases}$

###### Proof.

It is clear that $O_{1}\circ O_{2}\subseteq R_{1}\circ R_{2}$ and that if
$O_{1},O_{2}\subseteq\;\prec$ then

$O_{1}\circ O_{2}\subseteq\,\prec\circ\prec\,=\,\prec.$

So the $\subseteq$-containment in the statement of the lemma holds in the
first case, and by similar reasoning also in the other two cases. The reverse
containment in the first two cases is also clear since the homogeneity of
$(\mathfrak{R},\prec)$ implies that the expression in the statement on the
right describes an orbit of pairs in $\operatorname{Aut}(\mathfrak{R},\prec)$
(we have already seen that it is non-empty). To show the equality in the third
case, let $(x,z)\in R_{1}\circ R_{2}$. If $R_{1}\circ R_{2}$ equals
$\mathtt{PP}$ (or $\mathtt{PPI}$) then $x\prec z$ (or $z\succ x$), and again
$R_{1}\circ R_{2}$ is an orbit of pairs in
$\operatorname{Aut}(\mathfrak{R},\prec)$ and the equality holds. If
$R_{1}\circ R_{2}$ equals $\mathtt{EQ}$ then the statement is clear, too.
Otherwise, let $x^{\prime},y^{\prime},z^{\prime}\in R$ be such that
$(x^{\prime},y^{\prime})\in O_{1}$ and $(y^{\prime},z^{\prime})\in O_{2}$. If
$(x^{\prime},z^{\prime})$ lies in the same orbit as $(x,z)$ in
$\operatorname{Aut}(\mathfrak{R},\prec)$ then $(x,z)\in O_{1}\circ O_{2}$.
Otherwise, consider the structure induced by $(\mathfrak{R},\prec)$ on
$\\{x^{\prime},y^{\prime},z^{\prime}\\}$; we claim that if we replace the
tuple $(x^{\prime},z^{\prime})$ in $\prec$ by the tuple
$(z^{\prime},x^{\prime})$, the resulting structure still embeds into
$(\mathfrak{R};\prec)$. By assumption, $O_{1}\subseteq\,\prec$ and
$O_{2}\subseteq\,\succ$, or $O_{1}\subseteq\,\succ$ and
$O_{2}\subseteq\,\prec$, so the modified relation $\prec$ is still acyclic.
Moreover, since $R_{1}\circ R_{2}\in\\{\mathtt{DR},\mathtt{PO}\\}$, the
modified relation $\prec$ is still a linear extension of $\mathtt{PP}$ and
hence in $\operatorname{Age}(\mathfrak{R};\prec)$. The homogeneity of
$(\mathfrak{R};\prec)$ implies that $(x^{\prime},z^{\prime})$ lies in the same
orbit as $(x,z)$, and hence $(x,z)\in O_{1}\circ O_{2}$. This concludes the
proof that $R_{1}\circ R_{2}\subseteq O_{1}\circ O_{2}$. ∎

######  Corollary 9.14.

Let $O\subseteq\;\prec$ be an orbit of pairs in
$\operatorname{Aut}(\mathfrak{R};\prec)$. Then $\mathtt{PP}\subseteq O\circ
O$.

###### Proof.

If $O=\mathtt{PP}$, then $O\circ O=O=\mathtt{PP}$. If
$O=(\mathtt{DR}\;\cap\prec)$ then

$\displaystyle O\circ O$
$\displaystyle=(\mathtt{DR}\circ\mathtt{DR})\,\cap\prec$ (Lemma 9.13)
$\displaystyle={\bf 1}\,\cap\prec$ (table in Figure 1)
$\displaystyle=\;\prec\,.$

Similarly we may compute that $\mathtt{PP}$ is contained in
$(\mathtt{PO}\,{\cap}\,{\prec})\circ(\mathtt{PO}\,{\cap}\,{\prec})$. ∎

The following general observations are useful when working with operations
that preserve binary relations over some set $B$. If $f\colon B^{k}\to B$ is
an operation that preserves
$R_{1},\dots,R_{k},R^{\prime}_{1},\dots,R_{k}^{\prime}\subseteq B^{2}$ then

$\displaystyle f(R_{1}\circ R_{1}^{\prime},\dots,R_{k}\circ R^{\prime}_{k})$
(13) $\displaystyle\subseteq\;$ $\displaystyle f(R_{1},\dots,R_{k})\circ
f(R^{\prime}_{1},\dots,R^{\prime}_{k}).$

Also note that

(14) $\displaystyle
f(R_{1}^{\smile},\dots,R_{k}^{\smile})=f(R_{1},\dots,R_{k})^{\smile}.$

######  Lemma 9.15.

Let
$f\in\operatorname{Pol}(\mathfrak{R})\cap\operatorname{Can}(\mathfrak{R},\prec)$.
Then $f$ preserves $\prec$ and $\smash{{}^{\bot}_{\prec}}$.

###### Proof.

Let $a_{1},\dots,a_{k},b_{1},\dots,b_{k}$ be elements of $\mathfrak{R}$ such
that $a_{i}\prec b_{i}$ for all $i\in\\{1,\dots,k\\}$ and
$f(b_{1},\dots,b_{k})\preceq f(a_{1},\dots,a_{k})$. For $i\in\\{1,\dots,k\\}$,
let $O_{i}$ be the orbit of $(a_{i},b_{i})$ in
$\operatorname{Aut}(\mathfrak{R},\prec)$. We then have

$\displaystyle f(\mathtt{PP},\dots,\mathtt{PP})$ $\displaystyle\subseteq
f(O_{1}\circ O_{1},\dots,O_{k}\circ O_{k})$ (Corollary 9.14)
$\displaystyle\subseteq f(O_{1},\dots,O_{k})\circ f(O_{1},\dots,O_{k})$ (13)
$\displaystyle\subseteq(\succeq\circ\succeq)$ (canonicity)
$\displaystyle=\;\succeq$

which is a contradiction to $f$ being a polymorphism of $\mathfrak{R}$. Since
$\bot$ is primitively positively definable in $\mathfrak{R}$, it also follows
that every polymorphism of $\mathfrak{R}$ which is canonical with respect to
$(\mathfrak{R},\prec)$ preserves $\smash{{}^{\bot}_{\prec}}$. ∎

######  Lemma 9.16.

Let $f\in\operatorname{Pol}(\mathfrak{R})$ be canonical over $\mathfrak{R}$ or
over $(\mathfrak{R},\prec)$. Then $f$ preserves $1\setminus\mathtt{EQ}$.

###### Proof.

Let $k$ be the arity of $f$. First suppose that $f$ is canonical over
$(\mathfrak{R},\prec)$. Let $O_{1},\dots,O^{k}$ be orbits of pairs of
$\operatorname{Aut}(\mathfrak{R};\prec)$ that are distinct from $\mathtt{EQ}$.
Suppose for contradiction that $f(O_{1},\dots,O_{k})=\mathtt{EQ}$. Then

$\displaystyle f(O_{1}\circ O_{1},\dots,O_{k}\circ O_{k})$
$\displaystyle\subseteq f(O_{1},\dots,O_{k})\circ\cdots\circ
f(O_{1},\dots,O_{k})$
$\displaystyle\subseteq\mathtt{EQ}\circ\cdots\circ\mathtt{EQ}=\mathtt{EQ}.$

Since $O_{i}\circ O_{i}$ contains $\mathtt{PP}$ or $\mathtt{PPI}$ for every
$i\in\\{1,\dots,k\\}$ by Corollary 9.14, it follows that
$f(P_{1},\dots,P_{k})\subseteq\mathtt{EQ}$ for some
$P_{1},\dots,P_{k}\in\\{\mathtt{PP},\mathtt{PPI}\\}$. Note that
$f(P_{1}^{\smile},\dots,P_{k}^{\smile})=\mathtt{EQ}^{\smile}=\mathtt{EQ}$ by
14. Since $\mathtt{PP}\subseteq\mathtt{PP}\circ\mathtt{PPI}$ and
$\mathtt{PP}\subseteq\mathtt{PPI}\circ\mathtt{PP}$ we obtain that
$f(\mathtt{PP},\mathtt{PP})\subseteq\mathtt{EQ}\circ\mathtt{EQ}=\mathtt{EQ}$,
a contradiction to $f(\mathtt{PP},\mathtt{PP})\subseteq\mathtt{PP}$. We
conclude that $f$ preserves $1\setminus\mathtt{EQ}$. If $f$ is canonical over
$\mathfrak{R}$ instead of $(\mathfrak{R},\prec)$, then the statement can be
shown similarly, using the table in Figure 1 instead of Corollary 9.14. ∎

###  9.3. Independent substructures

To verify the UIP property, we will use Theorem 6.4 and therefore need certain
pairs $(\mathfrak{A}_{1},\mathfrak{A}_{2})$ of independent elementary
substructures of $(\mathfrak{R},\prec)$.

######  Lemma 9.17.

There are elementary substructures $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$
of $(\mathfrak{R},\prec)$ such that for all $a_{1}\in A_{1}$ and $a_{2}\in
A_{2}$ we have $(a_{1},a_{2})\in\mathtt{DR}$ and $a_{1}\prec a_{2}$; in
particular, $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are independent.

###### Proof.

By the homogeneity of $(\mathfrak{R},\prec)$ it suffices to show that for
every structure
$(\mathfrak{B},\prec)\in\operatorname{Age}(\mathfrak{R},\prec)$ there are
embeddings $e_{1},e_{2}\colon\mathfrak{B}\to(\mathfrak{R},\prec)$ such that
for all $b_{1},b_{2}\in B$ we have $(e_{1}(a_{1}),e_{2}(a_{2}))\in\mathtt{DR}$
and $e_{1}(b_{1})\prec e_{2}(b_{2})$. Choose an embedding $f$ of
$\mathfrak{B}$ into the structure $\mathfrak{S}$ from the definition of
$\mathfrak{R}$; so $f(b)\subseteq{\mathbb{N}}$ for each $b\in B$. Then
$f_{1}\colon b\mapsto\\{2n\colon n\in f(b)\\}$ and $f_{2}\colon
b\mapsto\\{2n+1\colon n\in f(b)\\}$ are two embeddings of $\mathfrak{B}$ into
$\mathfrak{S}$ such that $(f_{1}(b_{1}),f_{2}(b_{2}))\in\mathtt{DR}$ for all
$b_{1},b_{2}\in B$. Let $\mathfrak{B}^{\prime}$ be the substructure of
$\mathfrak{S}$ with domain $B^{\prime}\coloneqq f_{1}(B)\cup f_{2}(B)$. For
all $b_{1},b_{2}\in B$ with $b_{1}\prec b_{2}$, define the linear order
$\prec$ on $B^{\prime}$ by $f_{1}(b_{1})\prec f_{1}(b_{2})$,
$f_{2}(b_{1})\prec f_{2}(b_{2})$, $f_{1}(b_{1})\prec f_{2}(b_{2})$. Then it is
straightforward to check that $\prec$ extends $\mathtt{PP}$, and hence
$(\mathfrak{B}^{\prime},\prec)\in\operatorname{Age}(\mathfrak{R},\prec)$,
which concludes the proof. ∎

Independent substructures are used in the proof of the following lemma that
plays an important role when verifying the UIP later.

######  Lemma 9.18.

Let $\mathfrak{C}$ be a first-order expansion of $\mathfrak{R}$ and let
$\zeta\colon\operatorname{Pol}(\mathfrak{C})\cap{\operatorname{Can}(\mathfrak{R},\prec)}\to\operatorname{Proj}$
be a clone homomorphism which does not have the UIP with respect to
$\operatorname{Pol}(\mathfrak{C})$. Then for every finite 2-rich finite subset
$F$ of the domain of $\mathfrak{R}$ there exist
$f\in\operatorname{Pol}(\mathfrak{C})^{(2)}$ and
$\alpha_{1},\alpha_{2}\in\operatorname{Aut}(\mathfrak{R};\prec)$ such that

  * •

$f$ is canonical on $F\times\alpha_{1}(F)$ and on $F\times\alpha_{2}(F)$ with
respect to $(\mathfrak{R},\prec)$,

  * •

$\zeta(f(\operatorname{id},\alpha_{1})|_{F^{2}})\neq\zeta(f(\operatorname{id},\alpha_{2})|_{F^{2}})$
(recall Definition 8),

  * •

for all $a,b\in F$, if $(a,b)\in\mathtt{PP}\cup\mathtt{EQ}$, then
$(\alpha_{1}(a),\alpha_{2}(b))\in\mathtt{PP}$, and

  * •

for all $a,b\in F$, if $(a,b)\in\;\bot$ then
$(\alpha_{1}(a),\alpha_{2}(b))\in\;\bot$.

###### Proof.

Let $\mathfrak{A}_{1},\mathfrak{A}_{2}$ be the two independent elementary
substructures of $(\mathfrak{R},\prec)$ from Lemma 9.17. Since $\zeta$ does
not have the UIP with respect to $\operatorname{Pol}(\mathfrak{C})$, by
Theorem 6.4 there exists $f^{\prime}\in\operatorname{Pol}(\mathfrak{C})^{(2)}$
and $u_{1},u_{2}\in\overline{\operatorname{Aut}(\mathfrak{A})}$ such that for
$i\in\\{1,2\\}$ the image $\Im(u_{i})$ of $u_{i}$ is contained in $A_{i}$, the
operation $f^{\prime}(\operatorname{id},u_{i})$ is canonical with respect to
$(\mathfrak{R},\prec)$, and
$\zeta(f^{\prime}(\operatorname{id},u_{1}))\neq\zeta(f^{\prime}(\operatorname{id},u_{2}))$.
By Lemma 5.5 there exists a finite subset $X$ of the domain of $\mathfrak{R}$
such that for all $g\in\operatorname{Pol}(\mathfrak{R})^{(2)}$ there exist
$\beta_{1},\beta_{2}\in\operatorname{Aut}(\mathfrak{R},\prec)$ with
$\beta_{1}(F),\beta_{2}(F)\subseteq X$ such that $g$ is canonical on
$\beta_{1}(F)\times\beta_{2}(F)$. For $i\in\\{1,2\\}$, let
$\epsilon_{i}\in\operatorname{Aut}(\mathfrak{R},\prec)$ be such that
$\epsilon_{i}(X)\subseteq\Im(u_{i})$. We may view the substructure of
$\mathfrak{R}$ induced by $\epsilon_{1}(X)\cup\epsilon_{2}(X)$ as a
substructure of $\mathfrak{S}$. By the homogeneity of $\mathfrak{R}$ we may
also assume that the substructure of $\mathfrak{S}$ on
$\epsilon_{1}(X)\cup\epsilon_{2}(X)\cup\\{\epsilon_{1}(x)\cup\epsilon_{2}(x)\colon
x\in X\\}$ has an embedding $e$ into $\mathfrak{R}$ such that
$e(\epsilon_{i}(x))=\epsilon_{i}(x)$ for all $x\in X$ and $i\in\\{1,2\\}$.
Define

$\epsilon\colon X\to\mathfrak{R}\text{ by }\epsilon(x)\coloneqq
e\big{(}\epsilon_{1}(x)\cup\epsilon_{2}(x)\big{)}.$

Let $a,b\in X$. Note that

  1. (1)

if $(a,b)\in\mathtt{PP}\cup\mathtt{EQ}$ then

$\displaystyle\epsilon_{i}(a)=e(\epsilon_{i}(a))$ $\displaystyle\subset
e\big{(}\epsilon_{1}(a)\cup\epsilon_{2}(a)\big{)}$ $\displaystyle\subseteq
e\big{(}\epsilon_{1}(b)\cup\epsilon_{2}(b)\big{)}=\epsilon(b)$

and hence $(\epsilon_{i}(a),\epsilon(b))\in\mathtt{PP}$;

  2. (2)

if $(a,b)\in\;\bot$ then $(\epsilon_{i}(a),\epsilon_{i}(b))\in\;\bot$. Since
$\epsilon_{i}(a)\in A_{i}$ it follows that $\epsilon_{i}(a)$ is disjoint from
$\epsilon_{j}(b)$ for $j\neq i$. This implies that

$\epsilon_{i}(a)\setminus\epsilon(b)=\epsilon_{i}(a)\setminus\big{(}\epsilon_{1}(b)\cup\epsilon_{2}(b)\big{)}=\epsilon_{i}(a)\setminus\epsilon_{i}(b)\neq\emptyset$

and that for $j\neq i$ we have

$\epsilon_{j}(b)=\epsilon_{j}(b)\setminus\epsilon_{i}(a)\subseteq\epsilon(b)\setminus\epsilon_{i}(a).$

In particular, $\epsilon(b)\setminus\epsilon_{i}(a)\neq\emptyset$. We obtained
that the sets $\epsilon_{i}(a)\setminus\epsilon(b)$ and
$\epsilon(b)\setminus\epsilon_{i}(a)$ are both non-empty. Therefore
$(\epsilon_{i}(a),\epsilon(b))\in\;\bot$.

We define an order $\prec^{\prime}$ on
$\epsilon_{1}(X)\cup\epsilon_{2}(X)\cup\epsilon(X)$ by setting
$a\prec^{\prime}b$ if one of the following holds.

  * •

$a,b\in\epsilon_{1}(X)\cup\epsilon_{2}(X)$ and $a\prec b$;

  * •

$a\in\epsilon_{1}(X)\cup\epsilon_{2}(X)$ and $b\in\epsilon(X)$;

  * •

$a,b\in\epsilon(X)$ and $\epsilon^{-1}(a)\prec\epsilon^{-1}(b)$.

Then it is easy to see that $\prec^{\prime}$ defines a partial order that
extends $\mathtt{PP}$; let $\prec^{\prime\prime}$ be a linear order that
extends $\prec^{\prime}$. By the definition of $(\mathfrak{R};\prec)$ there
exists an automorphism $\gamma$ of $\mathfrak{R}$ that maps
$\prec^{\prime\prime}$ to $\prec$. This shows that we may assume that
$\epsilon$ preserves $\prec$ (otherwise, replace $\epsilon$ by
$\gamma\circ\epsilon$).

By the definition of $X$ there are
$\beta_{1},\beta_{2}\in\operatorname{Aut}(\mathfrak{R},\prec)$ such that
$\beta_{1}(F)\subseteq X$, $\beta_{2}(F)\subseteq X$, and
$f^{\prime}(\operatorname{id},\epsilon)$ is canonical on
$\beta_{1}(F)\times\beta_{2}(F)$ over $(\mathfrak{R},\prec)$. Since

$\epsilon_{i}\beta_{2}(F)\subseteq\epsilon_{i}(X)\subseteq\Im(u_{i})$

for $i\in\\{1,2\\}$ we have that
$\zeta(f^{\prime}|_{\beta_{1}(F)\times\epsilon_{1}\beta_{2}(F)})\neq\zeta(f^{\prime}|_{\beta_{1}(F)\times\epsilon_{2}\beta_{2}(F)})$.
Then for some $i\in\\{1,2\\}$ we have that
$\zeta(f^{\prime}|_{\beta_{1}(F)\times\epsilon_{i}\beta_{2}(F)})\neq\zeta(f^{\prime}|_{\beta_{1}(F)\times\epsilon\beta_{2}(F)})$.
We claim that $f\coloneqq f^{\prime}(\beta_{1},\operatorname{id})$,
$\alpha_{1}\coloneqq\epsilon_{i}\circ\beta_{2}$ and
$\alpha_{2}\coloneqq\epsilon\circ\beta_{2}$ satisfy the conclusion of the
lemma:

  * •

$f$ is canonical on $F\times\alpha_{i}(F)$, for $i\in\\{1,2\\}$, because
$f^{\prime}(\operatorname{id},\epsilon)$ is canonical on
$\beta_{1}(F)\times\beta_{2}(F)$.

  * •

for all $(a,b)\in F^{2}\cap(\mathtt{PP}\cup\mathtt{EQ})$ we have that
$(\beta_{2}(a),\beta_{2}(b))\in X^{2}\cap(\mathtt{PP}\cup\mathtt{EQ})$ and by
(1) we obtain
$(\alpha_{1}(a),\alpha_{2}(b))=(\epsilon_{i}(\beta_{2}(a)),\epsilon(\beta_{2}(b)))\in\mathtt{PP}$.

  * •

for all $(a,b)\in F^{2}\cap\bot$ we have that $(\beta_{2}(a),\beta_{2}(b))\in
X^{2}\cap\bot$ and by (2) we obtain

$\displaystyle(\alpha_{1}(a),\alpha_{2}(b))$
$\displaystyle=(\epsilon_{i}(\beta_{2}(a)),\epsilon(\beta_{2}(b)))\in\;\bot.\qed$

###  9.4. Uniformly continuous minor-preserving maps

Let $\mathfrak{B}$ be a first-order expansion of $\mathfrak{R}$. In this
section we show that if there exists a uniformly continuous minor-preserving
map from
$\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{R})$ to
$\operatorname{Proj}$, then a specific minor-preserving map $\eta$ (introduced
in Section 9.4.2) or $\rho$ (introduced in Section 9.4.3) is a uniformly
continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{B})\cap\operatorname{Can}(\mathfrak{R},\prec)\to\operatorname{Proj}$.
For this task, we need some more results from finite universal algebra that
will be recalled in the following (Section 9.4.1).

####  9.4.1. Cyclic polymorphisms

An operation $f\colon A^{k}\to A$ is

  * •

_idempotent_ if $f(x,\dots,x)=x$ for every $x\in A$.

  * •

_cyclic_ if $k\geq 2$ and $f(x_{1},\dots,x_{k})=f(x_{2},\dots,x_{k},x_{1})$