Interval dimension of a partially ordered set

Let $P = ( X _ { P } , < _ { P } )$ be a partially ordered set. Its interval dimension $\operatorname{Idim}( P )$ is the least $k$ such that there are interval extensions $Q _ { 1 } , \dots , Q _ { k }$ of $P$ such that for $x , y \in X _ { P }$ one has $x <_P y$ exactly if $x <_{ Q _ { i }} y$ for all $1 \leq i \leq k$. An interval extension of $P$ is an extension $Q = ( X _ { P } , <_{ Q} )$ of $P$ (i.e., $x <_P y$ implies $x < _{Q} y$), such that $Q$ is an interval order. Since every linear extension of $P$ is an interval extension, the interval dimension is related to the dimension $\dim ( P )$ (cf. Dimension of a partially ordered set) by the inequality

\begin{equation*} \operatorname { Idim } ( P ) \leq \operatorname { dim } ( P ). \end{equation*}

For partially ordered sets $P = ( X _ { P } , < _ { P } )$ and $Q = ( Y _ { Q } , < _ { Q } )$ one says that $P$ has an interval representation on $Q$ if there are mappings $L : X _ { P } \rightarrow Y _ { Q }$ and $U : X _ { P } \rightarrow Y _ { Q }$, such that

1) $L ( x ) <_QU ( x )$, i.e, $[ L ( x ) , U ( x ) ]$ is a non-degenerate interval of $Q$ for each $x \in X _ { P }$;

2) $U ( x _ { 1 } ) \leq_{Q} L ( x _ { 2 } )$ exactly if $x _ { 1 } <_{P} x _ { 2 }$. The inequality $\operatorname { Idim } ( P ) \leq \operatorname { dim } ( Q )$ holds for any two partially ordered sets $P$ and $Q$ such that $P$ has an interval representation on $Q$. There are partially ordered sets $Q$ with the property that $P$ has an interval representation on $Q$ and $\operatorname { Idim } ( P ) = \operatorname { dim } ( Q )$. For the most notable construction of such a $Q$, define $\operatorname{Pred} ( x ) = \{ y : y <_{P} x \}$, $\operatorname { Succ } ( x ) = \{ y : x <_ P y \}$ and $\operatorname{PredSucc}( x ) = \{ y : y <_{P} z \ \text { for allz } \in \operatorname { Succ } ( x ) \}$. Let $\operatorname { PrSu } ( P )$ denote the inclusion ordering on the set $\{ \operatorname { Pred } ( x ) , x \in X _ { P } \} \cup \{ \operatorname { Pred } \operatorname { Succ } ( x ) , x \in X _ { P } \}$. It can be shown that $P$ has an interval representation on $\operatorname { PrSu } ( P )$, that $\operatorname { Idim }( P ) = \operatorname { dim } ( \operatorname { PrSu } ( P ) )$, and that in some sense $\operatorname { PrSu } ( P )$ is the smallest partially ordered set admitting an interval representation of $P$, see [a3].

The concept lattice $\mathcal{C} ( P )$ is the lattice completion of $\operatorname { PrSu } ( P )$. Therefore $\mathcal{C} ( P )$ admits an interval representation of $P$, and again $\operatorname { ldim } ( P ) = \operatorname { dim } ( \mathcal{C} ( P ) )$. It can be shown that every lattice $L$ such that $P$ has an interval representation on $L$ contains $\mathcal{C} ( P )$ as suborder, see [a5].

The mapping $P \rightarrow \operatorname { PrSu } ( P )$ 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 $\operatorname { PrSu } ( P )$. The fastest reduction [a4] avoids this step and has time complexity $O ( n ^ { 2 } )$. The decision problem for $ \operatorname{Idim}( P ) \leq k$ is $\cal N P$-complete for every $k > 3$ (cf. also Complexity theory).

Characterization of $3$-interval irreducible partially ordered sets.

A $3$-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 $3$-interval irreducible partially ordered sets. S. Felsner [a3] proved that every $3$-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 $3$-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 $3$-interval irreducible partially ordered set. Both parts of this work depend deeply on the list of $3$-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 $\operatorname { dim } ( P ) \leq \operatorname { max } \{ 2 , | A | \}$, where $A$ 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 $G = ( V , E )$, let $\operatorname{dim} (G )$ be the least $k$ such that there are linear orders $L _ { 1 } , \ldots , L _ { k }$ on $V$ such that for every edge $e = \{ x , y \}$ and every vertex $z \notin \{ x , y \}$ there is an $L_i$ with $x , y <_{ i} z$. The incidence poset of $G$ is the partially ordered set $P _ { G } = ( V \cup E , < )$, where the order relation takes a vertex $v$ below an edge $e$ if $v \in e$. It can be shown that $\operatorname { dim } ( G ) = \operatorname { Idim } ( P _ { G } )$.

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, "$3$-interval irreducible partially ordered sets" Order , 11 (1994) pp. 97–125
[a4]	T. Ma, J. Spinrad, "An $O ( n ^ { 2 } )$ time algorithm for the $2$-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