Interval Orders

When we discussed , 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\), \(y\in X\), \(x\lt y\) in \(P\) if and only if \(b_x\lt a_y\) in \(\reals\). We call \(I\) an interval representation of \(\bfP\), or just a representation for short. For brevity, whenever we say that \(I\) is a representation of an interval order \(\PXP\), 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(x)|=b_x-a_x\). Returning to the poset \(\bfP_3\), the representation shown in 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)\). We even allow degenerate intervals, , 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 \(\bfn\) (for \(n\geq 1\) an integer), we mean the chain with \(n\) points. \(\bfn\) 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\). If \(\PXP\) and \(\QYQ\) are posets with \(X\) and \(Y\) disjoint, then \(\bfP+\bfQ\) \(\bfP+\bfQ\) disjoint sum of posets 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\). 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).

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.