Maximal flat antichains of minimum weight

Abstract

We study maximal families 𝒜 of subsets of [𝑛]={1,2, . . . , 𝑛} such that 𝒜 contains only pairs and triples and 𝐴⊈𝐵 for all {𝐴,𝐵}⊆𝒜, i.e. 𝒜 is an antichain. For any 𝑛, all such families 𝒜 of minimum size are determined. This is equivalent to finding all graphs 𝐺=(𝑉,𝐸) with |𝑉|=𝑛 and with the property that every edge is contained in some triangle and such that|𝐸|−|𝑇| is maximum, where 𝑇 denotes the set of triangles in 𝐺. The largest possible value of |𝐸|−|𝑇| turns out to be equal to ⌊(𝑛+1)²/8⌋. Furthermore, if all pairs and triples have weights 𝑤₂ and 𝑤₃, respectively, the problem of minimizing the total weight 𝑤(𝒜) of 𝒜 is considered. We show that min 𝑤(𝒜)=(2𝑤₂+𝑤₃)𝑛²/8+𝑜(𝑛²) for 3/𝑛≤𝑤₃/𝑤₂=:λ=λ(𝑛)<2. For λ≥2 our problem is equivalent to the (6,3)-problem of Ruzsa and Szemerédi, and by a result of theirs it follows that min 𝑤(𝒜)= 𝑤₂𝑛²/2+𝑜(𝑛²).