Length 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]
The greatest possible length of a chain (totally ordered subset) in a partially ordered set (the length of a finite chain is one less than the number of elements). There exist infinite partially ordered sets of finite length. A partially ordered set of length zero is a trivial order.
Dilworth's theorem [1] states that in a finite partially ordered set the length is equal to the minimal number of anti-chains (sets of mutually incomparable elements) that cover the set.
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:
Length of a partially ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Length_of_a_partially_ordered_set&oldid=54441
Length of a partially ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Length_of_a_partially_ordered_set&oldid=54441
This article was adapted from an original article by T.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article