Dilworth Chain–Antichain Duality

Dilworth's Theorem describes the relationship between the maximum antichain size and the minimum number of chains required to cover a partially ordered set.

Experimenting with Posets

You can interactively explore Dilworth's Theorem for different posets using the Dilworth Chain–Antichain Duality module.

1. Open the module and observe the default Divisibility poset. Note that the width (maximum antichain size) is 3, which matches the minimum number of chains.
2. Change the Poset control to Grid. This represents points ordered by coordinate-wise inequality. The width becomes 2, and the matching size increases to 4.
3. Select the Total poset. Here, every element is comparable to every other element. The width drops to 1, as the entire set forms a single chain. The maximum antichain contains only a single element.
4. Finally, try the Antichain poset where no distinct elements are comparable. The matching size is 0, meaning the minimum number of chains is exactly the number of elements (6), which is also the width.