Lemma 7.6

2016-12-02T07:07:31Z

Tomtom2357: Created page with "This page proves a lemma for the m=13 case of FUNC. ==Lemma 7.6:== If <math>\mathcal{A}</math> contains a size 5 set, then <math>\mathcal{A}</math> is Frankl's. WLOG le..."

Lemma 7

2016-12-02T00:12:55Z

Tomtom2357: /* Lemma 7: */

This page proves a lemma for the [[m=13 case of FUNC]].

==Lemma 7:==
This proof is much longer than anticipated (and it's still not completed), but it will be split into six cases (with each case relying on the previous cases):

[[Lemma 7.1]]: If there are two size 5 sets intersecting at 4 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.2]]: If there are two size 5 sets intersecting at 3 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.3]]: If there are two size 5 sets intersecting at 2 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.4]]: If there are two size 5 sets intersecting in 1 element, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.5]]: If there are two size 5 sets, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.6]]: If there is a size 5 set, then <math>\mathcal{A}</math> is Frankl's

M=13 case of FUNC

2016-12-02T00:12:21Z

Tomtom2357: /* Lemmas */

On this page, we attempt a proof of the m=13 case of Frankl's conjecture. This will probably end up being a long case analysis, with the cases being tackled out of order, so bear with me while the page is in progress. In all results below, we will try to prove that the set <math>\mathcal{A}</math> is Frankl's (satisfies the conjecture), but will assume the opposite. We will use the terminology defined in the paper "The 11 element case of Frankl's Conjecture" by Ivica Bosnjak and Petar Markovic.

==Lemmas==

Note that the lemmas will get moved around in the process of proof. Right now this is an outline of the different things to prove.

[[Lemma 1]]: If <math>\mathcal{A}</math> contains 2 three element sets with a two element intersection, then <math>\mathcal{A}</math> is Frankl's. (Not completed)

[[Lemma 2]]: If <math>\mathcal{A}</math> contains 2 intersecting 3 element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 3]]: If <math>\mathcal{A}</math> contains 2 three element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 4]]: If <math>\mathcal{A}</math> contains a four element set and a three element subset, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 5]]: If <math>\mathcal{A}</math> contains a 3 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 6]]: If <math>\mathcal{A}</math> contains a 4 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 7]]: If <math>\mathcal{A}</math> contains a 5 element set, then <math>\mathcal{A}</math> is Frankl's. (Not completed)

[[Lemma 8]]: If <math>\mathcal{A}</math> contains two 6 element sets intersecting at five elements, then <math>\mathcal{A}</math> is Frankl's.

[[M=13 Theorem]]: <math>\mathcal{A}</math> is Frankl's. Note that this relies on the prior lemmas, which so far haven't all been proved.

Lemma 7

2016-12-01T03:36:25Z

Tomtom2357: Created page, split into sections

This page proves a lemma for the [[m=13 case of FUNC]].

==Lemma 7:==
This proof is much longer than anticipated (and it's still not completed), but it will be split into six cases (with each case relying on the previous cases):

[[Lemma 7.1]]: If there are two size 5 sets intersecting at 4 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.1]]: If there are two size 5 sets intersecting at 3 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.1]]: If there are two size 5 sets intersecting at 2 elements, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.1]]: If there are two size 5 sets intersecting in 1 element, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.1]]: If there are two size 5 sets, then <math>\mathcal{A}</math> is Frankl's

[[Lemma 7.1]]: If there is a size 5 set, then <math>\mathcal{A}</math> is Frankl's

M=13 Theorem

2016-11-12T23:41:36Z

Tomtom2357: /* Proof */

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>\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>\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>\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.

M=13 Theorem

2016-11-12T06:11:05Z

Tomtom2357: 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..."

M=13 case of FUNC

2016-11-12T05:08:00Z

Tomtom2357: /* Lemmas */

On this page, we attempt a proof of the m=13 case of Frankl's conjecture. This will probably end up being a long case analysis, with the cases being tackled out of order, so bear with me while the page is in progress. In all results below, we will try to prove that the set <math>\mathcal{A}</math> is Frankl's (satisfies the conjecture), but will assume the opposite. We will use the terminology defined in the paper "The 11 element case of Frankl's Conjecture" by Ivica Bosnjak and Petar Markovic.

==Lemmas==

Note that the lemmas will get moved around in the process of proof. Right now this is an outline of the different things to prove.

[[Lemma 1]]: If <math>\mathcal{A}</math> contains 2 three element sets with a two element intersection, then <math>\mathcal{A}</math> is Frankl's. (Not completed)

[[Lemma 2]]: If <math>\mathcal{A}</math> contains 2 intersecting 3 element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 3]]: If <math>\mathcal{A}</math> contains 2 three element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 4]]: If <math>\mathcal{A}</math> contains a four element set and a three element subset, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 5]]: If <math>\mathcal{A}</math> contains a 3 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 6]]: If <math>\mathcal{A}</math> contains a 4 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 7]]: If <math>\mathcal{A}</math> contains a 5 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 8]]: If <math>\mathcal{A}</math> contains two 6 element sets intersecting at five elements, then <math>\mathcal{A}</math> is Frankl's.

[[M=13 Theorem]]: <math>\mathcal{A}</math> is Frankl's. Note that this relies on the prior lemmas, which so far haven't all been proved.

M=13 case of FUNC

2016-11-12T05:07:17Z

Tomtom2357: /* Lemmas */

On this page, we attempt a proof of the m=13 case of Frankl's conjecture. This will probably end up being a long case analysis, with the cases being tackled out of order, so bear with me while the page is in progress. In all results below, we will try to prove that the set <math>\mathcal{A}</math> is Frankl's (satisfies the conjecture), but will assume the opposite. We will use the terminology defined in the paper "The 11 element case of Frankl's Conjecture" by Ivica Bosnjak and Petar Markovic.

==Lemmas==

Note that the lemmas will get moved around in the process of proof. Right now this is an outline of the different things to prove.

