Lemma 7.5

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

If there are two size 5 sets in [math]\displaystyle{ \mathcal{A} }[/math], then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

WLOG let those sets be 12345, 67890.

Let the weight function be defined as: w(x)=3 if x=1, 2, 3, 4, 5, 6, 6, 7, 8, 0, and 2 otherwise. The target weight is 18.

|K|=0:

The only sets with deficit are the [math]\displaystyle{ C_0 }[/math] set and the [math]\displaystyle{ C_5 }[/math] sets. These have deficit 18+3+3=24.

The [math]\displaystyle{ C_10 }[/math] set has surplus 12, so S+12=d

|K|=1:

Only [math]\displaystyle{ C_5 }[/math] sets cause deficit (any smaller sets would violate the assumption), and each of them has deficit 1. Each [math]\displaystyle{ C_5 }[/math] set with one element from 1, 2, 3, 4, 5 and 4 from 6, 7, 8, 9, 0 can be paired with it's union with 12345, and vice versa for those with 4 of 1, 2, 3, 4, 5 and 1 of 6, 7, 8, 9, 0, as follows:

16789, 26789, 36789, 46789, 56789: 123456789 (surplus 11) etc

12346, 12347, 12348, 12349, 12340: 123467890 etc

The sets with 2 of 1, 2, 3, 4, 5 and 3 of 6, 7, 8, 9, 0 can be paired with their union with 12345, and a couple of their unions with each other, as follows:

12678 and 13678: 123678

14678 and 15678: 145678 (surplus one, so only one of each group can cause deficit each)

12678, 13678, 14678, 15678, 23678, 24678, 25678, 34678, 35678, 45678: 12345678 (surplus 8) etc

The same can be done with the sets with 3 of 1, 2, 3, 4, 5 and 2 of 6, 7, 8, 9, 0.

The only sets remaining are 12345 and 67890. These have deficit 1 each, so the net deficit is at most 2. Since the surplus of the [math]\displaystyle{ C_10 }[/math] set is 14, the surplus is at least the deficit.

|K|=2:

Only [math]\displaystyle{ C_4 }[/math] sets cause deficit, and each of them has deficit 2. The [math]\displaystyle{ C_10 }[/math] set has surplus 16. Every set that is a subset of 12345 can be matched with it's union with 67890, and vice versa, as follows:

1234: 123467890

6789: 123456789 etc

The same can be done with sets with 3 of 1, 2, 3, 4, 5 and 1 of 6, 7, 8, 9, 0, and vice versa:

1236, 1237, 1238, 1239, 1230: 12367890 (surplus 10)

1678, 2678, 3678, 4678, 5678: 12345678

The only sets remaining are those that have 2 of 1, 2, 3, 4, 5 and 2 of 6, 7, 8, 9, 0. For there to be a net deficit, there must be one of these sets. WLOG, let it be 1267. Every set that has completely different elements from 1, 2, 3, 4, 5, can be paired with the union with 1267, and same if it has completely different elements from 1, 2, 3, 4, 5, as follows:

1289: 126789 (surplus 4)

1389, 2389: 1236789 (surplus 7)

3467: 123467

3468, 3478: 1234678

3489: 12346789

The remaining sets are in this grid:

1267, 1268, 1269, 1260, 1278, 1279, 1270

1367, 1368, 1369, 1360, 1378, 1379, 1370

1467, 1468, 1469, 1460, 1478, 1479, 1470

1567, 1568, 1569, 1560, 1578, 1579, 1570

2367, 2368, 2369, 2360, 2378, 2379, 2370

2467, 2468, 2469, 2460, 2478, 2479, 2470

2567, 2568, 2569, 2560, 2578, 2579, 2570

Each row can be paired with its union with 67890, and each column can be paired with its union with 12345 (both unions have surplus 7), with half the deficit of each set going to the row, and half to the column.

Thus there is no net deficit, and therefore the surplus is greater than the deficit.

|K|=3:

Only [math]\displaystyle{ C_3 }[/math] sets cause deficit, and each of them has deficit 3. The [math]\displaystyle{ C_10 }[/math] set has surplus 18.

The [math]\displaystyle{ C_3 }[/math] sets which are a subset of 12345 can be paired with their union with 67890, and vice versa.

The remaining sets have 1 element from 12345 and 2 from 67890 or vice versa. WLOG let this be 167. Every set with 1 element from 12345 and 2 from 67890 not containing 6 or 7 can be paired with its union with 167, as follows:

189: 16789

289: 126789 etc

Also, we can pair other sets which differ in two elements as follows:

268: 12678

269: 12679

260: 12670

368: 13678

369: 13679

360: 13670

468: 14678

469: 14679

460: 14670

568: 15678

569: 15679

560: 15670

The remaining sets not containing 1 can be paired with their unions with 67890 and 167 as follows:

267, 268, 269, 260, 278, 279, 270: 267890, 1267890

367, 368, 369, 360, 378, 379, 370: 367890, 1367890

467, 468, 469, 460, 478, 479, 470: 467890, 1467890

567, 568, 569, 560, 578, 579, 570: 567890, 1567890

We know that 167890 is in C, and it has a surplus of 6. Thus, to create a net deficit, there must be more of the remaining sets in C. WLOG, let one of them be 168. Pair some of the sets as follows:

169, 179: 123456789 160, 170: 123456780

So only the three sets 167, 168, 178 cause net deficit, and since 167890 has surplus 6, the net deficit is at most three.

This same reasoning can be applied to the sets with 2 of 12345 and 1 of 67890. So the net deficit is at most 3+3=6. Since the [math]\displaystyle{ C_10 }[/math] set has surplus 18, S=d+12, cancelling out the |K|=0 case.

Therefore, the surplus is always at least the deficit, so [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.

QED