TY  - BOOK
AU  - Grüttmüller, Martin
AU  - Kalinowski, Thomas
AU  - Leck, Uwe
AU  - Hartmann, Sven
AU  - Roberts, Ian T.
PY  - 2005
DA  - 2005//
TI  - Maximal flat antichains of minimum weight
T3  - Preprints aus dem Institut für Mathematik
CY  - Germany; Rostock
AB  - We study maximal families A of subsets of [n] = {1; 2; : : : ; n} such that A contains only pairs and triples and A /⊆ B for all {A,B} ⊆ A, i.e. A is an antichain. For any n, all such families 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 ⌊(n+1)^2/8⌋. Furthermore, if all pairs and triples have weights w2 and w3, respectively, the problem of minimizing the total weight w(A) of A is considered. We show that min w(A) = (2w2 + w3)n^2/8 + o(n^2) for 0 < w3/w2 =: λ = λ(n) < 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 w(A) = w2n^2/2 + o(n^2).<eng>
UR  - https://purl.uni-rostock.de/rosdok/id00005898
UR  - https://doi.org/10.18453/rosdok_id00005898
DO  - 10.18453/rosdok_id00005898
LA  - English
N1  - Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Roberts
ID  - 1987259742
ER  -