Interval dimension of a partially ordered set
Let be a partially ordered set. Its interval dimension is the least such that there are interval extensions of such that for one has exactly if for all . An interval extension of is an extension of (i.e., implies ), such that is an interval order. Since every linear extension of is an interval extension, the interval dimension is related to the dimension (cf. Dimension of a partially ordered set) by the inequality
For partially ordered sets and one says that has an interval representation on if there are mappings and , such that
1) , i.e, is a non-degenerate interval of for each ;
2) exactly if . The inequality holds for any two partially ordered sets and such that has an interval representation on . There are partially ordered sets with the property that has an interval representation on and . For the most notable construction of such a , define , and . Let denote the inclusion ordering on the set . It can be shown that has an interval representation on , that , and that in some sense is the smallest partially ordered set admitting an interval representation of , see [a3].
The concept lattice is the lattice completion of . Therefore admits an interval representation of , and again . It can be shown that every lattice such that has an interval representation on contains as suborder, see [a5].
The mapping can be used to transform questions about interval dimensions of partially ordered sets into questions about dimensions. Two instances of this approach are given below.
Recognizing partially ordered sets of interval dimension two.
This problem can be reduced to recognition of partially ordered sets of dimension two. The bottleneck of the obvious approach is the construction of . The fastest reduction [a4] avoids this step and has time complexity . The decision problem for is -complete for every (cf. also Complexity theory).
Characterization of -interval irreducible partially ordered sets.
A -interval irreducible partially ordered set is a partially ordered set of interval dimension three whose interval dimension drops to two upon deletion of any element. This characterization problem was attacked in two steps. W.T. Trotter [a6] gave a complete list of bipartite -interval irreducible partially ordered sets. S. Felsner [a3] proved that every -interval irreducible partially ordered set is the reduced partial stack of a partially ordered set in Trotter's list and that a complete list of -interval irreducible partially ordered set is too complex to be given explicitly. In particular, every two-dimensional partially ordered set is a suborder of some -interval irreducible partially ordered set. Both parts of this work depend deeply on the list of -irreducible partially ordered sets for ordinary dimension.
In some cases, interval dimension is more tractable than dimension. Compare, for example, the forbidden-suborder characterization of the inequality , where is an anti-chain for ordinary dimension with the result for interval dimension.
Another example is the positive solution to the removable-pair problem. For ordinary dimension it is conjectured that every partially ordered set of at least three points contains a pair of points whose removal decreases the dimension by at most one. This conjecture remains one of the most tantalizing open problems in the field (1998). However, the interval dimension is reduced by at most one upon removal of any critical pair. The proof of this can be given by a straightforward construction.
There is also a beautiful connection with graph dimension, see [a2] and the references therein. For a graph , let be the least such that there are linear orders on such that for every edge and every vertex there is an with . The incidence poset of is the partially ordered set , where the order relation takes a vertex below an edge if . It can be shown that .
|[a1]||W.T. Trotter, "Combinatorics and partially ordered sets: dimension theory" , John Hopkins Univ. Press (1991)|
|[a2]||S. Felsner, W.T. Trotter, "Posets and planar graphs" J. Graph Theory (submitted) (ftp://ftp.inf.fu-berlin.de/pub/reports/tr-b-98-11.ps.gz)|
|[a3]||S. Felsner, "-interval irreducible partially ordered sets" Order , 11 (1994) pp. 97–125|
|[a4]||T. Ma, J. Spinrad, "An time algorithm for the -chain cover problem and related problems" , Proc. Second Annual ACM-SIAM Symp. Discr. Algebra (1991) pp. 363–372|
|[a5]||J. Mitas, "Interval representations on arbitrary ordered sets" Discrete Math. , 144 (1995) pp. 75–95|
|[a6]||W.T. Trotter, "Stacks and splits of partially ordered sets" Discrete Math. , 35 (1981) pp. 229–256|
Interval dimension of a partially ordered set. S. Felsner (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Interval_dimension_of_a_partially_ordered_set&oldid=17636