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 1.5, so the total surplus is now at least 16. 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]>=3:

In this case, we have 3 size 3 sets all contained in a 5 element set. Therefore, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.