
doi: 10.37236/158
We study maximal families ${\cal A}$ of subsets of $[n]=\{1,2,\dots,n\}$ such that ${\cal A}$ contains only pairs and triples and $A\not\subseteq B$ for all $\{A,B\}\subseteq{\cal A}$, i.e. ${\cal A}$ is an antichain. For any $n$, all such families ${\cal 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({\cal A})$ of ${\cal A}$ is considered. We show that $\min w({\cal 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\ge 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({\cal A})=w_2n^2/2+o(n^2)$.
Combinatorics of partially ordered sets, Extremal problems in graph theory, Extremal set theory
Combinatorics of partially ordered sets, Extremal problems in graph theory, Extremal set theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
