Find set configurations that imply FUNC - Revision history

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

2017-12-19T03:57:52Z

Case 2: {} is not in C

← Older revision		Revision as of 20:57, 18 December 2017
Line 103:		Line 103:

	None of the size 1 sets contribute to the net deficit. We also have a pairing:		None of the size 1 sets contribute to the net deficit. We also have a pairing:

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

Tomtom2357: Added a corollary

2016-10-27T21:02:04Z

Added a corollary

← Older revision		Revision as of 14:02, 27 October 2016
Line 122:		Line 122:

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

			==Corollary==
			These together imply that if there are 4 sets of size 3 contained in the same size 6 set, then <math>\mathcal{A}</math> is Frankl's. Lemma 1 covers the case where none of the sets have a size 2 intersection, and lemma 2 takes care of the case when there are size 2 intersections.

	== Finding the implied abundance given a configuration ==		== Finding the implied abundance given a configuration ==

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

2016-10-27T20:47:32Z

Case 2: {} is not in C

← Older revision		Revision as of 13:47, 27 October 2016
Line 91:		Line 91:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2016-10-27T20:46:57Z

Case 1: {} is in C:

← Older revision		Revision as of 13:46, 27 October 2016
Line 51:		Line 51:

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

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

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

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

Line 58:		Line 61:

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

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

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

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

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

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

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

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

Tomtom2357: Added another lemma

2016-10-27T20:46:12Z

Added another lemma

← Older revision		Revision as of 13:46, 27 October 2016
Line 39:		Line 39:
	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.		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 ==		== Finding the implied abundance given a configuration ==

Tomtom2357: /* Finding the implied abundance given a configuration */

2016-10-27T19:55:20Z

Finding the implied abundance given a configuration

← Older revision		Revision as of 12:55, 27 October 2016
Line 42:		Line 42:
	== Finding the implied abundance given a configuration ==		== 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 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.		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]]		[[Category:Frankl's union-closed sets conjecture]]

TobiasFritz at 09:51, 11 March 2016

2016-03-11T09:51:20Z

← Older revision		Revision as of 02:51, 11 March 2016
Line 1:		Line 1:
	~~Click [http://michaelnielsen.org/polymath1/index.php?title=Frankl's_union-closed_conjecture here] to go back to the main page~~

	== Introduction ==		== Introduction ==

Line 45:		Line 43:

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

Tomtom2357 at 15:33, 16 February 2016

2016-02-16T15:33:23Z

← Older revision		Revision as of 08:33, 16 February 2016
Line 40:		Line 40:

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


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

Tomtom2357: /* Lemma 1 */

2016-02-10T03:17:34Z

Lemma 1

← Older revision		Revision as of 20:17, 9 February 2016
Line 25:		Line 25:
	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.		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. ~~Such a~~ bijection is ~~given below~~:		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, 2}->{1, 2, 4, 5},
	{1, 3}->{1, 3, 5, 6},		{1, 3}->{1, 3, 5, 6},

Tomtom2357: /* Lemma 1 */

2016-02-10T03:17:02Z

Lemma 1

← Older revision		Revision as of 20:17, 9 February 2016
Line 26:		Line 26:

	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. Such a bijection is given below:		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. Such a bijection is given below:
	{1, 2}->{1, 2, 4, 5}		{1, 2}->{1, 2, 4, 5},
	{1, 3}->{1, 3, 5, 6}		{1, 3}->{1, 3, 5, 6},
	{1, 4}->{1, 2, 4, 6}		{1, 4}->{1, 2, 4, 6},
	{1, 5}->{1, 2, 3, 5}		{1, 5}->{1, 2, 3, 5},
	{2, 3}->{2, 3, 4, 6}		{2, 3}->{2, 3, 4, 6},
	{2, 4}->{1, 2, 3, 4}		{2, 4}->{1, 2, 3, 4},
	{2, 6}->{2, 3, 5, 6}		{2, 6}->{2, 3, 5, 6},
	{3, 5}->{1, 3, 4, 5}		{3, 5}->{1, 3, 4, 5},
	{3, 6}->{1, 2, 3, 6}		{3, 6}->{1, 2, 3, 6},
	{4, 5}->{3, 4, 5, 6}		{4, 5}->{3, 4, 5, 6},
	{4, 6}->{1, 4, 5, 6}		{4, 6}->{1, 4, 5, 6},
	{5, 6}->{2, 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.		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.