Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section6.3Dilworth'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.

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.

Proof

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

The argument given for the proof of Theorem 6.18 yields an efficient algorithm, one that is defined recursively. Set \(\bfP_0= \bfP\). If \(\bfP_i\) has been defined and \(\bfP_i\neq \emptyset\), let \(A_i=\min(\bfP_i)\) and then let \(\bfP_{i+1}\) denote the subposet remaining when \(A_i\) is removed from \(\bfP_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\).

<<SVG image is unavailable, or your browser cannot render it>>

Figure6.19A Poset of Height 5
Discussion6.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(\bfP)\) of maximal points of \(\bfP\). We can also partition \(\bfP\) into \(\height(\bfP)\) antichains by recursively removing the set of maximal points.

We pause to remark that when \(\PXP\) is a poset, the set of all chains of \(\bfP\) 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|\lt |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 \(\bfP\). Of course, we also get a handy partition of the poset into \(h\) antichains.

Subsection6.3.1Proof of Dilworth's Theorem

The argument for Dilworth's theorem is simplified by the following notation. When \(\PXP\) is a poset and \(x\in X\), we let \(D(x)=\{y\in X:y\lt x \text{ in } P\}\); \(D[x]=\{y\in X:y\le x\text{ in } P\}\); \(U(x)=\{y\in X:y>x \text{ in } P\}\); \(U[x]=\{y\in X:y\ge x\}\); and \(I(x)=\{y\in X-\{x\}:x\Vert y \text{ in } P\}\). When \(S\subseteq X\), we let \(D(S)= \{y\in X:y\lt 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 \(\bfP\), 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 \(\PXP\) be a poset and let \(w\) denote the width of \(\bfP\). As in Theorem 6.18, the Pigeon Hole Principle implies that we require at least \(w\) chains in any chain partition of \(\bfP\). 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|\le k\) and suppose that \(\PXP\) 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'\lt w\), then we can partition \(X-C\) as \(X-C=C_1\cup C_2\cup\dots\cup C_{w'}\), so that \(X=C\cup C_1\cup\dots\cup C_{w'}\) is a partition into \(w'+1\) chains. Since \(w'\lt w\), we know \(w'+1\le 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\le 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,\dots,a_w\}\). Note that \(U[A]\ne X\) since \(y\notin U[A]\), and \(D[A]\ne X\) since \(x\notin D[A]\). Therefore, we may apply the inductive hypothesis to the subposets of \(\bfP\) determined by \(D[A]\) and \(U[A]\), respectively, and partition each of these two subposets into \(w\) chains: \begin{equation*} U[A]= C_1\cup C_2\cup\dots\cup C_w\quad\text{and} \quad D[A]=D_1\cup D_2\cup\dots\cup D_w. \end{equation*} Without loss of generality, we may assume these chains have been labeled so that \(a_i\in C_i\cap D_i\) for each \(i=1,2,\dots,w\). However, this implies that \begin{equation*} X=(C_1\cup D_1)\cup (C_2\cup D_2)\cup\dots\cup(C_w\cup D_w) \end{equation*} 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.

<<SVG image is unavailable, or your browser cannot render it>>

Figure6.21A Poset of Width 7
Discussion6.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.