Maximal flat antichains of minimum weight
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)\).
- Flattening antichains with respect to the volume
- Maximal antichains of minimum size
- The domination number of the graph defined by two levels of the \(n\)-cube
- The domination number of the graph defined by two levels of the \(n\)-cube. II
- Antichains and completely separating systems -- a catalogue and applications
- Minimum weight flat antichains of subsets
- Saturating Sperner families
- scientific article; zbMATH DE number 1051291 (Why is no real title available?)
- Improved bounds for cross-Sperner systems
- The saturation spectrum for antichains of subsets
- Independent domination in the graph defined by two consecutive levels of the \(n\)-cube
- Sizes of flat maximal antichains of subsets
This page was built for publication: Maximal flat antichains of minimum weight
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028854)
