×

Extensions intervallaires minimales. (Minimal interval extensions). (French) Zbl 0734.06003

Summary: We consider the possible extensions of an ordering by interval orders. Under a finiteness assumption, we show that the minimal ones are in 1-1 correspondence with the maximal chains of the lattice of maximal antichains. From this, we deduce that the number of these extensions is a comparability invariant; we also show that the computation of this number is #P-complete. We show that a poset and its MacNeille completion have the same interval dimension; under some assumptions, it coincides with the least number of chains needed to generate the lattice of maximal antichains.

MSC:

06A06 Partial orders, general
68Q25 Analysis of algorithms and problem complexity