zbMATH — the first resource for mathematics

Note on generating all subsets of a finite set with disjoint unions. (English) Zbl 1229.05260
Summary: We call a family \({\mathcal G} \subset {\mathbb P}[n]\) a \(k\)-generator of \({\mathbb P}[n]\) if every \(x \subset [n]\) can be expressed as a union of at most \(k\) disjoint sets in \({\mathcal G}\). Y. Frein, Lévêque and A. Sebő [Comb. Probab. Comput. 17, No. 5, 641–660 (2008; Zbl 1191.05010)] 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 \({\mathbb P}[n]\) must have size at least \(k2^{n/k}(1-o(1))\), thereby verifying the conjecture asymptotically for multiples of \(k\).

05D05 Extremal set theory
Zbl 1191.05010
Full Text: EuDML EMIS