\documentstyle[a4,12pt]{article}
\def \card#1{{\left| #1\right|}}     
\def\Min{\mathop{\rm min}\nolimits}
\def\sup{\mathop{\rm sup}\nolimits}
\def\cof{\mathop{\rm cof}\nolimits}
\def\coi{\mathop{\rm coi}\nolimits}
\def\Car{\mathop{\rm char}\nolimits}
\def\Sym{\mathop{\rm Sym}\nolimits}
\def\Max{\mathop{\rm max}\nolimits}
\def\At{\mathop{\rm A}\nolimits}
\def\Aut{\mathop{\rm Aut}\nolimits}
\def\id{\mathop{\rm id}\nolimits}
\begin{document}
\title{Set-homogeneous graphs and embeddings of total orders}
\author{Manfred Droste,\\ Institut f\"ur Algebra,\\ 
Technische Universit\"at Dresden,\\ 01062 Dresden,\\ 
Germany 
\and Michele Giraudet,\\ 
32 rue de la
R\/eunion,\\ 
75020 Paris,\\ 
France 
\and Dugald Macpherson,\\
Department of Pure Mathematics,\\ 
University of Leeds,\\ Leeds LS2 9JT,\\
England
}
\date{}
\maketitle
\newtheorem{defi}{Definition}[section]
\newtheorem{theorem}[defi]{Theorem}
\newtheorem{definition}[defi]{Definition}
\newtheorem{lemma}[defi]{Lemma}
\newtheorem{proposition}[defi]{Proposition}
\newtheorem{conjecture}[defi]{Conjecture}
\newtheorem{corollary}[defi]{Corollary}
\newtheorem{problem}[defi]{Problem}
\newtheorem{remark}[defi]{Remark}
\newtheorem{example}[defi]{Example}
\newtheorem{question}[defi]{Question}


\section{Introduction}
This paper is in part a sequel to \cite{dgms} and \cite{dgm}. 
We construct a certain uncountable graph,
thereby answering a question on automorphism groups 
of infinite graphs which was
raised in \cite{dgms}. The method of construction is order-theoretic, 
and uses
ideas from \cite{dgm}. We first build a certain uncountable totally ordered
set, then obtain from it a cyclic ordering, and finally impose a graph 
structure on this
cyclic ordering.

