# 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