Lemma 1

This page proves a lemma for the m=13 case of FUNC.

Lemma 1:

If [math]\displaystyle{ \mathcal{A} }[/math] contains 2 size 3 sets with a two element intersection, then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

Let w(1)=w(2)=8, w(3)=w(4)=6, and w(x)=1 otherwise. The target weight is 18.5. Let C be an arbitrary 1234-hypercube with bottom set K.

|K|=0:

The deficit is exactly 18.5, and the sets 123, 124, 1234 together have 1.5+1.5+7.5=10.5 surplus. Therefore the deficit is 8 more than the surplus.

|K|=1:

As there cannot be 3 size three sets contained in a size 5 set, there are no [math]\displaystyle{ C_2 }[/math] sets. Therefore, there is no deficit.

|K|=2:

There are no [math]\displaystyle{ C_0 }[/math] sets, so the deficit is made up from the [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] sets. The 1234 set has surplus 11.5. We have a few cases:

[math]\displaystyle{ P_1 }[/math]=0:

Aside from 34, with deficit 4.5 the [math]\displaystyle{ C_2 }[/math] sets each have deficit at most 2.5, so [math]\displaystyle{ P_2 }[/math]>=4. Therefore, [math]\displaystyle{ P_3 }[/math]>=3. Each of those sets has surplus at least 3.5, so the total surplus is now at least 22. This is more than the maximum deficit (14.5), so in this case the surplus is greater than the deficit.

[math]\displaystyle{ P_1 }[/math]=1:

The [math]\displaystyle{ C_1 }[/math] set has deficit at most 10.5, and it guarantees at least one of 123 or 124 are in C. Thus the surplus is at least 11.5+5.5=17. Therefore, there are at least two [math]\displaystyle{ C_2 }[/math] sets.

If one of them is 34, then it guarantees one of 134, 234 is in C. This means there is at least 17+3.5=20.5 surplus. That would mean [math]\displaystyle{ P_2 }[/math]>=4. That means [math]\displaystyle{ P_3 }[/math]>=3, so there is now at least 20.5+3.5=24 surplus. So now [math]\displaystyle{ P_2 }[/math]>=5 to compensate, and [math]\displaystyle{ P_3 }[/math]=4, so the surplus is 24+5.5=29.5. This cannot be matched by the deficit, so the surplus is greater than the deficit.

If 34 is not in C, then there are 3 other [math]\displaystyle{ C_2 }[/math] sets. This guarantees that both 123 and 124 are in C. Therefore, there is at least 11.5+11=23.5 surplus. This cannot be matched by the allowable deficit (10.5+12.5=23).

In either case, the surplus is greater than the deficit.

[math]\displaystyle{ P_1 }[/math]>=2:

In this case, either we have 3 size 3 sets that are subsets of the same 5 element set (123, 156, 256 or 124, 256, 456 etc), or we have 4 size three sets of the form 123, 124, 356, 456. This implies that [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's from the article Find set configurations that imply FUNC.

|K|=3:

The [math]\displaystyle{ C_4 }[/math] set has surplus 12.5. There are two cases:

Case 1: The bottom set K is not in C

The [math]\displaystyle{ C_2 }[/math] sets can only contribute 9.5 to the deficit, so at least one of the [math]\displaystyle{ C_1 }[/math] sets is in C. This means one of 123 and 124 are in C, and they each have surplus 6.5, so the surplus is at least 19. We have four subcases:

[math]\displaystyle{ P_1 }[/math]=1:

If the [math]\displaystyle{ C_1 }[/math] set is 1 or 2, then it contributes only 7.5 to the deficit, but the [math]\displaystyle{ C_2 }[/math] sets can't make up the remaining 12 necessary deficit.

If the [math]\displaystyle{ C_1 }[/math] set is 3 or 4 (WLOG assume it's 3), it's deficit is 9.5, and 123 is in C. The surplus is at least 17, so the deficit of the [math]\displaystyle{ C_2 }[/math] sets is at least 7.5. Since all those sets other than 34 have deficit 1.5 (except 12 which has surplus), 34 must be in C, along with at least 3 of the others. This implies that all the size 3 sets are in C, raising the surplus to 32.5, which cannot be matched by the deficit.

(Needs to be continued)

6<=|K|<=8:

In this case, the surplus of the top set is at least 15.5. The [math]\displaystyle{ C_2 }[/math] sets have no deficit, so the deficit only comes from the [math]\displaystyle{ C_0 }[/math] set and the [math]\displaystyle{ C_1 }[/math] sets. The total deficit of the [math]\displaystyle{ C_1 }[/math] sets are at most 22, but having even one of them in C implies that 123 or 124 is in C. Those sets have weight 9.5 each, so even one of them being in C makes the total surplus more than that deficit.

The [math]\displaystyle{ C_0 }[/math] set has deficit 12, but if it is in C, then both 123 and 124 are, so the total surplus is at least 34.5. This is more than the maximum deficit of that set and the [math]\displaystyle{ C_1 }[/math] sets combined, so the surplus is greater than the deficit in these cases.

|K|=9:

The top set has weight 37, with surplus 18.5. The total deficit of the [math]\displaystyle{ C_1 }[/math] sets are at most 10, and having any of them implies that one of 123 or 124 is in C. Those have surplus 12.5 each. The [math]\displaystyle{ C_0 }[/math] set has deficit 9.5, but it implies that both 123, 124 are in C. Therefore, no matter what, the surplus is at least 18.5 greater than the deficit.