On saturated \(k\)-Sperner systems (Q405311)

Summary: Given a set \(X\), a collection \(\mathcal{F}\subseteq\mathcal{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. \textit{D. Gerbner} et al. [Graphs Comb. 29, No. 5, 1355--1364 (2013; Zbl 1272.05212)] conjectured that, if \(|X|\) is sufficiently large with respect to \(k\), then the minimum size of a saturated \(k\)-Sperner system \(\mathcal{F}\subseteq\mathcal{P}(X)\) is \(2^{k-1}\). We disprove this conjecture by showing that there exists \(\epsilon0\) such that for every \(k\) and \(|X| \geq n_0(k)\) there exists a saturated \(k\)-Sperner system \(\mathcal{F}\subseteq\mathcal{P}(X)\) with cardinality at most \(2^{(1-\epsilon)k}\).{ }A collection \(\mathcal{F}\subseteq \mathcal{P}(X)\) is said to be an oversaturated \(k\)-Sperner system if, for every \(S\in\mathcal{P}(X)\setminus\mathcal{F}\), \(\mathcal{F}\cup\{S\}\) contains more chains of length \(k+1\) than \(\mathcal{F}\). Gerbner et al. proved that, if \(|X|\geq k\), then the smallest such collection contains between \(2^{k/2-1}\) and \(O\left(\frac{\log{k}}{k}2^k\right)\) elements. We show that if \(|X|\geq k^2+k\), then the lower bound is best possible, up to a polynomial factor.