Width of a partially ordered set
From Encyclopedia of Mathematics
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
Width of a partially ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Width_of_a_partially_ordered_set&oldid=54718