[[Lemma 1]]: If <math>\mathcal{A}</math> contains 2 three element sets with a two element intersection, then <math>\mathcal{A}</math> is Frankl's. (Not completed)

[[Lemma 2]]: If <math>\mathcal{A}</math> contains 2 intersecting 3 element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 3]]: If <math>\mathcal{A}</math> contains 2 three element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 4]]: If <math>\mathcal{A}</math> contains a four element set and a three element subset, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 5]]: If <math>\mathcal{A}</math> contains a 3 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 6]]: If <math>\mathcal{A}</math> contains a 4 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 7]]: If <math>\mathcal{A}</math> contains a 5 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 8]]: If <math>\mathcal{A}</math> contains two 6 element sets intersecting at five elements, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 9]]: <math>\mathcal{A}</math> is Frankl's. Note that this relies on the prior lemmas, which so far haven't all been proved.

M=13 case of FUNC

2016-11-12T04:50:52Z

2016-11-01T03:44:15Z

Tomtom2357:

On this page, we attempt a proof of the m=13 case of Frankl's conjecture. This will probably end up being a long case analysis, with the cases being tackled out of order, so bear with me while the page is in progress. In all results below, we will try to prove that the set <math>\mathcal{A}</math> is Frankl's (satisfies the conjecture), but will assume the opposite. We will use the terminology defined in the paper "The 11 element case of Frankl's Conjecture" by Ivica Bosnjak and Petar Markovic.

==Lemmas==

Note that the lemmas will get moved around in the process of proof. Right now this is an outline of the different things to prove.

[[Lemma 1]]: If <math>\mathcal{A}</math> contains 2 three element sets with a two element intersection, then <math>\mathcal{A}</math> is Frankl's. (Not completed)

[[Lemma 2]]: If <math>\mathcal{A}</math> contains 2 intersecting 3 element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 3]]: If <math>\mathcal{A}</math> contains 2 three element sets, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 4]]: If <math>\mathcal{A}</math> contains a four element set and a three element subset, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 5]]: If <math>\mathcal{A}</math> contains a 3 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 6]]: If <math>\mathcal{A}</math> contains a 4 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 7]]: If <math>\mathcal{A}</math> contains a 5 element set, then <math>\mathcal{A}</math> is Frankl's.

[[Lemma 8]]: If m=13, then <math>\mathcal{A}</math> is Frankl's.

Lemma 1

2016-10-31T22:00:48Z

Tomtom2357: /* |K|=3: */

This page proves a lemma for the [[m=13 case of FUNC]].
==Lemma 1:==

If <math>\mathcal{A}</math> contains 2 size 3 sets with a two element intersection, then <math>\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>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:

===<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.

===<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.

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>P_2</math>>=4. That means <math>P_3</math>>=3, so there is now at least 20.5+3.5=24 surplus. So now <math>P_2</math>>=5 to compensate, and <math>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>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>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]].

==|K|=3:==

The <math>C_4</math> set has surplus 12.5. There are two cases:

===Case 1: The bottom set K is not in C===

The <math>C_2</math> sets can only contribute 9.5 to the deficit, so at least one of the <math>C_1</math> sets is in C. This means one of 123 and 124 are in C, and they each have surplus 6.5, so the surplus is at least 19. We have four subcases:

====<math>P_1</math>=1:====

If the <math>C_1</math> set is 1 or 2, then it contributes only 7.5 to the deficit, but the <math>C_2</math> sets can't make up the remaining 12 necessary deficit (since 123 is in C).

