13
$\begingroup$

Frankl's union-closed conjecture states that if $F$ is a finite union-closed family of sets (i.e. a family that is closed under taking unions), then there must be an element that belongs to at least half the sets.

1) Does anyone know an example of a finite union-closed family $F$ such that the set $\mathcal{A}(F)$ of elements that belong to at least half the sets of $F$ is not a member of $F$? [edit: this is answered below by Thomas Bloom]

2) Does anyone know an example where no member of $F$ is a subset of $\mathcal{A}(F)$?

$\endgroup$
1
  • $\begingroup$ We can say that $\mathcal{A}(F)$ is equal to a member of $F$ OR the intersection of some members of $F$. To see why, see equation $(1)$ here. Probably that doesn't help much though. $\endgroup$ Aug 14, 2021 at 13:26

3 Answers 3

8
$\begingroup$

The simplest example I found is the family

$$ \emptyset, \{1\}, \{1,2,3\}, \{1,2,4\}, \{1,2,3,4\} $$

This is a union-closed family with 5 elements. 1 appears in 4, 2 appears in 3, 3 and 4 both appear in 2, but $\{1,2\}$ is not in the family.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! I was too optimistic! Yet, I'm wondering if there is an example of a finite union-closed family $F$ such that the set of elements that belong to at least half the sets of $F$ does not contain any member of $F$? $\endgroup$ Apr 7, 2014 at 14:35
8
$\begingroup$

As for question 2), I just found the following example:

Let $\mathcal{P}$ be the family of all non-empty subsets of $\{1,2,3,4\}$, and $\mathcal{F}$ be the family whose elements are all the sets $P\cup\{5,6,7,8,9\}$ with $P\in\mathcal{P}$ and the 4 sets

$$\{1,5,6,7,8\},\{2,5,6,7,9\},\{3,5,6,8,9\},\{4,5,7,8,9\}.$$

This union-closed family has 19 members. 1,2,3 and 4 belong to 9 sets, 6,7,8,9 to 18 sets and 5 belongs to 19 sets. Thus $\mathcal{A}(F)=\{5,6,7,8,9\}$ and no member of the family is a subset of $\mathcal{A}(F)$.

$\endgroup$
1
$\begingroup$

What if you take $F$ to be all subsets of size $>k$ of $[n]$, add to it the sets $\{1...k-1\}$ and $\{2...k\}$ ? This family $F$ contains all sets of size $>k$ and two sets of size exactly $k-1$ (thus it is union-closed), and I would say that the most frequent elements are $\{2,...,k-1\}$, i.e. a set of size $k-2$ that does not belong to $F$.

Nathann

$\endgroup$
4
  • 1
    $\begingroup$ I think you mean $\ge k$. If so, then for $k=3, n=4$ this is not an example. $4 \in \lbrace 1,2,3,4 \rbrace,\lbrace 1,2,4 \rbrace, \lbrace 1,3,4\rbrace, \lbrace 2,3,4\rbrace$ so $4$ is in $4$ out of $7$ sets. $1$ and $3$ are in $5$ out of $7$. $2$ is in $6$ out of $7$. $\endgroup$ Apr 7, 2014 at 11:25
  • $\begingroup$ I ran a couple of tests in Sage, which convinced me that the idea does not work :-) $\endgroup$ Apr 7, 2014 at 11:37
  • 1
    $\begingroup$ (I mean that the most frequent elements are those I want and they do not form a set of $F$, but all other elements will all appear more than 50%) $\endgroup$ Apr 7, 2014 at 11:40
  • $\begingroup$ For other parameters, every element is in the set, since there is an injection from sets not containing $x$ to sets containing $x$ by adding $x$. $\endgroup$ Apr 7, 2014 at 11:57

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.