Theorem 6.29. Fishburn’s Theorem.
Let \(\PXP\) be a poset. Then \(\bfP\) is an interval order if and only if it excludes \(\bftwo+\bftwo\text{.}\)
Section 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 \(\PXP\) 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 \(\reals\) so that for all \(x\text{,}\) \(y\in X\text{,}\) \(x\lt y\) in \(P\) if and only if \(b_x\lt a_y\) in \(\reals\text{.}\) We call \(I\) an interval representation of \(\bfP\text{,}\) or just a representation for short. For brevity, whenever we say that \(I\) is a representation of an interval order \(\PXP\text{,}\) we will use the alternate notation \([a_x,b_x]\) for the closed interval \(I(x)\text{.}\) Also, we let \(|I(x)|\) denote the length of the interval, i.e., \(|I(x)|=b_x-a_x\text{.}\) Returning to the poset \(\bfP_3\text{,}\) the representation shown in Figure 6.28 shows that it is an interval order.
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)\text{.}\) We even allow degenerate intervals, i.e., those of the form \([a,a]\text{.}\) 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 \(\bfn\) (for \(n\geq 1\) an integer), we mean the chain with \(n\) points. More precisely, we take the ground set to be \(\{0,1,\dots,n-1\}\) with \(i \lt j\) in \(\bfn\) if and only if \(i\lt
j\) in \(\ints\text{.}\) If \(\PXP\) and \(\QYQ\) are posets with \(X\) and \(Y\) disjoint, then \(\bfP+\bfQ\) is the poset \(\bfR=(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\text{.}\) Thus, \(\bfn+\bfm\) consists of a chain with \(n\) points and a chain with \(m\) points and no comparabilities between them. In particular, \(\bftwo+\bftwo\) can be viewed as a four-point poset with ground set \(\{a,b,c,d\}\) and \(a\lt b\) and \(c\lt d\) as the only relations (other than those required to make the relation reflexive).
Proof.
We show only that an interval order cannot contain a subposet isomorphic to \(\bftwo+\bftwo\text{,}\) deferring the proof in the other direction to the next section. Now suppose that \(\PXP\) is a poset, \(\{x,y,z,w\}\subseteq X\) and the subposet determined by these four points is isomorphic to \(\bftwo+\bftwo\text{.}\) We show that \(\bfP\) is not an interval order. Suppose to the contrary that \(I\) is an interval representation of \(\bfP\text{.}\) Without loss of generality, we may assume that \(x\lt y\) and \(z\lt w\) in \(P\text{.}\) Thus \(x\Vert w\) and \(z\Vert y\) in \(P\text{.}\) Then \(b_x\lt
a_y\) and \(b_z \lt a_w\) in \(\reals\) so that \(a_w \le b_x \lt a_y \le b_z\text{,}\) which is a contradiction.
Reading Questions Reading Questions
1.
Consider the interval representation of an interval order shown below. The intervals depicted as vertical lines are degenerate intervals of the form \([z,z]\text{.}\) List the elements that are less than \(m\) in this interval order.
2.
Consider the interval representation of an interval order shown below. The intervals depicted as vertical lines are degenerate intervals of the form \([z,z]\text{.}\) List the elements that are incomparable to \(f\) in this interval order.
3.
Consider the poset whose diagram is shown below. Explain why this poset is not an interval order.
You have attempted of activities on this page.
