The partial order width of a set is equal to the minimum number of chains needed to cover . Equivalently, if a set of elements is partially ordered, then contains a chain of size or an antichain of size . Letting be the cardinal number of , the partial order width, and the partial order length, this last statement says . Dilworth's lemma is a generalization of the Erdős-Szekeres theorem. Ramsey's theorem generalizes Dilworth's lemma.

# Dilworth's Lemma

## See also

Antichain, Chain, Combinatorics, Erdős-Szekeres Theorem, Ramsey's Theorem## Explore with Wolfram|Alpha

## References

Dilworth, R. P. "A Decomposition Theorem for Partially Ordered Sets."*Ann. Math.*

**51**, 161-166, 1950.Skiena, S. "Dilworth's Lemma." §6.4.2 in

*Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica.*Reading, MA: Addison-Wesley, pp. 241-243, 1990.

## Referenced on Wolfram|Alpha

Dilworth's Lemma## Cite this as:

Weisstein, Eric W. "Dilworth's Lemma."
From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/DilworthsLemma.html