1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$ Commented Dec 26, 2022 at 23:28
  • $\begingroup$ 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$. $\endgroup$ Commented Dec 27, 2022 at 1:18
  • $\begingroup$ 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. $\endgroup$ Commented Dec 27, 2022 at 1:33
  • $\begingroup$ 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? $\endgroup$ Commented Jan 21, 2023 at 2:49
  • $\begingroup$ 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! $\endgroup$ Commented Jan 21, 2023 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.