Maximal flat antichains of minimum weight
type: Item
instance of: scholarly article
title: Maximal flat antichains of minimum weight
zbMATH Open document ID: 1229.05261
author: Martin Grüttmüller
author: Sven Hartmann
author: Thomas Kalinowski
author: Uwe Leck
author: Ian T. Roberts
published in: The Electronic Journal of Combinatorics
publication date: 2009-07-08T00:00:00Z
full work available at URL: https://eudml.org/doc/117526
full work available at URL: v16i1r69.html
review text: 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)\).
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 5576450
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5576450