Difficult examples for Frankl's union-closed conjecture

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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