On extensions, linear extensions, upsets and downsets of ordered sets Original Research Article

We consider the problem of characterizing the set image of all extensions of an order P on a set of elements image where image, image and image is the number of extensions of the order. Initially, we describe two distinct characterizations of image. The first characterization is a one-to-one correspondence between extensions of P and pairs of upsets and downsets of certain suborders of image. The second one characterizes the extensions of P in terms of linear extensions and sequences of downsets. Both characterizations lead to algorithms that generate all the extensions of image. Further, we discuss the notion of passive pairs of an order. Based on it, we describe a third characterization of image and an algorithm that generates all the extensions of P in image amortized time per extension.