In this memoir we define the class of 'cycle-free partial orders' (CFPOs),
and analyse in some detail the members of this class which fulfil a natu-
ral transitivity assumption, called '^-connected-set transitivity' (k CS-
transitivity for short) where k is a positive integer. We provide classifica-
tions in many of the interesting cases; though in all but the simplest it is
unrealistic to expect a complete answer for uncountable structures.
This work is a natural generalization of Droste's paper [5], where he
provided a full classification of the countable, ib-transitive trees. In a cycle-
free partial order the structure is allowed to branch downwards as well as
upwards, and to do this repeatedly, (though never to return to the starting
point by a cycle). This restriction means that the all-important 'piecewise
patching' property is retained. The added freedom on branching means
however that the obvious notion of fc-transitivity as in [5] is inappropri-
ate here, and it is for this reason that the weaker ck CS-transitivity' is
Chapter 1 provides an extended introduction which should make clear
the main scope of the work, and also set it in context. The remaining chap-
ters fill in the details. In Chapter 2 we spell out the necessary preliminaries
concerning the Dedekind-MacNeille completion, and the consequent defi-
nition of cycle-free partial order, together with information about paths,
cones, and convexity. After some general discussion in Chapter 3 of k CS-
transitivity, we concentrate for the remainder of the memoir on the special
case in which all maximal chains are finite, where it quickly emerges (in
non-trivial instances, and assuming k CS-transitivity for some k 2)
that they have length at most 2, (so can be viewed as bipartite graphs if
one wishes). Under appropriate assumptions, this case is then shown to
subdivide into what we call the 'sporadic' and 'skeletal' cases. The sporadic
case is straightforward and admits a full classification, irrespective of car-
dinality, detailed in the appendix. Most of the paper is concerned with the
skeletal case; here we give a full classification of countable k CS-transitive
skeletal CFPOs (k = 3,4). Although the classification is reasonably nat-
ural, it is considerably more complicated than for trees (even those with
infinite chains), and these structures exhibit rich, quite elaborate, and one
can say, rather surprising behaviour.
Similar results about cycle-free partial orders which contain infinite
chains will be presented in [4].
Previous Page Next Page