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

1 Answer 1

11
$\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
  • 4
    $\begingroup$ Nice, I assume this is from a computer search? $\endgroup$ Nov 1, 2020 at 0:45
  • 7
    $\begingroup$ No, this wasn't hard to do with pen and paper. $\endgroup$ Nov 1, 2020 at 0:48
  • 11
    $\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, 2020 at 1:14

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.