Maximal antichains of minimum size (Q1953477)

Summary: 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.