Minimizing the Number of Unions

Abstract

For a given number of $k$-sets, how should we choose them so as to minimize the union-closed family that they generate? Our main aim in this paper is to show that, if $\mathcal{A}$ is a family of $k$-sets of size $\left(\genfrac{}{}{0ex}{}{t}{k}\right)$, and $t$ is sufficiently large, then the union-closed family generated by $\mathcal{A}$ has size at least that generated by the family of all $k$-sets from a $t$-set. This proves (for this size of family) a conjecture of Roberts. We also make some related conjectures, and give some other results, including a new proof of the result of Leck, Roberts and Simpson that exactly determines this minimum (for all sizes of the family) when $k=2$.

arXiv comment13 pages