Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices

Abstract. We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders dened on the ground set of P. Two bijections of this type have been known: (1) The bijection between maximal chains in the antichain lattice A(P) and the linear extensions of P. (2) A bijection between maximal chains in the lattice of maximal antichains A M (P) and minimal interval extensions of P. We discuss two approaches to associate interval orders to chains in A(P). This leads to new bijections generalizing Bijections 1 and 2. As a consequence we char-acterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P. Seeking for a way of representing interval reductions of P by chains we came up with the separation lattice S(P). Chains in this lattice encode an interesting sub-class of interval reductions of P. Let S M (P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations the above bijection specializes to a bijection which nicely complements 1 and 2. (3) A bijection between maximal chains in the lattice of maximal separations S M (P) and minimal interval reductions of P