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, which all have deficit one. Pick one of these sets, let it be abc (where a, b, c, d, e, f, g are non-specified but distinct elements of {1, 2, 3, 4, 5, 6, 7}). The deficit of every set that doesn't intersect abc in at least two elements can be matched by the surplus of its union with abc, like this:

ade, bde, cde: abcde

The former sets all have deficit one, and abcde has surplus 3, cancelling all the deficit out. We can then map 4 of the remaining [math]\displaystyle{ C_3 }[/math] sets to their union with abc like so:

abd: abcd abe: abce abf: abcf abg: abcg

This leaves 9 remaining [math]\displaystyle{ C_3 }[/math] sets (including abc itself) that can cuae a net deficit. The [math]\displaystyle{ C_7 }[/math] set has surplus 7, and the [math]\displaystyle{ C_6 }[/math] sets have surplus 5, so if any of the [math]\displaystyle{ C_6 }[/math] sets are in C, then the surplus is greater than the deficit. However, if none of them are in C, that means that all sets contain both 6 and 7, otherwise one of 123456, 123457 are in C, due to the union between them and the original {1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 7} sets. However, there are only 5 such [math]\displaystyle{ C_3 }[/math] sets (167, 267, 367, 467, 567), and just those cannot match the surplus of the [math]\displaystyle{ C_7 }[/math] set.

Thus in this case, the surplus is always greater than the deficit.

|K|=4:

In this case, the only sets with a possible deficit are the [math]\displaystyle{ C_2 }[/math] sets. In the pairing below, the [math]\displaystyle{ C_4 }[/math] sets are each implied by two of the three [math]\displaystyle{ C_2 }[/math] sets (obviously a different two for each one). Thus only one of each group can contribute to the net deficit.

12, 34, 56: 1234, 1256, 3456 13, 27, 45: 1237, 1345, 2457 14, 26, 37: 1246, 1347, 2367 15, 36, 47: 1356, 1457, 3467 16, 23, 57: 1236, 1567, 2357 17, 25, 46: 1257, 1467, 2456 24, 35, 67: 2345, 2467, 3567

Thus, the net deficit (what isn't cancelled by the [math]\displaystyle{ C_4 }[/math] sets) is at most 14. As the [math]\displaystyle{ C_7 }[/math] set has surplus 8, and the [math]\displaystyle{ C_6 }[/math] sets have surplus 6 each, none of the [math]\displaystyle{ C_6 }[/math] sets are in C (otherwise they cancel out the deficit). In particular, 123456, 123457 aren't in C. However, the only [math]\displaystyle{ C_2 }[/math] set that doesn't make one of those in C is 67. This set alone cannot match the [math]\displaystyle{ C_7 }[/math] set, so the surplus is always at least as much as the deficit.

|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