Skip to main content
Logo image

Applied Combinatorics

Section 6.7 Finding a Representation of an Interval Order

In this section, we develop an algorithm for finding an interval representation of an interval order. In fact, this algorithm can be applied to any poset. Either it will find an interval representation or it will find a subposet isomorphic to \(\bftwo+\bftwo\text{.}\) As a consequence, we establish the other half of Fishburn’s Theorem.
When \(\PXP\) is an interval order and \(n\) is a positive integer, there may be many different ways to represent \(\bfP\) using intervals with integer end points in \([n]\text{.}\) But there is certainly a least \(n\) for which a representation can be found, and here we see that the representation is unique. The discussion will again make use of the notation for down sets and up sets that we introduced prior to the proof of Dilworth’s Theorem. As a reminder, we repeat it here. For a poset \(\PXP\) and a subset \(S\subset X\text{,}\) let \(D(S) = \{y\in X:\) there exists some \(x\in S\) with \(y\lt x\) in \(P\}\text{.}\) Also, let \(D[S]=D(S)\cup S\text{.}\) When \(|S|=1\text{,}\) say \(S=\{x\}\text{,}\) we write \(D(x)\) and \(D[x]\) rather than \(D(\{x\})\) and \(D[\{x\}]\text{.}\) Dually, for a subset \(S\subseteq X\text{,}\) we define \(U(S) = \{y\in X:\) there exists some \(x\in X\) with \(y>x\) in \(P\}\text{.}\) As before, set \(U[S]=U(S)\cup S\text{.}\) And when \(S=\{x\}\text{,}\) we just write \(U(x)\) for \(\{y\in X:x\lt y\) in \(P\}\text{.}\)
Let \(\PXP\) be a poset. We start our procedure by finding the following subsets of the ground set: \(\mathcal{D} = \{D(x):x\in X\}\text{.}\) We then distinguish two cases. In the first case, there are distinct elements \(x\) and \(y\) for which \(D(x)\nsubseteq D(y)\) and \(D(y)\nsubseteq D(x)\text{.}\) In this case, we choose an element \(z\in D(x)-D(y)\) and an element \(w\in D(y)-D(x)\text{.}\) It follows that the four elements in \(\{x,y,z,w\}\) form a subposet of \(\bfP\) which is isomorphic to \(\bftwo+\bftwo\text{.}\)
Our second case is that either \(D(x)\subseteq D(y)\) or \(D(y)\subseteq D(x)\) for all \(x,y\in X\text{.}\) In this case, we will show that \(\bfP\) is an interval order. Now find the family: \(\mathcal{U} = \{U(x):x\in X\}\text{.}\) In this case, it is easy to see that we will always have either \(U(x)\subseteq U(y)\) or \(U(y)\subseteq U(x)\) for all \(x,y\in X\text{.}\)
Let \(d=|\mathcal{D}|\text{.}\) In the exercises, we will provide (actually in doing your homework, you will provide) the details for backing up the following statement: \(|\mathcal{U}|=|\mathcal{D}|\text{,}\) so for now we assume that this statement is valid. Label the sets in \(\mathcal{D}\) and \(\mathcal{U}\) respectively as \(D_1\text{,}\) \(D_2,\dots,D_d\) and \(U_1\text{,}\) \(U_2,\dots,U_d\) so that
\begin{equation*} \emptyset= D_1\subset D_2\subset D_3\subset\dots\subset D_d \quad\text{and} \end{equation*}
\begin{equation*} U_1\supset U_{2}\cdots \supset U_{d-2}\supset U_{d-1}\supset\dots\supset U_d =\emptyset. \end{equation*}
We form an interval representation \(I\) of \(\bfP\) by the following rule: For each \(x\in X\text{,}\) set \(I(x)=[i,j]\text{,}\) where \(D(x)=D_i\) and \(U(x)=U_j\text{.}\) It is not immediately clear that this rule is legal, i.e., it might happen that applying the rule results in values of \(i\) and \(j\) for which \(j\lt i\text{.}\) But again, as a result of the exercises, we will see that this never happens. This collection of exercises is summarized in the following theorem.
Consider the poset shown in Figure 6.31.
Figure 6.31. An interval order on 10 Points
Then \(d= 5\) with \(D_1=\emptyset\text{,}\) \(D_2=\{c\}\text{,}\) \(D_3=\{c,f,g\}\text{,}\) \(D_4=\{c,f,g,h\}\text{,}\) and \(D_5=\{a,c,f,g,h,j\}\text{.}\) Also \(U_1=\{a,b,d,e,h,i,j\}\text{,}\) \(U_2=\{a,b,e,h,i,j\}\text{,}\) \(U_3=\{b,e,i\}\text{,}\) \(U_4=\{e\}\text{,}\) and \(U_5=\emptyset\text{.}\) So
\begin{align*} I(a) \amp = [3,4] \amp I(b) \amp = [4,5] \amp I(c) \amp = [1,1] \amp I(d) \amp = [2,5] \amp I(e) \amp = [5,5]\\ I(f) \amp = [1,2] \amp I(g) \amp = [1,2] \amp I(h) \amp = [3,3]\amp I(i) \amp = [4,5]\amp I(j) \amp = [3,4] \end{align*}
To illustrate the situation where this process can be used to determine when a poset is not an interval order, consider again the poset shown in Figure 6.31. Erase the line joining points \(c\) and \(j\text{.}\) For the resulting poset, you will then find that \(D(j)=\{f,g\}\) and \(D(d)=\{c\}\text{.}\) Therefore, the four points \(c\text{,}\) \(d\text{,}\) \(f\) and \(j\) form a copy of \(\bftwo+\bftwo\) in this modified poset.