Note on Generating All Subsets of a Finite Set with Disjoint Unions
Note on Generating All Subsets of a Finite Set with Disjoint Unions
复制标题
关于生成具有不相交并的有限集的所有子集的注意事项
DOI：
--
复制
发表时间：
2008
影响因子：
0.7
通讯作者：
David Ellis
中科院分区：
文献类型：
--
作者：
David Ellis
我们称一个族${cal G}子集{Bbb P}[n]$ a $k$- ${Bbb P}[n]$的生成器，如果每个$x子集[n]$可以表示为${cal G}$中最多$k个不相交集合的并集。Frein， Leveque和sebov推测，对于任意$n geq k$，这个族必须至少与$k$-生成器一样大，该生成器是通过将$[n]$划分为大小尽可能相等的类，并取这些类的幂集的并而得到的。我们推广了Alon和Frankl的一个定理，证明了对于固定的$k$, ${Bbb P}[n]$的任意$k$-生成器必须具有至少$k2^{n/k}(1- 0(1))$的大小，从而渐近地验证了对于$k$的倍数的猜想。
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, Leveque 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$.