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.
Previous Page Next Page