Article ID Journal Published Year Pages File Type
4649028 Discrete Mathematics 2010 5 Pages PDF
Abstract

Fix integers nn and kk with n≥k≥3n≥k≥3. Duffus and Sands proved that if PP is a finite poset and n≤|C|≤n+(n−k)/(k−2)n≤|C|≤n+(n−k)/(k−2) for every maximal chain in PP, then PP must contain kk pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if PP is a finite poset and n≤|A|≤n+(n−k)/(k−2)n≤|A|≤n+(n−k)/(k−2) for every maximal antichain in PP, then PP has kk pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,