Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem

Details Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem

1998-07-31

arxiv.org/abs/math/9807175v1

Mathematics

Combinatorics

11 pages, 5 figures

Scientific paper

A partition of a finite poset into chains places a natural upper bound on the size of a union of k antichains. A chain partition is k-saturated if this bound is achieved. Greene and Kleitman proved that, for each k, every finite poset has a simultaneously k- and k+1-saturated chain partition. West showed that the Greene-Kleitman Theorem is best-possible in a strong sense by exhibiting, for each c \ge 4, a poset with longest chain of cardinality c and no k- and l-saturated chain partition for any distinct, nonconsecutive k,l < c. We call such posets polyunsaturated. We give necessary and sufficient conditions for the existence of polyunsaturated posets with prescribed height, width, and cardinality. We prove these results in the more general context of graphs satisfying an analogue of the Greene-Kleitman Theorem. Lastly, we discuss analogous results for antichain partitions.

Affiliated with

Also associated with

No associations

Rating

Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-288943