Report Number: CS-TR-80-821
Institution: Stanford University, Department of Computer Science
Title: Semiantichains and unichain coverings in direct products of
Author: West, Douglas B.
Author: Tovey, Craig A.
Date: September 1980
Abstract: We conjecture a generalization of Dilworth's theorem to
direct products of partial orders. In particular, we
conjecture that the largest "semiantichain" and the smallest
"unichain covering" have the same size. We consider a special
class of semiantichains and unichain coverings and determine
when equality holds for them. This conjecture implies the
existence of k-saturated partitions. A stronger conjecture,
for which we also prove a special case, implies the
Greene-Kleitman result on simultaneous k and (k +