Lemma 7.6

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 [math]\displaystyle{ \mathcal{A} }[/math] contains a size 5 set, then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

WLOG let that set be 12345. Let w(x)=6 if 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 [math]\displaystyle{ C_5 }[/math] 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 [math]\displaystyle{ C_4 }[/math] 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 [math]\displaystyle{ C_5 }[/math] set 12345 has surplus 5, so the surplus is at least as much as the deficit in this case.

|K|=3:

Only [math]\displaystyle{ C_3 }[/math] 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 [math]\displaystyle{ C_5 }[/math] set has surplus 10.

Therefore, [math]\displaystyle{ S \geq d+4 }[/math].

|K|=4:

Only [math]\displaystyle{ C_2 }[/math] sets cause deficit, and each of them has deficit 3. The [math]\displaystyle{ C_5 }[/math] 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, [math]\displaystyle{ S \geq d+9 }[/math].

|K|=5:

Only the [math]\displaystyle{ C_1 }[/math] sets cause deficit, and each of them has deficit 4. The [math]\displaystyle{ C_5 }[/math] set has surplus 20. Either there is at most one of the [math]\displaystyle{ C_1 }[/math] sets, in which case [math]\displaystyle{ S \geq d+16 }[/math], 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 [math]\displaystyle{ S \geq d+12 }[/math].

|K|=6:

Only the [math]\displaystyle{ C_0 }[/math] set has deficit (5), and the [math]\displaystyle{ C_5 }[/math] 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 [math]\displaystyle{ C_5 }[/math] set has surplus 35. This is almost enough to balance out the deficit of the |K|=0 case. So, if any sets with [math]\displaystyle{ 4 \leq |K| \rvert \leq 7 }[/math], then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's, as each of those cases have at least 5 more surplus than deficit. If none of those sets are in [math]\displaystyle{ \mathcal{A} }[/math], 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 [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

Either way, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's. QED