|
Let 𝑛 ≥ 4 be a natural number, and let 𝐾 be a set 𝐾 ⊆ [𝑛] := {1, 2, . . . , 𝑛}. We study the problem to find the smallest possible size of a maximal family 𝒜 of subsets of [𝑛] such that 𝒜 contains only sets whose size is in 𝐾, and 𝐴 ⊈ 𝐵 for all {𝐴, 𝐵} ⊆ 𝒜, i.e. 𝒜 is an antichain. We present a general construction of such antichains for sets 𝐾 containing 2, but not 1. If 3 ∈ 𝐾 our construction asymptotically yields the smallest possible size of such a family, up to an 𝑜(𝑛²) error. We conjecture our construction to be asymptotically optimal also for 3 ∉ 𝐾, and we prove a weaker bound for the case 𝐾 = {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. |
|