Maximal flat antichains of minimum weight Grüttmüller, Martin , 1970- (VerfasserIn) Kalinowski, Thomas , 1980- (VerfasserIn) Leck, Uwe , 1969- (VerfasserIn) Hartmann, Sven , 1969- (VerfasserIn) Roberts, Ian T. (VerfasserIn) Text Text 2005 2005 eng electronic resourceremoteComputermedienOnline-Ressource1 Online-Ressource (19 Seiten) 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> Open Access Urheberrechtsschutz 1.0 Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Roberts 510 https://purl.uni-rostock.de/rosdok/id00005898 Maximal flat antichains of minimum weight--(DE-627)488263573 urn:nbn:de:gbv:28-rosdok_id00005898-4 doi: 10.18453/rosdok_id00005898 oclc: 1621945821 ppn: (DE-627)1987259742