If the <math>C_1</math> set is 3 or 4 (WLOG assume it's 3), it's deficit is 9.5, and 123 is in C. The surplus is at least 17, so the deficit of the <math>C_2</math> sets is at least 7.5. Since all those sets other than 34 have deficit 1.5 (except 12 which has surplus), 34 must be in C, along with at least 3 of the others. This implies that all the size 3 sets are in C, raising the surplus to 32.5, which cannot be matched by the deficit.

====<math>P_1</math>=2:====

This implies that both 123 and 124 are in C. Therefore, the surplus is at least 12.5+6.5+6.5=25.5. The deficit of those sets is at most 9.5+9.5=19. Therefore, the <math>C_2</math> deficit must be at least 7. This means that the set 34 must be in C, since the other <math>C_2</math> sets only contribute a total of 6 to the deficit. Also, at least 3 of the other <math>C_2</math> deficit sets must be in C. This means that 134 and 234 are also in C. This raises the total surplus to at least 25.5+4.5+4.5=34. This cannot be matched by the deficit, so the surplus is always greater than the deficit in this case.

====<math>P_1</math>>=3:====

This case is covered by [[Sublemma 1.1]], showing that in this case, <math>\mathcal{A}</math> is Frankl's.

(Needs to be continued)

==|K|=4:==

In this case, the top set has surplus 13.5. There are two cases:

===Case 1: The bottom set K is not in C===

In this case, since the maximum total deficit of the <math>C_2</math> sets is 4.5. Therefore, since the <math>C_1</math> sets can only have a deficit of at most 8.5 each, there must be at least two <math>C_1</math> sets in C. Therefore, both 123 and 124 are in C. Each of those have a surplus of 7.5, so this means the surplus is at least 28.5. Therefore, since the deficits of 1, 2, 3, 4 are 6.5, 6.5, 8.5, 8.5 respectively, and the deficit of 3 of these plus the maximum <math>C_2</math> deficit is at most 28, we need all four <math>C_1</math> sets in C. So the sets 134, 234 are in C. Each of these has surplus 5.5, so the surplus is at least 39.5. This is more than the maximum possible deficit (34.5).

===Case 2: The bottom set K is in C===

This case implies that both 123, 124 are in C. Thus the surplus is at least 28.5. The bottom set has deficit 14.5, and the maximum total deficit of the <math>C_2</math> sets is 4.5, which adds up to 19. Thus, since (as said above) the maximum deficit of a single <math>C_1</math> set is 8.5, there must be at least 2 of them in C.

In a sub-lemma (sorry this has been terribly organised), we'll prove that if this is the case, then <math>\mathcal{A}</math> is Frankl's.

(Needs to be continued)

==|K|=5:==

In this case, the surplus of the top set is 14.5. The <math>C_2</math> sets have no deficit, except for 34, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets and 34. The <math>C_1</math> sets 1 and 2 have deficit 5.5, the sets 3 and 4 have deficit 7.5, and the <math>C_0</math> set has deficit 13.5. If <math>P_1</math>=0, then the deficit of the <math>C_0</math> set is not enough to surpass the surplus. If <math>P_1</math>=1, then at least one of 123 or 124 are in C, so the total surplus is at least 14.5+8.5=23, which is greater than the maximum deficit (7.5+13.5+1.5=22.5). If <math>P_1</math>=2, then both 123 and 124 are in C, so the total surplus is at least 14.5+8.5+8.5=31.5, which is greater than the maximum deficit (7.5+7.5+13.5+1.5=30).

If <math>P_1</math>=3, then they are either (WLOG) 1, 2, 3 or 1, 3, 4. If it is 1,2,3, then the deficit is at most 13.5+5.5+5.5+7.5+1.5=33.5, and the surplus from the sets 12, 13, 23, 123, 124, 1234 is 2.5+0.5+0.5+8.5+8.5+14.5=35, which is greater than the deficit. If it is 1,3,4, then the deficit is 13.5+7.5+7.5+5.5+1.5=35.5, and the surplus from the sets 13, 14, 123, 124, 134, 1234 is 0.5+0.5+8.5+8.5+6.5+14.5=40, which is greater than the deficit.

If <math>P_1</math>=4, then the surplus from the sets is 48, which is greater than the maximum deficit (40).

In every case, the surplus is greater than the deficit.

==6<=|K|<=8:==

In this case, the surplus of the top set is at least 15.5. The <math>C_2</math> sets have no deficit, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets. The total deficit of the <math>C_1</math> sets are at most 22, but having even one of them in C implies that 123 or 124 is in C. Those sets have weight 9.5 each, so even one of them being in C makes the total surplus more than that deficit.

The <math>C_0</math> set has deficit 12, but if it is in C, then both 123 and 124 are, so the total surplus is at least 34.5. This is more than the maximum deficit of that set and the <math>C_1</math> sets combined, so the surplus is greater than the deficit in these cases.

==|K|=9:==

The top set has weight 37, with surplus 18.5. The total deficit of the <math>C_1</math> sets are at most 10, and having any of them implies that one of 123 or 124 is in C. Those have surplus 12.5 each. The <math>C_0</math> set has deficit 9.5, but it implies that both 123, 124 are in C. Therefore, no matter what, the surplus is at least 18.5 greater than the deficit.

Lemma 1

2016-10-31T12:17:40Z

Tomtom2357: /* |K|=4: */

This page proves a lemma for the [[m=13 case of FUNC]].
==Lemma 1:==

If <math>\mathcal{A}</math> contains 2 size 3 sets with a two element intersection, then <math>\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>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:

===<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.

===<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.

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>P_2</math>>=4. That means <math>P_3</math>>=3, so there is now at least 20.5+3.5=24 surplus. So now <math>P_2</math>>=5 to compensate, and <math>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>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>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]].

==|K|=3:==

The <math>C_4</math> set has surplus 12.5. There are two cases:

===Case 1: The bottom set K is not in C===

The <math>C_2</math> sets can only contribute 9.5 to the deficit, so at least one of the <math>C_1</math> sets is in C. This means one of 123 and 124 are in C, and they each have surplus 6.5, so the surplus is at least 19. We have four subcases:

====<math>P_1</math>=1:====

If the <math>C_1</math> set is 1 or 2, then it contributes only 7.5 to the deficit, but the <math>C_2</math> sets can't make up the remaining 12 necessary deficit.

