|
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+π(πΒ²). |
|