Back to Search
Start Over
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
- Publication Year :
- 2022
-
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 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).<br />Comment: 31 pages, 3 figures
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2207.07391
- Document Type :
- Working Paper