Homogeneous Directed Graphs. The Imprimitive Case

Homogeneous Directed Graphs. The Imprimitive Case

Logic Colloquium '85 Edited by The Paris Logic Group © Elsevier Science Publishers B.V. (North-Holland), 1987 HOMOGENEOUS DIRECTED GRAPHS. 67 THE I...

707KB Sizes 1 Downloads 15 Views

Logic Colloquium '85 Edited by The Paris Logic Group © Elsevier Science Publishers B.V. (North-Holland), 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 Ro-categorical, 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 83-01806 and INT-8313363.]

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-

L-structure

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: 2-type). imprimitive (carrying a nontrivial

a-definable 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 3-types 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 2-tournaments (these are tournaments partitioned into two distinguished subsets).

In dealing with directed graphs it may be

convenient to deal with 3-tournaments. allowing in addition three 2-types to be realized between distinct components (as opposed to two realized in a given component).

have worked out the classification of the

n-tournaments 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

2-types, 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 2-types 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 2-types 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 4-cycle 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(q-l) 2-types.)

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 I-classes 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 I-classes, 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 2-types (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 8-10 is

G.L. Cherlin

74

both straightforward and well known.

It remains to discuss examples 4-6.

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 back-and-forth 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) = a3-i' while for (Yi)

= a(y)i

(Zi)

= a(z)3-i

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 ••..• n-l} (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(n-l)·. where L(n-l)

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 I-classes, 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 I-imprimitive 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

r-equtva 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 1-equivalent 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 I-class 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

I-classes 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 I-classes 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 I-classes 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' '" In-L) * 1

(1)

00 •

For

n

Lemmas 1 and 2 that x'

has infinite

i-classes 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 i-class, 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

l-classes;

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 I-class, 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 I-class;

=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.n-n.

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 I-class 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 l-class. 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 I-class 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 r-ctass.

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 a-definable, 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

I-class.

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

+

I-equivalent;

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

l-class. 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

l-classes 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

l-classes 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 1-classes 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 1-class 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), 3-17.

2.

P. Cameron, "Orbits of permutation groups on unordered sets II," J. London Math. Soc. 23 (1981), 249-264.

3.

G. Cherlin, A. Harrington, and A. Lachlan, "l\o-categorical, ~o-stable

structures," APAL (1985), 103-135.

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), 494-500.

6.

A. Lachlan, "Finite homogeneous simple digraphs," in Logic Colloquium 1981, J. Stern ed., North-Holland, NY (1982), 189-208.

7.

A. Lachlan, "On countable stable structures which are homogeneous for a finite relational language," Israel J. Math. 49 (1984), 69-153.

8.

A. Lachlan, "Countable homogeneous tournaments," TAMS 284 (l984), 431-461.

9.

A. Lachlan, S. Shelah, "Stable structures homogeneous for a binary language," Israel J. Math. 49 (1984), 155-180.

10.

A. Lachlan, R. Woodrow, "Countable ultrahomogeneous graphs," TAMS 262 (1980), 51-94.

11.

D. Saracino and C. Wood, "QE commutative rings," J. Symb. Logic 49 (1984), 644-651.

12.

D. Saracino and C. Wood, "QE nil-2 groups of exponent 4," J.A1g. 76 (1982), 337-382.

13.

J. Schmer1, "Countable homogeneous partially ordered sets," Alg. Univ. 9 (1979), 317-321.

14.

T. Skolem, "Logi sch-kombi 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), 1-36, §4.