Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Abstract

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)-\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 generalisation of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

31 pages, 3 figures