Logic Colloquium '85 Edited by The Paris Logic Group © Elsevier Science Publishers B.V. (NorthHolland), 1987
HOMOGENEOUS DIRECTED GRAPHS.
67
THE IMPRIMITIVE CASE
Gregory l. Cherlin Rutgers University Mathematics Department New Brunswick, New Jersey 08903, U.S.A. INTRODUCTION A relational system H is said to be homogeneous if any isomorphism a:
A + B between two of its finite substructures is induced by an
automorphism of H.
Assuming the language is finite, such structures
are Rocategorical, and Lachlan has a very general theorem concerning the classification of the stable ones [4,6,9] which is a refinement (for this special case) of the results of [3].
Roughly speaking the
stable homogeneous structures for a fixed finite relational language fall into finitely many families, with the isomorphism type of the structures within a family determined by rather trivial numerical invariants.
In
particular there are only countably many countable stable homogeneous structures for a given finite relational language. In certain cases all the homogeneous structures have been classified, though not as a result of any general theory.
The homogeneous symmetric
graphs or tournaments (directed graphs with any two vertices joined by an edge) were classified in [10] and [8] respectively.
The methods of the
second paper seem particularly interesting, as the nimbUS of a general method seems dimly perceptible.
have shown recently that the same
method can be used to classify the homogeneous directed graphs omitting the edgeless graph
I~
on infinitely many vertices:
the tournaments are
of course those which omit I • 2
(* Research supported by NSF Grants OMS 8301806 and INT8313363.]
68
G.L. Cherlin ~o
What of the homogeneous directed graphs in general? There are
2
known types which are freely generated by tournaments in the following sense.
In the partial order of isomorphism types of finite tournaments
ordered by embeddability. fix an infinite antichain in
[5]. which I follow here).
the closure
A(I)
of
1:
For
X
~
(one is exhibited
an arbitrary subset of :::I. form
with respect to free amalgamation. isomorphism.
and substructure. where the free amalgamation of two directed graphs which agree on their common vertices is simply their union. pointwise and edgewise.
Following Fraisse. we associate to A(!)
homogeneous directed graph. from which this way we find
~o
2
Jt
the
A(!)generic
is easily recovered.
countable homogeneous directed graphs.
In
(In the
future structures are assumed countable without further mention.) And so it seems that Lachlan's theory cannot be extended to the unstable case; but actually this does not follow at all  not from these cardinality considerations.
If one is to draw this sort of conclusion
from such evidence then one must in particular regard the homogeneous directed graphs as intrinsically unclassifiable. while the opposite possibility  that they are all already known  is perfectly consistent with the evi dence.
I propose accordi ngly to work in thi s di recti on  an ex
plicit classification of the homogeneous directed graphs  partly in order to lay to rest these cardinality considerations. which have lately reared their heads in more algebraic contexts as well [1.11.12].
This is
not to say tha tone actua 11 y expects a smooth genera1 theory of homogeneous structures for finite relational languages. only that sensible criteria for classifiability are wanted; and indeed a very sensible criterion has already been suggested by Lachlan. style entailment relation for finite sets
.s4.E
He proposes a Gentzenof finite structures for
69
The Imprimitive Homogeneous Directed Graphs
a given language L:
s4 ~ 13
means that any homogeneous
embedding all the structures in
A
Lstructure
must also embed some structure in
:B.
Using Fraisse's theory relating homogeneous structures and amalgamation classes. one sees that this relation is r.e •• and that the problem of classifiability is expressed quite well by: (*)
Given
L. is
r
recursive?
This seems by far the most interesting problem in the area. and we know essentially nothing about it. The goal of the present paper is quite modest. I will describe the known homogeneous directed graphs in some detail. checking homogeneity when it seems appropriate. deficient (omitting some
They fall naturally into three families: 2type). imprimitive (carrying a nontrivial
adefinable equivalence relation).
~nd
freely generated (in the sense
described above. or in a dual sense). and there are in addition two more examples known which may be characterized by the 3types they realize. The deficient examples were classified in the papers [10.8] referred to earlier.
The imprimitive ones will be classified here.
There is one other topic which should be dealt with. at least in part. before attacking the primitive case directly.
In [10] Lachlan classifies
the homogeneous 2tournaments (these are tournaments partitioned into two distinguished subsets).
In dealing with directed graphs it may be
convenient to deal with 3tournaments. allowing in addition three 2types to be realized between distinct components (as opposed to two realized in a given component).
have worked out the classification of the
ntournaments with an arbitrary number of cross types between components. for all
n.
This seems to be a natural problem to consider prior to
tackling the homogeneous directed graphs. and the analysis suggests profitable lines for the latter problem. but I no longer expect the
70
G. L. Cherlin
result to be directly applicable (that is. it may be usable. but it seems that there are better approaches).
All of this will be explored in
detail elsewhere. §1. The known homogeneous directed graphs. Our description of the known homogeneous directed graphs will be keyed to the following catalog: I.
II.
III.
DEFICIENT. 1.
I
2.
C. Q. Q*. T"" 3
n
IMPRIMITIVE. 3.
Wreathed
5.
n
6.
semi generic
*
1
00
EXCEPTIONAL. 7.
S(3)
8. P IV. FREE. 9.
Generic omitting
I
10.
Generic omitting
Jr.
n+1
Proofs of homogeneity will be given in §2.
In the following discussion
H is some countable, homogeneous, directed graph. I.
Deficient cases. There are three nontrivial
2types, which will be denoted in two
71
The Imprimitive Homogeneous Directed Graphs
ways as convenience dictates: x
+ y
or y
E
XI
x + y
or y
E
IX
X !
Y or
Yc
xl.
If H omits one of these 2types then it is said to be deficient and is then either edgeless (Case 1. n
or a tournament. The homo
(~l
geneous tournaments as classified by Lachlan [8] are
1 included in 1, Case 1. the oriented triangle C, the rational order Q, the circular 3
order
described below, and the generic tournament ~.
Q*
To form
Q*
we can either partition Q into two dense subsets and
reverse the arrows between elements in distinct subsets, or alternatively, place astronomers at all points lying at rational angles on a circle of large radius, equip them with telescopes enabling them to see halfway around in either direction, and draw arrows to the right as far as the eye can see; then each astronomer believes he lives on the rational line.
This structure is mentioned in §6 of [2]. and is con
nected with §4 of [4]. II.
Imprimitive cases.
If H is imprimitive then the nontrivial equivalence relation is the union of equality with either 1 or its complement.
Wreath products
H [H] are formed by taking
H H with no 2types in common, and re1, 2 placing the points of H by copies of H In other words, if T is 1 2• one of the four nondegenerate homogeneous tournaments from Case 2, then 1 2
we form T[I ], or n
called
n
>
I [T] for n
1 < n <
~
; the latter is more commonly
1.
In all nonwreathed cases the equivalence relation will correspond to !.
For T a tournament, T
A
is constructed as follows.
Let
G.L. Cherlin
72
T+ = T U {al, where a
T. Then
+
T+ T+ of T+. For x I'
Xl
2
1
E
T+. Y 1
2
is the union of two copies
T~ E
T+
2
corresponding to
x.Y
E
T+.
Y iff Y + x. Observe that I has equivalence classes of size 2. 2 any two of which form a 4cycle C II '" C One may check also that 4' 4' C is isomorphic with a graph on the nonzero points of the plane V +
3
over the Galois field F
3
with edges defined by: x 2
equal to a fixed element of A V.
y iff x A y is
+
(The exterior product is just the de
terminant of the matrix with columns x. Y. once bases are chosen; there is a similar structure on the nonzero points of the plane over F. homoq
geneous for a binary language with 2(ql) 2types.)
The graph Q' is
a variant of Q* in which each astronomer has an antipodal twin which he cannot see.
co
T

is generic subject to the constraints:
1.
I
gives rise to an equivalence relation with classes of size 2.
2.
The union of two Iclasses is a copy of C. 4
The graph n *
I~
is defined as the generic graph on which
equivalence relation with n classes.
For n
=~
is an
there is a variant
which for lack of a more suggestive term we call semi generic, cc
I
The graph
* L" is generic for the constraint: 1.
I
gives rise to an equivalence relation;
To get the semi generic variant we impose the further constraint: 2,
For any pairs AI' A taken from distinct Iclasses, the number 2 of edges from A to A is even. 1
2
III. Exceptional homogeneous directed graphs. We can define the myopic circular order 5(3)
most simply in terms of
astronomers whose telescopes enable them to see 1/3 of their circular universe in each direction  leaving a third invisible.
Alternatively,
73
The Imprimitive Homogeneous Directed Graphs
,
partition Q into three dense sets Q. the types
1. .... +
indexed by i
with 0.1.2 respectively. and for
EO
1131. identify
x
EO
Q. , 1
Y EO
i  j + tp (xy).
distinct, assign to xy the type
Q. J
Q
The generi c partially ordered set P needs no commentary. IV. Freely generated homogeneous directed graphs. These are the graphs which are generic subject to a constraint of the form:
H embeds no X from l
of a gi ven type.
In (9) 3; is
here Xis a class of defi cient graphs (I
n+l
)
and in (10)
X =J
is a class
of tournaments. These are all the homogeneous graphs known to me, and I conjecture that in fact:
only countably many are missing.
(Just as in the im
primitive case the semi generic graph appears unexpectedly, others could easily turn up.)
§2.
Proofs of homogeneity. For the homogeneity of Q* see [2] or [8].
analyzed along similar lines:
Q* and 5(3)
can
be
the astronomical description shows that
the automorphism group is transitive. so we need only check that the expansion of the structure by a single parameter x is homogeneous, and up to a permutation of 2types (and the removal of the element x) this expansion is just Q partitioned into 2 or 3 dense subsets, respectively. In the case of 5(3). identifying 1.... ,
+
with 0.1,2 respectively. and
letting Q = {y: tp(xy) = i}, we assign to y i (i  j) + tp(yz).
EO
Qi'
Z
EO
41. the type J
The homogeneity of wreath products of homogeneous structures in disjoint languages has been noted previously by Lachlan, if not earlier, and the existence of amalgamation classes corresponding to examples 810 is
G.L. Cherlin
74
both straightforward and well known.
It remains to discuss examples 46.
Recall as a matter of notation that T· and T = T.
=
r; U T; with
T~ = {ail U T
i
It is quite easy to see that the structure imposed on
i
T U T by {al' a is homogeneous if (and only if) T is. as it conl 2} 2 sists of two copies of T with a definable isomorphism. As {a} = a 1. 2
1
is transitive when T '1 Q* is homogeneous.
it suffices to see that T·
The following condition is sufficient for this. though not necessary: (*)
For x
€
Y. z
X:
+
T there is an isomorphism a: y
az iff ay
+
,
,
X+ X
such that for
z.
+
This condition evidently holds for
II. C3. and Q; for
T = roo and
X € T the desired a comes from a backandforth construction. To check the transitivity of T· observe first that there is a canonical involution
i
E
Aut T· defined by
to find maps ~
E
Aut T· which take al
corresponds to
x
E
X 1 i(x). so it suffices
to any Xl
€
Tl.
If Xl
T then let a be as in (*) and define (ai)
(Xi) = a3i' while for (Yi)
= a(y)i
(Zi)
= a(z)3i
y
+
x
+
xi.
z:
;
(*) expresses the condition that this is an automorphism of T·.
To see that (*) is not a necessary condition for transitivity. notice that if 7./2n7. is made into a directed graph by taking "(y  x)
€
{l ••..• nl} (mod 2n)". then 1/2n1
is the transi ti ve tournament of order It will be useful later to know that
x
+
y to mean
= L(nl)·. where L(nl)
n  1. Q*.
is not homogeneous. and for
this we check the failure of transitivity directly.
On the one hand
Q* by the construction. while on the other hand. for
75
The Imprimitive Homogeneous Directed Graphs
is linearly ordered, by inspection.
X' 
1
n * reo
115.
We must check that the class of finite directed graphs satisfying:
=
(1)
the union of
and I
is an equivalence relation;
(2)
this relation has at most n classes;
is an amalgamation class.
It suffices to describe how to complete an
amalgamation of
with
type of
a a 1 2 We can take
H U {a} 1 suitably. a
1
+
a
2
H U {a} 2
over
H, by specifying the
unless there is an obstruction of one of the
following forms: (1.1)
a
(2.0
H has n  1 Iclasses, and there is no b e: H with a
1
I
b I
a
2
b e: H;
b I a
1
or
2
We can take (1.2)
a ,
i
a I a 1
2
leI a , {i,j} j
unless there is an obstruction of the form:
= {1,2}.
There cannot be both sorts of obstruction, so the amalgamation succeeds. 116.
The semi generic Iimprimitive case. We claim that the constraint (1) above can be combined with the con
straint: (3)
IA X A () EI 1 2
is even for
A, A 1 2
two
requtva lerrt pairs (where
E is the set of edges) to give an amalgamation class of finite directed graphs.
With the notation of the previous example, we must again specify
the type of
a a . 1 2 We take a + a unless there is either an obstruction of the form 1 2 (1.1), or this choice yields:
76
G.L. Cherlin
} (\ EI is odd. If (1.1) occurs a 1 b E H and I {al,b x {a 2,b2 l l l} x An EI is then we take \ 1 a and we have to check that 1{a 1,a 2} 2 even for any 1equivalent pair A in H; this follows since (3.1)
I {a 1.• b)
x
An EI
is even for
i
1,2.
If case (1.1) does not apply but (3.1) does, then we take a
2
+
constraint (1) is still satisfied, and moreover (3.1) is now false. must still be checked is that for
I {a
1
, c } x {a , c }
1
{a .b }
2
x
2
n EI
a. 1 c 1
i
E
a
1
and
What
H, that always
is even; for this it suffices to consider
{a ,b }, {a ,b }
x
{a .c },
11221122
This completes the description of the currently known examples. The next order of business is to show that the list of imprimitive types is complete.
Imprimitive homogeneous graphs with finite classes.
§3.
Throughout the remainder of this article, H denotes an imprimitive homogeneous directed graph.
As the nontrivial equivalence relation on H
is the union of equality with either 1 or its complement, and in the latter case H is necessarily a wreath product, we may assume the equivalence relation is
"= U 1"; by a slight abuse of notation we will denote
the equivalence relation also by 1. Theorem.
The theorem we aim at is of course:
If H is an imprimitive homogeneous directed graph then H is
one of the following: 1.
a wreath product T[l ] or n
3.
n
*
1
00
;
I [T] n
77
The Imprimitive Homogeneous Directed Graphs
4.
semigeneric for
I
an equivalence relation.
As noted, we may take the equivalence relation on H to be (essentially)
We consider first the case in which this relation has finite
1.
classes. We can dispose of the case in which H is finite by reference to the list in
[6J
of all finite examples. So we may assume that
ite, and not a wreath product.
Fix an Iclass C, and find
H
is infin
x,y e H  C
with: x
+
s,
x' (\ C = y' {\ C.
If x' fI C
o or
n c. [x ' n CI
C then it follows easily that H is wreathed.
Fix a e x' If
k with 1 < k < n, then we can find
A * x'lI C and z e H  C with
x
+
z or
z
+
A'=. C, a e A,
x so that z'{\ C
Then axy and axz or azx have the same type, a contradiction. conclude that k
= I,
and similarly that n  k
follows rapidly that H = T~
n
*
n
= 2.
We
It then
for some homogeneous T, and we checked in
the previous section that this forces §4.
= I,
= A.
T
r Q* .
I"" •
We have assumed that I defines an equivalence relation on H, and we will assume throughout that H is not a wreath product. the condition that all
Iclasses are infinite.
We now impose
We first take up the
case in which H/I is finite, but we begin with two general lemmas. Lemma 1. I' {\ C
2
For distinct Iclasses C ,C 1
is infinite.
2
and Is C
1
finite, the set
G. L. Cher/in
78
Proof: Fix
We will show that for some
n.
IcC

Suppose the contrary, and choose
infini teo
of order
1
n, I'
n C2
is
10 maximal so that
C is infinite. Let J 1 II c • For IcC  I finite, 2 0 1 1 0 2 0' 'I is cofinite in J, hence infinite. Hence for J c J of order n, 1 0  0 J'II C is infinite. As H is not a wreath product, there is an autoII
o
(\
1
morphism of
H which switches
C and 1
C. 2
o
The claim follows.
Corollary. With the same notation, if I'll 'J II C 2
I, J
~
C are finite and disjoint, then 1
is infinite.
Proof: Fix
n and 11 == 'K n C 1 1' = III, IJ11 = IJI. Apply homogeneity.
n arbitrary, K c;; C
J {\ K' ~ C where 1 1' Lemma 2.
IH/ll
Let
product for
x
€
11
2
11
n with
of order
3 ( n
(~.
Then
x'
is not a wreath
H.
Proof: We have supposed that
H is not a wreath product. If the lemma fails,
fix
C, C C distinct Iclasses with x € C. The tournaments y'/l 1' 2 are canonically isomorphic for y € C, and hence no automorphism a of H carries
(C,C,e)
1 2
to
(e,e,e).
2 1
(If
a
carries
x e e
to
y e e,
(xy)' (\ (C u C).) Therefore 'x is also a 1 2 wrea th product. Let A = x' (\ e , B = x' 1\ e , a e A , b € B • If 1 1 1 2 1 1 1 1 the edges a b and a b have the same orientation then the map 1 2 2 1 x,a,b + x,a ,b is induced by an automorphism taking (e,e,C) to 1 2 2 1 1 2 look at its effect on
79
The Imprimitive Homogeneous Directed Graphs
(C,C
a contradiction. Thus the edges from Al to B have con2,C1), 2 stant orientation. It follows that any two points of A realize the 1
same type over C • From this, homogeneity readily yields that H is a 2
wreath product, a contradiction. ProposHi on. Assume
n
= IH/ll is finite. Then
H
n * 1
00 •
Proof: We proceed by induction on n, starting at n
1.
For the inductive
= 2 this is contained in Lemma 1. For n
> 2, we deduce from
step we show first: For x e: H, x' '" InL) * 1
(1)
00 •
For
n
Lemmas 1 and 2 that x'
has infinite
iclasses and is not a wreath pro
duct, so induction applies. Now we will prove that all finite directed graphs of the form: T U
with
T a tournament of order
H.
in
n  I, and I a disjoint iclass, embed
Our claim will then follow, as any subgraph of
n *
can be
100
built up from such graphs by amalgamations with unique solutions. the same reason we may take n
to be indiscernible over T.
For
For
= 2 (1) already suffices. For
n > 2 and T U 1 as described, fix
a,b e: T with
a
+
band
form a directed graph K on a set:
T U T U {a ,a ,b ,b } U 1 U 1 12121212 (leaving the orientation of T
1
U {a ,b } U 1
1
1
1
(a
1,b1
T U 1 with
)
unspecified, however) so that: + b •
I'
G.L. Cherlin
80
(a ,a} 1
1
1
has order
K/l b
and {b ,b}
2
are
2
lclasses;
n;
K  (a 11), b + K  (a / 1)  {a } . 1 2 2 2
+
We need to see that K K  {a} and K = K  {b are embedded 2 1 1 1} in H, so that an amalgam of Hand H will contain a copy of T U 1. 1 2 That K < H follows from (1) with x = a , and that K < H follows by 2
1
taking
K
2
1
over their common part, applying (I) with x
§5.
2
to be the (unique) amalgam of K  {a ,b}
= a2 ,b 2
1
and K  {a ,b } 2
1
respectively.
The semigeneric case. From now on we assume that HII
is infinite.
We will refer to the
extra constraint placed on the semigeneric graph as the parity constraint.
We wish to show that if H satisfies the parity constraint,
then it is semigeneric.
We will prove the following two claims by
i nducti on: (l.n)
If K = T U I is a finite directed graph, with T a tournament of order
(2.n)
nand
a disjoint Iclass, then K embeds in H.
If K embeds in the semi generic graph and IK/II = n then K embeds in H.
Observe that
(l.n)
implies
(2.n+l)
by a straightforward amalgamation,
invoking the parity constraint. We prove (Ln) inductively. Lemma 1.
For n = 1 we use the corollary to
For the inductive step we form a directed graph K
II U 1 U T U T U {x,Xo,y}, with the orientation of 2 2 1
1
on the set
(x,y) unspecified,
The Imprimitive Homogeneous Directed Graphs
81
so that: I
1
UI
I xyT 1
2
1
I xyT 2 2
is a single Iclass;
=K
with x,y
++
a,b, I
=K
with x,y
++
b,a, I
1
2
if
++
++
I
x
if y
+ y;
+
x;
Corresponding elements c e T c e T are unlinked; 1, 2 2 1
K
1
embeds in the semigeneric graph.
More preci sely, K
is an amalgamation problem, whose solution must
I
conta in a copy of K.
The point
x
0
forces an edge to 1i nk
x and y.
It remains to be seen that the factors embed in H. The factor sequence of
K  {y} I
u.nn.
embeds in In the factor
H by
(2.n), which we have as a con
K  {x} 1
the point x
0
the others.
dominates
Taking any x e H, we can apply (2.n) to x in the o 0 manner of the previous proof, so this factor also embeds in H. This I
completes the argument.
§6.
'"
*
leo.
We treat the last case in a similar but more elaborate fashion.
We
assume that H/l is infinite and that H does not satisfy the parity constraint. which
I
If
Jt
is an amalgamation class of finite directed graphs on
is an equivalence relation, then let
A*
be the set of all
directed graphs K e J4 such that an arbitrary extension by a new Iclass 1 will belong to
5f.
K U I of K
let Q be the simplest
directed graph Violating the parity constraint:
82
G.L. Cherlin
o Then the inductive argument corresponding to the ones we have given above is expressed as follows. if it contains all
I
g. Lemma.
If
on which
A
for
n
n < 00. arbitrarily large tournaments. and
is a robust amalgamation class of finite directed graphs
is an equivalence relation. then
1
Corollary.
Call a class of finite directed graphs robust
J4* is also robust.
With .f4 as above. any finite directed graph K on which
is an equivalence relation belongs to
Jf.
We run through the proof of the corollary first: duction on
n = IK/ll
from
1
n = O. assume
IK III = n  1 and I an lclass. 1 hence K E i.
with
proceeding by in
n > 0 and let K = K U I 1 By induction K E A* and 1
Proof of the Lemma: Let J = K U I either
I
n
be the graph we wish to show is in
or L(n) for some
n. or
g.
J4.
where K is
Making use of straightforward
amalgamations with unique solutions, we find that we need only consider the following two cases: (1) (2)
is indiscernible over K;
III = 2.
The Imprimitive Homogeneous Directed Graphs
Let H be the (3) For x
E
~generi c
H. x' embeds
homogeneous di rected graph.
First form the amalgamation diagram:
/.~
<.«> a. (
*x
The factors embed in x'. since by Lemmas 1 and 2. x' generic.
We show first:
g.
We give a direct construction.
y*
83
is at worst semi
If the edge goes from x to y we are done. and otherwise
amalgamate the result with:
/.~
y.~.~.b
taking a.b as the new points. (If this last factor is omitted then we get g embedded in x'
more
directly. ) Next we prove: (4)
If K is a finite directed graph on which
1
is an equivalence
relation with two classes. then K embeds in H.
G. L. Cherlin
84
Let K/I = {I,J}.
Extending J
if necessary, assume the elements of
III = 2,
realize distinct types over J; we can then reduce to the case and then further to the cases: (4.1)
II I
IJ I
(4.2)
II I
2, J indiscernible over I.
In case
2;
(4.1)
there are four cases:
one is
~,
one is covered by
Lemma I, and the other two can be forced by amalgamating the first two, with three points in one Iclass and two in the other. In case (4.2) Lemma 1 applies unless fix
a, b
€
H with a
b
1
1
a, b
1
so a' (\ 'b
*b
+
J
+
b, and let C.s H be a second rctass.
1
claim is that a'A 'b{)C If
rapid contradiction.
{a.b} with a
is infinite.
b.
So
Our
If this set is empty one gets a
[a ' 1\ 'b /] CI = k with 0 < k < 00, then choose
with b e: (a n 'b)'.
Then a'(\ 'bn C = a' (\ 'b f\C
1
1
is adefinable, a contradiction.
'
Thus (4.2) is treated.
Next we claim: (5)
Suppose that every finite directed graph on which alence relation with n classes embeds in every tournament T of order
n lies in
Indeed consider K = T U I with
x'
is an equiv
1
for
x e: H.
Then
.A*.
an additional
Iclass.
We form
a directed graph (or amalgamation diagram with unspecified edge (x,y)) K
1
on the set I U {x,x ,y} U T U T 0
IxyT
1
or
IxyT '" H if 2
1
(x,y)
2
so that: is suitably oriented;
corresponding elements of T T are 1, 2 X 1 x, X
o
0
+
Iequivalent;
K  (X/I). 1
As usual it SUffices to check that the factors
K  {x} 1
and K  {y} 1
The Imprimitive Homogeneous Directed Graphs
embed in H.
In fact both K 1
embed in x'. by o
hypothesis. (6) A
[.
t • ~ .]
a
85
belongs to
.94*.
c
b
This is a fairly lengthy argument. We consider K = A U I with an additional
lclass. which we must embed in H.
I
We may suppose that
is either indiscernible over A, or of order 2. If
is indiscernible over A then take three
H. and fix a, c
in "a
I
+
x
+
E
lclasses C. C C 1, 2 C. Let p be the type over a,c defined by:
c", in other words the type of b. and let q be the type of lover {a,c}.
the elements of
Let B be the set of all realizations
of
p in C and let J be the set of all realizations of q in C 2. 1• Both Band J are infinite. We claim that each element of B is linked to J
by infinitely many edges with either orientation, so that
K embeds in H in this case. ferred orientation.
If this claim fails, then there is a pre
Now if p = q. then no automorphism of H carries
to (C,C and then as in the proof of Lemma 2. H is a 1,C2) 2.C1). wreath product. Now suppose that p * q. If c + I + a. then no auto(C,C
morphism carries a,c,C.C to c,a.C ,C • which gives a contradiction, 1 2 1 2 for example by taking x, E a'f'I c'rI C and mapping ac\x to 1 2 i cax x. (Here we apply Lemma 1.). 1 2 If type r
I is indiscernible over A and a and c realize the same over
I. then we consider also
our claim is that
tp(b/I).
If
tp(blI) = r. then
I'. 'I are not wreath products; the proof of Lemma 2
is readily adapted to this purpose.
So suppose that tp(b/I) = s
* r.
86
G.L. Cherlin
Then we perform the following amalgamation (with a unique solution): a
*
\ s · x.::...._; ·
(*)
b
c * with factors: a.
r
x.
~.2
.>. (As
5
s
:
b .
and
c.
r,s are asymmetric, the labelled edges should be read from left to
right.)
If abx or xbc ;s isomorphic to A, the corresponding factor
embeds in H by the case treated at the outset, and otherwise it suffices to examine When
'b or
b'.
is of order 2 and is not indiscernible over A, it suffices
to show that for any three
lclasses C,C
1,C2
in H and any i somorphi c
copy abc of A with a,c e: C and b e C , the two types realized by 1
are realized in C • Let q be the type rea 1i zed by one element of 2
over a,c.
If q is either
"a
+
x
+
c" or
"c
v
x
v
e", then this
was done in the course of the argument above, and in the remaining cases it suffices either to look at x'
or
'x
for
x
e:
C , or else to amal2
gamate in the manner of (*). using factors whose elements lie ;n the appropriate classes.
This completes the proof of (6).
After these preparations we can turn directly to the proof that is robust.
By (4)
I c ~* n
for all finite
n.
Next we claim:
**
87
The Imprimitive Homogeneous Directed Graphs
Arbitrarily large tournaments T are in ~*.
(7)
Equivalently, if H* is the homogeneous directed graph associated with .54*, then we claim that H*/1
is infinite.
On the basis of (4,6)
we know that H* is not a wreath product, and that its 1classes are infinite.
By our work so far, if
for some
IH*/11
is finite then H* ~ n * I~
n.
But this means that every finite directed graph K on which equivalence relation with n+1
classes embeds in H.
so as to minimize the value of
n here.
robust.
A'
Let
choice of
n, the ~I*generic directed graph is again
n+1
robust
x e: H, x' is
be the amalgamation class associated with x' .
every finite directed graph K on which with
A
Choose
Observe that for
1 is an
n * I"".
By our Thus
1 is an equivalence relation
classes embeds in x', and hence by (5), every tournament of lies in ~ *, a contradiction.
order n+1
It remains only to prove: (*)
Q e:~*. We consider K = I UQ with
cernible over
Q, or of order
sults so far either embeds Thus if
K embeds in
omits Q, then it embeds in H*, and hence
H, as claimed.
This argument applies in particular if
has order two, and both
I U {b,d} are isomorphic with
amalgamate __0 U {ik,j}
for
k = 1,2
This can be set up so that neither is isomorphic with
Q.
I
Q.
In the only case remaining, and (similarly)
directed graph H*, which by our re
Q (which is the present claim), or is semi
I U {a,c}
is indiscernible over
Label 0 a,b,c,d as before.
Jf *generic
We again consider the
generic.
2.
an 1class which is either indis
U {a,c}
Q. In this case just
so as to force
0 U {i ,i }
=
{i , j } U {a,c} nor 1 This completes the argument.
~
K.
1 2 {i , j } U {b,d}
2
88
G.L. Cherlin
REFERENCES
1.
C. Berline and G. Cherlin, "QE rings of prime characteristic," in Bull. Soc. Math. Belg. B 33 (1981), 317.
2.
P. Cameron, "Orbits of permutation groups on unordered sets II," J. London Math. Soc. 23 (1981), 249264.
3.
G. Cherlin, A. Harrington, and A. Lachlan, "l\ocategorical, ~ostable
structures," APAL (1985), 103135.
4.
G. Cherlin and A. Lachlan, "Stable finitely homogeneous structures," TAMS, to appear 1986.
5.
C.W. Henson, "Countable homogeneous relational systems and categorical theories," JSL 37 (1972), 494500.
6.
A. Lachlan, "Finite homogeneous simple digraphs," in Logic Colloquium 1981, J. Stern ed., NorthHolland, NY (1982), 189208.
7.
A. Lachlan, "On countable stable structures which are homogeneous for a finite relational language," Israel J. Math. 49 (1984), 69153.
8.
A. Lachlan, "Countable homogeneous tournaments," TAMS 284 (l984), 431461.
9.
A. Lachlan, S. Shelah, "Stable structures homogeneous for a binary language," Israel J. Math. 49 (1984), 155180.
10.
A. Lachlan, R. Woodrow, "Countable ultrahomogeneous graphs," TAMS 262 (1980), 5194.
11.
D. Saracino and C. Wood, "QE commutative rings," J. Symb. Logic 49 (1984), 644651.
12.
D. Saracino and C. Wood, "QE nil2 groups of exponent 4," J.A1g. 76 (1982), 337382.
13.
J. Schmer1, "Countable homogeneous partially ordered sets," Alg. Univ. 9 (1979), 317321.
14.
T. Skolem, "Logi schkombi natori sche Untersuchungen tiber di e Erful1barkeit and Beweisbarkeit mathematischen Satze nebst einem Theorem tiber di chte Mengen, II Skriften Vitenskapsakad. Kri sti ana 4 (1920), 136, §4.