Saturation of \(k\)-chains in the Boolean lattice

Ryan Martin¹ ; Nick Veldt¹

¹Iowa State University

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

Given a set $X$, a collection $\mathcal{F} \subset \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. Gerbner et al. conjectured that, if $|X|$ is sufficiently large compared to $k$, then the minimum size of a saturated $k$-Sperner system is $2^{k-1}$. Noel, Morrison, and Scott disproved this conjecture later by proving that there exists $\varepsilon$ such that for every $k$ and $|X| > n_0(k)$, there exists a saturated $k$-Sperner system of cardinality at most $2^{(1-\varepsilon)k}$. In particular, Noel, Morrison, and Scott proved this for $\varepsilon = 1-\frac{1}{4}\log_2 15 \approx 0.023277$. We find an improvement to $\varepsilon = 1-\frac{1}{5}\log_2 28 \approx 0.038529$. We also prove that, for $k$ sufficiently large, the minimum size of a saturated $k$-Sperner family is at least $\sqrt{k}\, 2^{k/2}$, improving on the previous Gerbner, et al. bound of $2^{k/2-0.5}$

Détail

DOI : 10.37236/12910

Classification : 06A07, 05D05