AC Dilworth’s Theorem for Interval Orders

Section 6.8 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 Chapter 5.

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\text{.}$ Then let $\bfG$ be the interval graph determined by this family of intervals. Note that if $x$ and $y$ are distinct elements of $X\text{,}$ then $x$ and $y$ are incomparable in $\bfP$ if and only if $xy$ is an edge in $\bfG\text{.}$ In other words, $\bfG$ is just the incomparability graph of $\bfP\text{.}$

Recall from Chapter 5 that interval graphs are perfect, i.e., $\chi(\bfG)=\omega(\bfG)$ for every interval graph $\bfG\text{.}$ 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\text{,}$ $x_2,\dots,x_n$ so that $i\lt j$ whenever $D(x)$ is a proper subset of $D(y)\text{.}$ 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:

\begin{align*} 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{align*}

Now apply the First Fit algorithm to the points of $\bfP\text{,}$ in this order, to assign them to chains $C_1\text{,}$ $C_2,\dots\text{.}$ In other words, assign $x_1$ to chain $C_1\text{.}$ Thereafter if you have assigned points $x_1\text{,}$ $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\text{.}$ For example, this rule results in the following chains for the interval order $\bfP$ shown in Figure 6.31.

\begin{align*} 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{align*}

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.

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.

Example 6.32.

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\text{?}$

On the right side, we show a poset of width $2\text{.}$ 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\text{?}$

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.

Reading Questions Reading Questions

1.

Start applying the First Fit algorithm for chain partitioning to the interval order shown below, ordering the intervals by left endpoint (and then right endpoint if you have a tie to break). Only apply the algorithm until you assign interval $q$ to a chain! What chain is interval $q$ assigned to? Why?

$An interval order$

2.

Consider the interval order with representation shown below. Can you see how to visually inspect the interval representation to find its width without needing to apply the First Fit algorithm? If so, what is the width of this interval order and explain how you came up with this. If you’re not able to see how to do this, briefly describe some things you’ve thought about and ask a question that might help get you unstuck.

$An interval order$

You have attempted of activities on this page.

Prev Top Next