- Main
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\(^*(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
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-