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