[Math] Difficult examples for Frankl’s union-closed conjecture

co.combinatoricsexamplesopen-problems

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.

Best Answer

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.

Related Question