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

Stefan Felsner 1 Jens Gustedt 2 Michel Morvan
2 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 bijection between maximal chains in the antichain lattice $AA(P)$ and the linear extensions 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 $AA(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 $SL(P)$. Chains in this lattice encode an interesting subclass of interval reductions of $P$. Let $SLM(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 $\SLM(P)$ and minimal interval reductions of $P$.
Type de document :
Article dans une revue
Order, Springer Verlag, 1999, 15 (3), pp.221-246
Liste complète des métadonnées

https://hal.inria.fr/inria-00098826
Contributeur : Jens Gustedt <>
Soumis le : mardi 26 septembre 2006 - 08:38:55
Dernière modification le : dimanche 20 mai 2018 - 20:20:10

Identifiants

  • HAL Id : inria-00098826, version 1

Collections

Citation

Stefan Felsner, Jens Gustedt, Michel Morvan. Interval Reductions and Extensions of Orders : Bijections to Chains in Lattices. Order, Springer Verlag, 1999, 15 (3), pp.221-246. 〈inria-00098826〉

Partager

Métriques

Consultations de la notice

158