Unichain coverings in partial orders with the nested saturation property
✍ Scribed by Douglas B. West
- Publisher
- Elsevier Science
- Year
- 1987
- Tongue
- English
- Weight
- 457 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
The theory of saturated chain partitions of partial orders is applied to the minimum unichain covering problem in the product of partial orders (posets). Define the nested saturation property for a poset to be the existence of a sequence of chain partitions %,, %a, . . such that (e, is k-and k + l-saturated and the elements on chains of size at most k in 4 contain the elements on chains of size at most (k -1) in %k_,. For the product of two posets P and Q with the nested saturation property, a unichain covering is constructed of size C AcAf, where d[ is the size of the largest k-family in P and A, = d* -d,_,. This is applied to prove that the largest semiantichain and smallest unichain covering have the same size for products of a special class of posets.