The saturation spectrum for antichains of subsets

DOI10.1007/S11083-022-09622-6MaRDI QIDQ6139859zbMATH OpenFDO

Authors

Publication date 19 December 2023

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.02226

zbMATH Keywords

antichainSperner familyKruskal-Katona theoremsaturation spectrumshadow spectrum

Mathematics Subject Classification ID

Order, lattices, ordered algebraic structures (06-XX)

Abstract: 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 $mathcalF$ of $k$-sets with $lvertmathcalFvert=t$ such that the shadow of $mathcalF$ has size $s$, where the shadow of $mathcalF$ is the collection of $(k-1)$-sets that are contained in at least one member of $mathcalF$. We provide a complete answer for $tleqslantk+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $sqrt2k^{3/2}+sqrt[4]8k^{5/4}+O(k)$.

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 1792287 (Why is no real title available?)
• scientific article; zbMATH DE number 7272503 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• A survey of minimum saturated graphs
• Computationally efficient bounds for the Catalan numbers
• Induced and non-induced poset saturation problems
• Maximal antichains of minimum size
• Maximal flat antichains of minimum weight
• Minimum shadows in uniform hypergraphs and a generalization of the Takagi function
• Minimum weight flat antichains of subsets
• On saturated \(k\)-Sperner systems
• Saturating Sperner families
• Size in maximal triangle-free graphs and minimal graphs of diameter 2
• Supersaturation and stability for forbidden subposet problems.

Cited in

(1)

• Improved bounds for cross-Sperner systems

This page was built for publication: The saturation spectrum for antichains of subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139859)