Maximal flat antichains of minimum weight (Q1028854)

Summary: We study maximal families \({\mathcal A}\) of subsets of \([n]=\{1,2,\dots,n\}\) such that \({\mathcal A}\) contains only pairs and triples and \(A\not\subseteq B\) for all \(\{A,B\}\subseteq{\mathcal A}\), i.e., \({\mathcal A}\) is an antichain. For any \(n\), all such families \({\mathcal A}\) of minimum size are determined. This is equivalent to finding all graphs \(G=(V,E)\) with \(|V|=n\) and with the property that every edge is contained in some triangle and such that \(|E|-|T|\) is maximum, where \(T\) denotes the set of triangles in \(G\). The largest possible value of \(|E|-|T|\) turns out to be equal to \(\lfloor(n+1)^2/8\rfloor\). Furthermore, if all pairs and triples have weights \(w_2\) and \(w_3\), respectively, the problem of minimizing the total weight \(w({\mathcal A})\) of \({\mathcal A}\) is considered. We show that \(\min w({\mathcal A})=(2w_2+w_3)n^2/8+o(n^2)\) for \(3/n\leq w_3/w_2=:\lambda=\lambda(n)<2\). For \(\lambda\geq 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 w({\mathcal A})=w_2n^2/2+o(n^2)\).