CYCLE-FREE PARTIAL ORDERS 3
Fig. 1.2.
With n = 4 the a,- shown constitute a cycle, and so since non-adjacent a,s
are incomparable, this is not a CFPO according to the definition. A limited
class of non-trees does satisfy the definition; for instance the partial order
shown in figure 1.3. In fact a CFPO in our sense (given below) fulfils the
above definition if and only if there are no four points ao, a\y a^, as related
in precisely the same way as in figure 1.2.
Instead of living with this restriction, we prefer to modify the definition
so as to capture the class which it appears was intended in the first place.
Partly this is because it seems likely that it is in some sense a maximal class
to which Rubin's reconstruction methods for trees may apply. Specifically
it will allow us sufficient freedom to carry out 'piecewise patching', meaning
that we may glue together isomorphisms between (convex) pieces so that
their union will be an automorphism.
The definition of CFPO is given in terms of a suitable completion,
called the 'Dedekind-MacNeille completion' (or sometimes just 'Dedekind-
completion' for short) of the original partial order. As motivation for taking
Fig. 1.3.
Previous Page Next Page