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

Stefan Felsner
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin

Jens Gustedt
Fachbereich Mathematik
Technische Universität Berlin
Str. des 17. Juni 136 MA 611, D-10623 Berlin

Michel Morvan
LIAFA Université Paris 7 Denis Diderot
Case 7014 - 2, place Jussieu, F-75251 Paris Cedex 05

Report B 98-07
April 1998

We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known.

1. The bijections between maximal chains in the antichain lattice A (P) and the linear extension of P.
2. A bijection between maximal chains in the lattice of maximal antichains AM (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 characterize 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). Let SM (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.

Get the report here or by anonymous ftp: 
File:   pub/reports/