Find set configurations that imply FUNC: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
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.