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
email: felsner@inf.fu-berlin.de

Jens Gustedt
Fachbereich Mathematik
Technische Universität Berlin
Str. des 17. Juni 136 MA 611, D-10623 Berlin
email: gustedt@math.tu-berlin.de

Michel Morvan
LIAFA Université Paris 7 Denis Diderot
Case 7014 - 2, place Jussieu, F-75251 Paris Cedex 05
email: morvan@liafa.jussieu.fr

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 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 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 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.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-98-07.ps.gz