Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
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$? –  MassiveJack Apr 7 at 14:35

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

share|improve this answer
1  
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$. –  Douglas Zare Apr 7 at 11:25
    
I ran a couple of tests in Sage, which convinced me that the idea does not work :-) –  Nathann Cohen Apr 7 at 11:37
1  
(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%) –  Nathann Cohen Apr 7 at 11:40
    
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$. –  Douglas Zare Apr 7 at 11:57

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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