The saturation spectrum for antichains of subsets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910308967120896 |
|---|---|
| author | Griggs, Jerrold R. Kalinowski, Thomas Leck, Uwe Roberts, Ian T. Schmitz, Michael |
| author_facet | Griggs, Jerrold R. Kalinowski, Thomas Leck, Uwe Roberts, Ian T. Schmitz, Michael |
| contents | Extending a classical theorem of Sperner, we characterize the integers $m$ such that there exists a maximal antichain of size $m$ in the Boolean lattice $B_n$, that is, the power set of $[n]:=\{1,2,\dots,n\}$, ordered by inclusion. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers $t$ and $k$, we ask which integers $s$ have the property that there exists a family $\mathcal F$ of $k$-sets with $\lvert\mathcal F\rvert=t$ such that the shadow of $\mathcal F$ has size $s$, where the shadow of $\mathcal F$ is the collection of $(k-1)$-sets that are contained in at least one member of $\mathcal F$. We provide a complete answer for $t\leqslant k+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $\sqrt 2k^{3/2}+\sqrt[4]{8}k^{5/4}+O(k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_02226 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The saturation spectrum for antichains of subsets Griggs, Jerrold R. Kalinowski, Thomas Leck, Uwe Roberts, Ian T. Schmitz, Michael Combinatorics Discrete Mathematics 06A07 (Primary), 05D05 (Secondary) Extending a classical theorem of Sperner, we characterize the integers $m$ such that there exists a maximal antichain of size $m$ in the Boolean lattice $B_n$, that is, the power set of $[n]:=\{1,2,\dots,n\}$, ordered by inclusion. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers $t$ and $k$, we ask which integers $s$ have the property that there exists a family $\mathcal F$ of $k$-sets with $\lvert\mathcal F\rvert=t$ such that the shadow of $\mathcal F$ has size $s$, where the shadow of $\mathcal F$ is the collection of $(k-1)$-sets that are contained in at least one member of $\mathcal F$. We provide a complete answer for $t\leqslant k+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $\sqrt 2k^{3/2}+\sqrt[4]{8}k^{5/4}+O(k)$. |
| title | The saturation spectrum for antichains of subsets |
| topic | Combinatorics Discrete Mathematics 06A07 (Primary), 05D05 (Secondary) |
| url | https://arxiv.org/abs/2106.02226 |