Note on Generating All Subsets of a Finite Set with Disjoint Unions

  • David Ellis

Abstract

We call a family ${\cal G} \subset {\Bbb P}[n]$ a $k$-generator of ${\Bbb P}[n]$ if every $x \subset [n]$ can be expressed as a union of at most $k$ disjoint sets in ${\cal G}$. Frein, Lévêque and Sebő conjectured that for any $n \geq k$, such a family must be at least as large as the $k$-generator obtained by taking a partition of $[n]$ into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We generalize a theorem of Alon and Frankl in order to show that for fixed $k$, any $k$-generator of ${\Bbb P}[n]$ must have size at least $k2^{n/k}(1-o(1))$, thereby verifying the conjecture asymptotically for multiples of $k$.

Published
2009-05-20
Article Number
N16