# Entropy upper bound for the union of uniform distributions over union-closed families

The following question is motivated by the recent breakthrough result by Justin Gilmer on the union-closed sets (aka Frankl) conjecture.

Let $$\mathcal{F}\subseteq\mathcal{P}(\mathbb{N})$$ be a finite, union-closed family, i.e. $$A,B\in\mathcal{F}\Rightarrow A\cup B\in\mathcal{F}$$. Let $$A_{\mathcal{F}}$$ and $$B_{\mathcal{F}}$$ be two independent random variables, uniformly distributed over the elements of $$\mathcal{F}$$. Denoting by $$H$$ the entropy, we clearly have $$H(A_{\mathcal{F}}\cup B_{\mathcal{F}})\leq H(A_{\mathcal{F}})=\ln|\mathcal{F}|,$$ since the entropy is maximized by the uniform distribution. I am wondering whether a sharper bound of the form $$H(A_{\mathcal{F}}\cup B_{\mathcal{F}})\leq \lambda H(A_{\mathcal{F}})$$, for some $$\lambda<1$$, still continue to hold. The intuition is that the distribution $$A_{\mathcal{F}}\cup B_{\mathcal{F}}$$ should "deviate" enough from the uniform bound in order to get a non-trivial upper bound on its entropy. Denoting by $$\mathrm{UC}$$ the collection of all finite, union-closed families $$\mathcal{F}\subseteq\mathcal{P}(\mathbb{N})$$ (with $$|\mathcal{F}|>1$$), we then consider the following quantity:

$$\lambda:=\sup_{\mathcal{F}\in UC}\frac{H(A_{\mathcal{F}}\cup B_{\mathcal{F}})}{H(A_{\mathcal{F}})}=\sup_{\mathcal{F}\in UC}\frac{H(A_{\mathcal{F}}\cup B_{\mathcal{F}})}{\ln|\mathcal{F}|}.$$

We have $$\lambda\leq 1$$, and by considering the union-closed families $$\mathcal{P}[n]\setminus\{\emptyset\}$$, we get the lower bound $$\lambda\geq 0.82$$.

Is $$\lambda=1$$ or $$\lambda<1$$? In the latter case, it is possible to provide an explicit, non-trivial upper bound?

## 1 Answer

The best upper bound is $$\lambda=1$$. Here is a simple family of examples: Let $$\mathcal F_n$$ be $$\Big\{\{1,\ldots,i\}\colon 1\le i\le n\}\Big\}$$. That is $$\mathcal F_n$$ is the collection of all initial segments of $$\{1,\ldots,n\}$$, which is clearly union-closed. Clearly $$|\mathcal F_n|=n$$, so that $$H(A)=\log n$$. Also if $$A:=[1,i]$$ and $$B:=[1,j]$$ are random elements of $$\mathcal F_n$$, then $$[1,i]\cup[1,j]=[1,\max(i,j)]$$ so that $$\mathcal P(A\cup B)=\{1,\ldots,k\}=(2k-1)/n^2$$. We now estimate $$H(A\cup B)$$. This is given by $$H(A\cup B)=-\sum_{j=1}^n \frac{2j-1}{n^2}\log \frac{2j-1}{n^2}.$$ We will approximate this by a Riemann sum to show that for large $$n$$, $$H(A\cup B)\approx H(A)-\log 2+\frac 12$$. To see this, we have $$H(A\cup B)=\sum_{j=1}^n\frac{2j-1}{n^2}\log n-\frac 1n \sum_{j=1}^n \frac{2j-1}n\log\frac{2j-1}n.$$ Hence $$H(A\cup B)\approx \log n - \int_{0}^1 2x\log(2x)\,dx,$$ giving $$H(A\cup B)\approx\log n-\log 2+\frac 12$$ as claimed.

• Thank you! In your example there is an element ($i=1$) which appears in every member of the family. Do you think the situation changes if we restrict to the case when $Pr(i\in A_{\mathcal{F}})\leq \lambda$ for every $i$, for some $\lambda<1$? Dec 26, 2022 at 23:28
• Cheaply, we could have the sets $\{i\colon i<j\}$ where $j$ runs from 1 to $n$ so that there is no element contained in all of the sets. But this doesn't solve the question with the additional constraint (I assume that the $\lambda$ in the question (the proportional entropy drop) is supposed to be distinct from this $\lambda$: the probability that each element lies in a random element of $\mathcal F$. Dec 27, 2022 at 1:18
• Yes sorry, they are not the same $\lambda$. I suspect indeed that with the extra constraint $Pr(i\in A_{F})\leq u<1\,\forall i$ , one could get $\lambda=\lambda(u)<1$. This would lead to an improvement on the best bound for the Frankl conjecture, so either it's false or it's probably an hard task. Dec 27, 2022 at 1:33
• I'm likely wrong (not my area), but didn't Gilmer (arxiv.org/abs/2211.09055) just give a constant lower bound (0.01 I think) for Frankl's conjecture? Jan 21 at 2:49
• Oops, I now see that you referenced Gilmer's paper in your post, so obviously you didn't need me to mention it. Sorry for the poor reading comprehension! Jan 21 at 3:42