Lemma 1: Difference between revisions
Tomtom2357 (talk | contribs) |
Tomtom2357 (talk | contribs) No edit summary |
||
| Line 5: | Line 5: | ||
Let w(1)=w(2)=8, w(3)=w(4)=6, and w(x)=1 otherwise. The target weight is 18.5 Let C be an arbitrary 1234-hypercube with bottom set K. | Let w(1)=w(2)=8, w(3)=w(4)=6, and w(x)=1 otherwise. The target weight is 18.5 Let C be an arbitrary 1234-hypercube with bottom set K. | ||
==|K|=0:== | |||
The deficit is exactly 18.5, and the sets 123, 124, 1234 together have 1.5+1.5+7.5=10.5 surplus. Therefore the deficit is 8 more than the surplus | The deficit is exactly 18.5, and the sets 123, 124, 1234 together have 1.5+1.5+7.5=10.5 surplus. Therefore the deficit is 8 more than the surplus | ||
==|K|=1:== | |||
As there cannot be 3 size three sets contained in a size 5 set, there are no <math>C_2</math> sets. Therefore, there is no deficit. | As there cannot be 3 size three sets contained in a size 5 set, there are no <math>C_2</math> sets. Therefore, there is no deficit. | ||
==|K|=2:== | |||
There are no <math>C_0</math> sets, so the deficit is made up from the <math>C_1</math> and <math>C_2</math> sets. The 1234 set has surplus 11.5. We have a few cases: | There are no <math>C_0</math> sets, so the deficit is made up from the <math>C_1</math> and <math>C_2</math> sets. The 1234 set has surplus 11.5. We have a few cases: | ||
===<math>P_1</math>=0:=== | |||
Aside from 34, with deficit 4.5 the <math>C_2</math> sets each have deficit at most 2.5, so <math>P_2</math>>=4. Therefore, <math>P_3</math>>=3. Each of those sets has surplus at least 3.5, so the total surplus is now at least 22. This is more than the maximum deficit (14.5), so in this case the surplus is greater than the deficit. | Aside from 34, with deficit 4.5 the <math>C_2</math> sets each have deficit at most 2.5, so <math>P_2</math>>=4. Therefore, <math>P_3</math>>=3. Each of those sets has surplus at least 3.5, so the total surplus is now at least 22. This is more than the maximum deficit (14.5), so in this case the surplus is greater than the deficit. | ||
===<math>P_1</math>=1:=== | |||
The <math>C_1</math> set has deficit at most 10.5, and it guarantees at least one of 123 or 124 are in C. Thus the surplus is at least 11.5+5.5=17. Therefore, there are at least two <math>C_2</math> sets. | The <math>C_1</math> set has deficit at most 10.5, and it guarantees at least one of 123 or 124 are in C. Thus the surplus is at least 11.5+5.5=17. Therefore, there are at least two <math>C_2</math> sets. | ||
| Line 26: | Line 26: | ||
In either case, the surplus is greater than the deficit. | In either case, the surplus is greater than the deficit. | ||
===<math>P_1</math>>=2:=== | |||
In this case, either we have 3 size 3 sets that are subsets of the same 5 element set (123, 156, 256 or 124, 256, 456 etc), or we have 4 size three sets of the form 123, 124, 356, 456. This implies that <math>\mathcal{A}</math> is Frankl's from the article [[Find set configurations that imply FUNC]]. | In this case, either we have 3 size 3 sets that are subsets of the same 5 element set (123, 156, 256 or 124, 256, 456 etc), or we have 4 size three sets of the form 123, 124, 356, 456. This implies that <math>\mathcal{A}</math> is Frankl's from the article [[Find set configurations that imply FUNC]]. | ||
==|K|=3:== | |||
Revision as of 13:20, 27 October 2016
This page proves a lemma for the m=13 case of FUNC.
Lemma 1:
If [math]\displaystyle{ \mathcal{A} }[/math] contains 2 size 3 sets with a two element intersection, then [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's.
Let w(1)=w(2)=8, w(3)=w(4)=6, and w(x)=1 otherwise. The target weight is 18.5 Let C be an arbitrary 1234-hypercube with bottom set K.
|K|=0:
The deficit is exactly 18.5, and the sets 123, 124, 1234 together have 1.5+1.5+7.5=10.5 surplus. Therefore the deficit is 8 more than the surplus
|K|=1:
As there cannot be 3 size three sets contained in a size 5 set, there are no [math]\displaystyle{ C_2 }[/math] sets. Therefore, there is no deficit.
|K|=2:
There are no [math]\displaystyle{ C_0 }[/math] sets, so the deficit is made up from the [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] sets. The 1234 set has surplus 11.5. We have a few cases:
[math]\displaystyle{ P_1 }[/math]=0:
Aside from 34, with deficit 4.5 the [math]\displaystyle{ C_2 }[/math] sets each have deficit at most 2.5, so [math]\displaystyle{ P_2 }[/math]>=4. Therefore, [math]\displaystyle{ P_3 }[/math]>=3. Each of those sets has surplus at least 3.5, so the total surplus is now at least 22. This is more than the maximum deficit (14.5), so in this case the surplus is greater than the deficit.
[math]\displaystyle{ P_1 }[/math]=1:
The [math]\displaystyle{ C_1 }[/math] set has deficit at most 10.5, and it guarantees at least one of 123 or 124 are in C. Thus the surplus is at least 11.5+5.5=17. Therefore, there are at least two [math]\displaystyle{ C_2 }[/math] sets.
If one of them is 34, then it guarantees one of 134, 234 is in C. This means there is at least 17+3.5=20.5 surplus. That would mean [math]\displaystyle{ P_2 }[/math]>=4. That means [math]\displaystyle{ P_3 }[/math]>=3, so there is now at least 20.5+3.5=24 surplus. So now [math]\displaystyle{ P_2 }[/math]>=5 to compensate, and [math]\displaystyle{ P_3 }[/math]=4, so the surplus is 24+5.5=29.5. This cannot be matched by the deficit, so the surplus is greater than the deficit.
If 34 is not in C, then there are 3 other [math]\displaystyle{ C_2 }[/math] sets. This guarantees that both 123 and 124 are in C. Therefore, there is at least 11.5+11=23.5 surplus. This cannot be matched by the allowable deficit (10.5+12.5=23).
In either case, the surplus is greater than the deficit.
[math]\displaystyle{ P_1 }[/math]>=2:
In this case, either we have 3 size 3 sets that are subsets of the same 5 element set (123, 156, 256 or 124, 256, 456 etc), or we have 4 size three sets of the form 123, 124, 356, 456. This implies that [math]\displaystyle{ \mathcal{A} }[/math] is Frankl's from the article Find set configurations that imply FUNC.
