12
$\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$
    – BillyJoe
    Aug 14 '21 at 13:26
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 '14 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 '14 at 11:25
  • $\begingroup$ I ran a couple of tests in Sage, which convinced me that the idea does not work :-) $\endgroup$ Apr 7 '14 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 '14 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 '14 at 11:57

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.