TOPICS
Search

Dilworth's Lemma


The partial order width of a set P is equal to the minimum number of chains needed to cover P. Equivalently, if a set P of ab+1 elements is partially ordered, then P contains a chain of size a+1 or an antichain of size b+1. Letting N be the cardinal number of P, W the partial order width, and L the partial order length, this last statement says N<=LW. Dilworth's lemma is a generalization of the Erdős-Szekeres theorem. Ramsey's theorem generalizes 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

Subject classifications