Lemma 8

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

Lemma 8:

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

WLOG let those sets be 123456, 123457. Let w(x)=2 if x=1,2,3,4,5,6,7, and w(x)=1 otherwise. The target weight is 10.

|K|=0:

In this case there are only four sets, the bottom set, 123456, 123457, 1234567. The bottom set has deficit 10, but the other sets have combined surplus 8, so the deficit is only 2 greater than the surplus in this case.

|K|=1 or 2:

In this case, the smallest sets allowed have weight at least 10, so there is not deficit in this case.

|K|=3:

In this case, the only sets with a possible deficit are the [math]\displaystyle{ C_3 }[/math] sets. These each have deficit 1, so since the top set has surplus 7, there must be at least 8 of them.

(Needs more work)

|K|=4:

In this case, the only sets with a possible deficit are the [math]\displaystyle{ C_2 }[/math] sets.

|K|=6:

In this case, only the [math]\displaystyle{ C_0 }[/math] set and the [math]\displaystyle{ C_1 }[/math] sets can contribute to the discrepancy. However, if any of those are in C, then at least one of 123456 or 123457 are in C also, so the surplus is at least 10+8=18. Thus all the [math]\displaystyle{ C_0 }[/math] and [math]\displaystyle{ C_1 }[/math] sets are in C to match the surplus. But then both of 123456 and 123457 are in C, so the surplus is at least 26, which is more than the maximum possible deficit (18). Either way, the surplus is at least two more than the deficit, cancelling out the |K|=0 case