posted on 2025-05-08, 16:41authored byThomas Kalinowski, Uwe Leck, Ian T. Roberts
Let n ⩾4 be a natural number, and let K be a set K⊆[n]:={1,2,...,n}. We study the problem of finding the smallest possible size of a maximal family A of subsets of [n] such that A contains only sets whose size is in K, and A⊈B for all {A,B}⊆A, i.e. A is an antichain. We present a general construction of such antichains for sets K containing 2, but not 1. If 3∈K our construction asymptotically yields the smallest possible size of such a family, up to an o(n²) error. We conjecture our construction to be asymptotically optimal also for 3∉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.