M=13 case of FUNC

On this page, we attempt a proof of the m=13 case of Frankl's conjecture. This will probably end up being a long case analysis, with the cases being tackled out of order, so bear with me while the page is in progress. In all results below, we will try to prove that the set [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's (satisfies the conjecture), but will assume the opposite. We will use the terminology defined in the paper "The 11 element case of Frankl's Conjecture" by Ivica Bosnjak and Petar Markovic.

The smallest size of a non-empty set must be 3, 4, 5, or 6, as if there were a set of size 1 or 2 in [math]\displaystyle{ \mathcal{A} }[/math], it would be Frankl's. Also, if all the nonempty sets have size 7 or larger, then the average set size is greater than 13/2=6.5, so [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's (to prove this more rigorously, use the uniform weight function over all the elements in X (the ground set).

Case 3: The smallest set has size 5

WLOG assume the size 5 set is 12345. For this case use the weight function w(x)=2 if x is in {1, 2, 3, 4, 5}, and w(x)=1 otherwise. The target weight is therefore 9. Going through the hypercube intervals [K,K U {1, 2, 3, 4, 5}], we have:

Case 4: The smallest set has size 6

In this case we will assume that the set is 123456 (omitting commas and brackets for simplicity) use the weight function w(x)=2 for x<=6, and w(x)=1 otherwise. The target weight is 9.5 With K as the bottom set we consider the set of sets in the interval [K, KU{1,2,3,4,5,6}] with K removed from each set. Going through each size of K, we have:

|K|=0:

The only sets in here are the [math]\displaystyle{ C_0 }[/math] set and the [math]\displaystyle{ C_6 }[/math] set. The deficit of the [math]\displaystyle{ C_0 }[/math] set is 9.5, and the surplus of the [math]\displaystyle{ C_6 }[/math] set is 2.5 (weight 12). So the deficit for this case is 7 more than the surplus.

|K|=1, 2 or 3:

Since all nonempty sets have size at least 6, the only sets in here have at least 3 elements from the original 123456 set, and there is no deficit.

|K|=4:

Only the [math]\displaystyle{ C_2 }[/math] sets cause deficit, each of those only has deficit 1, and the surplus of the [math]\displaystyle{ C_6 }[/math] set is 6, so there must be at least 7 [math]\displaystyle{ C_2 }[/math] sets. There must be an element in {1, 2, 3, 4, 5, 6} that occurs in at least 3 of these [math]\displaystyle{ C_2 }[/math] sets (you can see this by considering the 14 elements of {1, 2, 3, 4, 5, 6} in the [math]\displaystyle{ C_2 }[/math] sets, counting multiplicities, and using the pigeonhole principle). We can assume these are the sets 12, 13, 14 (I'm not including the elements that are not in {1, 2, 3, 4, 5, 6} for simplicity).

Thus we can say WLOG that the sets 123, 124, 134, 1234 are in C, so the surplus of these (1, 1, 3 respectively), raises the total surplus to 11. Therefore, there are at least 12 of the [math]\displaystyle{ C_2 }[/math].

Using the same logic as above, we can see that one element of {1, 2, 3, 4, 5, 6} is in 4 of the [math]\displaystyle{ C_2 }[/math] sets. WLOG we can say that 12, 13, 14, 15 are all [math]\displaystyle{ C_2 }[/math] sets. Therefore, 12345 is in C, which has surplus 5, raising the total surplus to 16. This cannot be matched by the deficit, so the surplus is always greater than the deficit in this case.

|K|=5:

Only the [math]\displaystyle{ C_1 }[/math] sets cause deficit. Each set has deficit 2, and the surplus of the [math]\displaystyle{ C_6 }[/math] set is 7. Therefore, to have a higher deficit than surplus, there must be at least 4 [math]\displaystyle{ C_1 }[/math] sets. Assume that they are 1, 2, 3, 4. Then the set 1234 is in C, and the surplus of that is 4, so the total surplus is at least 11, which the deficit cannot match.

|K|=6:

The [math]\displaystyle{ C_0 }[/math] and [math]\displaystyle{ C_1 }[/math] sets are the only sets that cause deficit. The [math]\displaystyle{ C_0 }[/math] set has deficit 3, and the [math]\displaystyle{ C_1 }[/math] sets all have deficit 1 each. Therefore the total deficit is at most 9. However, the surplus of the [math]\displaystyle{ C_6 }[/math] set is 8, so all the [math]\displaystyle{ C_0 }[/math] and [math]\displaystyle{ C_1 }[/math] sets are in C. But then the set 12 is in C, which has surplus 1, raising the total surplus to at least 9, matching the maximum deficit. Therefore, the surplus is always at least the deficit in this case.

|K|=7:

Only the [math]\displaystyle{ C_0 }[/math] set has deficit, and it has deficit 2.5. The [math]\displaystyle{ C_6 }[/math] set has surplus 9, so the surplus is at least 7 more than the deficit. This cancels out the extra deficit of the |K|=0 case, so [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.