direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1998

Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices
Zitatschlüssel Report-590-1998
Autor Felsner, Stefan and Gustedt, Jens and Morvan, Michel
Jahr 1998
Nummer 590
Notiz extended abstract to appear FPSAC'98
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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:\par (1) The bijection between maximal chains in the antichain lattice $Å(P)$ and the linear extensions of $P$. (2) A bijection between maximal chains in the lattice of maximal antichains $ÅM(P)$ and minimal interval extensions of $P$. \par We discuss two approaches to associate interval orders to chains in $Å(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$. \par 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 subclass 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.\par (3) A bijection between maximal chains in the lattice of maximal separations $S_M(P)$ and minimal interval reductions of $P$.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag