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

arXiv2207.07391MaRDI QIDQ6405070FDOQ6405070

Authors: Paul Bastide, Carla Groenland, H. Jacob, Tom Johnston 

Publication date: 15 July 2022

Abstract: For given positive integers $k$ and $n$, a family $mathcalF$ 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 $mathcalF$ 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(klogk)$, 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).

This page was built for publication: Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405070)