Dilworth Chain–Antichain Duality

Calculated Example: Divisibility Poset

Consider the set of integers {1, 2, 3, 5, 6, 30} partially ordered by divisibility. The order relation is a < b if and only if a properly divides b.

We can trace the computation of Dilworth's theorem:

1. Identify the elements: 0: 1, 1: 2, 2: 3, 3: 5, 4: 6, 5: 30.
2. Construct the bipartite comparability graph with edges for every strict relation. For example, 1 divides 2, 3, 5, 6, and 30, so node 0 has edges to all other nodes. 2 divides 6 and 30, etc.
3. Find a maximum bipartite matching. The matching pairs 1 → 2, 2 → 6, and 6 → 30 (or equivalent), giving a matching size of 3.
4. Calculate minimum chains: The number of elements (6) minus the matching size (3) equals 3 chains.
5. Identify the maximum antichain: The elements {2, 3, 5} (IDs 1, 2, 3) form a set where no element divides another. This antichain has size 3.

Since the size of the maximum antichain equals the minimum number of chains (3), Dilworth's Theorem holds.

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.

Limitations

This implementation uses a direct construction of the comparability graph and applies the Hopcroft-Karp algorithm for maximum bipartite matching. This approach is well-suited for finite, relatively small partially ordered sets.

For very large posets, computing the full transitive closure and performing bipartite matching can become computationally expensive. The current visualization and computation are constrained to a predefined set of small examples (up to 6 elements) to ensure interactive performance and visual clarity. Empty sets correctly yield a width and height of 0.

References and Primary Sources

The mathematics and proof of Dilworth's Theorem for finite partially ordered sets can be found in standard algebraic combinatorics literature.

• Chains and Antichains (Richard Stanley) - MIT lecture slides detailing the proof and applications of Dilworth's Theorem. This source supports the decomposition of a poset into the minimum number of chains corresponding to the maximum antichain size.