Approximate union closed conjecture
Approximate union closed conjecture
复制标题
近似并集封闭猜想
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Zachary Chase;Shachar Lovett
如果集合系统中的任意两个集合的并也在集合系统中，则集合系统称为并闭集。Gilmer最近证明了在任何并闭集系统中，某些元素至少属于0。01集的分数，并猜想他的技巧可以推广到常数3−√5 2。我们验证了他的猜想；证明了它推广到近似并闭集系统，其中对于几乎所有的集合对，它们的并属于集合系统；并且证明了对于这样的集合系统，这个界是最优的。
A set system is called union closed if for any two sets in the set system their union is also in the set system. Gilmer recently proved that in any union closed set system some element belongs to at least a 0 . 01 fraction of sets, and conjectured that his technique can be pushed to the constant 3 −√ 5 2 . We verify his conjecture; show that it extends to approximate union closed set systems, where for nearly all pairs of sets their union belong to the set system; and show that for such set systems this bound is optimal.