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

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there must be an element that belongs to at least half the sets.

I know that pretty well any naive approach one takes to this conjecture is known to fail. By "naive approach" I suppose I mean something like an observation that it would follow from such-and-such a stronger conjecture -- it seems that all sensible stronger conjectures one thinks of are false. A very simple example of a stronger conjecture would be that if you pick a random element then on average it will belong to at least half the sets. That is completely false: take the family that consists of the empty set, {1}, and {1,2,3,4,5,6,7,8,9,10}, for example. One can try to "correct" this strengthening by devices such as insisting that for any two elements there is a set that contains one and not the other (which WLOG is the case), but such corrections don't get one very far.

What I am asking for is examples, either small ones or ones that are constructed theoretically, of union-closed families that defeat more sophisticated strengthenings of the original conjecture. I'm fairly sure they are out there but I am not an expert on this problem so I don't know them myself.

Apologies in advance if this resembles an existing question (which it feels as thought it easily might). But I've looked and not found anything.

share|improve this question
    
Small detail: you want to rule out the case $F = \{\emptyset\}$, where the conjecture is false –  user332 Nov 26 '10 at 12:16
    
Out of curiosity: you may also assume WLOG that in the Venn diagram of your family every non-empty piece has just one element. (Forcing one to replace {2,3,4,5,6,7,8,9} in your example by just one element.) Is the stronger conjecture that mentioned still false then? –  Tim Dokchitser Nov 26 '10 at 13:20
    
The answer to Tim's question is yes. For instance, take all subsets of $\lbrace 1,2,3,4\rbrace$ together with the sets $\lbrace 1,2,\dots,n\rbrace$ for $5\leq n\leq 19$. –  Richard Stanley Nov 26 '10 at 20:30
    
The literature has the classic example of a union closed family with a three element set, none of whose elements are in half the members of the famiy. Work of Teresa Vaughn and colleagues have pushed this a little further, and also have results on a "dual" family. There are some lattice theoretic versions that Dwight Duffus might tell you about. I myself do not have any explicit examples for you. Will Jagy has my email address if you want to discuss some related ideas on the problem with me. Gerhard "17 Years and Still Thinking" Paseman, 2010.11.26 –  Gerhard Paseman Nov 26 '10 at 22:58
    
Does the conjecture still fails if your choose your random element by first choosing a random non-empty set in the family and then a random element in that set? –  Sune Jakobsen Nov 27 '10 at 8:38
show 1 more comment

2 Answers

i) Definitions:
Let $F$ be a union closed family (U.C. family for short)
Let $S$ := $\cup_{ \Omega \in F} \Omega $ (the support of the family).
Let $F_{x} $ denote the members of $F$ containing $x$.

A) Union Closed Average variation : ( with $S$ being $T_0$-separated by $F$)

$ \sum_{x \in S}{ |F_{x}| } is \ge |F|.|S|/2 $.
( That is average $F_x$ size (on $S$) is greater than $|F|/2$)

Note: I cannot find any counter-example.
The $T_0$ separation of $ S $ by $ F $ means that for any two different points ${x,y} $ there exist a member of $F$ containing one point and not the other(you can choose which!) .

Another avenue of generalization that I cannot dismiss is a the multiset variation.

B) Mutltiset variation :
F is a family of $(\Omega,\eta_{\Omega})$ where:
- the $\Omega$ forms an U.C family say $F_0$
- $\eta : F_0 \rightarrow \mathbb {N}^{\gt 0}$ ( or $\mathbb {R^{\gt 0}}$ or $ [1,2,..,p]$ ordered naturally )
- for any $ \Omega_1 , \Omega_2$ of $F_0$ : $ \eta_{\Omega_1 \cup \Omega_2} \ge Sup ( \eta_{\Omega_1} ,\eta_{\Omega_2} )$

Now the conjecture is: The best measured $F_x$ is at least half that of $F$, where measure means the sum of members measure : the standard U.C. conjecture appears when $\eta$ is the constant one function.

C) The general point of view: (not strictly a generalization as asked by M.O.),
The U.C. problem is I believe of a fundamental nature, it pertains to very weak structures in the following sense: in algebra the weak (or basic or atomic) structures are the ideals, in the case of an order (or lattice) it is an upset (a family stable by overclusion , otherwise said an over-set of any member is a member), whereas we have in this problem something even weaker or more basic: stable by max only. All this comes of observing first that U.C. conjecture is easy for upsets family and still unsolved otherwise and second that algebraic techniques are not very helpful.

share|improve this answer
add comment

I am not sure whether this is the type of things you are looking for, but here is a strengthening of the original conjecture for which I would like to have a counterexample.

Let $\mathcal{S}$ be a union-closed family and let $V$ be the maximal set in $\mathcal{S}$. Given $x \in V$, write $\mathcal{S}\_x $ for the family $\{A\setminus\{x\}: \ A \in \mathcal{S}, x \in A\}$ and $d_{\mathcal{S}}(x)= |\mathcal{S}_x|$ for the degree of $x$ in $\mathcal{S}$.

Claim: Suppose $x$ is an element of $\mathcal{V}$ of minimal degree in $\mathcal{S}$. Then for every $y \neq x$, we have \[ \frac{d_{\mathcal{S}_x}(y)}{d(x)}\geq \min \left(\frac{1}{2}, \frac{d(y)}{|\mathcal{S}|}\right).\]

(In other words if an element has lowest degree in $\mathcal{S}$ than the other elements must correlate well with it.)

share|improve this answer
    
Sorry that was meant to be a comment/question, not an answer. –  Victor Falgas--Ravry Jan 5 '11 at 9:54
2  
Actually I am being stupid. The claim above is easily seen to be false. Here is a counterexample: let $V= [2n]\cup\{a,b\}$, and let $S_1= \{ X:\ X \subseteq [2n], |X|>2\}$, $S_2=\{X\cup[n]\cup \{a\}:\ X \subseteq \{n+1,n+2, \ldots 2n\}\}$, $S_3=\{X \cup\{n+1, n+2, \ldots 2n\} \cup \{b\}:\ X \subseteq [n]\}$. Then $\mathcal{S}= S_1\cup S_2\cup S_3 \cup \{V\}$ is union-closed, $a$ and $b$ have minimal degree and yet the density of $a$ in $\mathcal{S}_b$ is only $\frac{1}{2^n+1}$, while the density of $a$ in $\mathcal{S}$ is $\frac{2^{n}+1}{2^{2n}+2^{n+1}-2n}>\frac{1}{2^n+1}$. –  Victor Falgas--Ravry Jan 14 '11 at 13:59
    
$\mathcal{S}_1$ should be $\{X:\ X \subseteq[2n], |X| \geq 2\}$ in the above. So what I would be looking for rather is a precise-ish statement of the form ``either the claim holds or the family is quite structured (i.e. looks like $\mathcal{S}$ above '', and then a counterexample to that. –  Victor Falgas--Ravry Jan 14 '11 at 14:04
add comment

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.