The saturation spectrum for antichains of subsets

DOI10.1007/S11083-022-09622-6arXiv2106.02226MaRDI QIDQ6139859FDOQ6139859

Authors:

Publication date: 19 December 2023

Published in: Order (Search for Journal in Brave)

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)$.

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)

Cites Work

• A survey of minimum saturated graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computationally efficient bounds for the Catalan numbers
• Title not available (Why is that?)
• Maximal flat antichains of minimum weight
• Saturating Sperner families
• On saturated \(k\)-Sperner systems
• Minimum shadows in uniform hypergraphs and a generalization of the Takagi function
• Size in maximal triangle-free graphs and minimal graphs of diameter 2
• Supersaturation and stability for forbidden subposet problems.
• Induced and non-induced poset saturation problems
• Maximal antichains of minimum size
• Minimum weight flat antichains of subsets
• Title not available (Why is that?)

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)