Interval reductions and extensions of orders: Bijections to chains in lattices (Q1304911)

In the algorithmic aspects of poset theory of importance in applications such as computer architecture and industrial engineering, it is known that certain types of posets, e.g., \(N\)-free posets, permit certain problems which are NP-complete in general to be phrased as polynomially complete problems in adjusted algorithms which take advantage of structural facts, e.g., the chain-meets-antichain property in the \(N\)-free case or the even more fundamental property that such (finite) posets can be manufactured entirely from singletons by use of the sum and ordinal (linear) sum operations. Important classes of orders of this ``useful'' type include the interval orders, and the ability to construct (existence of) bijections of interest between lattices associated with posets \(P\) and families of interval orders often implies an ability to construct algorithms which permit the solution of certain counting problems for these posets by transfer to equivalent problems for these lattices and thus via the relevant bijections to the particular class of interval orders and thus to a simple problem soluble in polynomial rather than some greater time. If \(P\) is a poset, the lattices of most interest in this paper are the antichain lattice \(A(P)\), the maximal antichain lattice \(A_M(P)\) and the separation lattice \(S(P)\) consisting of pairs of disjoint subsets \(I\) (an ideal) and \(F\) (a filter) with \(I<F\) \((x\in I,\;y\in F\) implies \(x<y)\), and \((I,F)\leq(I',F')\) if \(I\leq I'\), \(F\geq F'\). Via \(S(P)\) interval orders are characterized as those posets for which \(S(P)\) is a chain. Given that arbitrary orders are contained in ``minimal'' extension interval orders and contain ``maximal'' reduction interval orders, it is the business of this extensive paper to take a close look at this relationship in establishing the required connections between lattice structures and interval orders, thus incidentally making clear matters of ``purely theoretical'' interest as well. Following this path the authors are able to associate interval orders with chains in \(A(P)\) in two different ways, generalizing the bijection between maximal chains in \(A(P)\) and linear extensions of \(P\) and the bijection between maximal chains in \(A_M(P)\) and minimal interval extensions, while further consideration provides a bijection between maximal chains in the lattice of maximal separations \(S_M(P)\) and maximal interval reductions of \(P\) (not as in the abstract).