Lesson 4

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

Proof. As usual, the maximum cannot exceed the minimum, so it suffices to construct a covering by antichains of size \(r\), where \(r\) is the size of the maximum chain. For this, define the set \(A_{i}\) as the set of elements \(p \in P\) for which the longest chain ending at \(p\) has size \(i\) (these are the levels on which we agreed to place the elements in the Hasse diagram). Then \(P=A_{1} \cup \dotsb \cup A_{r}\) (as chains of size greater than \(r\) do not exist). Moreover, \(A_{i}\) is an antichain: if \(p \prec q\) for \(p,q \in A_{i}\), then appending element \(q\) to the chain of size \(i\) ending at \(p\) yields a chain of size \(i+1\).◼