Maximal Antichains of Minimum Size

Abstract

Let $n\geqslant 4$ be a natural number, and let $K$ be a set $K\subseteq [n]:=\{1,2,\dots,n\}$. We study the problem of finding the smallest possible size of a maximal family $\mathcal{A}$ of subsets of $[n]$ such that $\mathcal{A}$ contains only sets whose size is in $K$, and $A\not\subseteq B$ for all $\{A,B\}\subseteq\mathcal{A}$, i.e. $\mathcal{A}$ is an antichain. We present a general construction of such antichains for sets $K$ containing 2, but not 1. If $3\in K$ our construction asymptotically yields the smallest possible size of such a family, up to an $o(n^2)$ error. We conjecture our construction to be asymptotically optimal also for $3\not\in K$, and we prove a weaker bound for the case $K=\{2,4\}$. Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory, which is interesting in its own right.