If the <math>C_1</math> set is 3 or 4 (WLOG assume it's 3), it's deficit is 9.5, and 123 is in C. The surplus is at least 17, so the deficit of the <math>C_2</math> sets is at least 7.5. Since all those sets other than 34 have deficit 1.5 (except 12 which has surplus), 34 must be in C, along with at least 3 of the others. This implies that all the size 3 sets are in C, raising the surplus to 32.5, which cannot be matched by the deficit.

(Needs to be continued)

==|K|=4:==

In this case, the top set has surplus 13.5. There are two cases:

===Case 1: The bottom set K is not in C===

In this case, since the maximum total deficit of the <math>C_2</math> sets is 4.5. Therefore, since the <math>C_1</math> sets can only have a deficit of at most 8.5 each, there must be at least two <math>C_1</math> sets in C. Therefore, both 123 and 124 are in C. Each of those have a surplus of 7.5, so this means the surplus is at least 28.5. Therefore, since the deficits of 1, 2, 3, 4 are 6.5, 6.5, 8.5, 8.5 respectively, and the deficit of 3 of these plus the maximum <math>C_2</math> deficit is at most 28, we need all four <math>C_1</math> sets in C. So the sets 134, 234 are in C. Each of these has surplus 5.5, so the surplus is at least 39.5. This is more than the maximum possible deficit (34.5).

===Case 2: The bottom set K is in C===

This case implies that both 123, 124 are in C. Thus the surplus is at least 28.5. The bottom set has deficit 14.5, and the maximum total deficit of the <math>C_2</math> sets is 4.5, which adds up to 19. Thus, since (as said above) the maximum deficit of a single <math>C_1</math> set is 8.5, there must be at least 2 of them in C.

In a sub-lemma (sorry this has been terribly organised), we'll prove that if this is the case, then <math>\mathcal{A}</math> is Frankl's.

(Needs to be continued)

==|K|=5:==

In this case, the surplus of the top set is 14.5. The <math>C_2</math> sets have no deficit, except for 34, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets and 34. The <math>C_1</math> sets 1 and 2 have deficit 5.5, the sets 3 and 4 have deficit 7.5, and the <math>C_0</math> set has deficit 13.5. If <math>P_1</math>=0, then the deficit of the <math>C_0</math> set is not enough to surpass the surplus. If <math>P_1</math>=1, then at least one of 123 or 124 are in C, so the total surplus is at least 14.5+8.5=23, which is greater than the maximum deficit (7.5+13.5+1.5=22.5). If <math>P_1</math>=2, then both 123 and 124 are in C, so the total surplus is at least 14.5+8.5+8.5=31.5, which is greater than the maximum deficit (7.5+7.5+13.5+1.5=30).

If <math>P_1</math>=3, then they are either (WLOG) 1, 2, 3 or 1, 3, 4. If it is 1,2,3, then the deficit is at most 13.5+5.5+5.5+7.5+1.5=33.5, and the surplus from the sets 12, 13, 23, 123, 124, 1234 is 2.5+0.5+0.5+8.5+8.5+14.5=35, which is greater than the deficit. If it is 1,3,4, then the deficit is 13.5+7.5+7.5+5.5+1.5=35.5, and the surplus from the sets 13, 14, 123, 124, 134, 1234 is 0.5+0.5+8.5+8.5+6.5+14.5=40, which is greater than the deficit.

If <math>P_1</math>=4, then the surplus from the sets is 48, which is greater than the maximum deficit (40).

In every case, the surplus is greater than the deficit.

==6<=|K|<=8:==

In this case, the surplus of the top set is at least 15.5. The <math>C_2</math> sets have no deficit, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets. The total deficit of the <math>C_1</math> sets are at most 22, but having even one of them in C implies that 123 or 124 is in C. Those sets have weight 9.5 each, so even one of them being in C makes the total surplus more than that deficit.

The <math>C_0</math> set has deficit 12, but if it is in C, then both 123 and 124 are, so the total surplus is at least 34.5. This is more than the maximum deficit of that set and the <math>C_1</math> sets combined, so the surplus is greater than the deficit in these cases.

==|K|=9:==

The top set has weight 37, with surplus 18.5. The total deficit of the <math>C_1</math> sets are at most 10, and having any of them implies that one of 123 or 124 is in C. Those have surplus 12.5 each. The <math>C_0</math> set has deficit 9.5, but it implies that both 123, 124 are in C. Therefore, no matter what, the surplus is at least 18.5 greater than the deficit.

Lemma 1

2016-10-31T12:01:37Z

Tomtom2357:

This page proves a lemma for the [[m=13 case of FUNC]].
==Lemma 1:==

If <math>\mathcal{A}</math> contains 2 size 3 sets with a two element intersection, then <math>\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>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:

===<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.

===<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.

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>P_2</math>>=4. That means <math>P_3</math>>=3, so there is now at least 20.5+3.5=24 surplus. So now <math>P_2</math>>=5 to compensate, and <math>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>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>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]].

==|K|=3:==

The <math>C_4</math> set has surplus 12.5. There are two cases:

===Case 1: The bottom set K is not in C===

The <math>C_2</math> sets can only contribute 9.5 to the deficit, so at least one of the <math>C_1</math> sets is in C. This means one of 123 and 124 are in C, and they each have surplus 6.5, so the surplus is at least 19. We have four subcases:

====<math>P_1</math>=1:====

If the <math>C_1</math> set is 1 or 2, then it contributes only 7.5 to the deficit, but the <math>C_2</math> sets can't make up the remaining 12 necessary deficit.

If the <math>C_1</math> set is 3 or 4 (WLOG assume it's 3), it's deficit is 9.5, and 123 is in C. The surplus is at least 17, so the deficit of the <math>C_2</math> sets is at least 7.5. Since all those sets other than 34 have deficit 1.5 (except 12 which has surplus), 34 must be in C, along with at least 3 of the others. This implies that all the size 3 sets are in C, raising the surplus to 32.5, which cannot be matched by the deficit.

(Needs to be continued)

==|K|=4:==

In this case, the top set has surplus 13.5. There are two cases:

===Case 1: The bottom set K is not in C===

In this case, since the maximum deficit of the <math>C_1</math> sets

(Needs to be continued)

==|K|=5:==

In this case, the surplus of the top set is 14.5. The <math>C_2</math> sets have no deficit, except for 34, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets and 34. The <math>C_1</math> sets 1 and 2 have deficit 5.5, the sets 3 and 4 have deficit 7.5, and the <math>C_0</math> set has deficit 13.5. If <math>P_1</math>=0, then the deficit of the <math>C_0</math> set is not enough to surpass the surplus. If <math>P_1</math>=1, then at least one of 123 or 124 are in C, so the total surplus is at least 14.5+8.5=23, which is greater than the maximum deficit (7.5+13.5+1.5=22.5). If <math>P_1</math>=2, then both 123 and 124 are in C, so the total surplus is at least 14.5+8.5+8.5=31.5, which is greater than the maximum deficit (7.5+7.5+13.5+1.5=30).

If <math>P_1</math>=3, then they are either (WLOG) 1, 2, 3 or 1, 3, 4. If it is 1,2,3, then the deficit is at most 13.5+5.5+5.5+7.5+1.5=33.5, and the surplus from the sets 12, 13, 23, 123, 124, 1234 is 2.5+0.5+0.5+8.5+8.5+14.5=35, which is greater than the deficit. If it is 1,3,4, then the deficit is 13.5+7.5+7.5+5.5+1.5=35.5, and the surplus from the sets 13, 14, 123, 124, 134, 1234 is 0.5+0.5+8.5+8.5+6.5+14.5=40, which is greater than the deficit.

If <math>P_1</math>=4, then the surplus from the sets is 48, which is greater than the maximum deficit (40).

In every case, the surplus is greater than the deficit.

==6<=|K|<=8:==

In this case, the surplus of the top set is at least 15.5. The <math>C_2</math> sets have no deficit, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets. The total deficit of the <math>C_1</math> sets are at most 22, but having even one of them in C implies that 123 or 124 is in C. Those sets have weight 9.5 each, so even one of them being in C makes the total surplus more than that deficit.

The <math>C_0</math> set has deficit 12, but if it is in C, then both 123 and 124 are, so the total surplus is at least 34.5. This is more than the maximum deficit of that set and the <math>C_1</math> sets combined, so the surplus is greater than the deficit in these cases.

==|K|=9:==

The top set has weight 37, with surplus 18.5. The total deficit of the <math>C_1</math> sets are at most 10, and having any of them implies that one of 123 or 124 is in C. Those have surplus 12.5 each. The <math>C_0</math> set has deficit 9.5, but it implies that both 123, 124 are in C. Therefore, no matter what, the surplus is at least 18.5 greater than the deficit.

Lemma 1

2016-10-31T08:50:57Z

Tomtom2357:

This page proves a lemma for the [[m=13 case of FUNC]].
==Lemma 1:==

If <math>\mathcal{A}</math> contains 2 size 3 sets with a two element intersection, then <math>\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>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:

===<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.

===<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.

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>P_2</math>>=4. That means <math>P_3</math>>=3, so there is now at least 20.5+3.5=24 surplus. So now <math>P_2</math>>=5 to compensate, and <math>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>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>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]].

