9
$\begingroup$

A Frankl family is a nonempty finite family $\mathcal F$ of nonempty finite sets such that $A,B\in\mathcal F\implies A\cup B\in\mathcal F.$ Define $d_\mathcal F(x)=|\{A\in\mathcal F:x\in A\}|$ and $\Delta(\mathcal F)=\max_xd_\mathcal F(x).$ Frankl's union-closed sets conjecture says that $\Delta(\mathcal F)\gt\frac12|\mathcal F|,$ or in other words $|\mathcal F|\le2\Delta(F)-1,$ for any Frankl family $\mathcal F.$ Has the following stronger conjecture been considered, and is a counterexample known?

For any Frankl family $\mathcal F$ there is an element $x$ such that $\Delta(\{A\in\mathcal F:x\notin A\})\le\frac12\Delta(\mathcal F),$

or better yet,

for any Frankl family $\mathcal F$ and any element $x,$ if $d_\mathcal F(x)=\Delta(\mathcal F)$ then $\Delta(\{A\in\mathcal F:x\notin A\})\le\frac12\Delta(\mathcal F)$?

$\endgroup$
  • $\begingroup$ Isn't the powerset of {1,2,3} counterexample to both? $\endgroup$ – joro Jan 11 '16 at 7:37
  • $\begingroup$ Maybe I misunderstood, but there 8 sets in the power set. $3$ is in half of the sets and not in the other half, so you have equality. If you don't count the empty set, this make $3$ not in $3$ sets and your inequality still doesn't hold. $\endgroup$ – joro Jan 11 '16 at 8:41
  • $\begingroup$ What has $\mathcal P(\{1,2\})$ to do with my claim? $\endgroup$ – joro Jan 11 '16 at 8:46
  • $\begingroup$ OK. $|\mathcal P(\{1,2\})|=2^2=4$. If you don't count the empty sets it makes it $3$. You divide by $2$. $\endgroup$ – joro Jan 11 '16 at 8:57
  • $\begingroup$ I misunderstood, sorry. Indeed mine is not counterexample. $\endgroup$ – joro Jan 11 '16 at 9:19
5
$\begingroup$

It seems that here is a counterexample to the stronger statement. Perhaps, it can be modified to provide one for the weaker statement?

Our universe is $\{1,\dots,7\}$. Each set of the family contains either $6$, or $7$, or both. We asume that the elements $1,\dots,5$ are arranged into a cycle $1-2-3-4-5-1$.

The sets containing $6$ but not $7$ are obtained from $\{6\}$ by adding either (2-6) two consecutive elements from the cycle, or (3-6) three consecutive elements, or $\{1,2,4\}$, or $\{2,3,5\}$, or $\{1,3,4\}$, or (4-6) arbitrary four or five elements from the cycle. 19 sets in all.

The sets containing $7$ but not $6$ are obtained from $\{7\}$ by adding either (2-7) two non-consecutive elements from the cycle, or (3-6) three non-consecutive elements, or $\{3,4,5\}$, or $\{5,1,2\}$, or (4-6) arbitrary four or five elements from the cycle. $18$ sets in all.

The sets containing both $6$ and $7$ are obtained from $\{6,7\}$ by adding at least three elements from the cycle. $16$ sets in all.

These sets form a Frankl family. Now, $6$ is contained in $35$ sets, $7$ --- in $34$ sets, any other element --- in at most $34$ sets. Thus the unique element with the largest degree is $6$ (this was the aim for which we have added extra triples), and this degree is $35.$ But all the sets not containing $6$ do contain $7$, and there are $18>35/2$ of them.

Thus the conjectured property may fail even for every element of the largest degree.

$\endgroup$
  • $\begingroup$ Thank you for the nice counterexample. I accept it now, but I will move the acceptance if someone provides a counterexample to the weaker conjecture. $\endgroup$ – bof Jan 15 '16 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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