50
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 26, 2010 at 13:20
  • 2
    $\begingroup$ 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$. $\endgroup$ Nov 26, 2010 at 20:30
  • 2
    $\begingroup$ 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 $\endgroup$ Nov 26, 2010 at 22:58
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 27, 2010 at 8:38
  • 1
    $\begingroup$ Sune, the system emptyset, 1, 2, 12, {1,...,10}, {1,...,100}, {1,...,1000},...,{1,...,10000000000} is a counterexample. I haven't checked whether there is a counterexample such that any two elements are separated by at least one set in the family, but I expect there is. $\endgroup$
    – gowers
    Nov 27, 2010 at 15:14

4 Answers 4

20
$\begingroup$

Here is a nice example due to Bjorn Poonen, which I have taken from this survey paper of Bruhn and Schaudt. It is motivated by the following observations. Let $\mathcal{A}$ be a union-closed family. Call an element $x$ abundant if $x$ is contained in at least half of the members of $\mathcal{A}$.

Observation. If $\mathcal{A}$ contains a singleton $\{x\}$, then $x$ is abundant.

Proof. Partition $\mathcal{A}$ as $\mathcal{A}_x$ and $\overline{A}_x$ where $\mathcal{A}_x$ consists of the members of $\mathcal{A}$ containing $x$ and $\overline{A}_x$ are the members of $\mathcal{A}$ not containing $x$. Since $\{x\} \in \mathcal{A}$ and $\mathcal{A}$ is union-closed, the map $S \mapsto S \cup \{x\}$ is an injection from $\overline{A}_x$ to $\mathcal{A}_x$. Thus, $|\overline{A}_x| \leq |\mathcal{A}_x|$, as required. $\square$

Similarly, we also have the following.

Observation. If $\mathcal{A}$ contains a $2$-set $\{x,y\}$, then $x$ or $y$ is abundant.

This might lead one to conjecture the following false strengthening of Frankl's Union-closed Conjecture.

False Strengthening. Let $S$ be a non-empty member of $\mathcal{A}$ with the smallest number of elements. Then $S$ contains an abundant element.

Disproof. For two families $\mathcal{A}$ and $\mathcal{B}$ we let $$ \mathcal{A} \uplus \mathcal{B}=\{S \cup T: S \in \mathcal{A}, T \in \mathcal{B}\}. $$

Fix $k \geq 3$ and for each $i \in [k]$ define $$ \mathcal{B}^i=\{[k+1,3k] \setminus \{2i+k-1\}, [k+1,3k] \setminus \{2i+k\}\}. $$

Finally, define $$ \mathcal{A}^k=\{[k]\} \cup \bigcup_{i=1}^k(\{\emptyset, \{i\}, [k]\} \uplus \mathcal{B}^i) \cup (2^{[k]} \uplus [k+1,3k]). $$

It is easy to check that $\mathcal{A}^k$ is union-closed and that $[k]$ is the unique smallest set in $\mathcal{A}^k$. However, $|\mathcal{A}^k|=1+6k+2^k$ and each $i \in [k]$ is contained in only $1+(2k+2)+2^{k-1}$ members of $\mathcal{A}^k$. Thus, no element of $[k]$ is abundant. $\square$

This example highlights one of the obstacles in proving the Union-closed Conjecture; it is difficult to predict where abundant elements will be.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Sorry that was meant to be a comment/question, not an answer. $\endgroup$ Jan 5, 2011 at 9:54
  • 2
    $\begingroup$ 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}$. $\endgroup$ Jan 14, 2011 at 13:59
  • $\begingroup$ $\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. $\endgroup$ Jan 14, 2011 at 14:04
1
$\begingroup$

Here is a generalisation, quite a strong one : Let $E$ be a finite set $F\subset \mathcal P(E)$, such that $\emptyset\notin F$, $E\in F$, and $F$ closed for union.

Let $f(F)=\left\{x\in E| |F_x|<|F|/2\right\}$ where $F_x=\left\{a\in F|x\in a\right\}$.

Conjecture: $f(F)\notin F$.

(Union Closed conjecture $\iff$ $f(F)\ne E$, so it's much stronger.)

$\endgroup$
4
  • $\begingroup$ I think it is too strong. I would start with Sarvate and Renaud's example showing an F (with E having 9 elements, I think) whose smallest member contains three elements, none of which belong to half the members of F. Gerhard "Doesn't Remember The Details Yet" Paseman, 2016.01.10 $\endgroup$ Jan 11, 2016 at 6:51
  • $\begingroup$ I don't realy understand... sorry^^. You have a exemple of failure of the"strong one" (whith E having nine éléments... etc...?) can you give it précisely? thank you:) $\endgroup$ Jan 11, 2016 at 23:46
  • $\begingroup$ bof posted one recently at mathoverflow.net/questions/138567 . If that doesn't work, I feel a similar example should. Gerhard "False Is Stronger Than True?" Paseman, 2016.01.11 $\endgroup$ Jan 11, 2016 at 23:50
  • $\begingroup$ The link wordek : You seem right! congratulations!! $\endgroup$ Jan 12, 2016 at 2:11

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.