==|K|=3:==

The <math>C_4</math> set has surplus 12.5. There are two cases:

===Case 1: The bottom set K is not in C===

The <math>C_2</math> sets can only contribute 9.5 to the deficit, so at least one of the <math>C_1</math> sets is in C. This means one of 123 and 124 are in C, and they each have surplus 6.5, so the surplus is at least 19. We have four subcases:

====<math>P_1</math>=1:====

If the <math>C_1</math> set is 1 or 2, then it contributes only 7.5 to the deficit, but the <math>C_2</math> sets can't make up the remaining 12 necessary deficit.

If the <math>C_1</math> set is 3 or 4 (WLOG assume it's 3), it's deficit is 9.5, and 123 is in C. The surplus is at least 17, so the deficit of the <math>C_2</math> sets is at least 7.5. Since all those sets other than 34 have deficit 1.5 (except 12 which has surplus), 34 must be in C, along with at least 3 of the others. This implies that all the size 3 sets are in C, raising the surplus to 32.5, which cannot be matched by the deficit.

(Needs to be continued)

==|K|=5:==

In this case, the surplus of the top set is 14.5. The <math>C_2</math> sets have no deficit, except for 34, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets and 34. The <math>C_1</math> sets 1 and 2 have deficit 5.5, the sets 3 and 4 have deficit 7.5, and the <math>C_0</math> set has deficit 13.5. If <math>P_1</math>=0, then the deficit of the <math>C_0</math> set is not enough to surpass the surplus. If <math>P_1</math>=1, then at least one of 123 or 124 are in C, so the total surplus is at least 14.5+8.5=23, which is greater than the maximum deficit (7.5+13.5+1.5=22.5). If <math>P_1</math>=2, then both 123 and 124 are in C, so the total surplus is at least 14.5+8.5+8.5=31.5, which is greater than the maximum deficit (7.5+7.5+13.5+1.5=30).

If <math>P_1</math>=3, then they are either (WLOG) 1, 2, 3 or 1, 3, 4. If it is 1,2,3, then the deficit is at most 13.5+5.5+5.5+7.5+1.5=33.5, and the surplus from the sets 12, 13, 23, 123, 124, 1234 is 2.5+0.5+0.5+8.5+8.5+14.5=35, which is greater than the deficit. If it is 1,3,4, then the deficit is 13.5+7.5+7.5+5.5+1.5=35.5, and the surplus from the sets 13, 14, 123, 124, 134, 1234 is 0.5+0.5+8.5+8.5+6.5+14.5=40, which is greater than the deficit.

If <math>P_1</math>=4, then the surplus from the sets is 48, which is greater than the maximum deficit (40).

In every case, the surplus is greater than the deficit.

==6<=|K|<=8:==

In this case, the surplus of the top set is at least 15.5. The <math>C_2</math> sets have no deficit, so the deficit only comes from the <math>C_0</math> set and the <math>C_1</math> sets. The total deficit of the <math>C_1</math> sets are at most 22, but having even one of them in C implies that 123 or 124 is in C. Those sets have weight 9.5 each, so even one of them being in C makes the total surplus more than that deficit.

The <math>C_0</math> set has deficit 12, but if it is in C, then both 123 and 124 are, so the total surplus is at least 34.5. This is more than the maximum deficit of that set and the <math>C_1</math> sets combined, so the surplus is greater than the deficit in these cases.

==|K|=9:==

The top set has weight 37, with surplus 18.5. The total deficit of the <math>C_1</math> sets are at most 10, and having any of them implies that one of 123 or 124 is in C. Those have surplus 12.5 each. The <math>C_0</math> set has deficit 9.5, but it implies that both 123, 124 are in C. Therefore, no matter what, the surplus is at least 18.5 greater than the deficit.

2016-10-27T20:47:32Z

Tomtom2357: /* Case 2: {} is not in C */

== Introduction ==

One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}</math>, contains at least as many sets as <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\}</math>. A slightly more clever argument shows that if a two element set {x, y} is in <math>\mathcal{A}</math>, then FUNC holds for <math>\mathcal{A}</math>:

Let <math>\mathcal{A}_{xy} = \{A \in \mathcal{A} : x, y \in A\}</math>, <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\ , y\notin A\}</math>, <math>\mathcal{A}_y = \{A \in \mathcal{A} : y \in A\ , x\notin A\}</math>, <math>\mathcal{A}_\emptyset = \{A \in \mathcal{A} : x, y\notin A\}</math>. Because {x, y} is in <math>\mathcal{A}</math>, the set <math>\mathcal{A}_{xy}</math> has at least as many sets as <math>\mathcal{A}_\emptyset</math>. Therefore, depending on which of <math>\mathcal{A}_x</math> and <math>\mathcal{A}_y</math> is larger, x or y are in at least half of the sets.

