Saturation of $k$-Chains in the Boolean Lattice
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}$
Authors
- Ryan R. Martin (ORCID: https://orcid.org/0000-0003-0683-1414)
- Nick Veldt
Institutions
- Iowa State University (US)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-03-27
- DOI
- https://doi.org/10.37236/12910
- Citations
- 1
- Primary Topic
- Advanced Algebra and Logic
- Type
- article
- Field-Weighted Citation Impact
- 1.50
Funders
- National Science Foundation