Recall from \cite{dgms}
(or initially Fra\"iss\/e \cite{f}) that a relational structure ${\cal M}$
is {\em $k$-set-homogeneous}  ($k$ a positive integer)
if, whenever $U$ and $V$ are isomorphic substructures of ${\cal M}$ of
size $k$, there is an automorphism of ${\cal M}$ taking $U$ to $V$.
We say that ${\cal M}$ is {\em $\leq$$k$-set-homogeneous} if it
is $l$-set-homogeneous for all $l\leq k$.
Also,
${\cal M}$ is said to be {\em $k$-homogeneous} if {\em every} isomorphism
between $k$-element substructures of ${\cal M}$ extends
to an automorphism of ${\cal M}$, and we also talk of
{\em $\leq$$k$-homogeneous} structures. These notions were examined in
\cite{dgms}, mainly for graphs and digraphs, and mainly in the countable case.
Two particular countable graphs were defined in \cite{dgms},
$R(3)$ and $T$. The graph $R(3)$ is defined later in this introduction,
and $T$ is the comparability graph of a certain semilinear order.
The central theorem of \cite{dgms}, Theorem 1.1, 
was that any infinite $\leq$8-set-homogeneous  but not
$\leq$3-homogeneous graph is elementarily equivalent to
$R(3)$ or its complement. It was also shown (Theorem 4.1) that any countable 
$\leq$3-set-homogeneous graph
which is not  $\leq$2-homogeneous is isomorphic to $T$ or its complement,
and that, without the countability assumption, any such graph is elementarily
equivalent to one of $R(3)$, $T$ or their complements. 
Here, we show that in this last result, the countability assumption 
cannot be removed. Our main theorem is the following.

\begin{theorem}\label{main}
For every uncountable cardinal $\kappa$, there is a graph 
of cardinality $\kappa$ which is
$\leq$3-set-homogeneous but
not 2-homogeneous 
and is elementarily equivalent
to $R(3)$.
\end{theorem}

These results do not conflict with the
L\"owenheim-Skolem Theorems, essentially because, in the natural 2-sorted
language for the automorphism group of a graph, the first order
theory cannot in general say that the group is the {\em full} automorphism
group of the graph. 

The graph $R(3)$ is determined up to isomorphism by the 
following construction rule. 
For the
vertices of $R(3)$, distribute $\aleph_0$ points densely around the 
unit circle, such that no two points make an angle of $2\pi/3$ at 
the centre.
Two vertices are adjacent in $R(3)$ if the angle they carry 
at the centre is less
than $2\pi/3$. The paper \cite{dgms} is mostly about $R(3)$, and
characterisations of it by its symmetry properties.

Theorem~\ref{main} is a straightforward corollary of a more technical 
result
on automorphisms of totally ordered sets, which will we hope have 
independent interest.
To state the latter, we need some definitions. Let $(C,\leq)$ and
$(S,\leq)$ be chains (that is, totally ordered sets). 
We denote by $\overline{S}$ the Dedekind completion of $S$.
An embedding
$\varphi:(C,\leq)\longrightarrow (S,\leq)$ is said to be {\em complete} 
if it preserves
all suprema and infima of subsets of $C$ which happen to exist in
$(C,\leq)$. If $\kappa$ is a cardinal, a subset $T$ of $S$ is called
{\em $\kappa$-dense in $S$} if $\card{T\cap [a,b]}\geq \kappa$ for
any $a,b \in S$ with $a<b$; we say that $T$ is {\em dense in $S$} if it
is $\aleph_0$-dense in $S$. If $x \in \overline{S}$ has no immediate
predecessor, we define the {\em cofinality} of $x$ to be
$$\cof{x}:=\Min\{\card{A}:A\subseteq \overline{S},x \not\in A,x=\sup(A)\}.$$
We adopt the convention that if $x$ has an immediate predecessor then
$\cof(x)=\aleph_0$. We define the {\em coinitiality} $\coi(x)$ of
$x$ dually. If $\cof(x)=\coi(x)$ then this cardinal is called the {\em
coterminality} of $x$, denoted $\cot{x}$. The ordered 
pair $(\cof(x),\coi(x))$ 
is called the {\em character} of $x$, and we let $\Car(S)$ denote the
set of all characters of elements of $S$. The chain $(S,\leq)$
(or $(\overline{S},\leq))$ is said to have {\em countable coterminality}
if it has no greatest or smallest element and contains a countable subset
which is unbounded above and below in $S$. 
A {\em non-trivial closed interval} of $(S,\leq)$ is a set of the form
$[a,b]:=\{s \in S:a\leq s\leq b\}$, where $a,b \in S$ with $a<b$.
Finally, for any totally ordered set $(S,\leq)$ we denote
by $\At(S)$ the group of all order-automorphisms of
$(S,\leq)$, and for any set $I$
we let
$\Sym(I)$ denote the full symmetric group on $I$.

Theorem~\ref{main} will be deduced from the following theorem.

\begin{theorem}\label{main2}
Let $(C,\leq)$ be a chain in which no non-trivial closed interval is
dense in itself. Let $I$ be a non-empty set, let $G\leq \Sym(I)$, and 
let $\kappa$
be an infinite cardinal with $\kappa\geq \Max\{\card{C},\card{I},\card{G}\}$.
Then there is a chain $(S,\leq)$ of cardinality $\kappa$, a
partition $S=\bigcup(S_i:i \in I)$ and a complete
embedding $\varphi:(\overline{C},\leq)\longrightarrow (\overline{S},\leq)$ with the
following properties:
\begin{enumerate}
\begin{enumerate}
\item $\varphi(\overline{C})\subseteq \overline{S}\setminus S$;
\item each $S_i$ ($i \in I$) is $\kappa$-dense in $(S,\leq)$;
\item whenever there are $j,k \in I$, $g \in G$ and $a \in S_j$,
$b\in S_k$, $c \in S_{j^g}$, $d \in S_{k^g}$ with $a<b$ and $c<d$,
there is $h \in \At(S)$ such that $a^h=c$, $b^h=d$, and
$S_i^h=S_{i^g}$ for each $i \in I$;
\item $\Car(\overline{S})=\Car(\overline{C})\cup\{(\mu,\aleph_0):
\mu\leq \kappa,\mu
\mbox{~regular}\}$;
\item whenever $a,b \in C$ with $a<b$ and there is no $c \in C$ 
such that
$a<c<b$, the interval $(\varphi(a),\varphi(b))$ in $S$ has countable coterminality;
\item each element $s$ in $S$ has countable coterminality.
\end{enumerate}
\end{enumerate}
\end{theorem}

Our proof of Theorem~\ref{main2} rests on the proof of Droste \cite{d1}
[Theorem 1 and Corollary 2.5], which in turn closely follows the proof of 
Theorem 
2.1 of Droste and Shelah \cite{ds}. We can obtain the cited results in 
\cite{d1} from Theorem~\ref{main2} by choosing $I$ to have size 1. In
our application of Theorem~\ref{main2}, that is, for Theorem~\ref{main},
we will only need the case $C=\emptyset$. However, the proof of 
Theorem~\ref{main2} for the case $C=\emptyset$ would be only slightly easier. 

Theorem~\ref{main2} is proved in Section 2, and Theorem~\ref{main} in 
Section 3. In the proof of Theorem~\ref{main}, we use ideas from \cite{dgm}
to obtain a cyclically ordered set (built from the totally ordered
set given in Theorem~\ref{main2}) which has strong homogeneity
properties with respect to a partition into $\card{I}$ parts, and
which is not isomorphic to its reverse cyclic ordering. These
conditions
will follow from parts (c) and (d) of Theorem~\ref{main2}.
We then build a graph on the cyclically ordered set
much as in the construction of $R(3)$ above.

We remark that these results on 3-set-homogeneous graphs have an analogue for
$\leq$4-homogeneous posets. It was shown in \cite{dm} that every countable
$\leq$4-homogeneous poset is homogeneous. However, by results of
Droste and Mekler, 
for any $k \in {\bf N}$ with $k\geq 4$, there is 
a $\leq$k-homogeneous poset of
cardinality $\aleph_1$ which is not $(k+1)$-homogeneous.
See \cite{m} (Theorem 17) for more detail on this.

\section{Proof of Theorem~\ref{main2}}

For the convenience of the reader, we sketch the main ideas from \cite{ds},
including the necessary changes. 

The building blocks of our chain 
$(S,\leq)$ are the
orderings defined in the following definition, which is similar to
Definition 4.1 of \cite{ds}.

\begin{definition}\label{good}
Let $\kappa$ be an infinite cardinal and $I$ a non-empty set. A chain
$(S,\leq)$ is called a {\em good $I$-coloured $\kappa$-set} if there is
a partition $S=\bigcup(S_i:i \in I)$ with the following properties:
\begin{description}
\item[(i)] $\card{S}=\kappa$;
\item[(ii)] $S$ has no greatest or smallest element;
\item[(iii)] each $s \in S$ has countable coterminality;
\item[(iv)] the sets $S_i$ ($i \in I$) and also the set
$\{x \in \overline{S}\setminus S:\cot(x)=\aleph_0\}$ are $\kappa$-dense in $S$.
\end{description}
\end{definition}

In the setting of Definition~\ref{good} we refer to the sets $S_i$ 
(and the elements of $I$) as 
{\em colours}. We now give an existence result for good $I$-coloured
$\kappa$-sets for arbitrary $\kappa$.  


\begin{lemma}\label{exist}
Let $\kappa$ be an infinite cardinal and $I$ a non-empty set with
$\card{I}\leq \kappa$. Then there is a good $I$-coloured $\kappa$-set
of countable coterminality.
\end{lemma}

{\em Proof.} It suffices to prove the result in the case 
when $\card{I}=\kappa$, for the result follows in general by
amalgamating colours. So assume $\card{I}=\kappa$. Let
$L$ be the set of all $\omega$-sequences $(\lambda_j:j<\omega)$
of ordinals $\lambda_j$ with $0\leq \lambda_j<\kappa$ which are
eventually equal to 1, that is, for which there is $n \in \omega$
such that $\lambda_j=1$ for all $j>n$. Order $L$ lexicographically. 
For any $\nu$ with $2\leq \nu<\kappa$ let $L_{\nu}$ comprise all sequences
$(\lambda_j:j<\omega)$ in $L$ such that for some $n<\omega$ we
have $\lambda_n=\nu$ and $\lambda_j=1$ for all $j>n$. Put
$$L_1:=L\setminus\bigcup\{L_{\nu}:2\leq \nu<\kappa\}.$$
Now choose $a,b \in L$ with $a<b$ and put $S:=(a,b)_L$ and
$S_{\nu}:= S \cap L_{\nu}$ (for $1\leq \nu<\kappa$) to obtain the
required chain. For more detail, see the proof of Lemma 4.2 of \cite{ds}.

\bigskip

The proof of Theorem~\ref{main2} uses two basic construction techniques from
\cite{ds}. We now describe these, omitting some details.
If $(S,\leq)$ is a chain, $T\subseteq \overline{S}$, and $a,b \in \overline{S}$ 
with $a<b$, then we put
$[a,b]_T:=\{t \in T: a\leq t\leq b\}$, and we define $(a,b)_T$ similarly.
If $A,B \subseteq S$, we write $A<B$ if $a<b$ for all $a \in A$ and $b \in B$.
Similarly, $A<x$ abbreviates $A<\{x\}$. 

\bigskip

{\em Basic Construction A (defining a colour-permuting isomorphism).}
Let $(S,\leq)$ be a good $I$-coloured $\kappa$-set with
colours $S_i$ for $i \in I$. Let $g\in \Sym(I)$, $j,k \in I$, and 
$a \in S_j$, $b \in S_k$, $c \in S_{j^g}$, $d \in S_{k^g}$ with
$a<b$ and $c<d$. We will enlarge $S$ to a good $I$-coloured $\kappa$-set
$(S^*,\leq)$ with colours $S_i^* \supseteq S_i$ (for each $i \in I$)
such that there is an isomorphism
$$h:[a,b]_{S^*}\longrightarrow [c,d]_{S^*}$$
with 
$$([a,b] \cap {S_i^*})^h=[c,d] \cap {S_{i^g}^*}$$
for each $i \in I$. This will be obtained by splitting both $(a,b)_S$
and $(c,d)_S$ into countably many subintervals, inserting copies of these
subintervals into $(c,d)_S$ and $(a,b)_S$ respectively, to obtain $S^*$,
and defining the isomorphism $h$ correspondingly.

First, we choose countable sets 
$$A=\{a_n:n \in {\bf Z}\}\subseteq [a,b]_{\overline{S}\setminus S}, \mbox{~and}$$
$$B=\{b_n:n \in {\bf Z}\}\subseteq [c,d]_{\overline{S}\setminus S}$$
such that $\cot(x)=\aleph_0$ for each $x \in A\cup B$, $a_n<a_{n+1}$ and
$b_n<b_{n+1}$ for each $n \in {\bf Z}$, and $a=\inf(A)$, $b=\sup(A)$,
$c=\inf(B)$, $d=\sup(B)$. For each $n \in {\bf Z}$ let $A_n'$ be an
isomorphic copy of $A_n:=(a_n,a_{n+1})_S$, let
$B_n'$ be a copy of $B_n:=(b_n,b_{n+1})_S$, and let $\pi_{An}$
(respectively $\pi_{Bn}$) be an isomorphism from $A_n$ onto $A_n'$
(respectively $B_n$ onto $B_n'$). Put
$$S^*:=S \cup\bigcup_{n \in {\bf Z}}(A_n'\cup B_n').$$
We define a linear order $\leq$ on $S^*$ in the natural way, 
so that it extends the orders of $S$ and of each of $A_n'$, $B_n'$,
and $B_{n-1}<A_n'<B_n$ and $A_n<B_n'<A_{n+1}$ for each $n \in {\bf Z}$. We
define the colours of $S^*$ by putting
$$S_i^*:=S_i\cup \bigcup_{n \in {\bf Z}}((A_n \cap S_{i^{g^{-1}}})\pi_{An}
\cup(B_n\cap S_{i^g})\pi_{Bn})$$
for each $i \in I$.
Finally, we define the required isomorphism $h$ as in Fig. 1
below, by putting
$a^h=c$, $b^h=d$, $h\mid_{A_n}=\pi_{An}$, and $h\mid_{B_n'}=
\pi_{Bn}^{-1}$.

\unitlength0.7ex
\begin{center}
\begin{picture}(100,60)
\put(47,9.2){$>$} \put(52,44.2){$<$}
\put(4.6,29.1){$[$} \put(94.5,29.1){$]$} 
\put(54.6,29.1){$[$} \put(44.5,29.1){$]$} 
\put(0,30){\line(1,0){100}}
\multiput(5,30)(10,0){10}{\circle*{0.7}}
\put(4,26){$a$} \put(13,26){$a_n$}  \put(23,26){$a_{n+1}$} \put(33,26){$a_{n+2}$} \put(43.5,25.8){$b$} \put(54,26){$c$} \put(63,26){$b_{n-1}$}  \put(73,26){$b_n$} \put(83,26){$b_{n+1}$} \put(94,25.8){$d$}
\put(16,25){$\underbrace{\hspace{5ex}}_{A_n}$}
\put(26,25){$\underbrace{\hspace{5ex}}_{A_{n+1}}$}
\put(66,31){$\overbrace{\hspace{5ex}}^{B_{n-1}}$}
\put(76,31){$\overbrace{\hspace{5ex}}^{B_n}$}
\put(20,18){\line(0,-1){8}} \put(20,10){\line(1,0){55}} \put(75,10){\vector(0,1){15}} 
\put(47,13){$\pi_{A_n}$} \put(77,15){Insert $A_n'$ here}
\put(80,37){\line(0,1){8}} \put(80,45){\line(-1,0){55}}
\put(25,45){\vector(0,-1){13}}
\put(52,40){$\pi_{B_n}$} \put(3,39){Insert $B_n'$ here}
\put(90,48){Fig. 1}
\end{picture}
\end{center}

{\em Basic Construction B (extension of a colour permuting isomorphism).}
Let $(S,\leq)$, $(T,\leq)$ be good $I$-coloured $\kappa$-sets with colours
$S_i$ and $T_i$ (for $i \in I$), such that $S_i \subseteq T_i$ for each
$i \in I$. Assume that 
$$
\begin{array}{c}
\mbox{~whenever~} t \in T\setminus S, \mbox{~the set}\\
D:=\{x \in T:\forall{s\in S}(s<t\leftrightarrow s<x)\}\\
\mbox{has countable coterminality and no greatest or smallest elements.}
\end{array}
\eqno(*)
$$
Now let $j,k \in I$, $g \in \Sym(I)$, let $a\in S_j$, $b \in S_k$,
$c \in S_{j^g}$, $d \in S_{k^g}$ with $a<b$ and $c<d$, and
let
$h:[a,b]_S\longrightarrow [c,d]_S$ be an isomorphism such that
$$([a,b]_{S_i})^h=[c,d]_{S_{i^g}}$$
for each $i \in I$. We want to enlarge $(T,\leq)$ to a good $I$-coloured
$\kappa$-set 
$$(U,\leq)\supseteq (T,\leq)$$ with colours $U_i\supseteq T_i$
such that $h$ extends to an isomorphism $\tilde{h}:[a,b]_U\longrightarrow
[c,d]_U$ satisfying
$$([a,b]_{U_i})^{\tilde{h}}=[c,d]_{U_{i^g}}$$
for each $i \in I$. This is achieved by inserting, for certain
decompositions $[a,b]_S=A\cup B$ with $A<B$, points into $T$ between the 
sets $A$ and $B$ and also between $A^h$ and $B^h$. 

Consider a decomposition $[a,b]_S=A\cup B$ with $A<B$. We distinguish
between four cases.

\medskip

{\em Case 1.} There is no $x \in [a,b]_T$ with $A<x<B$ and no
$y \in [c,d]_T$ with $A^h<y<B^h$.

In this case, no point is inserted, either between $A$ and $B$ or between
$A^h$ and $B^h$.

\medskip

{\em Case 2.} There is $x \in [a,b]_T$ with $A<x<B$ but no
$y \in [c,d]_T$ with $A^h<y<B^h$.

In this case, let $X:=\{x\in T: A<x<B\}$, let $(Y,\leq)$ be a copy
of $(X,\leq)$, and let $\pi:X\longrightarrow Y$ be an isomorphism.
We insert $Y$ into $T$ between $A^h$ and $B^h$, colouring $y \in Y$
with colour $i^g$ if $y^{\pi^{-1}}$ has colour $i$ (that is, lies in
$T_i$).  Let $\tilde{h}\mid_{X}:= \pi$.

\medskip

{\em Case 3.} There is $y \in [c,d]_T$ with $A^h<y<B^h$ but no
$x \in [a,b]_T$ with $A<x<B$.

This case is treated similarly to Case 2.

\medskip

{\em Case 4.} There are $x \in [a,b]_T$, $y \in [c,d]_T$ with
$A<x<B$ and $A^h<y<B^h$.

In this case, let $X:=\{x \in T:A<x<B\}$ and $Y:=\{y \in T: A^h<y<B^h\}$
and define $a':=\inf_{\overline{T}}X$, $b':=\sup_{\overline{T}}X$,
$c':=\inf_{\overline{T}}Y$, $d':=\sup_{\overline{T}}Y$. By $(*)$, 
$X$ and $Y$
contain no greatest or smallest elements and have countable coterminality.
It follows that we can deal with the intervals $[a',b']_T$
and $[c',d']_T$ precisely as we dealt with the intervals $[a,b]_S$
and $[c,d]_S$ in Basic Construction A, the only difference being that 
the endpoints $a',b',c',d'$ all belong to $\overline{T}$. Observe that here
 $a' \in S$ if and only if $a'=\Max(A)$ if and only if $c'=\Max(A^h)$
 if and only if $c' \in S$, and similarly that
 $b' \in S$ if and only if $d' \in S$. 
 
 \medskip

If these constructions are carried out for each decomposition 
$[a,b]_S=A\cup B$ where $A<B$, we clearly obtain the required
extension $(U,\leq)$.

\bigskip

We now return to the proof of Theorem~\ref{main2}. We may assume that
$(C,\leq)$ has no greatest or smallest element, since we may add a copy
of the reverse of $\omega$ to the beginning of $C$, and of $\omega$ 
to the end of $C$. 
Write $a|b$ if $a,b \in C$, $a<b$, and there is no $c \in C$ with $a<c<b$.
Let ${\cal P}:=\{(a,b):a|b\}$. For each $(a,b) \in {\cal P}$, we 
may choose by
Lemma~\ref{exist} a good $I$-coloured $\kappa$-set $L^{(a|b)}$ with colours
$L^{(a|b)}_i$ (for $i \in I$) and with countable coterminality
(we choose the particular such set given by Lemma~\ref{exist}). Define
$$S^{(0)}:=\bigcup(L^{(a|b)}: (a,b)\in {\cal P})$$
and
$$S^{(0)}_i:=\bigcup(L^{(a|b)}_i: (a,b)\in {\cal P})$$ 
for all $i \in I$. Next, we define a linear order on $\overline{C}\cup S^{(0)}$ 
in the unique
way so that it extends the given orders on $\overline{C}$ and each $L^{(a|b)}$,
and so that $a<L^{(a|b)}<b$ holds for each $(a,b)\in{\cal P}$. By
our assumption on $C$, whenever 
$c,d \in \overline{C}$ with $c<d$, there is $(a,b) \in {\cal P}$ with 
$c\leq a<b\leq d$ and there is $s \in S^{(0)}$ with $a<s<b$. Thus $S^{(0)}$
is dense in $S^{(0)}\cup \overline{C}$, and hence we may regard $C$ as a subset of
$\overline{S^{(0)}}\setminus S^{(0)}$ (so the map $\varphi$ will be the identity). 
In fact, the identity mapping
$\id:\overline{C}\longrightarrow \overline{S^{(0)}}$ is complete, $C$ is unbounded
above and below in $\overline{S^{(0)}}$, and $(S^{(0)},\leq)$ 
is a good $I$-coloured
$\kappa$-set.

If $\kappa=\aleph_0$ we now put $S:=S^{(0)}$. As $(S,\leq)$
is
isomorphic to $({\bf Q},\leq)$, the theorem follows easily in this case. 
>From now on, we therefore assume that $\kappa$
is uncountable. We 
argue as in \cite{d1} (Theorem 1 and Corollary 2.5), employing the
construction in the proof of Theorem 2.11 (parts (I)-(III)) of \cite{ds}.
That is, we define $(S,\leq)$ as the union of a tower (indexed
by $\kappa$) of good $I$-coloured
$\kappa$-sets $(S^{(\lambda)},\leq)$ (for $\lambda<\kappa$), so that for all 
$\lambda,\mu<\kappa$  with $\lambda<\mu$ we have
$(S^{(\lambda)},\leq)\leq(S^{(\mu)},\leq)$ and $S^{(\lambda)}_i
\subseteq S^{(\mu)}_i$
for each $i \in I$. Our description of the construction will 
be informal, as it is similar to P.254 of \cite{ds}.

Call a quintuple $(g,a,b,c,d)$ {\em good} if $g \in G$ and there
is $\lambda<\kappa$ such that $a,b,c,d \in S^{(\lambda)}$ with
$a<b$, $c<d$, and for each $i \in I$ we have
$a \in S^{(\lambda)}_i$ if and only if
$c \in S^{(\lambda)}_{i^g}$ and $b \in S^{(\lambda)}_i$ if and
only if $d \in S^{(\lambda)}_{i^g}$. 
For each $\lambda<\kappa$ we
let
$M^{(\lambda)}$ denote the set of good quintuples,
and enumerate $M^{(\lambda)}$ 
by a suitable subset $\mu_{\lambda}\subseteq \kappa$. If we deal during the
construction with such a quintuple $(g,a,b,c,d) \in M^{(\lambda)}$ for the 
first time at step $\nu+1$, we employ Basic Construction A to obtain 
$S^{(\nu+1)}$ and an isomorphism of $[a,b]_{S^{(\nu+1)}}$ onto
$[c,d]_{S^{(\nu+1)}}$ permuting the colours as prescribed by $g$. Later on, 
we employ Basic Construction B to extend isomorphisms constructed at 
previous stages.
The construction shows that $S^{(0)}$, and hence also $C$, is unbounded
above and below in $S$, and that 
$$S=\bigcup((p,q)_S:(p,q) \in {\cal P}).$$


We now verify that $S$ has the properties required in Theorem~\ref{main2}.
First, we sketch a proof
that $(S,\leq)$ is a good $I$-coloured $\kappa$-set with
colours $S_i=\bigcup 
\{S^{(\lambda)}_i:\ \lambda<\kappa\}$ $(i\in I)$ satisfying
properties (a), (b), (d)-(f) (with
$\varphi=id:\ \overline{C}\longrightarrow \overline{S}$).
To see that each element $s\in S$ has countable coterminality, 
observe that this is true in
$S^{(0)}$, and that if $\lambda<\kappa$, then in the 
construction of $S^{(\lambda+1)}$
new elements only get inserted at points of
$\overline{S^{(\lambda)}}\setminus S^{(\lambda)}$; so in particular, each
$s\in S^{(\lambda)}$ has the same character in $S^{(\lambda+1)}$ as in
$S^{(\lambda)}$. Induction also shows that each colour $S_i$ $(i\in I)$ is
$\kappa$-dense in $\overline{S}$. Now 
$\{x\in \overline{S^{(0)}}\setminus S^{(0)}:\ cot(x)=\aleph_0\}$ 
is $\kappa$-dense
in $\overline{S^{(0)}}$. Suppose that $\lambda<\kappa$ and 
$x\in \overline{S^{(\lambda)}}\setminus S^{(\lambda)}$ 
with $cot(x)=\aleph_0$.
Assume that in the construction of $S^{(\lambda+1)}$ the chain $(X,\leq)$
gets inserted into $\overline{S^{(\lambda)}}$ at $x$. Then
\cite[Lemma 4.10]{ds}
shows that $(X,\leq)$ has countable coterminality and the elements $\inf X$,
$\sup X$ of $\overline{S^{(\lambda+1)}}$ become `forbidden points' in the
terminology of \cite{ds}; that is,
later on in the construction no element gets inserted between $\inf X$
and $\{s\in S^{(\lambda)}:\ s<x\}=\{s\in S^{(\lambda)}:\ s<X\}$ 
or between $\inf X$
and $X$, and similarly for $\sup X$. Hence $\inf X$, $\sup X$ have
countable coterminality in $\overline{S^{(\lambda+1)}}$ and keep it in 
$\overline{S}$.
Consequently, 
$\{x\in \overline{S}\setminus S:\ cot(x)=\aleph_0\}$ is $\kappa$-dense in
$\overline{S}$. Thus $(S,\leq)$ is a good $I$-coloured $\kappa$-set with
colours $S_i$, and (b) and (f) are automatic.

We next prove (a),(e) and the completeness of
$\varphi=id: \overline{C}\longrightarrow \overline{S}$. As in
the construction for \cite[Theorem 1, p.320]{d1}
we declare the elements of $\overline{C}$ `forbidden points'. 
As before, this
ensures that during the construction, if $x\in \overline{C}$ then no point
gets inserted between $x$ and $\{s\in \overline{S^{(0)}}:\ s<x\}$ or 
between $x$ and $\{s\in \overline{S^{(0)}}:\ x<s\}$. 
If $a,b\in C$ with $a<b$ and
there is no $c\in C$ with $a<c<b$, then $\{x\in S^{(0)}:\ a<x<b\}=L^{(a|b)}$
has countable coterminality in $S^{(0)}$, 
hence so does the interval $(a,b)$ in
$\overline{S}$. 

The proof of (d) is similar to that of the corresponding statement of
\cite[Corollary 2.5]{d1}.

Before we prove (c), we note without proof the following claim, which follows
immediately from the construction.

\medskip

{\em Claim.}
 Whenever $j,k \in I$, $g \in G$, and $a \in S_j$, $b \in S_k$, 
 $c \in S_{j^g}$ and $d \in S_{k^g}$ with $a<b$ and $c<d$, there is
 an isomorphism
 $h:[a,b]_S\longrightarrow [c,d]_S$ satisfying $([a,b]_{S_i})^h
 =[c,d]_{S_{i^g}}$ for each $i \in I$.

\medskip


It remains to check that property (c) holds. Let $j,k,g,a,b,c,d$ be as
in the last paragraph. Choose $(p,q),(u,v) \in {\cal P}$ so that 
$q<\{a,c\}$ and $\{b,d\}<u$, and then pick
$$e \in (p,q)_{S_j}, e'\in (p,q)_{S_{j^g}}, f\in (u,v)_{S_k},
f'\in(u,v)_{S_{k^g}}.$$
By the claim, there are isomorphisms $h_1:[e,a]_S\longrightarrow [e',c]_S$,
$h_2:[a,b]_S\longrightarrow[c,d]_S$, and
$h_3:[b,f]_S\longrightarrow [d,f']_S$, each mapping the elements of 
colour $S_i$
onto those of colour $S_{i^g}$ for each $i \in I$. By (e), 
for each $(x,y) \in {\cal P}$ the interval
$(x,y)_S$ has countable coterminality. Hence, again by the claim, there
are isomorphisms $h_0:(p,e]_S\longrightarrow (p,e']_S$,
$h_4:[f,v)_S\longrightarrow [f',v)_S$ and 
$h_{(x|y)}:(x,y)_S\longrightarrow (x,y)_S$ for each $(x|y) \in {\cal P}$
with $y\leq p$ or $v\leq x$, each permuting the colours $S_i$ as prescribed by
$g$. Patching all these isomorphisms together, we obtain 
$h \in A(S)$ as required in (c). 

\begin{remark} \label{stronger}
By patching together partial isomorphisms, condition (c) of
Theorem~\ref{main2} implies the following stronger-looking 
symmetry condition.

(c$'$) 
Suppose that $g \in G$, $n \in {\bf N}$, and $a_1,\ldots,a_n,b_1,\ldots,b_n
\in S$ with $a_1<\ldots <a_n$, $b_1<\ldots<b_n$ and, for each 
$i \in I$ and $j \in \{1,\ldots,n\}$, $a_j \in S_i$ if and only if $b_j 
\in S_{i^g}$. Then there is
$h \in \At(S)$ such that $a_j^h=b_j$ and $S_i^h=S_{i^g}$ for each 
such $i$ and $j$.
\end{remark}

\section{Proof of Theorem~\ref{main}}

The proof of Theorem~\ref{main} uses 
ideas from Sections 3 and 4 of \cite{dgm}, but we give details here.  
First, recall that a {\em cyclic ordering} is a structure $(T,C)$, 
where $C$ is a ternary relation on $T$ which satisfies
\begin{enumerate}
\begin{enumerate}
\item for all $a\in T$, if we define a binary relation $<_a$ on 
$T\setminus \{a\}$
by the rule: $x<_a y$ if and only if $C(a,x,y)$ holds, then 
$<_a$ is a strict total order, and
\item for all $x,y,z \in T$, $C(x,y,z)\longleftrightarrow C(y,z,x)
\longleftrightarrow C(z,x,y)$.
\end{enumerate}
\end{enumerate}


We apply Theorem~\ref{main2},
with $C=\emptyset$, $I=\{0,1,2\}$, and $G=\Sym(I)$. This yields
a chain $(S,\leq)$ of cardinality $\kappa$ with a decomposition
$S=S_0\cup S_1\cup S_2$ into dense subsets of $S$, such that properties
(c) and (d) of Theorem~\ref{main2} hold. We may assume that
$\cot(S)=\aleph_0$ (for if necessary we may choose $a,b \in \overline{S}$ with
$\coi(a)=\cof(b)=\aleph_0$ and replace $S$ by $(a,b)_S$). It follows that
there are sequences $(a_i:i \in {\bf Z})$, $(b_i:i \in {\bf Z})$,
$(c_i:i \in {\bf Z})$ in $S$, each sequence unbounded above and below in
$S$, such that for each $i \in {\bf Z}$ we have $a_i \in S_0$, $b_i \in S_1$,
$c_i \in S_2$, and $a_i<b_i<c_i<a_{i+1}$. By a slight extension of 
Remark~\ref{stronger}, there is $z \in \At(S)$ such that $S_0^z=S_1$, 
$S_1^z=S_2$, $S_2^z=S_0$, and $(a_i,b_i,c_i)^z=(b_i,c_i,a_{i+1})$ for
each $i \in {\bf Z}$.

The sets $S_1$ and $S_2$ lie in the Dedekind completion $\overline{S}_0$
of $S_0$, and we have $z \in \At(\overline{S}_0)$ and $z^3 \in \At(S_0)$.
For each $a \in S$ let $\bar{a}$ denote the orbit of $a$ under
$\langle z^3 \rangle$ (in what follows, there should be no
confusion with the $n$-tuple notation).
Put $V:= \{\bar{a}: a \in S_0\}$. We
define on $V$ a ternary cyclic ordering $C$, and a binary digraph
structure $\Delta_{\kappa}=(V,\rightarrow)$ and graph structure
$\Gamma_{\kappa}=
(V,\sim)$, as follows.
For $\bar{a},\bar{b},\bar{c}\in V$, put $C(\bar{a},\bar{b},\bar{c})$ 
if and only if there
are $a' \in \bar{a}$, $b' \in \bar{b}$ and $c' \in \bar{c}$ such that
$a'<b'<c'<a'^{z^3}$. Also, for $\bar{a}$, $\bar{b} \in V$, put 
$\bar{a}\rightarrow \bar{b}$
if and only if there are $a' \in \bar{a}$ and $b' \in \bar{b}$ such that
$a'<b'<a'^z$, and put $\bar{a}\sim \bar{b}$ if and only if
$\bar{a}\rightarrow \bar{b}$ or $\bar{b}\rightarrow \bar{a}$.

It is immediate that $C$ is a cyclic ordering (see also Section
4 of \cite{dgm}) and that the group $H:=C_{\At(S_0)}(\langle z\rangle)$
acts on $V$, preserving each of the relations $C$, $\rightarrow$
and $\sim$. We shall show that $\Gamma_{\kappa}$ is $\leq$3-set-homogeneous
but not
2-homogeneous, as required in Theorem~\ref{main}.

\medskip

{\em Claim 1.} $\Gamma_{\kappa}$ is $\leq$3-set-homogeneous.

{\em Proof.} We first show that $\Delta_{\kappa}$ is $k$-homogeneous
for all $k$
(in fact, we just require that $\Delta_{\kappa}$ is $\leq$3-homogeneous).
Let $k$ be a positive integer. 
Suppose that there are $a_1,\ldots,a_k,b_1,\ldots,b_k\in S_0$ and
a digraph isomorphism 
$$(\bar{a}_1,\ldots,\bar{a}_k)\longrightarrow
(\bar{b}_1,\ldots,\bar{b}_k).$$ 
For each $i=1,\ldots,k$ there are unique
$a_i' \in [a_1,a_1^z)$ and $b_i' \in [b_1,b_1^z)$ such that the pairs
$\{a_i,a_i'\}$, $\{b_i,b_i'\}$ each lie in $\langle z\rangle$-orbits.
Furthermore, for each $i,j \in \{1,\ldots,k\}$  and $m \in \{0,1,2\}$,
we have $a_i'<a_j'$ if and only if $b_i'<b_j'$ and 
$a_i' \in S_m$ if and and only if $b_i' \in S_m$. It follows from
Remark~\ref{stronger} that there is $g \in \At(S)$ such that
$(a_1',\ldots,a_k')^g=(b_1',\ldots,b_k')$. Since
$a_1',b_1' \in S_0$, the element $g$ fixes $S_0$ setwise, so 
we may identify it with
an element of $\At(S_0)$. There is 
unique $g' \in H$ agreeing with $g$
on $[a_1',a_1'^z)$. The element $g'$ induces an automorphism of
$\Delta_{\kappa}$ mapping $(\bar{a}_1,\ldots,\bar{a}_k)$ to
$(\bar{b}_1,\ldots,\bar{b}_k)$. It follows that $\Delta_{\kappa}$ is
$k$-homogeneous. 

To show that $\Gamma_{\kappa}$ is $\leq$3-set-homogeneous, it now suffices
to
consider all subdigraphs of $\Delta_{\kappa}$ on at most
3 vertices, and apply the $\leq$3-homogeneity of $\Delta_{\kappa}$. 
Oberve that, by its construction,
$\Delta_{\kappa}$ does not embed a directed triangle
$\bar{a}\rightarrow \bar{b}\rightarrow \bar{c} \rightarrow \bar{a}$, 
and that paths of length
2 in $\Gamma_{\kappa}$ come from directed paths in $\Delta_{\kappa}$.

\medskip

We show next that $\Gamma_{\kappa}$ is not 2-homogeneous. 
Observe
that $H$ acts transitively on $V$, so $\Gamma_{\kappa}$ is 1-homogeneous.
Let $K:=\Aut(\Gamma_{\kappa})$. We first prove the following.

\medskip

{\em Claim 2.} The group
$K$
preserves or reverses the cyclic relation $C$
on $V$, that is, preserves the induced quaternary separation
relation. 

{\em Proof.} Since $H$ is transitive on $V$ and preserves $C$,
it suffices to show that if $a \in S_0$ then the stabiliser
$K_{\bar{a}}$ preserves the induced linear betweenness relation $B$ on
$V\setminus \{\bar{a}\}$, and for this, we show that $B$ is first-order 
definable
using $\sim$ and the parameter $\bar{a}$.

First, let $D:=\{\bar{x}\in V:\bar{a}\sim \bar{x}\}$. There is a 
$K_{\bar{a}}$-invariant
equivalence relation $\equiv$ on $D$: for $\bar{u},\bar{v} \in D$, put
$\bar{u}\equiv \bar{v}$ if and only if one of the sets
$$\{\bar{x}: \bar{x}\sim \bar{u}\land \bar{x}\sim \bar{a}\} \mbox{~and~}
\{\bar{x}:\bar{x}\sim\bar{v}\land \bar{x}\sim \bar{a}\}$$
contains the other. There are two $\equiv$-classes, $E_1$ and $E_2$ say.
Also, without loss of generality $E_1$ is exactly 
the set of vertices dominated by $\bar{a}$ in $\Delta_{\kappa}$, and $E_2$ is
the set of
vertices dominating $\bar{a}$. Let $F:=V\setminus (D\cup\{\bar{a}\})$.

We now define the betweenness relation $B(\bar{u};\bar{v},\bar{w})$ (read 
`$\bar{u}$ is between $\bar{v}$ and $\bar{w}$'). 
Vertices of $F$ lie between those
of $E_1$ and $E_2$. Let $i \in \{1,2\}$, and $\bar{r},\bar{s}, \bar{t},\bar{u},\bar{v},\bar{w}$ be
distinct, with $\bar{r},\bar{s},\bar{t}\in E_i$, and $\bar{u},\bar{v},\bar{w}\in F$. Then
\begin{enumerate}
\item $B(\bar{r};\bar{s},\bar{t})$ holds if and only if the set $\{\bar{x} \in F:\bar{r}\sim \bar{x}\}$
contains one of $\{\bar{x}\in F:\bar{s}\sim \bar{x}\}$, $\{\bar{x}\in F:\bar{t}\sim \bar{x}\}$,
and is contained by the other.
\item $B(\bar{r};\bar{s},\bar{u})$ holds if and only if
$$\{\bar{x}\in F:\bar{s}\sim \bar{x}\}\subset \{\bar{x}\in F:\bar{r}\sim \bar{x}\}.$$
\item $B(\bar{u};\bar{r},\bar{v})$ holds if and only if
$$\{\bar{x}\in E_i:\bar{u}\sim \bar{x}\}\supset \{\bar{x}\in E_i:\bar{v}\sim \bar{x}\}.$$
\item $B(\bar{u};\bar{v},\bar{w})$ holds if and only if for each $j \in \{1,2\}$,
$\{\bar{x}\in E_j:\bar{u}\sim \bar{x}\}$  contains one of
$\{\bar{x}\in E_j:\bar{v}\sim \bar{x}\}$, $\{\bar{x}\in E_j:\bar{w}\sim \bar{x}\}$, and
is contained by the other.
\item if $\bar{w}\in E_j$ where $\{i,j\}=\{1,2\}$ then 
$B(\bar{r};\bar{w},\bar{s})$ holds if and only if 
$$\{\bar{x} \in E_j:\bar{r}\sim \bar{x}\}\supset \{\bar{x}\in E_j:\bar{s}\sim \bar{x}\}.$$

\end{enumerate}
It is easy to check that this relation is indeed the betweenness relation
on $V\setminus \{\bar{a}\}$ determined by the cyclic order on $V$.

\medskip

We now prove the following claim.

\medskip

{\em Claim 3.} The graph
$\Gamma_{\kappa}$ is not 2-homogeneous.

{\em Proof.} Pick
$a,b \in S_0$ such that $\bar{a}\sim \bar{b}$. We must show that no element
of $k \in K$ maps $(\bar{a},\bar{b})$ to $(\bar{b},\bar{a})$. 
We may suppose that
$a<b<a^z$. The set $X:=\{\bar{x}\in V: C(\bar{a},\bar{x},\bar{b})\}$ 
would have to be fixed 
setwise by such an element $k$, with its natural $\bar{a}$-invariant
ordering reversed (for otherwise $k$ would have to interchange
$X$ with $Y:=V\setminus (X \cup\{\bar{a},\bar{b}\})$, 
which is impossible as $Y$, 
unlike $X$, contains vertices adjacent to neither $\bar{a}$ nor $\bar{b}$). 
However,
this ordering on $X$ is isomorphic to the ordering $(a,b)_{S_0}$. By
Theorem~\ref{main2}(d), the Dedekind completion of the latter
contains elements of character $(\aleph_0,\aleph_1)$ but not
elements
of character $(\aleph_1,\aleph_0)$, so is not 
isomorphic to its reverse ordering.
Hence no such element $k$ can exist.

\medskip

Finally, to complete the proof of Theorem~\ref{main}, we must prove the
following.

\medskip

{\em Claim 4.} The graph $\Gamma_{\kappa}$ is elementarily equivalent to
the graph $R(3)$ mentioned in the Introduction.

{\em Proof.} By Theorem 4.1 of \cite{dgms}, $\Gamma_{\kappa}$ is elementarily 
equivalent to one of four graphs, $R(3)$, $T$ (the comparability
graph of a certain semilinear order) or their complements. 
The complement of $R(3)$ cannot be elementarily equivalent to
$\Gamma_{\kappa}$, since, unlike $\Gamma_{\kappa}$, it does not contain a
triangle. Also, $\Gamma_{\kappa}$ cannot be elementarily equivalent to
$T$ or its complement, since in these two graphs, unlike in
$\Gamma_{\kappa}$, there exist distinct vertices $x,y$ such that
the set of neighbours of $x$ outside $\{x,y\}$ contains the set of
neighbours of $y$ outside $\{x,y\}$. The claim, and 
hence the theorem, follow.

\begin{remark} 
Arguments as in
Section 4 of \cite{dgm} show that 
the automorphism group $K$ of $\Gamma_{\kappa}$ is exactly 
$H/\langle z^3 \rangle$. Furthermore,
by Theorem 1.1 of \cite{dgm}, $K$ is a simple group.
\end{remark}

\begin{thebibliography}{999}
\bibitem{d1} M. Droste, `Complete embeddings of linear
orderings and embeddings of lattice ordered groups', Israel J. Math.
56 (1986), 315--334.
\bibitem{dm} M. Droste, H.D. Macpherson, `On $k$-homogeneous posets
and graphs', J. Comb. Theory Ser. A, 56 (1991), 1--15.
\bibitem{ds} M. Droste, S. Shelah, `A construction of all normal subgroup
lattices of 2-transitive automorphism groups of linearly ordered sets',
Israel J. Math. 51 (1985), 223--261.
\bibitem{dgm} M. Droste, M. Giraudet, H.D. Macpherson, `Periodic
ordered permutation groups and cyclic orderings', J. Comb. Theory
Ser. B, 63 (1995), 310--321.
\bibitem{dgms} M. Droste, M. Giraudet, H.D. Macpherson, N. Sauer,
`Set-homogeneous graphs', J. Comb. Theory Ser. B, 62 (1994),
63--95.
\bibitem{f} R. Fra\"iss\/e, {\em Theory of Relations}, North-Holland,
Amsterdam, 1986.
\bibitem{m} A.H. Mekler, `Homogeneous partially ordered sets', in
{\em Finite and infinite Combinatorics in Sets and Logic,
Proceedings NATO ASI conference in Banff 1991, Eds. N.W. Sauer,
R.E. Woodrow, B. Sands}, Kluwer, Dordrecht, 1993, pps.
279--288.
\end{thebibliography}

\end{document}