\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.22}{21(2)}{2014}

\usepackage[british]{babel}
\usepackage[utf8]{inputenc}
\usepackage{eucal, url}
\usepackage{amsmath,amsxtra,mathrsfs,amsfonts,amssymb}
\numberwithin{equation}{section}
%\usepackage{fourier}
\let\sffamily\rmfamily

\usepackage{amsthm}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{fact}{Fact}

\theoremstyle{remark}
\newtheorem*{rem}{Remark}

\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}

\usepackage{paralist}

\bibliographystyle{abbrv}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\N{\mathcal{N}}
\def\C{\mathcal{C}}
\def\V{\mathcal{V}}
\def\E{\mathcal{E}}
\def\T{\mathcal{T}}
\def\G{\mathcal{G}}
\def\P{\mathcal{P}}
\def\F{\mathcal{F}}
\def\B{\mathcal{B}}
\def\LO{\mathcal{LO}}

\def\M{\mathfrak{M}}

\let\phi\varphi

\DeclareMathOperator{\acl}{acl}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\Csp}{CSP}
\DeclareMathOperator{\age}{age}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\Forbh}{Forb_{h}}
\newcommand{\ignore}[1]{}
\newcommand{\Nesetril}{Nešetřil}
\newcommand{\Roedl}{Rödl}
\newcommand{\Fresse}{Fra\"{i}ss\'{e}}

\newtheorem{question}{Question}
\newtheorem{conjecture}{Conjecture}

\def\ocat{$\omega$-cat\-e\-gor\-i\-cal}
\def\sutst{$(\sigma\cup\tau)$-struc\-ture}
\def\sutordst{$(\sigma\cup\tau\cup\{{\preq}\})$-struc\-ture}
\def\sigst{$\sigma$-struc\-ture}

%\let\preq\preccurlyeq
\let\preq\preceq

\def\ol#1{\bar #1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\bf New Ramsey Classes from Old}

\author{Manuel Bodirsky\thanks{Manuel Bodirsky has received funding from the ERC %European Research Council 
under the European Community's Seventh Framework Programme
(FP7/2007-2013 Grant Agreement no. 257039).
}\\
\small LIX, {\' E}cole Polytechnique\\[-0.8ex]
\small 91128 Palaiseau, France\\
\small \texttt{bodirsky@lix.polytechnique.fr}
}

\date{\dateline{Jul 19, 2012}{Apr 22, 2014}{May 9, 2014}\\
\small Mathematics Subject Classifications: 05D10, 03C10, 22F50
}

\begin{document}

\maketitle

\begin{abstract}
Let $\C_1$ and $\C_2$ be strong amalgamation classes of
finite structures, with disjoint finite signatures $\sigma$ and $\tau$. Then
$\C_1 \wedge \C_2$ denotes the class of 
all finite $(\sigma \cup \tau)$-structures 
whose $\sigma$-reduct is from $\C_1$ and whose $\tau$-reduct is from $\C_2$. 
We prove that when $\C_1$ and $\C_2$ are Ramsey,
then $\C_1 \wedge \C_2$ is also Ramsey. We also discuss variations of this statement,
and give several examples of new Ramsey classes derived from those general results. 
\end{abstract}

\section{Introduction and Results}
A class of relational structures is a \emph{Ramsey class} if
it satisfies a strong combinatorial property that resembles the statement of Ramsey's theorem.
Surprisingly many classical classes of relational
structures turned out to be Ramsey classes. 
\Nesetril~\cite{RamseyClasses} asked whether one may classify all
Ramsey classes that are closed under induced substructures and have the joint embedding property, and he indicated a link to the model-theoretic classification of countably infinite homogeneous structures as an approach to such a classification. 
This program has recently attracted
attention because of a fascinating correspondence between Ramsey classes and the concept of extreme amenability in topological dynamics~\cite{Topo-Dynamics}. We would also like to mention that
Ramsey classes play an important role in
classifications of first-order reducts of homogeneous
relational structures~\cite{BP-reductsRamsey},
and for complexity classification of infinite-domain
constraint satisfaction~\cite{Bodirsky-HDR}.
Establishing
that a class has the Ramsey property is often 
a substantial combinatorial challenge, and we
are therefore interested in general transfer principles that allow to prove the Ramsey property by reducing to known Ramsey classes; this will be the topic of this text. 


For structures $A$ and $B$ over the same relational signature, 
let $\binom{B}{A}$ denote the set of
all embeddings of~$A$ into~$B$.
%all induced substructures of~$A$ into~$B$. 
% (also called \emph{copies} of~$A$ in~$B$).
When $f$ is such an embedding, we write $f[A]$ for the copy of $A$ in $B$ that is induced by the image of $A$ under $f$ in $B$.
The partition arrow $C\to(B)^A_r$ means that 
for every function $\chi \colon \binom{C}{A} \rightarrow \{1,\dots,r\}$ 
%whenever
%$\binom{C}{A}=\E_1\cup\E_2\cup\dotsb\cup\E_r$
(a \emph{colouring}
with $r$ colours) there exists $g\in\binom{C}{B}$ such that $\chi$ is constant on $\binom{g[B]}{A}$. In this case we call $g[B]$ 
a \emph{monochromatic copy} of~$B$ in~$C$.
A class of finite relational structures $\C$ has the \emph{Ramsey property (with respect to embeddings)}\footnote{In some papers, a class $\C$ has the Ramsey property if and only if $\C$ satisfies an analogous property where the partition arrow is not about embeddings, but induced substructures. The two variants are closely related; for a discussion, see~\cite{RamseyClasses,Topo-Dynamics}.} if 
for all $A,B \in \C$ and $r \in {\mathbb N}$ there exists a $C \in \C$ such that $C\to(B)^A_r$.
It is easy to see that every class $\C$ with the Ramsey property only contains \emph{rigid} structures,
that is, structures with only one automorphism, the identity. 
Note that an \emph{ordered} structure, that is, a structure that has a strict linear order
as one of its relations, is always rigid. 
A class of relational structures 
that is closed under isomorphisms 
and has the 
Ramsey property is also called a
\emph{Ramsey class}. 

Examples of Ramsey classes 
are 
\begin{itemize}
\item $\LO$, the class of all finite linear orders (this is equivalent to Ramsey's original theorem);
\item the class of all ordered finite graphs (see~\cite{NesetrilRoedlPartite});
\item the class of all ordered $K_n$-free graphs (see~\cite{NesetrilRoedlPartite});
\item the class of all finite partially ordered sets with a linear extension (see~\cite{RamseyClasses});
\item the class of all finite tournaments with an additional linear order;
\item the class of all finite convexly ordered binary branching $C$-relations on a finite set (see~\cite{BodirskyPiguet}; this is essentially due to~\cite{Mil79}).
%\item The class of all naturally ordered vector spaces over a finite field~\cite{Topo-Dynamics}
%\item The class of all naturally ordered finite Boolean algebras~\cite{Topo-Dynamics}
\end{itemize}
It is of major interest in combinatorics 
to obtain a more systematic understanding of the question which
classes of structures have the Ramsey property. 

\Nesetril\ made the important observation that Ramsey classes that are closed under taking induced substructures are linked with the concept of
\emph{amalgamation} in model theory. 
We say that a class of structures has the \emph{amalgamation property} if for all
$A,B_1,B_2\in \C$ and embeddings $e_1 \colon A \rightarrow B_1$ and $e_2 \colon A \rightarrow B_2$
there exists  
%with $A=B_1\cap B_2$ there is
 a $C \in \C$ and embeddings $f_i$ of $B_i$ to $C$ such that $f_1(e_1(a))=f_2(e_2(a))$ for all $a \in A$.  We call $(A,B_1,B_2,e_1,e_2)$ the \emph{amalgamation diagram},
 and $(C,f_1,f_2)$ an \emph{amalgam} of the diagram $(A,B_1,B_2,e_1,e_2)$ (in $\C$).
 If $\C$ has the amalgamation property for the special case that $A$ is empty,
we say that $\C$ has the \emph{joint embedding property} (here, our assumption that the signature is relational becomes important). 
The mentioned link between Ramsey theory and amalgamation is that 
every class $\C$ of rigid finite relational structures that is closed under isomorphisms and induced substructures, and that has the joint embedding and the Ramsey property also has 
amalgamation property~\cite{RamseyClasses}. Classes of finite structures with countably many non-isomorphic structures that are closed under isomorphisms, induced substructures, and have the amalgamation property are called \emph{amalgamation classes}. 

The \emph{age} of a relational structure $\Gamma$ is the class of all finite structures
that embed into $\Gamma$. 
A structure is \emph{homogeneous} if any isomorphism between finite induced substructures of $\Gamma$ can be extended to an automorphism of $\Gamma$. 
When $\C$ is an amalgamation class, then \Fresse's theorem shows that there exists a countable homogeneous structure $\Gamma$ whose age is $\C$ 
(see e.g.~\cite{Hodges}). 
The structure $\Gamma$ is unique up to isomorphism, and called the \emph{\Fresse-limit} of $\C$;  these homogeneous limit structures
will play an important role in the proof of our main result. 
The significance of \Nesetril's observation is that the transition to countable homogeneous structures brings new tools for the systematic understanding 
of Ramsey classes; and indeed, under some additional assumptions, there are many 
\emph{classification results} for homogeneous structures (such as the classification of all homogeneous directed graphs~\cite{Cherlin}). 


A \emph{strong amalgam} of an amalgamation diagram 
$(A,B_1,B_2,e_1,e_2)$ is an amalgam $(C,f_1,f_2)$ 
such that $f_1(e_1(A)) = f_2(e_2(A)) = f_1(B_1) \cap f_2(B_2)$.
A class $\C$ has \emph{strong amalgamation} if every
amalgamation diagram has a strong amalgam in $\C$.
We say that $\C$ is a \emph{strong amalgamation class} if $\C$ is closed under isomorphisms, induced substructures, and has the strong amalgamation property. An example of a strong amalgamation class is $\LO$. 

We write $\Aut(\Gamma)$ for the automorphism group of $\Gamma$.
An \emph{orbit} of $\Gamma$ is meant to be an orbit of $\Aut(\Gamma)$, that is,
a set of the form $\{\alpha(c) \; | \; \alpha \in \Aut(\Gamma)\}$ for some element $c$ of the domain of $\Gamma$. 
Homogeneous structures $\Gamma$ that arise as the \Fresse-limits
of strong amalgamation classes can be characterized via algebraic closure. In this context, we define 
the algebraic closure $\acl(A)$ of a finite subset $A = \{a_1,\dots,a_n\}$ 
of the domain of $\Gamma$
to be the set of all those elements of $\Gamma$ which lie in finite orbits of the expansion
$(\Gamma,a_1,\dots,a_n)$ of $\Gamma$ by the constants $a_1,\dots,a_n$. 

\begin{prop}[see (2.15) in~\cite{Oligo}]
\label{prop:acl}
The age of a homogeneous structure $\Gamma$ has strong amalgamation if and only if for any finite subset $A$ of the domain of $\Gamma$, $\acl(A)=A$. 
\end{prop}


\begin{dfn}[(3.9) in~\cite{Oligo}]
Let $\C_1$ and $\C_2$ be strong amalgamation classes with disjoint 
signatures $\sigma$ and $\tau$. Then
$\C_1 \wedge \C_2$ denotes the class of all finite $(\sigma \cup \tau)$-structures 
whose $\sigma$-reduct is from $\C_1$ and whose $\tau$-reduct is from $\C_2$. 
\end{dfn}

It is clear that $\C_1 \wedge \C_2$ also has strong
amalgamation. In  Section~\ref{sect:full-product}, we prove the following.

\begin{thm}\label{thm:pre-main}
Let $\C_1$ and $\C_2$ be strong amalgamation classes with the Ramsey property, with disjoint finite signatures $\sigma$ and $\tau$.
Then $\C_1 \wedge \C_2$ has the Ramsey property. 
\end{thm}


The following is an immediate consequence of Theorem~\ref{thm:pre-main}
and the previously known Ramsey results mentioned above. 


\begin{cor}\label{cor:applications}
The following classes of finite structures are Ramsey. 
\begin{enumerate}
\item The class of all permutations of a finite set (represented by two linear orders);
\item The class of all finite sets carrying $n$ linear orders;
\item The class of all finite posets with a linear extension and an additional arbitrary linear order;
\item The class of all finite sets carrying two posets, a linear extension of the first, and a linear extension of the second poset;
\item The class of all finite sets carrying a poset and a linear extension of it, 
and additional linear order and a graph relation.
%\item The class of all all convexly ordered binary branching $C$-relations on finite sets that additionally carry a poset and a linear extension of this poset. 
\end{enumerate}
\end{cor}

Item 1 in Corollary~\ref{cor:applications} has been obtained independently 
by  B\"ottcher and Foniok~\cite{BoettcherFoniok} and by Soki\'c~\cite{Sokic}. 
To prove the statement in item 1, Soki\'c developed a technique called
\emph{cross construction}; also see~\cite{SokicIsrael}. He also proved
item 2 and 3 in Corollary~\ref{cor:applications}. The present work has been found independently from~\cite{SokicIsrael}, and it would be interesting to compare our approach with the approach in~\cite{SokicIsrael}.
The other items in the list have been added
mainly for illustration reasons, and it is clear that the list can be prolonged easily. 

Homogeneous structures with a finite relational signature
are \emph{$\omega$-categorical}, % (or countably categorical)}, 
that is, their first-order theory has only one countable model up to isomorphism. 
We can weaken the assumption of having a finite signature slightly, 
and prove the following stronger version which captures 
several additional interesting classes (see Corollary~\ref{cor:examples}). 

\begin{thm}\label{thm:main}
Let $\C_1$ and $\C_2$ be strong amalgamation classes with $\omega$-categorical
\Fresse-limits. If $\C_1$ and $\C_2$ have disjoint relational signatures and the Ramsey property, then $\C_1 \wedge \C_2$ is also Ramsey. 
\end{thm}

To show the Ramsey property for even more classes, we would also like to be able to
generate Ramsey classes that only have one linear order in their signature; this can be accomplished using the following proposition whose proof can be found in Section~\ref{sect:forget-order}.


\begin{prop}\label{prop:forget-order}
Let $\C_1$ and $\LO \wedge \C_2$ be Ramsey classes 
with strong amalgamation and $\omega$-categorical \Fresse-limits,
and suppose that $\C_1$, $\C_2$, and $\LO$ have pairwise disjoint relational signatures.
Then $\C_1 \wedge \C_2$ has the Ramsey property. 
\end{prop}

Proposition~\ref{prop:forget-order} 
%in combination with 
%Theorem~\ref{thm:main} becomes 
is a versatile tool to construct a variety of new Ramsey classes. 
To state many examples, we make the following definitions.
\begin{dfn}\label{def:classes}
Write 
\begin{itemize}
\item $\T$ for the class of all finite tournaments, 
\item $\G$ for the class of all finite graphs,
\item $\F_n$ for the class of all finite $K_n$-free graphs,
\item $\vec \T$ for the class of all linearly ordered finite tournaments, 
\item $\vec \G$ for the class of all linearly ordered finite graphs,
\item $\vec \F_n$ for the class of all linearly ordered finite $K_n$-free graphs,
\item $\vec \P$ for the class of all linearly extended finite posets,
\item $\vec \C$ for the class of all convexely ordered binary branching $C$-relations on a finite set,
%\item $\vec \B$ for the class of all finite naturally ordered Boolean algebras, 
%represented as relational  structures with an infinite signature
%that contains a relation symbol for every equation that can be expressed using the function symbols $\wedge,\vee,\neq,0,1$ of the Boolean algebra,
\item $\vec \V$ for the class of all finite affine vector spaces $V$, equipped with a `natural order' (see~\cite{Topo-Dynamics}); the vector spaces will be
represented as relational structures with an infinite signature that contains a relation symbol for every affine equation.
%(represented relationally as described in the case of Boolean algebras).
\end{itemize}
\end{dfn}

\begin{cor}\label{cor:examples}
Let $\C_1$ be one of the classes $\vec\T,\vec\G,\vec\F_n,\vec\P,\vec\C,\vec\V$, and let $\C_2$ be one of the classes $\T,\G,\F_n$.
Then $\C_1 \wedge \C_2$ has the Ramsey property. 
\end{cor}

Also Corollary~\ref{cor:my-kpt} covers
examples of particular interest; for example
the class $\vec \C \wedge \T$ will 
be discussed at the end of Section~\ref{sect:topo-dyn}. 

%\subsection{Introduction for Group Theorists}
\section{Topological Dynamics}
\label{sect:topo-dyn}
Our combinatorial result translates nicely
into a result that shows that certain intersections of extremely amenable groups are again extremely amenable,
based on a connection between Ramsey theory and topological dynamics (Theorem~\ref{thm:kpt}). 
In fact, our presentation of the proof of Theorem~\ref{thm:main} makes use of this connection, and so we briefly present it in the following. 

Let us first mention that the property of $\omega$-categoricity of a structure $\Gamma$ can
be characterized in terms of the automorphism group of $\Gamma$; this has been shown Engeler, Svenonius, and Ryll-Nardzewski, and we state it for easy reference. When $\Gamma$ is a $\tau$-structure with domain $D$, and $R \subseteq D^k$, then we say that $R$ has a \emph{first-order definition} in $\Gamma$ if there exists
a first-order formula $\phi$ with $k$ free variables over the signature $\tau$
such that $R = \{(d_1,\dots,d_k) \in D^k \; | \; \phi(d_1,\dots,d_n) \text{ holds in } \Gamma\}$. 

\begin{thm}
[see Theorem~6.3.1 and Corollary~6.3.3 in~\cite{Hodges}]
\label{thm:ryll}
A countable structure is $\omega$-categorical if and only if
its automorphism group 
is \emph{oligomorphic}, that is, has only finitely many orbits of $n$-tuples, for all $n$.
If $\Gamma$ is $\omega$-categorical,
then all relations that are preserved by
all automorphisms of $\Gamma$ have
a first-order definition in $\Gamma$. 
\end{thm}

We say that $R$ has a \emph{quantifier-free definition} in $\Gamma$ if $\phi$ can be chosen to be without quantifiers.

\begin{prop}[see (2.22) in~\cite{Oligo}]
\label{prop:qe}
When $\Gamma$ is $\omega$-categorical, then $\Gamma$ is homogeneous if and only if 
$\Gamma$ has \emph{quantifier-elimination}, that is, every first-order definable relation in $\Gamma$ also has a quantifier-free definition. 
\end{prop}
 
A topological group $G$ is called \emph{extremely amenable} if every continuous action of $G$ on a compact Hausdorff space has a fixed point. 
%It is easy to see (see e.g.~\cite{Topo-Dynamics}) that $\Gamma$ is Ramsey if and
%only if for all finite substructures $P$, $H$ of $\Gamma$
%it holds that $\Gamma \rightarrow (H)^P_2$. 
We say that a homogeneous structure $\Gamma$ 
is \emph{Ramsey} if the class of all finite induced substructures that embed into 
$\Gamma$ is a Ramsey class. 
The following is the central result from~\cite{Topo-Dynamics}.

\begin{thm}[Theorem~4.8 in~\cite{Topo-Dynamics}]\label{thm:kpt}
Let $\Gamma$ be a countable ordered homogeneous structure.
Then the following are equivalent.
\begin{itemize}
\item $\Aut(\Gamma)$ is extremely amenable. 
\item $\Gamma$ is Ramsey. 
\end{itemize}
\end{thm}

This result and other known facts %from~\cite{Topo-Dynamics} 
have the following consequence 
for the special case that $\Gamma$ is additionally  
$\omega$-categorical.

\begin{cor}%[Kechris, Pestov, Todorcevic~\cite{Topo-Dynamics}]
\label{cor:my-kpt}
Let $\Gamma$ be an $\omega$-categorical countable homogeneous structure. Then the following are equivalent.
\begin{enumerate}
\item $\Gamma$ is Ramsey.
\item For all finite substructures $A,B$ of $\Gamma$ it holds that $\Gamma \to (B)^A_2$.
\item $\Aut(\Gamma)$ is extremely amenable.
\item $\Gamma$ is Ramsey, and there is a quantifier-free 
definition of 
a linear order over $\Gamma$. 
%there is a
%quantifier-free definable linear order on $D$.
%there is a linear order on $D$ with a quantifier-free definition in $\Gamma$. 
\end{enumerate}
\end{cor}
%Some explanations are in place, since Corollary~\ref{\thm:my-kpt} is only implicitly in~\cite{Topo-Dynamics}. 
\begin{proof}
The equivalence
between the first two items is based on compactness argument and a standard fact that can be found in many text-books on Ramsey theory. For the equivalence of the last two items, recall that we color \emph{embeddings}, and not
induced substructures, so the Ramsey property implies rigidity. 
The equivalence of rigidity and the existence of a linear order which is preserved by all automorphisms of $\Gamma$
for Ramsey structures $\Gamma$ is stated
in Proposition 4.3 in~\cite{Topo-Dynamics}.
Note that our additional assumption that 
$\Gamma$ is $\omega$-categorical implies 
that such a linear order 
has a first-order definition over $\Gamma$ (Theorem~\ref{thm:ryll}).
Finally, homogeneity and $\omega$-categoricity of $\Gamma$ imply by
Proposition~\ref{prop:qe} that
we can even find a quantifier-free definition over $\Gamma$. 
\end{proof}

%When $\mathcal C$ is an amalgamation class, then it is in general \emph{not} true
%that an order is first-order definable in 
%the \Fresse-limit of $\C$, even when
%all structures in $\C$ are rigid. 
We would like to comment on the consequence of Corollary~\ref{cor:my-kpt} which says that \Fresse-limits of Ramsey classes always have a definable linear order. 
Recall that 
Ramsey classes only contain rigid structures;
so it is natural to ask whether more generally
there is a definable linear order in every \Fresse-limit of an
amalgamation class of \emph{rigid} structures (without the assumption 
that the class has the Ramsey property). This turns out to be false, and Dugald Macpherson communicated the following example to the author, an example which he credits to Peter Cameron. 

Consider the class $\C \wedge \T$
(in the terminology of Definition~\ref{def:classes}). We claim that this class only
contains rigid structures. To see this, let
$\alpha$ be an automorphism of a structure $A$ from this class. Note that there exists a
partition $V_1 \cup V_2$ of the vertices of $A$ such that for all $x,y \in V_1$ and $u,v \in V_2$ we have $C(x,y,u)$ and $C(u,v,y)$. 
Then either $\alpha(V_1) = V_1$ and
$\alpha(V_2) = V_2$, or $\alpha(V_1) = V_2$ and $\alpha(V_2) = V_1$. The same argument can be applied to the structures induced in $A$ by $V_1$ and by $V_2$. Repeating this argument, we finally obtain 
that $\alpha^2 = \text{id}$. But then $\alpha$ must be the identity, for if $\alpha(x) = y$ and
$x$ and $y$ are distinct, then either $(x,y)$ or $(y,x)$ is an edge in the tournament; but then
$(\alpha(x),\alpha(y))=(y,x)$ is an edge as well, which is impossible in tournaments. 

On the other hand, we claim that there is no order definable in the \Fresse-limit $\Gamma$
of $\C \wedge \T$. To see this, recall that $\Gamma$ has quantifier-elimination 
by Corollary~\ref{prop:qe}, so it can
be checked exhaustively that none of 
the finitely many quantifier-free formulas with
variables $x,y$ defines a linear order in $\Gamma$. As a consequence of Corollary~\ref{cor:my-kpt}, 
the class $\C \wedge \T$ is not Ramsey.
But the structures in this class can be expanded by a linear order
so that the resulting class of expansions has the Ramsey property:
this is a consequence of Corollary~\ref{cor:examples}, since $\vec C \wedge \T$ has the Ramsey property. 


%We remark that the class $\C$ of all $C$-relations on a finite set that additionally carries the relation of a tournament is \emph{not} a Ramsey class. This can be seen directly, or derived from general principles as follows.
%First observe that all structures in $\C$
%are rigid. If the \Fresse-limit $\Gamma$ of $\C$ was Ramsey, it must therefore have an extremely amenable automorphism group (this follows from~\cite{Topo-Dynamics}, albeit it is somewhat hidden there). But this is impossible, since it is not possible to
%define a linear order in $\Gamma$.

\section{Model-Complete Cores}
In our proofs, we make use of the concept of \emph{model-complete cores} of $\omega$-categorical structures. 
A structure $\Gamma$ is called 
a \emph{core} if every endomorphism\footnote{An \emph{endomorphism} of $\Gamma$ is a homomorphism from $\Gamma$ to $\Gamma$.} of $\Gamma$ is
an embedding. A first-order theory $T$ is called \emph{model-complete} if all embeddings between models of $T$
preserve all first-order formulas. An $\omega$-categorical structure $\Gamma$ has a model-complete theory if and only if all self-embeddings $e$
of $\Gamma$ are locally generated by the automorphisms of
$\Gamma$, that is, for every finite tuple $t$ of elements from $\Gamma$
there exists an automorphism $\alpha$ of $\Gamma$ such that $e(t) = \alpha(t)$ (see e.g.~Theorem 3.6.11 in~\cite{Bodirsky-HDR}).
In this case, we say that $\Gamma$ is model-complete. Note that by the above, when $\Gamma$ is homogeneous, 
then $\Gamma$
is model-complete. 

%Hence, an $\omega$-categorical structure
%is a model-complete core if and only if the automorphisms
%of $\Gamma$ are dense in the endomorphisms of $\Gamma$.
The following has been shown in~\cite{Cores-Journal} (%for a more conceptual proof, 
also see~\cite{BodHilsMartin-Journal}).

\begin{thm}\label{thm:cores}
Every $\omega$-categorical structure is homomorphically equivalent\footnote{Two structures $\Gamma$ and $\Delta$ are \emph{homomorphically equivalent} if there is a homomorphism from $\Gamma$ to $\Delta$ and a homomorphism from $\Delta$ to $\Gamma$.} to
a model-complete core $\Delta$, which is unique up to isomorphism, and again $\omega$-categorical or finite.
%For all $n$, orbits of $n$-tuples in $\omega$-categorical model-complete cores $\Gamma$ are primitive positive definable in $\Gamma$. %  DON'T NEED THIS: the
% paper is at most about ep properties, but never about pp 
% properties.
The expansion of $\Delta$ by all existential positive definable relations is homogeneous. 
\end{thm}

The structure $\Delta$ in Theorem~\ref{thm:cores}
will be called \emph{the model-complete core of $\Gamma$}.
We need the following observation.

\begin{prop}\label{prop:mc-core-homogeneous}
The model-complete core $\Delta$ of an $\omega$-categorical homogeneous structure $\Gamma$ is homogeneous.
\end{prop}
\begin{proof}
Let $h$ be a homomorphism from $\Gamma$ to $\Delta$,
and let $i$ be a homomorphism from $\Delta$ to $\Gamma$. 
Suppose that $f$ is an isomorphism between two finite substructures $A,A'$ of $\Delta$.
The restriction of $i$ to $A$ and to $A'$ is an isomorphism as well, since
otherwise the endomorphism $x \mapsto h(i(x))$ of $\Delta$
would not be an embedding, contradicting the assumption that $\Delta$ is a core. 
By homogeneity of $\Gamma$ there exists an automorphism $\alpha$ 
of $\Gamma$ that extends the isomorphism $i \circ f \circ i^{-1}$ between $i(A)$ and $i(A')$. The mapping $e \colon x \mapsto h(\alpha i(x))$ is an endomorphism
of $\Delta$, and therefore an embedding. Since $\Delta$ is a model-complete core, this mapping is locally generated
by the automorphisms of $\Delta$, and in particular there exists an automorphism $\beta$ of $\Delta$ such that 
$\beta(x)=e(x)=f(x)$ for all $x \in A$. This proves homogeneity of $\Delta$.
\end{proof}

We now prove the following.

% Now comes the version for coloring embeddings:
\begin{thm}\label{thm:mc-core-Ramsey}
Let $\Gamma$ be $\omega$-categorical, homogeneous, and Ramsey, 
and let $\Delta$ be the model-complete core of $\Gamma$. 
Then $\Delta$ is also Ramsey. 
\end{thm}
\begin{proof}
First note that $\Delta$ is homogeneous, by Proposition~\ref{prop:mc-core-homogeneous}.
Let $h$ be a homomorphism from $\Gamma$ to $\Delta$,
and let $i$ be a homomorphism from $\Delta$ to $\Gamma$. 
%Write $D$ for the domain of $\Delta$, and $\tau$ for the signature of $\Gamma$ and $\Delta$. 

% removed, no longer need this:
%By Corollary~\ref{cor:my-kpt}, there is a linear order $<$ on the elements of $\Gamma$ 
%with a quantifier-free first-order definition $\phi(x,y)$ in $\Gamma$. We claim that
%$\phi$ defines a linear order on the elements of $\Delta$. 
%If there were three elements $x,y,z$
%such that $\phi(x,y)$, $\phi(y,z)$, and $\phi(z,x)$ hold in $\Delta$, then $\phi(i(x),i(y))$, $\phi(i(y),i(z))$, and $\phi(i(z),i(x))$ hold in $\Gamma$ since the restriction of $i$ to $\{x,y,z\}$ is an embedding. Similarly one can verify that the relation defined by $\phi$ in $\Gamma$ is total
%and antisymmetric. 

%Since $\Delta$ is ordered by a quantifier-free formula, we can prove the statement that 
%$\Delta$ is Ramsey by coloring finite induced substructures rather than embeddings.
Let $P,H$ be two finite substructures of $\Delta$. By Corollary~\ref{cor:my-kpt}, it suffices
 to prove that $\Delta \to (H)^P_2$. 
Note that $i(P)$ induces in $\Gamma$ a copy of $P$ since otherwise the endomorphism $x \mapsto h(i(x))$ of $\Delta$ would not be an embedding. Moreover, for every copy $Q$ of $P$ in $\Gamma$ we have that $h(Q)$ induces a copy of $P$ in $\Delta$. To see this, let $\alpha$ be the automorphism of $\Gamma$ that maps $i(P)$ to $Q$; such an $\alpha$ exists by homogeneity of $\Gamma$. Then $e \colon x \mapsto h(\alpha i(x))$ must be an embedding, and 
$e(P)=h(Q)$ which proves the claim. 

Let $\chi \colon {\Delta \choose P} \rightarrow \{1,2\}$ be arbitrary. 
We define a map $\xi \colon {\Gamma \choose P} \rightarrow \{1,2\}$ by setting
$\xi(q) := \chi(h \circ q)$ for every $q \in  {\Gamma \choose P}$. 
Since $\Gamma$ is Ramsey, there exists
a $g \in {\Gamma \choose H}$ 
% we find a copy $L$ of $H$ in $\Gamma$
such that $\xi$ is constant on ${g[H] \choose P}$. Then $h \circ g \in {\Delta \choose H}$,
and it suffices to show that $\chi$ is constant on ${h \circ g[H] \choose P}$.
By an argument similar as given above, the restriction $h'$ of $h$ to $g[H]$ is an embedding, and the image of $h'$ induces a copy $M$ of $H$ in $\Delta$.
Let $p_1,p_2 \in {h \circ g[H] \choose P}$. 
Then $h^{-1} \circ p_1, h^{-1} \circ p_2  \in {g[H] \choose P}$, and therefore
$\xi(h^{-1} \circ p_1) = \xi(h^{-1} \circ p_1)$,
and $\chi(p_1) = \chi(p_2)$. 
\end{proof}

\section{The Full Product Structure}
\label{sect:full-product}
Let $\Gamma_1$ and $\Gamma_2$ be two structures 
with the same domain $D$ and with disjoint signatures $\sigma$ and $\tau$,
respectively. The \emph{full product}  $\Gamma_1 \boxtimes \Gamma_2$
of $\Gamma_1$ and $\Gamma_2$ is a $(\sigma \cup \tau)$-structure
with domain $D^2$ defined as follows. 
For each $k$-ary $R \in \sigma$, the structure $\Gamma_1 \boxtimes \Gamma_2$ has 
the relation 
$$R^{\Gamma_1 \boxtimes \Gamma_2} = \big \{((a_1,b_1),\dots,(a_k,b_k)) \; | \; (a_1,\dots,a_k) \in R^{\Gamma_1}, b_1,\dots,b_k \in D \big \} \; ,$$ 
and for each $k$-ary $R \in \tau$, it has the relation 
$$R^{\Gamma_1 \boxtimes \Gamma_2} = \big \{((a_1,b_1),\dots,(a_k,b_k)) \; | \; (b_1,\dots,b_k) \in R^{\Gamma_2}, a_1,\dots,a_k \in D \big \} \; .$$
The proof of the following is straightforward
(Proposition~3.3.13 in~\cite{Bodirsky-HDR}).

\begin{prop}\label{prop:product-action}
Suppose that $\Gamma_1$ and $\Gamma_2$ are ordered, with disjoint signatures and the same domain $D$.
%let $G_1,G_2$ be the automorphism group of $\Gamma_1$ and $\Gamma_2$, respectively. 
Then the automorphism group of 
$\Gamma_1 \boxtimes \Gamma_2$ is the product action of the direct product
$\Aut(\Gamma_1) \times \Aut(\Gamma_2)$ on $D^2$.
\end{prop}


Note that we use here that $\Gamma_1$ and $\Gamma_2$ are ordered: for $\Gamma_1 := (D;E_1)$ and $\Gamma_2 := (D;E_2)$ where
both $E_1$ and $E_2$ denote the equality relation $\{(x,x) \; | x \in D\}$, 
the automorphism group of $\Gamma_1 \boxtimes \Gamma_2$ contains all permutations, and this is clearly not the product action of $\Aut(\Gamma_1) \times \Aut(\Gamma_2)$ on $D^2$. 
%(using that both $\Gamma_1$ and $\Gamma_2$ are ordered). 

\begin{prop}\label{prop:product-homogeneous} 
Let $\Gamma_1$ and $\Gamma_2$ be ordered homogeneous structures with the same domain $D$ and disjoint signatures.
Then $\Gamma := \Gamma_1 \boxtimes \Gamma_2$ is homogeneous as well. 
\end{prop}
\begin{proof}
Since $\Gamma_1$ and $\Gamma_2$ are ordered, the relation 
$\{((x,y),(u,v)) \; | \; x=u\}$ and the relation $\{((x,y),(u,v)) \; | \; y=v\}$ are 
%first-order definable in $\Gamma$.
preserved by isomorphisms between finite substructures of $\Gamma$.
Hence, an isomorphism $\mu$ between finite substructures of $\Gamma$ gives rise to isomorphisms
between finite substructures of $\Gamma_1$ and $\Gamma_2$, respectively. 
Those can be extended to automorphisms $\alpha,\beta$ of $\Gamma_1$ and $\Gamma_2$, by homogeneity.
Then $(x,y) \mapsto (\alpha(x),\beta(y))$ is an automorphism of $\Gamma$ which extends $\mu$.
\end{proof}

The following is also known under the name \emph{product Ramsey theorem}.

\begin{prop}\label{prop:product-Ramsey} 
Let $\Gamma_1$ and $\Gamma_2$ be $\omega$-categorical structures
with the same domain $D$ and disjoint signatures.
When $\Aut(\Gamma_1)$ and $\Aut(\Gamma_2)$ are
extremely amenable, then
the automorphism group of $\Gamma := \Gamma_1 \boxtimes \Gamma_2$ is oligomorphic and extremely amenable. 
\end{prop}
\begin{proof}
It is easy to bound the number of orbits of $n$-tuples 
in $\Gamma$ by the number of orbits of $n$-tuples
of $\Gamma_1$ and $\Gamma_2$, so $\Gamma$ can be seen to be $\omega$-categorical. 
When $G_1$ and $G_2$ are extremely amenable groups, then $G_1 \times G_2$ is extremely amenable as well (see Lemma~6.7 in~\cite{Topo-Dynamics}). 
The statement follows since $\Aut(\Gamma_1 \boxtimes \Gamma_2)$ is the product action of $\Aut(\Gamma_1) \times \Aut(\Gamma_2)$ on $D^2$ by Proposition~\ref{prop:product-action}.
%(here we use that $\Gamma_1$ and $\Gamma_2$ are ordered; see~\cite{Bodirsky-HDR} for a more detailed discussion of full products).
\end{proof}

Strong amalgamation will be used via the following lemma.
A relation is called \emph{injective} if it only contains tuples with pairwise distinct entries. 

\begin{lem}\label{lem:homo-strong-amalgamation}
Let $\tau$ be a relational signature, and 
let $\Gamma$ be a homogeneous $\tau$-structure 
such that the class of all finite $\tau$-structures that embed into $\Gamma$ has the strong amalgamation property. Suppose moreover that all relations of
$\Gamma$ are injective. 
Then every finite structure $F$ that homomorphically maps to $\Gamma$
also has an injective homomorphism to $\Gamma$. 
\end{lem}
\begin{proof}
Let $f$ be a homomorphism from $F$ to $\Gamma$ 
such that the range $f(F)$ of $f$ is maximal. 
If $f$ is injective, we are done, otherwise $F$ has elements $u$
and $v$ such that $f(u)=f(v)$. 
Let $A$ be the structure induced by $f(F) \setminus \{f(u)\}$ in $\Gamma$, 
and let $B_1$ and $B_2$ be two disjoint copies of the structure induced 
by $f(F)$ in $\Gamma$. Let $e_1$ be the embedding of $A$ into $B_1$
that maps an element of $f(F) \setminus \{f(u)\}$ to its copy in $B_1$. 
Similarly, there is an embedding $e_2 \colon A \rightarrow B_2$ that maps an element
of $f(F) \setminus \{f(u)\}$ to its copy in $B_2$. By 
strong amalgamation of the age of $\Gamma$, there exist %s a structure $C \in \$ and 
embeddings 
$f_1 \colon B_1 \rightarrow \Gamma$ and $f_2 \colon B_2 \rightarrow \Gamma$
such that $f_1[e_1[A]] = f_2[e_2[A]] = f_1[B_1] \cap f_2[B_2]$.
Then the mapping $f' \colon F \rightarrow \Gamma$ defined by $f'(w) = f_1(e_1(f(w)))$
if $w \neq u$, and defined by $f'(w) = f_2(e_2(f(w)))$ 
if $w \neq v$, is well-defined.
To see that it is a homomorphism, note that 
when $R(x_1,\dots,x_n)$ holds in
$F$, then at most one of the $x_i$ can be mapped to
$f(u)$ since the tuples of $R$ in $\Gamma$ have only pairwise
distinct entries. 
Since $f(x) \neq f(y)$ implies that 
$f'(x) \neq f'(y)$, and since moreover $f'(u) \neq f'(v)$,
%$f_1(e_1(f(u))) \neq f_2(e_2(f(u)))$, 
the function $f'$ also has a larger range than $f$, a contradiction.
\end{proof}


The following is the central lemma connecting the Fraisse-limit of
$\C_1 \wedge \C_2$ with the full product of the Fraisse-limits of $\C_1$ and $\C_2$,
so that we can ultimately use the product Ramsey theorem. 

\begin{lem}\label{lem:link}
Let $\C_1$ and $\C_2$ be strong amalgamation classes of ordered structures, 
with disjoint 
signatures $\sigma$ and $\tau$, such that all relations of $\C_1$ and all
relations of $\C_2$ are injective. 
Let $\Gamma$ be the \Fresse-limit of $\C_1 \wedge \C_2$ with domain $D$,
and suppose that $\Gamma$ is $\omega$-categorical. 
Let $\Gamma_1$ and $\Gamma_2$ be the
$\sigma$- and $\tau$-reduct of $\Gamma$, respectively. 
If $\Gamma_1$ and $\Gamma_2$ are cores, then the following structures are isomorphic.
\begin{enumerate}
\item $\Gamma$ 
\item the substructure induced by $\{(d,d) \; | \; d \in D\}$ in $\Gamma_1 \boxtimes \Gamma_2$
\item the model-complete core of $\Gamma_1 \boxtimes \Gamma_2$
\end{enumerate}
\end{lem}
\begin{proof}
It is straightforward to verify that $d \mapsto (d,d)$ is an isomorphism between $\Gamma$ and the substructure of $\Gamma_1 \boxtimes \Gamma_2$ 
induced by $\{(d,d) \; | \; d \in D\}$. 
%Note that $\Gamma_1$ and $\Gamma_2$ are homogeneous, and hence 
%$\Pi := \Gamma_1 \boxtimes \Gamma_2$ is homogeneous by Proposition~\ref{prop:product-homogeneous}.
%Moreover, the model-complete core $\Delta$ of $\Pi$ is homogeneous 
%by Proposition~\ref{prop:mc-core-homogeneous}.

To find an isomorphism between $\Gamma$ and the model-complete core of $\Gamma_1 \boxtimes \Gamma_2$,
it suffices to show that $\Gamma$ is a model-complete core, 
and that $\Gamma$ is homomorphically equivalent to $\Gamma_1 \boxtimes \Gamma_2$.
We then use that the model-complete core is unique up to isomorphism (Theorem~\ref{thm:cores}), which gives us the desired isomorphism. 
Model-completeness of $\Gamma$ follows from homogeneity.
To show that $\Gamma$ is a core,
let $e$ be an endomorphism of $\Gamma$. 
Then $e$ is an endomorphism of
the $\sigma$-reduct $\Gamma_1$ of $\Gamma$, and an endomorphism 
of the $\tau$-reduct of $\Gamma_2$ of $\Gamma$.
Since both $\Gamma_1$ and $\Gamma_2$ are cores,
$e$ must be an embedding of $\Gamma$ into
$\Gamma$, which is what we wanted to show.

We finally show that $\Gamma_1 \boxtimes \Gamma_2$ and $\Gamma$ are homomorphically equivalent. For one direction, recall that $\Gamma$ maps to $\Gamma_1 \boxtimes \Gamma_2$ via the mapping $d \mapsto (d,d)$. 
For the other direction, it suffices to show 
that every finite substructure $F$ of $\Gamma_1 \boxtimes \Gamma_2$ homomorphically maps to $\Gamma$, by a standard compactness argument and $\omega$-categoricity of $\Gamma$ (see e.g.~Lemma 3.1.5 in~\cite{Bodirsky-HDR}). 
By Lemma~\ref{lem:homo-strong-amalgamation}, there is 
an \emph{injective} homomorphism $h_1$ from the $\sigma$-reduct of $F$ to $\Gamma_1$ (recall here that the order of $\Gamma_1$ is by assumption strict). 
Similarly, there is an injective homomorphism $h_2$ from the $\tau$-reduct of $F$ into $\Gamma_2$. Let $U$ be the $(\sigma \cup \tau)$-structure with the same domain as $F$, and with
 relations defined as follows: for each $R \in \sigma$ of arity $k$,
 a $k$-tuple $t$ of elements of $U$ is in $R^U$ if and only if $h_1(t)$ is in $R^{\Gamma_1}$. Similarly we define $R^U$ for relations $R \in \tau$,
 with $h_2$ taking the role of $h_1$ and $\Gamma_2$ taking the role of $\Gamma_1$.
Clearly, $h_1$ is an embedding of the $\sigma$-reduct $U_1$ of $U$
 into $\Gamma_1$, and $h_2$ is an embedding of the 
 $\tau$-reduct $U_2$ of $U$ into $\Gamma_2$. Therefore, $U_1 \in \C_1$ and $U_2 \in \C_2$.  By definition of $\C := \C_1 \wedge \C_2$, we have that
$U \in \C$, and there is an embedding $e$ of $U$
into $\Gamma$. Then $e$ is the desired homomorphism from $F$ to $\Gamma$. 
\end{proof}

% If algebraic closure in Gamma_i is not trivial, first blow up each vertex of Gamma_i
% by infinitely many copies. This should still be Ramsey,
% when convexly ordered. 

%To use Lemma~\ref{lem:link}, we need one more observation.
%\begin{lem}
%Let $\Gamma$ be a homogeneous $\omega$-categorical structure with domain $D$
%Then there exists a homogeneous $\omega$-categorical core 
%structure $\Gamma^*$ with domain $D$ and 
%$\Aut(\Gamma) = \Aut(\Gamma^*)$ such
%that all relations in $\Gamma^*$ only contain tuples with pairwise distinct
%entries. 
%\end{lem}
%\begin{proof}
%Let $\Gamma^*$ be the structure with domain $D$ 
%that contains for all $n$ all the orbits of $n$-tuples of distinct elements 
%as $n$-ary relations. 
%Clearly, this structure has the same automorphism
%group as $\Gamma$, and homogeneous and $\omega$-categorical. 
%To see that it is a core, observe that 
%all relations that have a first-order definition in $\Gamma$
%and only contain tuples with pairwise distinct entries. 
%\end{proof}
%We can finally prove Theorem~\ref{thm:main}. 

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $\Gamma$ be the \Fresse-limit of $\C_1 \wedge \C_2$,
and let $\Gamma_1$ and $\Gamma_2$ be the $\sigma$- and $\tau$-reduct of $\Gamma$, respectively. It can be shown by a straightforward back-and-forth argument that $\Gamma_1$ and $\Gamma_2$ are also homogeneous, and hence isomorphic to the \Fresse-limit of $\C_1$ and $\C_1$, respectively. Therefore, $\Gamma_1$ and
$\Gamma_2$ are 
$\omega$-categorical by assumption.
%and therefore they are the \Fresse-limit of $\C_1$
%and $\C_2$, respectively. %, and hence
Moreover, since $\C_1$ and $\C_2$ have the Ramsey property,
by Corollary~\ref{cor:my-kpt} there are linear orders $<^{\Gamma_1}$ and
$<^{\Gamma_2}$ with quantifier-free 
first-order definitions $\phi_1$ and $\phi_2$ in $\Gamma_1$ and $\Gamma_2$,
respectively. 

Let $\Gamma_1^*$ be the structure with the same domain as $\Gamma_1$
whose relations are exactly the injective relations that are first-order definable in
$\Gamma_1$. 
Note that this includes in particular the linear order $<^{\Gamma_1}$,
and so $\Gamma_1^*$ is ordered. 
Since $\Gamma^*_1$ contains an $n$-ary relation for each orbit of $n$-tuples of distinct elements from $\Gamma$, we have that
$\Gamma^*_1$ is homogeneous and a core, and has the same (oligomorphic) automorphism group as $\Gamma_1$.
Moreover, observe that the algebraic closure 
operator only depends
on the automorphism group of $\Gamma_1$, and it follows by Proposition~\ref{prop:acl} that that also the age of $\Gamma_1^*$ has strong amalgamation.
We write $\sigma^*$ for the signature of $\Gamma_1^*$.

Analogously we define the structure $\Gamma_2^*$ from $\Gamma_2$;
we choose the signature $\tau^*$ for $\Gamma_2^*$ such that $\tau^*$ is disjoint 
from $\sigma^*$. Finally, let $\Gamma^*$ be the $(\tau^* \cup \sigma^*)$-structure
whose domain equals the domain of $\Gamma_1$ and $\Gamma_2$
and which is given uniquely by the requirement
that it is both an expansion of $\Gamma_1^*$ and an expansion of $\Gamma_2^*$. 
Then $\Aut(\Gamma^*) = \Aut(\Gamma)$, because an orbit of an $n$-tuple $t$
in $\Gamma$ is uniquely given by the orbit of $t$ in $\Gamma_1^*$ and
the orbit of $t$ in $\Gamma_2^*$. 
Since $\Gamma^*$ contains relation symbols for tuples of pairwise distinct elements for the orbits of $n$-tuples in $\Gamma_1$ and in $\Gamma_2$, it is for the same reason homogeneous and
therefore the \Fresse-limit of its age. 
Theorem~\ref{thm:ryll} implies that
the automorphism group of $\Gamma^*$ is oligomorphic because $\Gamma$ is $\omega$-categorical, and that
$\Gamma^*$ is $\omega$-categorical. 

% TODO: why?

The groups $\Aut(\Gamma^*_1) = \Aut(\Gamma_1)$ and $\Aut(\Gamma^*_2)=\Aut(\Gamma_2)$ are 
oligomorphic, and extremely amenable by Corollary~\ref{cor:my-kpt}. 
By Proposition~\ref{prop:product-homogeneous}, $\Gamma^*_1 \boxtimes \Gamma^*_2$ is homogeneous,
and by Proposition~\ref{prop:product-Ramsey}, $\Aut(\Gamma^*_1 \boxtimes \Gamma^*_2)$ is extremely amenable. 
Then Theorem~\ref{thm:mc-core-Ramsey} (again in combination with Corollary~\ref{cor:my-kpt}) shows that the model-complete core of $\Gamma^*_1 \boxtimes \Gamma^*_2$ has an extremely amenable automorphism group $G$.
By Lemma~\ref{lem:link}, the model-complete core of $\Gamma^*_1 \boxtimes \Gamma^*_2$ is isomorphic
to $\Gamma^*$, and hence $\Aut(\Gamma^*) = \Aut(\Gamma)$ is extremely amenable. 
We conclude by Corollary~\ref{cor:my-kpt} that $\C_1 \wedge \C_2$ has the Ramsey property.
\end{proof}

\section{Forgetting one order}
\label{sect:forget-order}
We finally prove Proposition~\ref{prop:forget-order}: let $\C_1$ and $\LO \wedge \C_2$ be Ramsey classes 
with strong amalgamation and $\omega$-categorical \Fresse-limits,
and suppose that $\C_1$, $\C_2$, and $\LO$ have pairwise disjoint relational signatures.
We have to show that $\C_1 \wedge \C_2$ has the Ramsey property. 
\begin{proof}[Proof of Proposition~\ref{prop:forget-order}]
We use the fact that $\C_3 := \C_1 \wedge (\LO \wedge \C_2)$ has the Ramsey property by Theorem~\ref{thm:main}. Let $\Gamma$ be the \Fresse-limit of $\C_1$.
By Corollary~\ref{cor:my-kpt}, there is a linear order $<$ on the elements of $\Gamma$ that has a quantifier-free first-order definition $\phi(x,y)$ in $\Gamma$. 

To show that $\C_1 \wedge \C_2$ has the Ramsey property, let $A$ and $B$ 
be from $\C_1 \wedge \C_2$. Let $A',B'$ be the expansion of $A,B$ by the relation $<$
defined by $\phi$ over $A$ and $B$, respectively. Note that $A',B' \in \C_3$.
Since $\C_3$ has the Ramsey property, there exists a
$C' \in \C_3$ such that $C' \to(B')^{A'}_r$. 
Let $C$ be the reduct of $C'$ where we drop the relation $<$. 
We claim that $C \to(B)^A_r$. Let $\chi \colon \binom{C}{A} \rightarrow \{1,\dots,r\}$ be arbitrary. 
We define a coloring $\chi' \colon \binom{C'}{A'} \rightarrow \{1,\dots,r\}$ as follows. 
Let $e$ be an arbitrary embedding of $A'$ into $C'$. 
Since $A$ is a reduct of $A'$, and $C$ is a reduct of $C'$ with the same signature, 
the mapping $e$ is also an embedding of $A$ into $C$. Therefore, $e$ is in the range 
of $\chi$, and we can define $\chi'(e) := \chi(e)$. 
Since $C' \to(B')^{A'}_r$, there exists an $f \in \binom{C'}{B'}$ such that
$\chi'$ is constant $c$ on $\binom{f[B']}{A'}$. By the same argument as above,
$f$ is also an embedding of $B$ into $C$. 
We claim that $\chi$ is constant on $\binom{f[B]}{A}$. 
Let $e$ be an arbitrary embedding of $A$ into $f[B]$. 
Recall that $A'$ and $B'$ are the expansion of $A$ and $B$ by the relation $<$ defined
by $\phi$. Since embeddings preserve quantifier-free formulas, $e$ preserves in particular $\phi$. Therefore, the mapping $e$ is an embedding of $A'$ into the substructure $f[B']$
of $C'$. In particular, $e$ is in the range of $\chi'$, and $\chi'(e) = c$. 
It follows that $\chi(e) = c$, which concludes the proof that $\chi$ is constant on $\binom{f[B]}{A}$. 
\end{proof}


\paragraph{Acknowledgements}
Many thanks to Fran\c{c}ois Bossi\`ere, Jan Foniok, Andr\'as Pongr\'acz, Miodrag Soki\'c, and an anonymous referee for their valuable comments on earlier versions.

\begin{thebibliography}{10}

\bibitem{Cores-Journal}
M.~Bodirsky.
\newblock Cores of countably categorical structures.
\newblock {\em Logical Methods in Computer Science}, 3(1):1--16, 2007.

\bibitem{Bodirsky-HDR}
M.~Bodirsky.
\newblock Complexity classification in infinite-domain constraint satisfaction.
\newblock M\'emoire d'habilitation \`a diriger des recherches, Universit\'{e}
  Diderot -- Paris 7, 2012. \arxiv{1201.0856}

\bibitem{BodHilsMartin-Journal}
M.~Bodirsky, M.~Hils, and B.~Martin.
\newblock On the scope of the universal-algebraic approach to constraint
  satisfaction.
\newblock {\em Logical Methods in Computer Science (LMCS)}, 8(3:13), 2012.
\newblock An extended abstract that announced some of the results appeared in
  the proceedings of Logic in Computer Science (LICS'10).

\bibitem{BodirskyPiguet}
M.~Bodirsky and D.~Piguet.
\newblock Finite trees are {R}amsey with respect to topological embeddings.
\newblock Preprint, 2010. \arxiv{1002.1557}.

\bibitem{BP-reductsRamsey}
M.~Bodirsky and M.~Pinsker.
\newblock Reducts of {R}amsey structures.
\newblock {\em AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods
  in Finite Combinatorics)}, pages 489--519, 2011.

\bibitem{BoettcherFoniok}
J.~B\"ottcher and J.~Foniok.
\newblock Ramsey properties of permutations.
\newblock {\em Electronic Journal of Combinatorics}, 20(1), 2013.

\bibitem{Oligo}
P.~J. Cameron.
\newblock {\em Oligomorphic permutation groups}.
\newblock Cambridge University Press, Cambridge, 1990.

\bibitem{Cherlin}
G.~Cherlin.
\newblock The classification of countable homogeneous directed graphs and
  countable homogeneous n-tournaments.
\newblock {\em AMS Memoir}, 131(621), January 1998.

\bibitem{Hodges}
W.~Hodges.
\newblock {\em A shorter model theory}.
\newblock Cambridge University Press, Cambridge, 1997.

\bibitem{Topo-Dynamics}
A.~Kechris, V.~Pestov, and S.~Todorcevic.
\newblock Fraiss\'e limits, {R}amsey theory, and topological dynamics of
  automorphism groups.
\newblock {\em Geometric and Functional Analysis}, 15(1):106--189, 2005.

\bibitem{Mil79}
K.~R. Milliken.
\newblock A {R}amsey theorem for trees.
\newblock {\em Journal of Combinatorial Theory, Series A}, 26(3):215 -- 237,
  1979.

\bibitem{RamseyClasses}
J.~Ne\v{s}et\v{r}il.
\newblock Ramsey classes and homogeneous structures.
\newblock {\em Combinatorics, Probability \& Computing}, 14(1-2):171--189,
  2005.

\bibitem{NesetrilRoedlPartite}
J.~Ne\v{s}et\v{r}il and V.~R\"odl.
\newblock The partite construction and {R}amsey set systems.
\newblock {\em Discrete Mathematics}, 75(1-3):327--334, 1989.

\bibitem{Sokic}
M.~Soki\'{c}.
\newblock {\em Ramsey property of posets and related structures}.
\newblock PhD thesis, University of Toronto, 2010.

\bibitem{SokicIsrael}
M.~Soki\'{c}.
\newblock Ramsey property, ultrametric spaces, finite posets, and universal
  minimal flows.
\newblock {\em Israel Journal of Mathematics}, 194(2):609--640, 2013.

\end{thebibliography}

\end{document}

