Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.14113 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911907358703616 |
|---|---|
| author | Martin, Ryan R. Veldt, Nick |
| author_facet | Martin, Ryan R. Veldt, Nick |
| contents | 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 probability. Gerbner et al. proved that the smallest saturated $k$-Sperner system contains at least $2^{k/2-1}$ elements, and later, Morrison, Noel, and Scott showed that the smallest such set contains no more than $2^{0.976723k}$ elements. We improve both the upper and lower bounds, showing that the size of the smallest saturated $k$-Sperner system lies between $\sqrt{k}2^{k/2}$ and $2^{0.961471k}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14113 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Saturation of $k$-chains in the Boolean lattice Martin, Ryan R. Veldt, Nick Combinatorics 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 probability. Gerbner et al. proved that the smallest saturated $k$-Sperner system contains at least $2^{k/2-1}$ elements, and later, Morrison, Noel, and Scott showed that the smallest such set contains no more than $2^{0.976723k}$ elements. We improve both the upper and lower bounds, showing that the size of the smallest saturated $k$-Sperner system lies between $\sqrt{k}2^{k/2}$ and $2^{0.961471k}$. |
| title | Saturation of $k$-chains in the Boolean lattice |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.14113 |