Find set configurations that imply FUNC

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. One such bijection is: {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.

Lemma 2

If [math]\displaystyle{ \mathcal{A} }[/math] contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 2, 4}, {3, 5, 6}, {4, 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, 2, 4}, {3, 5, 6}, {4, 5, 6} are in C, along with their unions, which are {1, 2, 3, 4}, {3, 4, 5, 6}, {1, 2, 3, 5, 6}, and {1, 2, 4, 5, 6}. This generates a surplus of 6. We can map each set of size 1 except {3} and {4} to an implied sets of size 5, which cancels out their deficit.

1: {1, 3, 4, 5, 6}

2: {2, 3, 4, 5, 6}

5: {1, 2, 3, 4, 5}

6: {1, 2, 3, 4, 6}

We have another mapping from some size 2 sets to implied size 4 or 5 sets, cancelling out their deficit (each set on the left implies all of the sets on the right by itself).

{1, 3}: {1, 3, 5, 6}

{1, 4}: {1, 4, 5, 6}

{2, 3}: {2, 3, 5, 6}

{2, 4}: {2, 4, 5, 6}

{3, 5}: {1, 2, 3, 5}

{3, 6}: {1, 2, 3, 6}

{4, 5}: {1, 2, 4, 5}

{4, 6}: {1, 2, 4, 6}

Case 1.1: neither {3} nor {4} are in C

Then all the sets not in the above pairing must be in C. But this generates the set {1, 2, 5, 6} which pushes the net surplus up to 7, which the deficit cannot surpass.

Case 1.2: Only one of {3} and {4} are in C

WLOG, assume this set is {3}. In this case, there must be at least 5 size 2 sets not in the above list in C. If {3, 4} is in C, then we can pair each of the remaining size 2 sets with it's union with {3, 4}, so {3, 4} cannot be in C. But sine 5 of the size 2 subsets of {1, 2, 5, 6} are in C, that means {1, 2, 5, 6} is in C as well. This raises the surplus by one, forcing all 6 size 2 subsets of {1, 2, 5, 6} to be in C. Therefore, the sets {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 4, 5, 6}, {2, 4, 5, 6}, {1, 3, 5, 6}, {2, 3, 5, 6} are in C, raising the surplus to 15. This forces all the size 2 sets other than {3, 4} to be in C. But then, {1, 3, 4, 6} is in C, raising the surplus to 16, which the deficit cannot surpass.

Case 1.3: Both {3} and {4} are in C

Each of the sets disjoint from {3, 4} can be paired with it's union with {3, 4}, and the pairing above remains valid. Therefore, all size 2 sets other than {3, 4} do not contribute towards the net deficit, so the net deficit is at most 5, which is less than the net surplus (6).

Thus, in either case, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

Case 2: {} is not in C

In this case, the only set we know is in C is {1, 2, 3, 4, 5, 6}. Thus the surplus is at least 6. Given the pairing:

{1}: {1, 3, 4, 5, 6} {2}: {2, 3, 4, 5, 6} {3}: {1, 2, 3, 5, 6} {4}: {1, 2, 4, 5, 6} {5}: {1, 2, 3, 4, 5} {6}: {1, 2, 3, 4, 6}

None of the size 1 sets contribute to the net deficit. We also have a pairing: {1, 3}: {1, 3, 5, 6} {1, 4}: {1, 4, 5, 6} {2, 3}: {2, 3, 5, 6} {2, 4}: {2, 4, 5, 6} {3, 4}: {1, 2, 3, 4} {3, 5}: {1, 2, 3, 5} {3, 6}: {1, 2, 3, 6} {4, 5}: {1, 2, 4, 5} {4, 6}: {1, 2, 4, 6}

Thus only 6 size 2 sets contribute to the net deficit. Thus the deficit cannot surpass the surplus. Therefore, in either case, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

Finding the implied abundance given a configuration

Even if a configuration does not directly imply Frankl's conjecture holds for [math]\displaystyle{ \mathcal{A} }[/math], it can give some interesting results about the minimal abundance, and the weight function. Having one set of size 3, the only way to weight the set is to give equal weight to each element, and the lowest possible abundance on elements of that set is 4/9. If there are two sets of size 3 having an intersection of size 2 ({1, 2, 3}, {1, 2, 4}), then the lowest possible abundance of an element is 27/55, which is the best possible, and it is given by the weight function w(1)=w(2)=31, w(3)=w(4)=24. This was found by equating the abundance at the two extreme cases of this case: {1}, {2}, {3} in C (and same replacing 3 with 4), and {3}, {4} in C. Hopefully I will be able to find the optimal weight distribution for larger configurations.