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${}^{\ast }(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${}^{\ast }(n,k)$. Our result implies that sat${}^{\ast }(n,k)=n(k-1)-\mathrm{\Theta }(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat${}^{\ast }(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}^m{C}^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