Maximal flat antichains of minimum weight (Q1028854): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:57, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximal flat antichains of minimum weight |
scientific article |
Statements
Maximal flat antichains of minimum weight (English)
0 references
8 July 2009
0 references
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)\).
0 references