For given positive integers \(k\) and \(n\), a family \(F\) of subsets of \(\{1,,n\}\) is \(k\)-antichain saturated if it does not contain an antichain of size \(k\), but adding any set to \(F\) creates an antichain of size \(k\). We use sat\(^*(n, k)\) to denote the smallest size of such a family. For all \(k\) and sufficiently large \(n\), we determine the exact value of sat\(^*(n, k)\). Our result implies that sat\(^*(n, k)=n(k-1)-Θ(klog k)\), which confirms several conjectures on antichain saturation. Previously, exact values for sat\(^*(n,k)\) were only known for \(k\) up to \(6\).We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given \(m\) disjoint chains \(C^1,,C^m\) in the Boolean lattice, we can create \(m\) disjoint skipless chains that cover the elements from \(∪ᵢ₌₁^mC^i\) (where we call a chain skipless if any two consecutive elements differ in size by exactly one).Mathematics Subject Classifications: 06A07, 05D99Keywords: Skipless chains, poset saturation, antichain saturation, Boolean lattice
No takes yet. Share an insight, caveat, or question.
Bastide et al. (2024) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: