Improving the Lower Bound for the Union-closed Sets Conjecture via Conditionally IID Coupling
- Resource Type
- Conference
- Authors
- Liu, Jingbo
- Source
- 2024 58th Annual Conference on Information Sciences and Systems (CISS) Information Sciences and Systems (CISS), 2024 58th Annual Conference on. :1-6 Mar, 2024
- Subject
- Aerospace
Communication, Networking and Broadcast Technologies
Robotics and Control Systems
Signal Processing and Analysis
Couplings
Heart
Vectors
Random variables
Optimization
Information theory
- Language
- ISSN
- 2837-178X
Recently, Gilmer proved the first constant lower bound for the union-closed sets conjecture via an information-theoretic argument. The heart of the argument is an entropic inequality involving the OR function of two i.i.d. binary vectors, and the best constant obtainable through the i.i.d. coupling is $\frac{{3 - \sqrt 5 }}{2} \approx 0.38197$. Sawin demonstrated that the bound can be strictly improved by considering a convex combination of the i.i.d. coupling and the max-entropy coupling, and the best constant obtainable through this approach is around 0.38234, as evaluated by Yu and Cambie. In this work we show analytically that the bound can be further strictly improved by considering another class of coupling under which the two binary sequences are i.i.d. conditioned on an auxiliary random variable. We also provide a new class of bounds in terms of finite-dimensional optimization. Additional results about evaluations of the bounds can be found in arXiv:2306.08824