One might assume that a similar argument would work for three element sets, but unfortunately the argument fails. In fact, there is a family <math>\mathcal{A}</math> with only 9 elements in the ground set, and one set with three elements, such that none of those three elements is in at least half of the sets. However, one can show that if <math>\mathcal{A}</math> contains certain configurations of sets of size 3, then FUNC holds for <math>\mathcal{A}</math>. For example, in [http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r88/pdf this] article, it is shown that if <math>\mathcal{A}</math> contains 3 sets of size three that are subsets of the same set of size 5, then FUNC holds for <math>\mathcal{A}</math>. This article attempts to extend the results given in that paper.

== Lemma 1 ==
If <math>\mathcal{A}</math> contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}, then FUNC holds for <math>\mathcal{A}</math>.

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in <math>\mathcal{A}</math>. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for <math>\mathcal{A}</math>.

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

Case 1: {} is in C: The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, along with all their unions, which together make up all the sets of size 5. The total surplus of these sets is 12 (there are 6 sets of size 5, and each has surplus 2, and we’re ignoring the full set), therefore the total deficit must be at least 13. However, for every set of size 1 in C, there are two sets of size 4 in C, as follows:
1: {1, 2, 4, 6}, {1, 3, 5, 6}
2: {1, 2, 4, 5}, {2, 3, 5, 6}
3: {1, 3, 4, 5}. {2, 3, 4, 6}
4: {1, 2, 3, 4}, {3, 4, 5, 6}
5: {1, 2, 3, 5}, {2, 4, 5, 6}
6: {1, 2, 3, 6}, {1, 4, 5, 6}
Therefore, the total deficit of the size two sets must make up the 13. But then there must be at least 13 sets of size 2 in C (since they only have deficit 1), and together, these 13 sets generate all of the sets of size 4 (since each set of size 4 can be generated in 3 ways, you need to remove 3 sets before you can’t generate a set of size 4). Therefore, the total surplus is 27, which is the maximum that the total deficit can be.

Case 2: {} is not in C. In this case, since {} is not in C, we consider the set {1, 2, 3, 4, 5, 6} as counting towards the total surplus (as the empty set isn’t there to cancel it out). Now, each set of size 1 in C means that two of {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, and the union of those is a size 5 set, so each size one set cancels out with a size 5 set. Now, every set of size 2 in C forces a set of size 4 to be in C, except {1, 6}, {2, 5}, {3, 4}. We just need a bijection from the sets of size 2 (excluding the above) to the sets of size 4 (excluding {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}), such that if a set of size 2 is in C, then the associated set of size 4 is in C. One such bijection is:
{1, 2}->{1, 2, 4, 5},
{1, 3}->{1, 3, 5, 6},
{1, 4}->{1, 2, 4, 6},
{1, 5}->{1, 2, 3, 5},
{2, 3}->{2, 3, 4, 6},
{2, 4}->{1, 2, 3, 4},
{2, 6}->{2, 3, 5, 6},
{3, 5}->{1, 3, 4, 5},
{3, 6}->{1, 2, 3, 6},
{4, 5}->{3, 4, 5, 6},
{4, 6}->{1, 4, 5, 6},
{5, 6}->{2, 4, 5, 6}

So, the surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of {1, 6}, {2, 5}, {3, 4}, and every other set of size 2 has an associated set of size 4. Therefore, the surplus is at least the deficit.

== Lemma 2 ==

If <math>\mathcal{A}</math> contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 2, 4}, {3, 5, 6}, {4, 5, 6}, then FUNC holds for <math>\mathcal{A}</math>.

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in <math>\mathcal{A}</math>. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for <math>\mathcal{A}</math>.

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

===Case 1: {} is in C:===
The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 2, 4}, {3, 5, 6}, {4, 5, 6} are in C, along with their unions, which are {1, 2, 3, 4}, {3, 4, 5, 6}, {1, 2, 3, 5, 6}, and {1, 2, 4, 5, 6}. This generates a surplus of 6. We can map each set of size 1 except {3} and {4} to an implied sets of size 5, which cancels out their deficit.

1: {1, 3, 4, 5, 6}

2: {2, 3, 4, 5, 6}

5: {1, 2, 3, 4, 5}

6: {1, 2, 3, 4, 6}

We have another mapping from some size 2 sets to implied size 4 or 5 sets, cancelling out their deficit (each set on the left implies all of the sets on the right by itself).

{1, 3}: {1, 3, 5, 6}

{1, 4}: {1, 4, 5, 6}

{2, 3}: {2, 3, 5, 6}

{2, 4}: {2, 4, 5, 6}

{3, 5}: {1, 2, 3, 5}

{3, 6}: {1, 2, 3, 6}

{4, 5}: {1, 2, 4, 5}

{4, 6}: {1, 2, 4, 6}

==== Case 1.1: neither {3} nor {4} are in C====
Then all the sets not in the above pairing must be in C. But this generates the set {1, 2, 5, 6} which pushes the net surplus up to 7, which the deficit cannot surpass.

====Case 1.2: Only one of {3} and {4} are in C====
WLOG, assume this set is {3}. In this case, there must be at least 5 size 2 sets not in the above list in C. If {3, 4} is in C, then we can pair each of the remaining size 2 sets with it's union with {3, 4}, so {3, 4} cannot be in C. But sine 5 of the size 2 subsets of {1, 2, 5, 6} are in C, that means {1, 2, 5, 6} is in C as well. This raises the surplus by one, forcing all 6 size 2 subsets of {1, 2, 5, 6} to be in C. Therefore, the sets {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 4, 5, 6}, {2, 4, 5, 6}, {1, 3, 5, 6}, {2, 3, 5, 6} are in C, raising the surplus to 15. This forces all the size 2 sets other than {3, 4} to be in C. But then, {1, 3, 4, 6} is in C, raising the surplus to 16, which the deficit cannot surpass.

