


























We show that for any union-closed family $\mathcal{F} \subseteq 2^{[n]}, \mathcal{F} \neq \{\emptyset\}$, 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 $Ω(\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)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。