Dimension-Free Bounds for the Union-Closed Sets Conjecture

并集-闭集猜想的无维界限

阅读:1

Abstract

The union-closed sets conjecture states that, in any nonempty union-closed family F of subsets of a finite set, there exists an element contained in at least a proportion 1/2 of the sets of F. Using an information-theoretic method, Gilmer recently showed that there exists an element contained in at least a proportion 0.01 of the sets of such F. He conjectured that their technique can be pushed to the constant 3-52 which was subsequently confirmed by several researchers including Sawin. Furthermore, Sawin also showed that Gilmer's technique can be improved to obtain a bound better than 3-52 but this new bound was not explicitly given by Sawin. This paper further improves Gilmer's technique to derive new bounds in the optimization form for the union-closed sets conjecture. These bounds include Sawin's improvement as a special case. By providing cardinality bounds on auxiliary random variables, we make Sawin's improvement computable and then evaluate it numerically, which yields a bound approximately 0.38234, slightly better than 3-52≈0.38197.

特别声明

1、本页面内容包含部分的内容是基于公开信息的合理引用;引用内容仅为补充信息,不代表本站立场。

2、若认为本页面引用内容涉及侵权,请及时与本站联系,我们将第一时间处理。

3、其他媒体/个人如需使用本页面原创内容,需注明“来源:[生知库]”并获得授权;使用引用内容的,需自行联系原作者获得许可。

4、投稿及合作请联系:info@biocloudy.com。