====Case 1.3: Both {3} and {4} are in C====
Each of the sets disjoint from {3, 4} can be paired with it's union with {3, 4}, and the pairing above remains valid. Therefore, all size 2 sets other than {3, 4} do not contribute towards the net deficit, so the net deficit is at most 5, which is less than the net surplus (6).

Thus, in either case, <math>\mathcal{A}</math> is Frankl's.

===Case 2: {} is not in C===
In this case, the only set we know is in C is {1, 2, 3, 4, 5, 6}. Thus the surplus is at least 6. Given the pairing:

{1}: {1, 3, 4, 5, 6}

{2}: {2, 3, 4, 5, 6}

{3}: {1, 2, 3, 5, 6}

{4}: {1, 2, 4, 5, 6}

{5}: {1, 2, 3, 4, 5}

{6}: {1, 2, 3, 4, 6}

None of the size 1 sets contribute to the net deficit. We also have a pairing:
{1, 3}: {1, 3, 5, 6}

{1, 4}: {1, 4, 5, 6}

{2, 3}: {2, 3, 5, 6}

{2, 4}: {2, 4, 5, 6}

{3, 4}: {1, 2, 3, 4}

{3, 5}: {1, 2, 3, 5}

{3, 6}: {1, 2, 3, 6}

{4, 5}: {1, 2, 4, 5}

{4, 6}: {1, 2, 4, 6}

Thus only 6 size 2 sets contribute to the net deficit. Thus the deficit cannot surpass the surplus. Therefore, in either case, <math>\mathcal{A}</math> is Frankl's.

== Finding the implied abundance given a configuration ==

Even if a configuration does not directly imply Frankl's conjecture holds for <math>\mathcal{A}</math>, it can give some interesting results about the minimal abundance, and the weight function. Having one set of size 3, the only way to weight the set is to give equal weight to each element, and the lowest possible abundance on elements of that set is 4/9. If there are two sets of size 3 having an intersection of size 2 ({1, 2, 3}, {1, 2, 4}), then the lowest possible abundance of an element is 27/55, which is the best possible, and it is given by the weight function w(1)=w(2)=31, w(3)=w(4)=24. This was found by equating the abundance at the two extreme cases of this case: {1}, {2}, {3} in C (and same replacing 3 with 4), and {3}, {4} in C. Hopefully I will be able to find the optimal weight distribution for larger configurations.

[[Category:Frankl's union-closed sets conjecture]]

Find set configurations that imply FUNC

2016-10-27T20:46:57Z

Tomtom2357: /* Case 1: {} is in C: */

== Introduction ==

One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}</math>, contains at least as many sets as <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\}</math>. A slightly more clever argument shows that if a two element set {x, y} is in <math>\mathcal{A}</math>, then FUNC holds for <math>\mathcal{A}</math>:

Let <math>\mathcal{A}_{xy} = \{A \in \mathcal{A} : x, y \in A\}</math>, <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\ , y\notin A\}</math>, <math>\mathcal{A}_y = \{A \in \mathcal{A} : y \in A\ , x\notin A\}</math>, <math>\mathcal{A}_\emptyset = \{A \in \mathcal{A} : x, y\notin A\}</math>. Because {x, y} is in <math>\mathcal{A}</math>, the set <math>\mathcal{A}_{xy}</math> has at least as many sets as <math>\mathcal{A}_\emptyset</math>. Therefore, depending on which of <math>\mathcal{A}_x</math> and <math>\mathcal{A}_y</math> is larger, x or y are in at least half of the sets.

One might assume that a similar argument would work for three element sets, but unfortunately the argument fails. In fact, there is a family <math>\mathcal{A}</math> with only 9 elements in the ground set, and one set with three elements, such that none of those three elements is in at least half of the sets. However, one can show that if <math>\mathcal{A}</math> contains certain configurations of sets of size 3, then FUNC holds for <math>\mathcal{A}</math>. For example, in [http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r88/pdf this] article, it is shown that if <math>\mathcal{A}</math> contains 3 sets of size three that are subsets of the same set of size 5, then FUNC holds for <math>\mathcal{A}</math>. This article attempts to extend the results given in that paper.

== Lemma 1 ==
If <math>\mathcal{A}</math> contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}, then FUNC holds for <math>\mathcal{A}</math>.

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in <math>\mathcal{A}</math>. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for <math>\mathcal{A}</math>.

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

Case 1: {} is in C: The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, along with all their unions, which together make up all the sets of size 5. The total surplus of these sets is 12 (there are 6 sets of size 5, and each has surplus 2, and we’re ignoring the full set), therefore the total deficit must be at least 13. However, for every set of size 1 in C, there are two sets of size 4 in C, as follows:
1: {1, 2, 4, 6}, {1, 3, 5, 6}
2: {1, 2, 4, 5}, {2, 3, 5, 6}
3: {1, 3, 4, 5}. {2, 3, 4, 6}
4: {1, 2, 3, 4}, {3, 4, 5, 6}
5: {1, 2, 3, 5}, {2, 4, 5, 6}
6: {1, 2, 3, 6}, {1, 4, 5, 6}
Therefore, the total deficit of the size two sets must make up the 13. But then there must be at least 13 sets of size 2 in C (since they only have deficit 1), and together, these 13 sets generate all of the sets of size 4 (since each set of size 4 can be generated in 3 ways, you need to remove 3 sets before you can’t generate a set of size 4). Therefore, the total surplus is 27, which is the maximum that the total deficit can be.

