Namespaces
Variants
Actions

Width of a partially ordered set

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 06A [MSN][ZBL]

Dilworth number, Sperner number

The greatest possible size of an anti-chain (set of mutually incomparable elements) in a partially ordered set. A partially ordered set of width 1 is a chain (totally ordered set).

Dilworth's theorem [1] states that in a finite partially ordered set the width is equal to the minimal number of chains that cover the set.


See also Sperner property.


References

[1] R.P. Dilworth, "A decomposition theorem for partially ordered sets" Ann. of Math. , 51 (1950) pp. 161–166 Zbl 0038.02003
[2] George Grätzer, General Lattice Theory, Springer (2003) ISBN 3764369965 Zbl 1152.06300
How to Cite This Entry:
Width of a partially ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Width_of_a_partially_ordered_set&oldid=54718