Union closed conjecture induction

I would like an example showing that one of the most basic induction approaches to the union-closed conjecture fails. If, for any union-closed family $$\mathcal{A}$$ of subsets of a finite set $$X$$, there is some $$x \in X$$ such that each $$y \in X$$ has $$|\{A \in \mathcal{A} : A \ni y \text{ and } A \ni x\}| \ge \frac{1}{2}|\{A \in \mathcal{A} : A \ni x\}|$$, then we can merely use induction applied to the union-closed family $$\{A \in \mathcal{A} : A \not \ni x\}$$ to get some $$y \in X$$ in at least half of the sets of $$\{A \in \mathcal{A} : A \not \ni x\}$$, and by our choice of $$x$$, we then see that $$y$$ is in at least half the sets of $$\mathcal{A}$$.

I have to think that there is a known example showing this approach doesn't work, i.e., there is an $$\mathcal{A}$$ with no such $$x$$. But I couldn't think of an example. So,:

Give an example of a finite set $$X$$ and a union-closed family $$\mathcal{A} \subseteq \mathcal{P}(X)$$ such that, for each $$x \in X$$, there is some $$y \in X$$ with $$|\{A \in \mathcal{A} : A \ni y \text{ and } A \ni x\}| < \frac{1}{2}|\{A \in \mathcal{A} : A \ni x\}|.$$ (Or prove the union-closed conjecture!)

I avoid degenerate cases, like $$X = \emptyset$$, $$\mathcal{A} = \emptyset$$, or $$\mathcal{A} = \{\emptyset\}$$.

1 Answer

Let $$X = 123456$$, and $$\mathcal{A} = \{134, 1345, 1346, 13456, 256, 2356, 2456, 23456, 123456\}$$. Let $$f_x$$ and $$f_{x, y}$$ be the number of sets in $$\mathcal{A}$$ containing $$x$$, or both $$x$$ and $$y$$ respectively. Say that $$y$$ is rare for $$x$$ if $$f_{x, y} < f_x / 2$$. Then:

• $$f_1 = f_2 = 5$$, but $$f_{1, 2} = 1$$, thus $$1$$ and $$2$$ are rare for each other;

• $$f_3 = f_4 = 7$$, but $$f_{3, 2} = f_{4, 2} = 3$$, thus $$2$$ is rare for $$3$$ and $$4$$;

• similarly, $$1$$ is rare for $$5$$ and $$6$$.

• Nice, I assume this is from a computer search? – Bjørn Kjos-Hanssen Nov 1 '20 at 0:45
• No, this wasn't hard to do with pen and paper. – Mikhail Tikhomirov Nov 1 '20 at 0:48
• You can also reduce it to 1234, 12, 123, 23, 234, 34, 1->4, 2->4, 3->1, 4->1. – fedja Nov 1 '20 at 1:14
• Thanks a lot! Also, thanks @fedja for the even simpler example! I can't believe there was an example for $X = \{1,2,3,4\}$ that I missed. Welp, I guess examples weren't insanely hard to come up with. I'll check if the union-closed family generated by $\{1,2\},\{2,3\},\dots,\{n-1,n\}$ always works. – mathworker21 Nov 2 '20 at 3:13