Chains, Antichains, and Dilworth Theory

The structure of chains and antichains in partially ordered sets reveals fundamental combinatorial relationships. Dilworth's theorem and its dual (Mirsky's theorem) provide powerful connections between width, height, and decompositions of posets.

DefinitionWidth and Height

For a finite poset $P$ :

Width $w(P)$ = maximum size of an antichain
Height $h(P)$ = maximum size of a chain minus 1 (length of longest chain)
Chain decomposition: partition of $P$ into disjoint chains
Antichain decomposition: partition of $P$ into disjoint antichains

TheoremDilworth's Theorem

In any finite poset, the minimum number of chains needed to cover all elements equals the maximum size of an antichain: $\text{min chain cover} = \text{width}$

TheoremMirsky's Theorem (Dual of Dilworth)

The minimum number of antichains needed to cover all elements equals the maximum size of a chain: $\text{min antichain cover} = \text{height} + 1$

ExampleBoolean Lattice

For $B_n = \mathcal{P}([n])$ ordered by inclusion:

Width = $\binom{n}{\lfloor n/2 \rfloor}$ (Sperner's theorem)
Height = $n$
Natural antichain decomposition: levels $\{A : |A| = k\}$ for $k = 0, 1, \ldots, n$
Minimum chain cover has $\binom{n}{\lfloor n/2 \rfloor}$ chains

Sperner's theorem states that the middle level forms a maximum antichain.

Remark

Dilworth's theorem can be proved using:

Induction: Remove maximal antichain, apply induction
Kőnig's theorem: via bipartite graph matching
Network flows: max-flow min-cut theorem

Each proof reveals different aspects of the underlying combinatorial structure.

DefinitionSymmetric Chain Decomposition

A symmetric chain in $B_n$ is a chain $\{A_i\}$ where $A_i \subset A_{i+1}$ and $|A_i| = i$ for consecutive integers, symmetric about $n/2$ .

A symmetric chain decomposition (SCD) partitions $B_n$ into symmetric chains. The existence of an SCD provides an alternative proof of Sperner's theorem.

ExampleYoung's Lattice

Young's lattice consists of all integer partitions ordered by diagram inclusion: $\lambda \subseteq \mu$ if the Ferrers diagram of $\lambda$ is contained in that of $\mu$ .

Chains correspond to sequences of partitions (tableaux fillings)
Antichains appear in representation theory
Width and height connect to partition enumeration

This theory provides essential tools for analyzing the combinatorial structure of partially ordered sets.