Abstract

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

adopted.

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].

IX