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 2+2. As a consequence, we establish the other half of Fishburn's Theorem.

When \(P=(X,P)\) is an interval order and \(n\) is a positive integer, there may be many different ways to represent \(\textbf{P}\) using intervals with integer end points in \([n]\). 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 \(P=(X,P)\) and a subset \(S \subset X\), let \(D(S)=\{y \in X\): there exists some \(x \in S\) with \(y<x\) in \(P\)}. Also, let \(D[S]=D(S) \cup S\). When \(|S|=1\), say \(S=\{x\}\), we write \(D(x)\) and \(D[x]\) rather than \(D(\{x\})\) and \(D[\{x\}]\). Dually, for a subset \(S \subseteq X\), we define \(U(S)=\{y \in X\): there exists some \(x \in X\) with \(y>x\) in \(P\)}. As before, set \(U[S]=U(S) \cup S\). And when \(S=\{x\}\), we just write \(U(x)\) for \(\{y \in X:x<y\) in \(P\)}.

Let \(P=(X,P)\) be a poset. We start our procedure by finding the following subsets of the ground set: \(D=\{D(x):x \in X\}\). 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)\). In this case, we choose an element \(z \in D(x)−D(y)\) and an element \(w \in D(y)−D(x)\). It follows that the four elements in {\(x,y,z,w\)} form a subposet of \(P\) which is isomorphic to 2+2.

Our second case is that either \(D(x) \subseteq D(y)\) or \(D(y) \subseteq D(x)\) for all \(x,y \in X\). In this case, we will show that \(\textbf{P}\) is an interval order. Now find the family: \(\mathcal{U}=\{U(x):x \in X\}\). 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\).

Let \(d=|\mathcal{D}|\). 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}|\), so for now we assume that this statement is valid. Label the sets in \(\mathcal{D}\) and \(\mathcal{U}\) respectively as \(D_1, D_2,…,D_d\) and \(U_1, U_2,…,U_d\) so that

\(\emptyset = D_1 \subset D_2 \subset D_3 \subset \cdot \cdot \cdot \subset D_d\) and

\(U_1 \supset U_2 \cdot \cdot \cdot \supset U_{d-2} \supset U_{d-1} \supset \cdot \cdot \cdot \supset U_d = \emptyset\).

We form an interval representation \(I\) of \(\textbf{P}\) by the following rule: For each \(x \in X\), set \(I(x)=[i,j]\), where \(D(x)=D_i\) and \(U(x)=U_j\). 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<i\). 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.

Theorem 6.30.

If \(\textbf{P}\) is a poset excluding 2+2, then the following statements hold.

1. The number of down sets equals the number of up sets. That is, \(|\mathcal{D}|=|\mathcal{U}|\).
2. For each \(x \in X\), if \(I(x)=[i,j]\), then \(i \leq j\) in \(\mathbb{R}\).
3. For each \(x,y \in X\), if \(I(x)=[i,j]\) and \(I(y)=[k,l]\), then \(x<y\) in \(P\) if and only if \(j<k\) in \(\mathbb{R}\).
4. The integer \(d\) is the least positive integer for which \(\textbf{P}\) has an interval representation using integer end points from \([d]\). This representation is unique.

Consider the poset shown in Figure 6.31.

Figure 6.31. An interval order on 10 Points

Then \(d=5\) with \(D_1= \emptyset\), \(D_2=\{c\}\), \(D_3=\{c,f,g\}\), \(D_4=\{c,f,g,h\}\), and \(D_5=\{a,c,f,g,h,j\}\). Also \(U_1=\{a,b,d,e,h,i,j\}\), \(U_2=\{a,b,e,h,i,j\}\), \(U_3=\{b,e,i\}\), \(U_4=\{e\}\), and \(U_5= \emptyset\). So

\(I(a)=[3,4]\) \(I(b)=[4,5]\) \(I(c)=[1,1]\) \(I(d)=[2,5]\) \(I(e)=[5,5]\)

\(I(f)=[1,2]\) \(I(g)=[1,2]\) \(I(h)=[3,3]\) \(I(i)=[4,5]\) \(I(j)=[3,4]\)

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\). For the resulting poset, you will then find that \(D(j)=\{f,g\}\) and \(D(d)=\{c\}\). Therefore, the four points \(c, d, f\) and \(j\) form a copy of 2+2 in this modified poset.