Generating all subsets of a finite set with disjoint unions |
| |
Authors: | David Ellis |
| |
Affiliation: | a St John?s College, Cambridge, CB2 1TP, United Kingdom b Department of Mathematics, UCLA, Los Angeles, CA 90095, United States |
| |
Abstract: | If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3. |
| |
Keywords: | Generator Disjoint unions Extremal set theory |
本文献已被 ScienceDirect 等数据库收录! |
|