6.6: Interval Orders

When we discussed Dilworth's Theorem, we commented that the algorithmic aspects would be deferred until later in the text. But there is one important class of orders for which the full solution is easy to obtain.

A poset \(P=(X,P)\) is called an interval order if there exists a function \(I\) assigning to each element \(x \in X\) a closed interval \(I(x)=[a_x,b_x]\) of the real line \(\mathbb{R}\) so that for all \(x, y \in X, x<y\) in \(P\) if and only if \(b_x<a_y\) in \(\mathbb{R}\). We call \(I\) an interval representation of \(P\), or just a representation for short. For brevity, whenever we say that \(I\) is a representation of an interval order \(P=(X,P)\), we will use the alternate notation \([a_x,b_x]\) for the closed interval \(I(x)\). Also, we let \(|I(x)|\) denote the length of the interval, i.e., \(|I(x)|=b_x−a_x\). Returning to the poset \(P_3\), the representation shown in Figure 6.28 shows that it is an interval order.

Figure 6.28. An interval order and its representation

Note that end points of intervals used in a representation need not be distinct. In fact, distinct points \(x\) and \(y\) from \(X\) may satisfy \(I(x)=I(y)\). We even allow degenerate intervals, i.e., those of the form \([a,a]\). On the other hand, a representation is said to be distinguishing if all intervals are non-degenerate and all end points are distinct. It is relatively easy to see that every interval order has a distinguishing representation.

As we shall soon see, interval orders can be characterized succinctly in terms of forbidden subposets. Before stating this characterization, we need to introduce a bit more notation. By \(n\) (for \(n \geq 1\) an integer), we mean the chain with \(n\) points. More precisely, we take the ground set to be \(\{0,1,…,n−1\}\) with \(i<j\) in \(\textbf{n}\) if and only if \(i<j\) in \(Z\). If \(\textbf{P}=(X,P)\) and \(\textbf{Q}=(Y,Q)\) are posets with \(X\) and \(Y\) disjoint, then \(\textbf{P}+\textbf{Q}\) is the poset \(\textbf{R}=(X \cup Y,R)\) where the partial order is given by \(z \leq w\) in \(R\) if and only if (a) \(z,w \in X\) and \(z \leq w\) in \(P\) or (b) \(z,w \in Y\) and \(z \leq w\) in \(Q\). Thus, \(\textbf{n}+\textbf{m}\) consists of a chain with \(n\) points and a chain with \(m\) points and no comparabilities between them. In particular, 2+2 can be viewed as a four-point poset with ground set \(\{a,b,c,d\}\) and \(a<b\) and \(c<d\) as the only relations (other than those required to make the relation reflexive).

Theorem 6.29. Fishburn's Theorem.

Let \(\textbf{P}=(X,P)\) be a poset. Then \(\textbf{P}\) is an interval order if and only if it excludes 2+2.

Proof

We show only that an interval order cannot contain a subposet isomorphic to 2+2, deferring the proof in the other direction to the next section. Now suppose that \(\textbf{P}=(X,P)\) is a poset, \(\{x,y,z,w\} \subseteq X\) and the subposet determined by these four points is isomorphic to 2+2. We show that \(\textbf{P}\) is not an interval order. Suppose to the contrary that \(I\) is an interval representation of \(\textbf{P}\). Without loss of generality, we may assume that \(x<y\) and \(z<w\) in \(\textbf{P}\). Thus \(x‖w\) and \(z‖y\) in \(\textbf{P}\). Then \(b_x<a_y\) and \(b_z<a_w\) in \(\mathbb{R}\) so that \(a_w \leq b_x<a_y \leq b_z\), which is a contradiction.