Note on generating all subsets of a finite set with disjoint unions
The electronic journal of combinatorics, Tome 16 (2009) no. 1
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$.
@article{10_37236_254,
author = {David Ellis},
title = {Note on generating all subsets of a finite set with disjoint unions},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/254},
zbl = {1229.05260},
url = {http://geodesic.mathdoc.fr/articles/10.37236/254/}
}
David Ellis. Note on generating all subsets of a finite set with disjoint unions. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/254
Cité par Sources :