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 (since 123 is in C).

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.

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

This implies that both 123 and 124 are in C. Therefore, the surplus is at least 12.5+6.5+6.5=25.5. The deficit of those sets is at most 9.5+9.5=19. Therefore, the [math]\displaystyle{ C_2 }[/math] deficit must be at least 7. This means that the set 34 must be in C, since the other [math]\displaystyle{ C_2 }[/math] sets only contribute a total of 6 to the deficit. Also, at least 3 of the other [math]\displaystyle{ C_2 }[/math] deficit sets must be in C. This means that 134 and 234 are also in C. This raises the total surplus to at least 25.5+4.5+4.5=34. This cannot be matched by the deficit, so the surplus is always greater than the deficit in this case.

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

This case is covered by Sublemma 1.1, showing that in this case, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

(Needs to be continued)

|K|=4:

In this case, the top set has surplus 13.5. There are two cases:

Case 1: The bottom set K is not in C

In this case, since the maximum total deficit of the [math]\displaystyle{ C_2 }[/math] sets is 4.5. Therefore, since the [math]\displaystyle{ C_1 }[/math] sets can only have a deficit of at most 8.5 each, there must be at least two [math]\displaystyle{ C_1 }[/math] sets in C. Therefore, both 123 and 124 are in C. Each of those have a surplus of 7.5, so this means the surplus is at least 28.5. Therefore, since the deficits of 1, 2, 3, 4 are 6.5, 6.5, 8.5, 8.5 respectively, and the deficit of 3 of these plus the maximum [math]\displaystyle{ C_2 }[/math] deficit is at most 28, we need all four [math]\displaystyle{ C_1 }[/math] sets in C. So the sets 134, 234 are in C. Each of these has surplus 5.5, so the surplus is at least 39.5. This is more than the maximum possible deficit (34.5).

Case 2: The bottom set K is in C

This case implies that both 123, 124 are in C. Thus the surplus is at least 28.5. The bottom set has deficit 14.5, and the maximum total deficit of the [math]\displaystyle{ C_2 }[/math] sets is 4.5, which adds up to 19. Thus, since (as said above) the maximum deficit of a single [math]\displaystyle{ C_1 }[/math] set is 8.5, there must be at least 2 of them in C.

In a sub-lemma (sorry this has been terribly organised), we'll prove that if this is the case, then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

(Needs to be continued)

|K|=5:

In this case, the surplus of the top set is 14.5. The [math]\displaystyle{ C_2 }[/math] sets have no deficit, except for 34, so the deficit only comes from the [math]\displaystyle{ C_0 }[/math] set and the [math]\displaystyle{ C_1 }[/math] sets and 34. The [math]\displaystyle{ C_1 }[/math] sets 1 and 2 have deficit 5.5, the sets 3 and 4 have deficit 7.5, and the [math]\displaystyle{ C_0 }[/math] set has deficit 13.5. If [math]\displaystyle{ P_1 }[/math]=0, then the deficit of the [math]\displaystyle{ C_0 }[/math] set is not enough to surpass the surplus. If [math]\displaystyle{ P_1 }[/math]=1, then at least one of 123 or 124 are in C, so the total surplus is at least 14.5+8.5=23, which is greater than the maximum deficit (7.5+13.5+1.5=22.5). If [math]\displaystyle{ P_1 }[/math]=2, then both 123 and 124 are in C, so the total surplus is at least 14.5+8.5+8.5=31.5, which is greater than the maximum deficit (7.5+7.5+13.5+1.5=30).

If [math]\displaystyle{ P_1 }[/math]=3, then they are either (WLOG) 1, 2, 3 or 1, 3, 4. If it is 1,2,3, then the deficit is at most 13.5+5.5+5.5+7.5+1.5=33.5, and the surplus from the sets 12, 13, 23, 123, 124, 1234 is 2.5+0.5+0.5+8.5+8.5+14.5=35, which is greater than the deficit. If it is 1,3,4, then the deficit is 13.5+7.5+7.5+5.5+1.5=35.5, and the surplus from the sets 13, 14, 123, 124, 134, 1234 is 0.5+0.5+8.5+8.5+6.5+14.5=40, which is greater than the deficit.

If [math]\displaystyle{ P_1 }[/math]=4, then the surplus from the sets is 48, which is greater than the maximum deficit (40).

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

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.