| Summary: | Given a set X, a collection F ⊆ P(X) is said to be k-Sperner if it does not contain a chain of length k + 1 under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. [11] conjectured that, if |X| is sufficiently large with respect to k, then the minimum size of a saturated k-Sperner system F ⊆ P(X) is 2<sup>k-1</sup>. We disprove this conjecture by showing that there exists ε > 0 such that for every k and |X| ≥ n<inf>0</inf>(k) there exists a saturated k-Sperner system F ⊆ P(X) with cardinality at most 2<sup>(1-ε)k</sup>. A collection F ⊆ P(X) is said to be an oversaturated k-Sperner system if, for every S ∈ P(X)\F, F∪{S} contains more chains of length k + 1 than F. Gerbner et al. [11] proved that, if |X| ≥ k, then the smallest such collection contains between 2<sup>k/2-1</sup> and O (logk/k2<sup>k</sup>] elements. We show that if |X| ≥ k<sup>2</sup> + k, then the lower bound is best possible, up to a polynomial factor.
|
|---|