On the size of maximal antichains and the number of pairwise disjoint maximal chains

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 ar...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2010-11, Vol.310 (21), p.2890-2894
Main Authors: Howard, David M., Trotter, William T.
Format: Article
Language:English
Subjects:
Algebra
Antichains
Chains
Combinatorics
Combinatorics. Ordered structures
Construction
Exact sciences and technology
Inequalities
Integers
Mathematical analysis
Mathematics
Partially ordered set
Sands
Sciences and techniques of general use
Two dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2010.06.034