BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-80-821
       ENTRY:: June 08, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Semiantichains and unichain coverings in direct products of
               partial orders
        TYPE:: Technical Report
      AUTHOR:: West, Douglas B.
      AUTHOR:: Tovey, Craig A.
        DATE:: September 1980
       PAGES:: 21
    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.
       NOTES:: [Adminitrivia V1/Prg/19950608]
         END:: STAN//CS-TR-80-821