Lesson 7

There are two natural ways to define the width of a poset: as the maximum size of an antichain or as the minimum size of a chain covering. Both definitions, in a sense, characterize the degree of non-linearity of the order: the smaller the width, the more linear the order. Dilworth's theorem (which we prove below) states that these two definitions are equivalent.

For the poset from the previous example, the maximum antichain size is equal to three. Examples of antichains of maximum size: \[\{\{a\}, \{b\}, \{c\}\}, \quad \{\{a, b\}, \{a, c\}, \{b, c\}\}.\]

The poset can also be covered by the following three chains: \[\{\varnothing, \{a\}, \{a, b\}, \{a, b, c\}\}, \quad \{\{b\}, \{b, c\}\}, \quad \{\{c\}, \{a, c\}\}.\]

For the following poset, these two quantities are also equal.