Lesson 8

Theorem (Dilworth, 1950). In any finite poset, the maximum size of an antichain equals the minimum size of a chain covering.

Proof. Again, it is enough to construct an antichain and a chain covering of the same size. We will do this by induction on \(n=|P|\). If \(|P|=1\), there is nothing to prove, so we move on to the induction step (pun intended!) \(n \to (n+1)\). Let \(|P|=n+1\) and let \(a\) be a maximal element. Consider the induced order \(P' = P \setminus \{a\}\). By the induction hypothesis, in \(P'\) there is an antichain \(A_{0}\) of size \(k\) and a chain covering \(C_{1}, \dotsc, C_{k}\).

The maximum size of an antichain in \(P\) is either \(k\) or \(k+1\). If it is \(k+1\), the case is simple: \(a\) lies in some maximum antichain of size \(k+1\) and there is a chain covering of \(P\) consisting of chains \(C_{1}, \dotsc, C_{k}, \{a\}\). Therefore, we will assume that the maximum size of an antichain in \(P\) is \(k\).

In each chain \(C_{1}, \dotsc, C_{k}\) in \(P'\), we take the largest element \(c_{i}\) that lies in some maximum antichain in \(P'\). Such elements certainly exist, because the maximum antichain \(A_{0}\) must intersect all chains \(C_{1}, \dotsc, C_{k}\). We will verify that \(C = \{c_{1}, \dotsc, c_{k}\}\) is an antichain in \(P'\). Suppose not: \(c_{j} \prec c_{i}\) for some \(i \neq j\). Let \(A_{i}\) be the maximum antichain containing \(c_{i}\), and let \(z \in A_{i} \cap C_{j}\). By the definition of the element \(c_{j}\), we have that \(z \preceq c_{j}\). But then, by transitivity, from \(z \preceq c_{j}\) and \(c_{j} \prec c_{i}\), we get \(z \prec c_{i}\), which is impossible, since these two elements lie in the antichain \(A_{i}\). Thus, \(C = \{c_{1}, \dotsc, c_{k}\}\) is an antichain in \(P'\).

Since there are no antichains of size \(k+1\) in \(P\), \(C \cup \{a\}\) is not an antichain, meaning \(c_{i} \prec a\) for some \(i\). Consider the chain in \(P\) defined by \[C_{i}' = \{a\} \cup \{z \in C_{i} : z \preceq c_{i}\}\ .\] Then, in \(P \setminus C_{i}'\), there are no antichains of size \(k\) (since we removed all elements of \(C_{i}\) that were in antichains of maximum size). Thus, by the induction hypothesis, \(P \setminus C_{i}'\) can be covered by \(k-1\) chains. We can then add \(C_{i}'\) to this covering, obtaining a covering of \(P\) by \(k\) chains, which is what we aimed to show.◼