Find set configurations that imply FUNC: Difference between revisions
Tomtom2357 (talk | contribs) No edit summary |
Tomtom2357 (talk | contribs) No edit summary |
||
Line 1: | Line 1: | ||
== Introduction == | == Introduction == | ||
One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}</math>, contains at least as many sets as <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\}</math> | One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}</math>, contains at least as many sets as <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\}</math>. A slightly more clever argument shows that if a two element set {x, y} is in <math>\mathcal{A}</math>, then FUNC holds for <math>\mathcal{A}</math>: | ||
Let <math>\mathcal{A}_{xy} = \{A \in \mathcal{A} : x, y \in A\}</math>, <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\ , y\notin A\}</math>, <math>\mathcal{A}_y = \{A \in \mathcal{A} : y \in A\ , x\notin A\}</math>, <math>\mathcal{A}_\emptyset = \{A \in \mathcal{A} : x, y\notin A\}</math>. Because {x, y} is in <math>\mathcal{A}</math>, the set <math>\mathcal{A}_{xy}</math> has at least as many sets as <math>\mathcal{A}_\emptyset</math>. Therefore, depending on which of <math>\mathcal{A}_x</math> and <math>\mathcal{A}_y</math> is larger, x or y are in at least half of the sets. | |||
One might assume that a similar argument would work for three element sets, but unfortunately the argument fails. In fact, there is a family <math>\mathcal{A}</math> with only 9 elements in the ground set, and one set with three elements, such that none of those three elements is in at least half of the sets. |
Revision as of 07:40, 9 February 2016
Introduction
One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set [math]\displaystyle{ \mathcal{A}_x = \{A \in \mathcal{A} : x \in A\} }[/math], contains at least as many sets as [math]\displaystyle{ \mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\} }[/math]. A slightly more clever argument shows that if a two element set {x, y} is in [math]\displaystyle{ \mathcal{A} }[/math], then FUNC holds for [math]\displaystyle{ \mathcal{A} }[/math]:
Let [math]\displaystyle{ \mathcal{A}_{xy} = \{A \in \mathcal{A} : x, y \in A\} }[/math], [math]\displaystyle{ \mathcal{A}_x = \{A \in \mathcal{A} : x \in A\ , y\notin A\} }[/math], [math]\displaystyle{ \mathcal{A}_y = \{A \in \mathcal{A} : y \in A\ , x\notin A\} }[/math], [math]\displaystyle{ \mathcal{A}_\emptyset = \{A \in \mathcal{A} : x, y\notin A\} }[/math]. Because {x, y} is in [math]\displaystyle{ \mathcal{A} }[/math], the set [math]\displaystyle{ \mathcal{A}_{xy} }[/math] has at least as many sets as [math]\displaystyle{ \mathcal{A}_\emptyset }[/math]. Therefore, depending on which of [math]\displaystyle{ \mathcal{A}_x }[/math] and [math]\displaystyle{ \mathcal{A}_y }[/math] is larger, x or y are in at least half of the sets.
One might assume that a similar argument would work for three element sets, but unfortunately the argument fails. In fact, there is a family [math]\displaystyle{ \mathcal{A} }[/math] with only 9 elements in the ground set, and one set with three elements, such that none of those three elements is in at least half of the sets.