# Lemma 7.6

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This page proves a lemma for the m=13 case of FUNC. It is a sublemma needed for the proof of Lemma 7.

## Lemma 7.6:

If $\mathcal{A}$ contains a size 5 set, then $\mathcal{A}$ is Frankl's.

WLOG let that set be 12345. Let w(x)=6 is x=1,2,3,4, or 5 and w(x)=1 otherwise. The target weight is 35.

## |K|=0:

In this case there are only two sets, the empty set and the full set 12345. The deficit is therefore 35+5=40.

## |K|=1:

The only possible set in this case is the $C_5$ set 12345 (as any smaller sets would violate the assumption), and it has weight exactly 35, so there is no deficit in this case

## |K|=2:

Only $C_4$ sets cause deficit, and each of them has deficit 1. There are 5 of them, so the total deficit is at most 5. However, the $C_5$ set 12345 has surplus 5, so the surplus is at least as much as the deficit in this case.

## |K|=3:

Only $C_3$ sets cause deficit, and each of them has deficit 2. WLOG assume 123 is in C. We can pair the sets as follows:

134, 234: 1234

135, 235: 1235

Any 2 of 124, 125, 145: 1245 (this cancels out the deficit of all but at most one of them)

245 and 345: 2345

Thus, only 3 sets (including 123) can contribute to the deficit, which makes at most 6 net deficit. The $C_5$ set has surplus 10.

Therefore, $S \geq d+4$.

## |K|=4:

Only $C_2$ sets cause deficit, and each of them has deficit 3. The $C_5$ set has surplus 15.

WLOG assume 12 is in C. Pair sets as follows:

23: 123

24: 124

25: 125

34: 1234

35: 1235

45: 1245

The other sets 13, 14, 15 can only have one set contributing to the deficit, due to: 13 and 14: 134

13 and 15: 135

14 and 15: 145

Thus the net deficit is at most 6 (as only two sets can contribute to the net deficit). Therefore, $S \geq d+9$.

## |K|=5:

Only the $C_1$ sets cause deficit, and each of them has deficit 4. The $C_5$ set has surplus 20. Either there is at most one of the $C_1$ sets, in which case $S \geq d+16$, or there are at least 2. In that case, let them (WLOG) be 1 and 2. The other sets can be paired off as follows:

3: 123

4: 124

5: 125

Thus, the net deficit is at most 8 in either case, and $S \geq d+12$.

## |K|=6:

Only the $C_0$ set has deficit (5), and the $C_5$ set has surplus 25, so S=d+20

## |K|=7:

There are no deficit sets in this case.

## |K|=8:

There are no deficit sets, and the $C_5$ set has surplus 35. This is almost enough to balance out the deficit of the |K|=0 case. So, if any sets with $4 \leq |K| \rvert \leq 7$, then $\mathcal{A}$ is Frankl's, as each of those cases have at least 5 more surplus than deficit. If none of those sets are in $\mathcal{A}$, then every nonempty set has at least 3 of 1, 2, 3, 4, 5.

Thus, we can change the weight to be 1 on 1, 2, 3, 4, 5 and 0 elsewhere. Now all nonempty sets are above the target weight (2.5), so $\mathcal{A}$ is Frankl's.

Either way, $\mathcal{A}$ is Frankl's. QED