Induction de conjecture fermée par union

Question

Je voudrais un exemple montrant que l'une des approches d'induction les plus élémentaires de la conjecture union-fermée échoue. Si, pour toute famille fermée par un syndicat$\mathcal{A}$ de sous-ensembles d'un ensemble fini $X$, il y en a $x \in X$ de telle sorte que chacun $y \in X$ possède $|\{A \in \mathcal{A} : A \ni y \text{ and } A \ni x\}| \ge \frac{1}{2}|\{A \in \mathcal{A} : A \ni x\}|$, alors nous pouvons simplement utiliser l'induction appliquée à la famille fermée par union $\{A \in \mathcal{A} : A \not \ni x\}$ pour avoir quelques $y \in X$ dans au moins la moitié des ensembles de $\{A \in \mathcal{A} : A \not \ni x\}$, et par notre choix de $x$, on voit alors que $y$ est dans au moins la moitié des ensembles de $\mathcal{A}$.

Je dois penser qu'il existe un exemple connu montrant que cette approche ne fonctionne pas, c'est-à-dire qu'il y a un $\mathcal{A}$ sans tel $x$. Mais je ne pouvais pas penser à un exemple. Donc,:

Donnez un exemple d'ensemble fini $X$ et une famille fermée par un syndicat $\mathcal{A} \subseteq \mathcal{P}(X)$ tel que, pour chaque $x \in X$, il y en a $y \in X$ avec $$|\{A \in \mathcal{A} : A \ni y \text{ and } A \ni x\}| < \frac{1}{2}|\{A \in \mathcal{A} : A \ni x\}|.$$ (Ou prouvez la conjecture fermée par union!)

J'évite les cas dégénérés, comme $X = \emptyset$, $\mathcal{A} = \emptyset$, ou alors $\mathcal{A} = \{\emptyset\}$.

Answer 1

Laisser $X = 123456$, et $\mathcal{A} = \{134, 1345, 1346, 13456, 256, 2356, 2456, 23456, 123456\}$. Laisser$f_x$ et $f_{x, y}$ être le nombre d'ensembles dans $\mathcal{A}$ contenant $x$, ou les deux $x$ et $y$respectivement. Dis ça$y$ est rare pour $x$ si $f_{x, y} < f_x / 2$. Puis:

• $f_1 = f_2 = 5$, mais $f_{1, 2} = 1$, Donc $1$ et $2$ sont rares les uns pour les autres;

• $f_3 = f_4 = 7$, mais $f_{3, 2} = f_{4, 2} = 3$, Donc $2$ est rare pour $3$ et $4$;

• De même, $1$ est rare pour $5$ et $6$.