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.
Tractability.
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
.
References
[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, "![]() |
[a4] | T. Ma, J. Spinrad, "An ![]() ![]() |
[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. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interval_dimension_of_a_partially_ordered_set&oldid=50129