6.8: Dilworth's Theorem for Interval Orders
- Page ID
- 97894
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 Chapter 5.
Let \(\textbf{P}=(X,P)\) be an interval order and let \(\{[a_x,b_x]:x \in X\}\) be intervals of the real line so that \(x<y\) in \(\textbf{P}\) if and only \(b_x<a_y\). Then let \(\textbf{G}\) 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 \(\textbf{P}\) if and only if \(xy\) is an edge in \(\textbf{G}\). In other words, \(\textbf{G}\) is just the incomparability graph of \(\textbf{P}\).
Recall from Chapter 5 that interval graphs are perfect, i.e., \(\chi(\textbf{G})=ω(\textbf{G})\) for every interval graph \(\textbf{G}\). 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 \(\textbf{P}\) 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,…,x_n\) so that \(i<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 Figure 6.31, here is such a labeling:
\(x_1=g\) \(x_2=f\) \(x_3=c\) \(x_4=d\) \(x_5=h\)
\(x_6=a\) \(x_7=j\) \(x_8=b\) \(x_9=i\) \(x_{10}=e\)
Now apply the First Fit algorithm to the points of \(\textbf{P}\), in this order, to assign them to chains \(C_1, C_2,….\) In other words, assign \(x_1\) to chain \(C_1\). Thereafter if you have assigned points \(x_1, x_2,…,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 \leq k \leq i\) and \(x_k\) has already been assigned to \(C_j\). For example, this rule results in the following chains for the interval order \(\textbf{P}\) shown in Figure 6.31.
\(C_1 = \{g,h,b\}\)
\(C_2 = \{f,a,e\}\)
\(C_3 = \{c,d\}\)
\(C_4 = \{j\}\)
\(C_5 = \{i\}\)
In this case, it is easy to see that the chain partition is optimal since the width of \(\textbf{P}\) is 5 and \(A=\{a,b,d,i,j\}\) is a 5-element antichain.
However, you should be very careful in applying First Fit to find optimal chain partitions of posets—just as one must be leary of using First Fit to find optimal colorings of graphs.
The poset on the left side of Figure 6.33 is a height 2 poset on 10 points, and if the poset is partitioned into antichains by applying First Fit and considering the points in the order of their labels, then 5 antichains will be used. Do you see how to extend this poset to force First Fit to use arbitrarily many antichains, while keeping the height of the poset at 2?
On the right side, we show a poset of width 2. Now if this poset is partitioned into chains by applying First Fit and considering the points in the order of their labels, then 4 chains will be used. Do you see how to extend this poset to force First Fit to use arbitrarily many chains while keeping the width of the poset at 2?
Do you get a feeling for why the second problem is a bit harder than the first?
In general, there is always some linear order on the ground set of a poset for which First Fit will find an optimal partition into antichains. Also, there is a linear order (in general different from the first) on the ground set for which First Fit will find an optimal partition into chains. However, there is no advantage in searching for such orders, as the algorithms we develop for finding optimal antichain and chain partitions work quite well.