Find set configurations that imply FUNC

From Polymath Wiki
Revision as of 06:40, 9 February 2016 by Tomtom2357 (talk | contribs)
Jump to navigationJump to search

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.