Namespaces
Variants
Actions

Difference between revisions of "Interval dimension of a partially ordered set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 92 formulas out of 92 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200601.png" /> be a [[Partially ordered set|partially ordered set]]. Its interval dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200602.png" /> is the least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200603.png" /> such that there are interval extensions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200604.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200605.png" /> such that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200606.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200607.png" /> exactly if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200608.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i1200609.png" />. An interval extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006010.png" /> is an extension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006011.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006012.png" /> (i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006013.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006014.png" />), such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006015.png" /> is an [[Interval order|interval order]]. Since every linear extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006016.png" /> is an interval extension, the interval dimension is related to the dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006017.png" /> (cf. [[Dimension of a partially ordered set|Dimension of a partially ordered set]]) by the inequality
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,  
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006018.png" /></td> </tr></table>
+
Out of 92 formulas, 92 were replaced by TEX code.-->
  
For partially ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006020.png" /> one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006021.png" /> has an interval representation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006022.png" /> if there are mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006024.png" />, such that
+
{{TEX|semi-auto}}{{TEX|done}}
 +
Let $P = ( X _ { P } , &lt; _ { P } )$ be a [[Partially ordered set|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 &lt;_P  y$ exactly if $x &lt;_{ Q _ { i }} y$ for all $1 \leq i \leq k$. An interval extension of $P$ is an extension $Q = ( X _ { P } , &lt;_{ Q} )$ of $P$ (i.e., $x &lt;_P  y$ implies $x &lt; _{Q} y$), such that $Q$ is an [[Interval order|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|Dimension of a partially ordered set]]) by the inequality
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006025.png" />, i.e, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006026.png" /> is a non-degenerate interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006027.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006028.png" />;
+
\begin{equation*} \operatorname { Idim } ( P ) \leq \operatorname { dim } ( P ). \end{equation*}
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006029.png" /> exactly if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006030.png" />. The inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006031.png" /> holds for any two partially ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006033.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006034.png" /> has an interval representation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006035.png" />. There are partially ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006036.png" /> with the property that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006037.png" /> has an interval representation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006039.png" />. For the most notable construction of such a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006040.png" />, define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006043.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006044.png" /> denote the inclusion ordering on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006045.png" />. It can be shown that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006046.png" /> has an interval representation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006047.png" />, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006048.png" />, and that in some sense <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006049.png" /> is the smallest partially ordered set admitting an interval representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006050.png" />, see [[#References|[a3]]].
+
For partially ordered sets $P = ( X _ { P } , &lt; _ { P } )$ and $Q = ( Y _ { Q } , &lt; _ { 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
  
The concept lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006051.png" /> is the lattice completion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006052.png" />. Therefore <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006053.png" /> admits an interval representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006054.png" />, and again <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006055.png" />. It can be shown that every lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006056.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006057.png" /> has an interval representation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006058.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006059.png" /> as suborder, see [[#References|[a5]]].
+
1) $L ( x ) &lt;_QU ( x )$, i.e, $[ L ( x ) , U ( x ) ]$ is a non-degenerate interval of $Q$ for each $x \in X _ { P }$;
  
The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006060.png" /> 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.
+
2) $U ( x _ { 1 } ) \leq_{Q} L ( x _ { 2 } )$ exactly if $x _ { 1 } &lt;_{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 &lt;_{P} x \}$, $\operatorname { Succ } ( x ) = \{ y : x &lt;_ P y \}$ and $\operatorname{PredSucc}( x ) = \{ y : y &lt;_{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 [[#References|[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 [[#References|[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.===
 
===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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006061.png" />. The fastest reduction [[#References|[a4]]] avoids this step and has time complexity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006062.png" />. The decision problem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006063.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006064.png" />-complete for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006065.png" /> (cf. also [[Complexity theory|Complexity theory]]).
+
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 [[#References|[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 &gt; 3$ (cf. also [[Complexity theory|Complexity theory]]).
  
===Characterization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006066.png" />-interval irreducible partially ordered sets.===
+
===Characterization of $3$-interval irreducible partially ordered sets.===
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006068.png" />-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 [[#References|[a6]]] gave a complete list of bipartite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006069.png" />-interval irreducible partially ordered sets. S. Felsner [[#References|[a3]]] proved that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006070.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006071.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006072.png" />-interval irreducible partially ordered set. Both parts of this work depend deeply on the list of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006073.png" />-irreducible partially ordered sets for ordinary dimension.
+
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 [[#References|[a6]]] gave a complete list of bipartite $3$-interval irreducible partially ordered sets. S. Felsner [[#References|[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.===
 
===Tractability.===
In some cases, interval dimension is more tractable than dimension. Compare, for example, the forbidden-suborder characterization of the inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006074.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006075.png" /> is an anti-chain for ordinary dimension with the result for interval dimension.
+
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.
 
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 [[#References|[a2]]] and the references therein. For a [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006076.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006077.png" /> be the least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006078.png" /> such that there are linear orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006079.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006080.png" /> such that for every edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006081.png" /> and every vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006082.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006083.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006084.png" />. The incidence poset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006085.png" /> is the partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006086.png" />, where the order relation takes a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006087.png" /> below an edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006088.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006089.png" />. It can be shown that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006090.png" />.
+
There is also a beautiful connection with graph dimension, see [[#References|[a2]]] and the references therein. For a [[Graph|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 &lt;_{ i} z$. The incidence poset of $G$ is the partially ordered set $P _ { G } = ( V \cup E , &lt; )$, 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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.T. Trotter,  "Combinatorics and partially ordered sets: dimension theory" , John Hopkins Univ. Press  (1991)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Felsner,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006091.png" />-interval irreducible partially ordered sets"  ''Order'' , '''11'''  (1994)  pp. 97–125</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  T. Ma,  J. Spinrad,  "An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006092.png" /> time algorithm for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i120/i120060/i12006093.png" />-chain cover problem and related problems" , ''Proc. Second Annual ACM-SIAM Symp. Discr. Algebra''  (1991)  pp. 363–372</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Mitas,  "Interval representations on arbitrary ordered sets"  ''Discrete Math.'' , '''144'''  (1995)  pp. 75–95</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  W.T. Trotter,  "Stacks and splits of partially ordered sets"  ''Discrete Math.'' , '''35'''  (1981)  pp. 229–256</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  W.T. Trotter,  "Combinatorics and partially ordered sets: dimension theory" , John Hopkins Univ. Press  (1991)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  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)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  S. Felsner,  "$3$-interval irreducible partially ordered sets"  ''Order'' , '''11'''  (1994)  pp. 97–125</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  J. Mitas,  "Interval representations on arbitrary ordered sets"  ''Discrete Math.'' , '''144'''  (1995)  pp. 75–95</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  W.T. Trotter,  "Stacks and splits of partially ordered sets"  ''Discrete Math.'' , '''35'''  (1981)  pp. 229–256</td></tr></table>

Revision as of 16:56, 1 July 2020

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
How to Cite This Entry:
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
This article was adapted from an original article by S. Felsner (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article