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|=5:

In this case, the [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] sets both contribute to the deficit (with deficits 1 and 3 respectively). There must be at least one [math]\displaystyle{ C_2 }[/math] set, because otherwise there would be only one [math]\displaystyle{ C_1 }[/math] set, and that wouldn't match the surplus of the [math]\displaystyle{ C_7 }[/math] set (which is 9). Pick one of the [math]\displaystyle{ C_2 }[/math] sets and call it ab. The deficit of each [math]\displaystyle{ C_2 }[/math] set that doesn't intersect with it (not including K) is cancelled by the surplus of it's union with ab. Also, each set in the pairing below is cancelled out as well:

bc: abc bd: abd be: abe bf: abf bg: abg

Now there must be another [math]\displaystyle{ C_2 }[/math] set that causes deficit (otherwise the net deficit isn't even 9). Call it ac (as that is the only option left). The remaining possible [math]\displaystyle{ C_2 }[/math] sets are cancelled out by their union with ac, as follows:

ad: acd ae: ace af: acf ag: acg

Thus, the [math]\displaystyle{ C_2 }[/math] sets can only contribute 2 to the maximum deficit. Since that plus the maximum deficit of the [math]\displaystyle{ C_1 }[/math] sets (7*3=21) is 23, the two sets 123456, 123457 can't both be in C. But that would mean that only one of the [math]\displaystyle{ C_1 }[/math] sets is in C (either 6 or 7), reducing the possible net deficit down to 2+3=5. This is easily matched by the [math]\displaystyle{ C_7 }[/math] set.

|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. Thus the total surplus of all the C's is always more than the total deficit.

Q.E.D