Report Number: CS-TR-80-821
Institution: Stanford University, Department of Computer Science
Title: Semiantichains and unichain coverings in direct products of partial orders
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 + 1)-saturated partitions.
http://i.stanford.edu/pub/cstr/reports/cs/tr/80/821/CS-TR-80-821.pdf