2

EXTENDED INTRODUCTION

structure under consideration acts transitively on any family of isomorphic

connected subsets of size fc, and similarly for fc-CS-homogeneity. In any

case when k = 1 all the notions (k-transitivity or Ar-homogeneity in either

sense) are equivalent, and then we say that (M, ) is transitive.

1.2 Cycle-free partial orders

The notion of a cycle-free partial order (CFPO) was first proposed (as far

as we know) by Rubin in [23]. (Actually there was an earlier definition in

[12], but it leads to a very different class of partial orders from those we wish

to consider, and was devised for other purposes, so we disregard it here).

The main purpose of his monograph was an analysis of the reconstruction

problem for trees, where by a tree (or 'semilinear order') is understood

a partial order in which any two elements have a common lower bound,

and the set of lower bounds of any single element is linearly ordered. The

main question addressed was 'for a tree T, how much information does

its automorphism group Aut(T) provide about the structure of TV His

particular reason for introducing CPFOs was that he felt that they formed

a wider class to which similar reconstruction methods should applicable.

The intuition behind the definition of a tree is that it should be a par-

tially ordered set which may branch as we move upwards through it, but

never on going downwards. (Often semilinear orders which branch down-

wards rather than upwards are considered; for these the theory is exactly

the same, but under the converse relation). The corresponding intuition

for CFPOs is that here one may branch either upwards or downwards, and

repeatedly, but no return to one's starting point is allowed. The natural

definition of CFPO as proposed by Rubin [23] in order to capture this idea

was for it to be a partial order in which for any sequence ao, a i , . . . , a

n

_i

of points for which each a,- and a,+i are comparable, and ao and a

n

_i are

also comparable, there are i and j such that j / %, i + 1, (even mod n) for

which a, a,- a,+i or a»+i aj a,-. See figure 1.1.

Unfortunately this definition turns out to be inadequate as it stands,

since it rules out even the five-element partial order shown in figure 1.2.

Fig. 1.1.