Title
Interval Reductions and Extensions of Orders:
Bijections to Chains in Lattices
Authors
-
Publication
extended abstract to appear FPSAC'98
Source
-
Classification
-
not available
Keywords
-
not available
-
-
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 AA(P) and the linear extensions of P.
(2) A bijection between maximal chains in the lattice of maximal
antichains AAM(P) and minimal interval extensions of P.
par
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.
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 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.par
(3) A bijection between maximal chains in the lattice of maximal
separations SM(P) and minimal interval reductions of P.
