6.3: Dilworth's Chain Covering Theorem and its Dual

In this section, we prove the following theorem of R.P. Dilworth, which is truly one of the classic results of combinatorial mathematics.

Theorem 6.17. Dilworth's Theorem

If \(P=(X,P)\) is a poset and width⁡\((P)=w\), then there exists a partition \(X=C_1 \cup C_2 \cup \cdot \cdot \cdot \cup C_w\), where \(C_i\) is a chain for \(i=1,2,…,w\). Furthermore, there is no chain partition into fewer chains.

Before proceeding with the proof of Dilworth's theorem in Subsection 6.3.1, we pause to discuss the dual version for partitions into antichains, as it is even easier to prove.

Theorem 6.18. Dual of Dilworth's Theorem

If \(P=(X,P)\) is a poset and height\(⁡(P)=h\), then there exists a partition \(X=A_1 \cup A_2 \cup \cdot \cdot \cdot \cup A_h\), where \(A_i\) is an antichain for \(i=1,2,…,h\). Furthermore, there is no partition using fewer antichains.

Proof

For each \(x \in X\), let \(height⁡(x)\) be the largest integer \(t\) for which there exists a chain

\(x_1 < x_2 < \cdot \cdot \cdot < x_t\)

with \(x=x_t\). Evidently, \(height⁡(x) \geq h\) for all \(x \in X\). Then for each \(i=1,2,…,h\) let \(A_i=\{x \in X:height⁡(x)=i\}\). It is easy to see that each \(A_i\) is an antichain, as if \(x,y \in A_i\) are such that \(x<y\), then there is a chain \(x_1<x_2< \cdot \cdot \cdot <x_i=x<x_{i+i}=y\), so \(height⁡(y) \geq i+1\). Since \(height⁡(P)=h\), there is a maximum chain \(C=\{x_1,x_2,…,x_h\}\). If it were possible to partition \(P\) into \(t<h\) antichains, then by the Pigeon Hole Principle, one of the antichains would contain two points from \(C\), but this is not possible.

When \(P=(X,P)\) is a poset, a point \(x \in X\) with \(height⁡(x)=1\) is called a minimal point of \(P\). We denote the set of all minimal points of a poset \(P=(X,P)\) by \(min(X,P)\).

The argument given for the proof of Theorem 6.18 yields an efficient algorithm, one that is defined recursively. Set \(P_0=P\). If \(P_i\) has been defined and \(P_i \neq \emptyset\), let \(A_i=min(P_i)\) and then let \(P_{i+1}\) denote the subposet remaining when \(A_i\) is removed from \(P_i\).

In Figure 6.19, we illustrate the antichain partition provided by this algorithm for the 17 point poset from Figure 6.5. The darkened points form a chain of size 5.

Figure 6.19. A Poset of Height 5

Discussion 6.20.

Alice claims that it is very easy to find the set of minimal elements of a poset. Do you agree?

Dually, we can speak of the set max(P) of maximal points of P. We can also partition P into height⁡(P) antichains by recursively removing the set of maximal points.

We pause to remark that when \(P=(X,P)\) is a poset, the set of all chains of \(P\) is itself partially ordered by inclusion. So it is natural to say that a chain \(C\) is maximal when there is no chain \(C′\) containing \(C\) as a proper subset. Also, a chain \(C\) is maximum when there is no chain \(C′\) with \(|C|<|C′|\). Of course, a maximum chain is maximal, but maximal chains need not be maximum.

Maximal antichains and maximum antichains are defined analogously.

With this terminology, the thrust of Theorem 6.18 is that it is easy to find the height \(h\) of a poset as well as a maximum chain \(C\) consisting of h points from \(P\). Of course, we also get a handy partition of the poset into \(h\) antichains.

6.3.1 Proof of Dilworth's Theorem

