On extensions, linear extensions, upsets and downsets of ordered sets

AbstractWe consider the problem of characterizing the set ε(P) of all extensions of an order P on a set of elements E, where |E|=n, |P|=m and μ is the number of extensions of the order. Initially, we describe two distinct characterizations of ε(P). The first characterization is a one-to-one correspondence between extensions of P and pairs of upsets and downsets of certain suborders of P. 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 P. Further, we discuss the notion of passive pairs of an order. Based on it, we describe a third characterization of ε(P) and an algorithm that generates all the extensions of P in O(n) amortized time per extension