# The Structure of \(k\)-\(CS\)- Transitive Cycle-Free Partial Orders

Share this page
*Richard Warren*

The class of cycle-free partial orders (CFPOs) is defined,
and the CFPOs fulfilling a natural transitivity assumption, called
\(k\)-connected set transitivity (\(k\)-\(CS\)-transitivity), are analyzed in
some detail. Classification in many of the interesting cases is
given. This work generalizes Droste's classification of the countable
\(k\)-transitive trees (\(k \geq 2\)). In a CFPO, the structure can branch
downwards as well as upwards, and can do so repeatedly (though it
never returns to the starting point by a cycle). Mostly it is assumed
that \(k \geq 3\) and that all maximal chains are finite. The main
classification splits into the sporadic and skeletal cases. The former
is complete in all cardinalities. The latter is performed only in the
countable case. The classification is considerably more complicated
than for trees, and skeletal CFPOs exhibit rich, elaborate and rather
surprising behavior.

Features:

- Lucid exposition of an important generalization of Droste's work
- Extended introduction clearly explaining the scope of the memoir
- Visually attractive topic with copious illustrations
- Self-contained material, requiring few prerequisites

#### Table of Contents

# Table of Contents

## The Structure of $k$-$CS$- Transitive Cycle-Free Partial Orders

- Contents vii8 free
- 1 Extended Introduction 112 free
- 2 Preliminaries 2536
- 3 Properties of k-CS-transitive CFPOs 4354
- 4 Constructing CFPOs 6475
- 5 Characterization and Isomorphism Theorems 92103
- 6 Classification of skeletal CFPOs (Part 1) 112123
- 6.1 Introduction 112123
- 6.2 Case A: ↑Ram(M) = ↓Ram(M) 112123
- 6.3 Case B: ↑Ram(M)∩↓Ram(M) = φand Ram(M) is dense 115126
- 6.4 Covering orders 118129
- 6.5 Case C: Fully covered cycle-free partial orders 119130
- 6.6 Case D: Partially covered cycle-free partial orders 121132
- 6.7 Subcase D1: The cycle-free partial orders D[sup(d,u,u')][sub(σ)] 123134
- 6.8 Subcase D2: The cycle-free partial orders e[sup(d,u,u')][sub(σ)] 127138
- 6.9 Subcase D3: The cycle-free partial orders F[sup(d,u,u')][sub(σ,z)] 130141
- 6.10 Summary 132143

- 7 Classification of skeletal CFPOs (Part 2) 134145
- Appendix: Sporadic Cycle-free Partial Orders 150161