We show that for any union-closed family F\subseeq 2^[n],F≠{∅}, there exists an i∈[n] which is contained in a 0.01 fraction of the sets in F. This is the first known constant lower bound, and improves upon the Ω(log_2(|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∈A]<0.01 for all i and H(A)>0, then H(A∪B)>H(A).
Abstract:
We show that for any union-closed family F\subseeq 2^[n],F≠{∅}, there exists an i∈[n] which is contained in a 0.01 fraction of the sets in F. This is the first known constant lower bound, and improves upon the Ω(log_2(|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∈A]<0.01 for all i and H(A)>0, then H(A∪B)>H(A).