M=13 Theorem: Difference between revisions
Tomtom2357 (talk | contribs) Created page with "This page proves the final theorem for the m=13 case of FUNC. Assuming all the previous lemmas (which at this time have not all been proven), we know that if <math>\mathca..." |
Tomtom2357 (talk | contribs) |
||
| Line 2: | Line 2: | ||
==Proof== | ==Proof== | ||
Let one of the size 6 sets (they must exist) WLOG be 123456. This set cannot be the only size 6 set, because either there would only be that set, and the empty and full sets, and 1 is in 2 out of the three sets, or there are other sets, of size at least 7, which mean that the average set size is at least 6.5. Either way, <math>\mathcal{A}</math> is Frankl's if there is only one size 6 set. | |||
However, all other size 6 sets are balanced out by their union with 123456, and if there are sets that are distinct in at least three elements, then that balances out 123456 as well, as seen below: | |||
1234ab, 1256ab, 3456ab: 123456ab (the left three all have size 6, and the right has size 8, so it averages out to size 6.5) | |||
123456, 123abc, 145abc, 246abc, 356abc: 123456abc (the left five all have size 6, and the right has size 9, so it averages out to size 6.5) | |||
123456, 12abcd, 34abcd, 56abcd: 123456abcd | |||
123456, 1abcde, 2abcde,...: 123456abcde | |||
123456, abcdef: 123456abcdef | |||
Thus, the only size 6 sets are those that intersect 123456 at exactly four elements. However, if they cause other unions, then that balances out 123456 too. Therefore, they must all be subsets of the same 8 element set. If there are any other sets, they would also balance out 123456, so these are the only sets in <math>\mathcal{A}</math>. So the sets are the empty and full sets, 123456, 123478, 125678, 345678 (WLOG). But 1 is in 4 of the 6 sets, so <math>\mathcal{A}</math> is still Frankl's. | |||
Thus, assuming the previous lemmas), if m=13, then <math>\mathcal{A}</math> is Frankl's. | |||
Latest revision as of 15:41, 12 November 2016
This page proves the final theorem for the m=13 case of FUNC. Assuming all the previous lemmas (which at this time have not all been proven), we know that if [math]\displaystyle{ \mathcal{A} }[/math] is not Frankl's, then the smallest nonempty set has size 6 (if it had a larger size, then the average set size would be more than 6.5, and it would be trivially Frankl's). We also know that no two of these size 6 sets intersect in 5 elements. Using this, we prove below that [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's (as long as m=13).
Proof
Let one of the size 6 sets (they must exist) WLOG be 123456. This set cannot be the only size 6 set, because either there would only be that set, and the empty and full sets, and 1 is in 2 out of the three sets, or there are other sets, of size at least 7, which mean that the average set size is at least 6.5. Either way, [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's if there is only one size 6 set.
However, all other size 6 sets are balanced out by their union with 123456, and if there are sets that are distinct in at least three elements, then that balances out 123456 as well, as seen below:
1234ab, 1256ab, 3456ab: 123456ab (the left three all have size 6, and the right has size 8, so it averages out to size 6.5) 123456, 123abc, 145abc, 246abc, 356abc: 123456abc (the left five all have size 6, and the right has size 9, so it averages out to size 6.5) 123456, 12abcd, 34abcd, 56abcd: 123456abcd 123456, 1abcde, 2abcde,...: 123456abcde 123456, abcdef: 123456abcdef
Thus, the only size 6 sets are those that intersect 123456 at exactly four elements. However, if they cause other unions, then that balances out 123456 too. Therefore, they must all be subsets of the same 8 element set. If there are any other sets, they would also balance out 123456, so these are the only sets in [math]\displaystyle{ \mathcal{A} }[/math]. So the sets are the empty and full sets, 123456, 123478, 125678, 345678 (WLOG). But 1 is in 4 of the 6 sets, so [math]\displaystyle{ \mathcal{A} }[/math] is still Frankl's.
Thus, assuming the previous lemmas), if m=13, then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.
