Find set configurations that imply FUNC

Click here to go back to the main page

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. However, one can show that if [math]\displaystyle{ \mathcal{A} }[/math] contains certain configurations of sets of size 3, then FUNC holds for [math]\displaystyle{ \mathcal{A} }[/math]. For example, in this article, it is shown that if [math]\displaystyle{ \mathcal{A} }[/math] contains 3 sets of size three that are subsets of the same set of size 5, then FUNC holds for [math]\displaystyle{ \mathcal{A} }[/math]. This article attempts to extend the results given in that paper.

Lemma 1

If [math]\displaystyle{ \mathcal{A} }[/math] contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}, then FUNC holds for [math]\displaystyle{ \mathcal{A} }[/math].

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in [math]\displaystyle{ \mathcal{A} }[/math]. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for [math]\displaystyle{ \mathcal{A} }[/math].

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

Case 1: {} is in C: The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, along with all their unions, which together make up all the sets of size 5. The total surplus of these sets is 12 (there are 6 sets of size 5, and each has surplus 2, and we’re ignoring the full set), therefore the total deficit must be at least 13. However, for every set of size 1 in C, there are two sets of size 4 in C, as follows: 1: {1, 2, 4, 6}, {1, 3, 5, 6} 2: {1, 2, 4, 5}, {2, 3, 5, 6} 3: {1, 3, 4, 5}. {2, 3, 4, 6} 4: {1, 2, 3, 4}, {3, 4, 5, 6} 5: {1, 2, 3, 5}, {2, 4, 5, 6} 6: {1, 2, 3, 6}, {1, 4, 5, 6} Therefore, the total deficit of the size two sets must make up the 13. But then there must be at least 13 sets of size 2 in C (since they only have deficit 1), and together, these 13 sets generate all of the sets of size 4 (since each set of size 4 can be generated in 3 ways, you need to remove 3 sets before you can’t generate a set of size 4). Therefore, the total surplus is 27, which is the maximum that the total deficit can be.

Case 2: {} is not in C. In this case, since {} is not in C, we consider the set {1, 2, 3, 4, 5, 6} as counting towards the total surplus (as the empty set isn’t there to cancel it out). Now, each set of size 1 in C means that two of {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, and the union of those is a size 5 set, so each size one set cancels out with a size 5 set. Now, every set of size 2 in C forces a set of size 4 to be in C, except {1, 6}, {2, 5}, {3, 4}. We just need a bijection from the sets of size 2 (excluding the above) to the sets of size 4 (excluding {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}), such that if a set of size 2 is in C, then the associated set of size 4 is in C. Such a bijection is given below: {1, 2}->{1, 2, 4, 5} {1, 3}->{1, 3, 5, 6} {1, 4}->{1, 2, 4, 6} {1, 5}->{1, 2, 3, 5} {2, 3}->{2, 3, 4, 6} {2, 4}->{1, 2, 3, 4} {2, 6}->{2, 3, 5, 6} {3, 5}->{1, 3, 4, 5} {3, 6}->{1, 2, 3, 6} {4, 5}->{3, 4, 5, 6} {4, 6}->{1, 4, 5, 6} {5, 6}->{2, 4, 5, 6}

So, the surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of {1, 6}, {2, 5}, {3, 4}, and every other set of size 2 has an associated set of size 4. Therefore, the surplus is at least the deficit.