A constant lower bound for the union-closed sets conjecture

Abstract

We show that for any union-closed family $\mathcal{F}\subseteq 2^{[n]},\mathcal{F}\ne \{\varnothing \}$, there exists an $i\in [n]$ which is contained in a $0.01$ fraction of the sets in $\mathcal{F}$. This is the first known constant lower bound, and improves upon the $\Omega ({\log }_2(|\mathcal{F}|{)}^{-1})$ bounds of Knill and Wójick. Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if $A,B$ are independent samples from a distribution over subsets of $[n]$ such that $Pr[i\in A]<0.01$ for all $i$ and $H(A)>0$, then $H(A\cup B)>H(A)$.

9 pages, 1 figure. (Update 11/28/22: Typos fixed, and added reference to follow up work improving the bound and refuting Conjecture 1.)