Dilworth's Theorem for Interval Orders

As remarked previously, we do not yet have an efficient process for determining the width of a poset and a minimum partition into chains. For interval orders, there is indeed a simple way to find both. The explanation is just to establish a connection with coloring of interval graphs as discussed in .

Let \(\PXP\) be an interval order and let \(\{[a_x,b_x]:x\in X\}\) be intervals of the real line so that \(x\lt y\) in \(\bfP\) if and only \(b_x\lt a_y\). Then let \(\bfG\) be the interval graph determined by this family of intervals. Note that if \(x\) and \(y\) are distinct elements of \(X\), then \(x\) and \(y\) are incomparable in \(\bfP\) if and only if \(xy\) is an edge in \(\bfG\). In other words, \(\bfG\) is just the incomparability graph of \(\bfP\).

Recall from that interval graphs are perfect, , \(\chi(\bfG)=\omega(\bfG)\) for every interval graph \(\bfG\). Furthermore, you can find an optimal coloring of an interval graph by applying first fit to the vertices in a linear order that respects left end points. Such a coloring concurrently determines a partition of \(\bfP\) into chains.

In fact, if you want to skip the part about interval representations, take any linear ordering of the elements as \(x_1\), \(x_2,\dots,x_n\) so that \(i\lt j\) whenever \(D(x)\) is a proper subset of \(D(y)\). Then apply First Fit with respect to chains. For example, using the \(10\) point interval order illustrated in , here is such a labeling: \[\begin{aligned}x_1 \amp=g \amp x_2 \amp=f \amp x_3 \amp=c \amp x_4 \amp=d \amp x_5 \amp=h \\ x_6 \amp=a \amp x_7 \amp=j \amp x_8 \amp=b \amp x_9 \amp=i \amp x_{10} \amp=e\end{aligned}\]

Now apply the First Fit algorithm to the points of \(\bfP\), in this order, to assign them to chains \(C_1\), \(C_2,\dots\). In other words, assign \(x_1\) to chain\(C_1\). Thereafter if you have assigned points \(x_1\), \(x_2,\dots,x_i\) to chains, then assign \(x_{i+1}\) to chain \(C_j\) where \(j\) is the least positive integer for which \(x_{i+1}\) is comparable to \(x_k\) whenever \(1\le k\le i\) and \(x_k\) has already been assigned to \(C_j\). For example, this rule results in the following chains for the interval order \(\bfP\) shown in . \[\begin{aligned}C_1 \amp = \{g,h,b\} \\ C_2 \amp = \{f,a,e\} \\ C_3 \amp = \{c,d\} \\ C_4 \amp = \{j\} \\ C_5 \amp = \{i\}\end{aligned}\] In this case, it is easy to see that the chain partition is optimal since the width of \(\bfP\) is \(5\) and \(A=\{a,b,d,i,j\}\) is a \(5\)-element antichain.

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