Martin Grüttmüller, Sven Hartmann, Thomas Kalinowski, Uwe Leck, Ian T. Roberts
Maximal flat antichains of minimum weight
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

05D05 Extremal set theory

06A07 Combinatorics of partially ordered sets

Abstract: 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 $0 Keywords: Antichain, Sperner family, Flat Antichain Theorem, LYM inequality, Extremal Graph Theory