Case 2: {} is not in C. In this case, since {} is not in C, we consider the set {1, 2, 3, 4, 5, 6} as counting towards the total surplus (as the empty set isn’t there to cancel it out). Now, each set of size 1 in C means that two of {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, and the union of those is a size 5 set, so each size one set cancels out with a size 5 set. Now, every set of size 2 in C forces a set of size 4 to be in C, except {1, 6}, {2, 5}, {3, 4}. We just need a bijection from the sets of size 2 (excluding the above) to the sets of size 4 (excluding {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}), such that if a set of size 2 is in C, then the associated set of size 4 is in C. One such bijection is:
{1, 2}->{1, 2, 4, 5},
{1, 3}->{1, 3, 5, 6},
{1, 4}->{1, 2, 4, 6},
{1, 5}->{1, 2, 3, 5},
{2, 3}->{2, 3, 4, 6},
{2, 4}->{1, 2, 3, 4},
{2, 6}->{2, 3, 5, 6},
{3, 5}->{1, 3, 4, 5},
{3, 6}->{1, 2, 3, 6},
{4, 5}->{3, 4, 5, 6},
{4, 6}->{1, 4, 5, 6},
{5, 6}->{2, 4, 5, 6}

So, the surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of {1, 6}, {2, 5}, {3, 4}, and every other set of size 2 has an associated set of size 4. Therefore, the surplus is at least the deficit.

== Lemma 2 ==

If <math>\mathcal{A}</math> contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 2, 4}, {3, 5, 6}, {4, 5, 6}, then FUNC holds for <math>\mathcal{A}</math>.

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in <math>\mathcal{A}</math>. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for <math>\mathcal{A}</math>.

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

===Case 1: {} is in C:===
The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 2, 4}, {3, 5, 6}, {4, 5, 6} are in C, along with their unions, which are {1, 2, 3, 4}, {3, 4, 5, 6}, {1, 2, 3, 5, 6}, and {1, 2, 4, 5, 6}. This generates a surplus of 6. We can map each set of size 1 except {3} and {4} to an implied sets of size 5, which cancels out their deficit.

1: {1, 3, 4, 5, 6}

2: {2, 3, 4, 5, 6}

5: {1, 2, 3, 4, 5}

6: {1, 2, 3, 4, 6}

We have another mapping from some size 2 sets to implied size 4 or 5 sets, cancelling out their deficit (each set on the left implies all of the sets on the right by itself).

{1, 3}: {1, 3, 5, 6}

{1, 4}: {1, 4, 5, 6}

{2, 3}: {2, 3, 5, 6}

{2, 4}: {2, 4, 5, 6}

{3, 5}: {1, 2, 3, 5}

{3, 6}: {1, 2, 3, 6}

{4, 5}: {1, 2, 4, 5}

{4, 6}: {1, 2, 4, 6}

==== Case 1.1: neither {3} nor {4} are in C====
Then all the sets not in the above pairing must be in C. But this generates the set {1, 2, 5, 6} which pushes the net surplus up to 7, which the deficit cannot surpass.

====Case 1.2: Only one of {3} and {4} are in C====
WLOG, assume this set is {3}. In this case, there must be at least 5 size 2 sets not in the above list in C. If {3, 4} is in C, then we can pair each of the remaining size 2 sets with it's union with {3, 4}, so {3, 4} cannot be in C. But sine 5 of the size 2 subsets of {1, 2, 5, 6} are in C, that means {1, 2, 5, 6} is in C as well. This raises the surplus by one, forcing all 6 size 2 subsets of {1, 2, 5, 6} to be in C. Therefore, the sets {1, 2, 3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 4, 5, 6}, {2, 4, 5, 6}, {1, 3, 5, 6}, {2, 3, 5, 6} are in C, raising the surplus to 15. This forces all the size 2 sets other than {3, 4} to be in C. But then, {1, 3, 4, 6} is in C, raising the surplus to 16, which the deficit cannot surpass.

====Case 1.3: Both {3} and {4} are in C====
Each of the sets disjoint from {3, 4} can be paired with it's union with {3, 4}, and the pairing above remains valid. Therefore, all size 2 sets other than {3, 4} do not contribute towards the net deficit, so the net deficit is at most 5, which is less than the net surplus (6).

Thus, in either case, <math>\mathcal{A}</math> is Frankl's.

===Case 2: {} is not in C===
In this case, the only set we know is in C is {1, 2, 3, 4, 5, 6}. Thus the surplus is at least 6. Given the pairing:

{1}: {1, 3, 4, 5, 6}
{2}: {2, 3, 4, 5, 6}
{3}: {1, 2, 3, 5, 6}
{4}: {1, 2, 4, 5, 6}
{5}: {1, 2, 3, 4, 5}
{6}: {1, 2, 3, 4, 6}

None of the size 1 sets contribute to the net deficit. We also have a pairing:
{1, 3}: {1, 3, 5, 6}
{1, 4}: {1, 4, 5, 6}
{2, 3}: {2, 3, 5, 6}
{2, 4}: {2, 4, 5, 6}
{3, 4}: {1, 2, 3, 4}
{3, 5}: {1, 2, 3, 5}
{3, 6}: {1, 2, 3, 6}
{4, 5}: {1, 2, 4, 5}
{4, 6}: {1, 2, 4, 6}

Thus only 6 size 2 sets contribute to the net deficit. Thus the deficit cannot surpass the surplus. Therefore, in either case, <math>\mathcal{A}</math> is Frankl's.

== Finding the implied abundance given a configuration ==

Even if a configuration does not directly imply Frankl's conjecture holds for <math>\mathcal{A}</math>, it can give some interesting results about the minimal abundance, and the weight function. Having one set of size 3, the only way to weight the set is to give equal weight to each element, and the lowest possible abundance on elements of that set is 4/9. If there are two sets of size 3 having an intersection of size 2 ({1, 2, 3}, {1, 2, 4}), then the lowest possible abundance of an element is 27/55, which is the best possible, and it is given by the weight function w(1)=w(2)=31, w(3)=w(4)=24. This was found by equating the abundance at the two extreme cases of this case: {1}, {2}, {3} in C (and same replacing 3 with 4), and {3}, {4} in C. Hopefully I will be able to find the optimal weight distribution for larger configurations.

[[Category:Frankl's union-closed sets conjecture]]

Find set configurations that imply FUNC

2016-10-27T20:46:12Z

2016-10-27T13:07:40Z

Tomtom2357: