# 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$$.

##### MSC:
 05D05 Extremal set theory
Zbl 1191.05010
Full Text: