Title of article :
On the size of maximal antichains and the number of pairwise disjoint maximal chains
Author/Authors :
Howard ، نويسنده , , David M. and Trotter، نويسنده , , William T.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Abstract :
Fix integers n and k with n ≥ k ≥ 3 . Duffus and Sands proved that if P is a finite poset and n ≤ | C | ≤ n + ( n − k ) / ( k − 2 ) for every maximal chain in P , then P must contain k 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 P is a finite poset and n ≤ | A | ≤ n + ( n − k ) / ( k − 2 ) for every maximal antichain in P , then P has k 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.
Keywords :
Partially ordered set , Chains , Antichains
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics