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)$?

Improve this question
$\endgroup$
8
  • $\begingroup$ Isn't the powerset of {1,2,3} counterexample to both? $\endgroup$
    – joro
    Commented Jan 11, 2016 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
    Commented Jan 11, 2016 at 8:41
  • $\begingroup$ What has $\mathcal P(\{1,2\})$ to do with my claim? $\endgroup$
    – joro
    Commented Jan 11, 2016 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
    Commented Jan 11, 2016 at 8:57
  • $\begingroup$ I misunderstood, sorry. Indeed mine is not counterexample. $\endgroup$
    – joro
    Commented Jan 11, 2016 at 9:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jan 15, 2016 at 3:24

You must log in to answer this question.

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