释义 |
Dilworth's LemmaThe Width of a set is equal to the minimum number of Chains neededto Cover . Equivalently, if a set of elements is Partially Ordered,then contains a Chain of size or an Antichain of size . Letting be theCardinality of , the Width, and the Length, this last statement says . Dilworth's lemma is a generalization of the Erdös-SzekeresTheorem. Ramsey's Theorem generalizes Dilworth's lemma. See also Combinatorics, Erdös-Szekeres Theorem, Ramsey's Theorem
|