The argument for Dilworth's theorem is simplified by the following notation. When \(P=(X,P)\) is a poset and \(x \in X\), we let in \(D(x)=\{y \in X:y<x in P\}\); in \(D[x]=\{y \in X:y \leq x in P\}\); in \(U(x)=\{y \in X:y>x in P\}\); \(U[x]=\{y \in X:y \geq x\}\); and in \(I(x)=\{y \in X−\{x\}:x‖y in P\}\). When \(S \subseteq X\), we let \(D(S)=\{y \in X:y<x\) in \(P\), for some \(x \in S\}\) and \(D[S]=S \cup D(S)\). The subsets \(U(S)\) and \(U[S]\) are defined dually. We call \(D(x), D[x], D(S)\), and \(D[S]\) down sets, while \(U(x), U[x], U(S)\), and \(U[S]\) are up sets. Note that when \(A\) is a maximal antichain in \(P\), the ground set \(X\) can be partitioned into pairwise disjoint sets as \(X=A \cup D(A) \cup U(A)\).

We are now ready for the proof. Let \(P=(X,P)\) be a poset and let \(w\) denote the width of \(P\). As in Theorem 6.18, the Pigeon Hole Principle implies that we require at least \(w\) chains in any chain partition of \(P\). To prove that \(w\) suffice, we proceed by induction on \(|X|\), the result being trivial if \(|X|=1\). Assume validity for all posets with \(|X| \leq k\) and suppose that \(P=(X,P)\) is a poset with \(|X|=k+1\). Without loss of generality, \(w>1\); otherwise, the trivial partition \(X=C_1\) satisfies the conclusion of the theorem. Furthermore, we observe that if \(C\) is a (nonempty) chain in \((X,P)\), then we may assume that the subposet \((X−C,P(X−C))\) also has width \(w\). To see this, observe that the theorem holds for the subposet, so that if \(width⁡(X−C,P(X−C))=w′<w\), then we can partition \(X−C\) as \(X−C=C_1 \cup C_2 \cup \cdot \cdot \cdot \cup C_{w′}\), so that \(X=C \cup C_1 \cup \cdot \cdot \cdot \cup C_{w′}\) is a partition into \(w′+1\) chains. Since \(w′<w\), we know \(w′+1 \leq w\), so we have a partition of \(X\) into at most \(w\) chains. Since any partition of \(X\) into chains must use at least \(w\) chains, this is exactly the partition we seek.

Choose a maximal point \(x\) and a minimal point \(y\) with \(y \leq x\) in \(P\). Then let \(C\) be the chain containing only the points \(x\) and \(y\). Note that \(C\) contains either one or two elements depending on whether \(x\) and \(y\) are distinct.

Let \(Y=X−C\) and \(Q=P(Y)\) and let \(A\) be a \(w\)-element antichain in the subposet \((Y,Q)\). In the partition \(X=A \cup D(A) \cup U(A)\), the fact that \(y\) is a minimal point while \(A\) is a maximal antichain imply that \(y \in D(A)\). Similarly, \(x \in U(A)\). In particular, this shows that \(x\) and \(y\) are distinct.

Label the elements of \(A\) as \(\{a_1,a_2,…,a_w\}\). Note that \(U[A] \neq X\) since \(y \notin U[A]\), and \(D[A] \neq X\) since \(x \notin D[A]\). Therefore, we may apply the inductive hypothesis to the subposets of \(P\) determined by \(D[A]\) and \(U[A]\), respectively, and partition each of these two subposets into \(w\) chains:

\(U[A] = C_1 \cup C_2 \cup \cdot \cdot \cdot \cup C_w\) and \(D[A] = D_1 \cup D_2 \cup \cdot \cdot \cdot \cup D_w\).

Without loss of generality, we may assume these chains have been labeled so that \(a_i \in C_i ∩ D_i\) for each \(i=1,2,…,w\). However, this implies that

\(X=(C_1 \cup D_1) \cup (C_2 \cup D_2) \cup \cdot \cdot \cdot \cup (C_w \cup D_w)\)

is the desired partition which in turn completes the proof.

In Figure 6.21, we illustrate Dilworth's chain covering theorem for the poset first introduced in Figure 6.5. The darkened points form a 7-element antichain, while the labels provide a partition into 7 chains.

Figure 6.21. A Poset of Width 7

Discussion 6.22.

The ever alert Alice notes that the proof given above for Dilworth's theorem does not seem to provide an efficient algorithm for finding the width \(w\) of a poset, much less a partition of the poset into \(w\) chains. Bob has yet to figure out why listing all the subsets of \(X\) is a bad idea. Carlos is sitting quietly listening to their bickering, but finally, he says that a skilled programmer can devise an algorithm from the proof. Students are encouraged to discuss this dilemma—but rest assured that we will return to this issue later in the text.