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.