9
$\begingroup$

Let $\mathcal{F}\subseteq2^{[n]},\emptyset\in\mathcal{F}$ be an union-closed family of sets. For $S\in\mathcal{F}$, let $w(S)$ be the number of subsets of $S$ in $\mathcal{F}$. Does there always exist real numbers $a_1,a_2,...,a_n\geq1$ such that $\prod_{i=1}^na_i=|\mathcal{F}|$ and for every $S\in\mathcal{F}$, $\prod_{i\in S}a_i\geq w(S)$?

Motivation: Let $w_i$ be the number of sets of $\mathcal{F}$ that contain $i$. If the above conjecture true, we have $\sum_{i=1}^n\ln a_iw_i\geq\sum_{S\in\mathcal{F}}\ln w(S)$, so we just have to prove $\sum_{S\in\mathcal{F}}\ln w(S)\geq\sum_{i=1}^n\ln a_i\frac{|\mathcal{F}|}{2}=\frac{|\mathcal{F}|\ln|\mathcal{F}|}{2}$ that would imply Frankl's conjecture.

$\endgroup$
5
  • 2
    $\begingroup$ Wait, so you don't know if an affirmative answer to your question implies Frankl's conjecture? You need to prove something else as well? (Just making sure I understand.) $\endgroup$ Commented Dec 1 at 13:12
  • 3
    $\begingroup$ @mathworker21 If my conjecture, together with the last inequality is true, then the Frankl's conjecture is true. In other way, if my conjecture is true, we just need to prove the last inequality to prove the Frankl's conjecture. $\endgroup$ Commented Dec 1 at 13:22
  • 1
    $\begingroup$ do you count $S$ itself in the definition of $w(S)$ or is it just proper subsets of $S$? i.e.: are all the $w(S) \geq 2$ because every $S$ contains the empty set and $S$ itself? $\endgroup$
    – mhum
    Commented Dec 3 at 19:45
  • 1
    $\begingroup$ @mhum count itself too $\endgroup$ Commented Dec 3 at 19:54
  • 1
    $\begingroup$ Ah, I think I see. When $\mathcal{F} = 2^{[n]}$, then we can take $a_i = 2$ for all $i$ and the inequality is tight. $\endgroup$
    – mhum
    Commented Dec 3 at 20:27

1 Answer 1

6
+50
$\begingroup$

so we just have to prove $\sum_{S\in\mathcal{F}}\ln w(S)\geq \dots\frac{|\mathcal{F}|\ln|\mathcal{F}|}{2}$

This inequality does not depend on the choice of $a_i$'s, and, unfortunately, it can fail. For instance, let $n=3$ and $\mathcal F=\{\emptyset,\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$). Then $|\mathcal F|=5$, $\sum_{S\in\mathcal{F}}\ln w(S)=\ln 1+3\ln 2+\ln 5$ and $\frac{|\mathcal{F}|\ln|\mathcal{F}|}{2}=\frac{5\ln 5}{2}$. But $$\ln 1+3\ln 2+\ln 5-\frac{5\ln 5}{2}=3\cdot\left(\ln 2-\frac{\ln 5}{2}\right)<0.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .