10
$\begingroup$

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\}$.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Nice, I assume this is from a computer search? $\endgroup$ – Bjørn Kjos-Hanssen Nov 1 '20 at 0:45
  • 6
    $\begingroup$ No, this wasn't hard to do with pen and paper. $\endgroup$ – Mikhail Tikhomirov Nov 1 '20 at 0:48
  • 9
    $\begingroup$ You can also reduce it to 1234, 12, 123, 23, 234, 34, 1->4, 2->4, 3->1, 4->1. $\endgroup$ – fedja Nov 1 '20 at 1:14
  • $\begingroup$ 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. $\endgroup$ – mathworker21 Nov 2 '20 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.