论文标题
联合关闭集的恒定下限猜想
A constant lower bound for the union-closed sets conjecture
论文作者
论文摘要
我们表明，对于任何关闭联盟的家庭$ \ Mathcal {f} \ subseteq 2^{[n]}，\ Mathcal {f} \ neq \ neq \ {\ emptySet \} $，存在于$ 0.01 $ fr的$ frats $ frats $ fr的$ i \ in [n]中的$ i \。这是第一个已知的常数下限，并且在$ω（\ log_2（| \ Mathcal {f} |）|）^{ - 1}）$ bounds上进行了改进。我们的结果源于信息的理论加强。具体来说，我们表明，如果$ a，b $是来自$ [n] $的子集的独立样本，则所有$ i $和$ i $和$ i $和$ h（a）> 0 $的$ pr [i \ in] <0.01 $，则是$ h（a \ cup b）> h（a）$。
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)$.
