Combinatorial Theory

For given positive integers \(k\) and \(n\), a family \(\mathcal{F}\) of subsets of \(\{1,\dots,n\}\) is \(k\)-antichain saturated if it does not contain an antichain of size \(k\), but adding any set to \(\mathcal{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)-\Theta(k\log 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,\dots,C^m\) in the Boolean lattice, we can create \(m\) disjoint skipless chains that cover the elements from \(\cup_{i=1}^mC^i\) (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

Mathematics Subject Classifications: 06A07, 05D99

Keywords: Skipless chains, poset saturation, antichain saturation, Boolean lattice