Article ; Online: Dimension-Free Bounds for the Union-Closed Sets Conjecture.
2023 Volume 25, Issue 5
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 ...
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. |
---|---|
Language | English |
Publishing date | 2023-05-08 |
Publishing country | Switzerland |
Document type | Journal Article |
ZDB-ID | 2014734-X |
ISSN | 1099-4300 ; 1099-4300 |
ISSN (online) | 1099-4300 |
ISSN | 1099-4300 |
DOI | 10.3390/e25050767 |
Database | MEDical Literature Analysis and Retrieval System OnLINE |
More links
Kategorien
Order via subito
This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.