The polynomial Hirsch conjecture - Revision history

KristalCantwell: addition of contact

2011-08-14T20:31:43Z

addition of contact

@@ Line 173: / Line 173: @@
 of two elements and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these
 which is a total of five positions. But we have two sets of three elements at both ends of the sequence which correspond to a set of two elements and the element 5 which lie on a span of 7 elements and we have a contradiction and we are done.
 == f(d,n) ==

KristalCantwell: /* f(n) for small n */

2011-05-29T19:54:52Z

f(n) for small n

← Older revision		Revision as of 12:54, 29 May 2011
Line 173:		Line 173:
	of two elements and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these		of two elements and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these
	which is a total of five positions. But we have two sets of three elements at both ends of the sequence which correspond to a set of two elements and the element 5 which lie on a span of 7 elements and we have a contradiction and we are done.		which is a total of five positions. But we have two sets of three elements at both ends of the sequence which correspond to a set of two elements and the element 5 which lie on a span of 7 elements and we have a contradiction and we are done.

	For the next case assume that in the restriction to sets containing the the element 5 we don’t have a set with four elements and the element 5 and we don’t have a set containing the element 5 only and we have exactly two containing the element 5 and three other elements.

	We note two sets of three elements and the element 5 contains all but one combinations of two elements and the element 5. We also note that this combination consists of the two elements which are only in one of the sets of three elements and the element 5. Call these elements a and b.

	== f(d,n) ==		== f(d,n) ==

KristalCantwell: /* f(n) for small n */

2011-05-29T19:45:39Z

f(n) for small n

← Older revision		Revision as of 12:45, 29 May 2011
Line 155:		Line 155:

	- But this would imply that in the restriction we can assume wlog that F_3={\emptyset}. Put differently, F_3 contains the singleton {5}. Since F_3 is the first level using 5, this singleton could be deleted from F_3 without breaking convexity. This gets us back to the case where F_1\cupF_2\cup F_3 use only two elements, which we had discarded.		- But this would imply that in the restriction we can assume wlog that F_3={\emptyset}. Put differently, F_3 contains the singleton {5}. Since F_3 is the first level using 5, this singleton could be deleted from F_3 without breaking convexity. This gets us back to the case where F_1\cupF_2\cup F_3 use only two elements, which we had discarded.

			I have been looking at the various cases using the method outlined above. And it looks like all the cases work and f(5) is 11. Let me start going through the cases. It may take a while to work through all of them.

			Suppose we have a counterexample that under restriction to sets containing the element 5 contains a set of length 7
			which does not contain the set containing only the element 5 but contains a set which under restriction contains all 4 elements then we know that the original set must contain a set which contains all the elements and hence has length 10. So
			we can eliminate this case.

			For the next case assume that in the restriction to sets containing the the element 5 we don’t have a set with four elements and the element 5 and we don’t
			have a set containing the element 5 only and we have three sets containing the element 5 and three other elements. We note 3 or more sets of three elements and the element 5 contains all combinations of two elements and the element 5.

			Now the first family and the second family must contain a set containing at least a pair of elements. If not there are only single elements in the first two elements. Then one element will only appear in one single set which cause the entire case to have at most 9 families and we are done. And the last and the second to last family must also contain a set containing a pair of elements by similar reasoning.

			And since all pairs are contained in the three sets containing three or more elements and the element 5 the pairs mentioned at the second and first families and those at the other end must be in the sets of three and the element 5. And this means that the third and third to last families must contain sets containing three or more elements. Now if either of these families doesn’t contain the element 5 then they will contain a common element and then we continue this proof with that element replacing the element 5. If it is a previous case we use the previous proof and if it one the cases to come we will deal with it then.

			Next we note that the three sets of three elements and the element 5 must lie within three consecutive positions or else the extremal sets of three elements must contain a common pair which must appear four times which is not possible.
			Now all the sets of two elements and the element 5 which are contained in the sets of three elements and the element 5 which as we have noted are all the sets
			of two elements and the element 5 must appear in the positions containing the the three element sets and the element 5 or the two other positions adjacent to these
			which is a total of five positions. But we have two sets of three elements at both ends of the sequence which correspond to a set of two elements and the element 5 which lie on a span of 7 elements and we have a contradiction and we are done.

			For the next case assume that in the restriction to sets containing the the element 5 we don’t have a set with four elements and the element 5 and we don’t have a set containing the element 5 only and we have exactly two containing the element 5 and three other elements.

			We note two sets of three elements and the element 5 contains all but one combinations of two elements and the element 5. We also note that this combination consists of the two elements which are only in one of the sets of three elements and the element 5. Call these elements a and b.

	== f(d,n) ==		== f(d,n) ==

KristalCantwell: /* f(n) for small n */

2010-12-06T20:58:43Z

f(n) for small n

@@ Line 144: / Line 144: @@
 '''Towards the value of <math>f(5)</math>
-f(5) is less than or equal to f(4) + f(2) +  f(2) -1 = 8+4+4-1=15. Also, it is at least 11: [{}, {1}, {15}, {14, 5},
+The following example shows that f(5) is at least 11: [{}, {1}, {15}, {14, 5}, {12, 35, 4}, {13, 25, 45}, {245, 3}, {24, 34}, {234}, {23}, {2}]
-Lemma: Suppose that a convex sequence of families of sets on [n] has an F_i
+I can now show that f(5) is at most 12. Since we have the above example of length 11, f(5) must be 11 or 12. In fact, as a byproduct of my proof I have also found a second example of length 11: [{}, {1}, {12}, {125}, {15, 25}, {135, 245}, {145, 235}, {35, 45}, {345}, {34}, {4}].
-Proof: Suppose wlog that j < i. Convexity implies that F_{j+1} has a set S'
+Suppose we have a sequence of length 13 on 5 elements. Wlog the first or last level consists only of the empty set, so we have a sequence of length 12 with no empty sets. Then:
 == f(d,n) ==

Klas Pettersson: /* Threads */ Fixed the link to poly3 (4)

2010-11-11T23:26:57Z

Threads: Fixed the link to poly3 (4)

← Older revision		Revision as of 16:26, 11 November 2010
Line 28:		Line 28:
	* [http://gilkalai.wordpress.com/2010/10/03/polymath-3-the-polynomial-hirsch-conjecture-2 The Polynomial Hirsch Conjecture 2] (Oct 3, 2010) Inactive		* [http://gilkalai.wordpress.com/2010/10/03/polymath-3-the-polynomial-hirsch-conjecture-2 The Polynomial Hirsch Conjecture 2] (Oct 3, 2010) Inactive
	* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-3/ Polymath3 : Polynomial Hirsch Conjecture 3] (Oct 10, 2010) '''Active'''		* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-3/ Polymath3 : Polynomial Hirsch Conjecture 3] (Oct 10, 2010) '''Active'''
	* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-4/ Polymath3 : Polynomial Hirsch Conjecture 4] (Oct 21, 2010) '''Active'''		* [http://gilkalai.wordpress.com/2010/10/21/polymath3-polynomial-hirsch-conjecture-4/ Polymath3 : Polynomial Hirsch Conjecture 4] (Oct 21, 2010) '''Active'''

	Here is a list of [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture]		Here is a list of [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture]

Pacosantos at 21:31, 26 October 2010

2010-10-26T21:31:33Z

← Older revision		Revision as of 14:31, 26 October 2010
Line 115:		Line 115:
	It is worth noting that in these two examples every F_i is a singleton. As mentioned above, in the singleton case the maximum length is in fact 2n.		It is worth noting that in these two examples every F_i is a singleton. As mentioned above, in the singleton case the maximum length is in fact 2n.

	: '''Theorem''' For math>n \leq 4</math>, <math>f(n) =2n</math>.		: '''Theorem''' For <math>n \leq 4</math>, <math>f(n) =2n</math>.

Pacosantos: cleaned the bits about f(5)

2010-10-26T21:23:35Z

cleaned the bits about f(5)

← Older revision		Revision as of 14:23, 26 October 2010
Line 115:		Line 115:
	It is worth noting that in these two examples every F_i is a singleton. As mentioned above, in the singleton case the maximum length is in fact 2n.		It is worth noting that in these two examples every F_i is a singleton. As mentioned above, in the singleton case the maximum length is in fact 2n.

	For ~~small~~ n>~~=1 (at least up to f(4)) the formula~~ f(n)=2n ~~holds~~. For f(1) and f(2) this is given by the "trivial" upper and lower bounds above. For f(3) and f(4) we first state the following two general properties:		: '''Theorem''' For math>n \leq 4</math>, <math>f(n) =2n</math>.


			'''Proof''' For f(1) and f(2) this is given by the "trivial" upper and lower bounds above. For f(3) and f(4) we first state the following two general properties:

	* If a sequence of families obeying (*) contains <math>12\ldots n</math>, then it contains an ascending chain to the left of this set and a descending chain to the right, and thus has length at most 2n (the maximal possible length in this case is the one achieved by example (2))		* If a sequence of families obeying (*) contains <math>12\ldots n</math>, then it contains an ascending chain to the left of this set and a descending chain to the right, and thus has length at most 2n (the maximal possible length in this case is the one achieved by example (2))
Line 137:		Line 140:

	Last, consider the case when all I(ab) are empty. Then we have at most 4 points covered by the I(a), and at most 5 by I(\emptyset), and we are (finally) done.		Last, consider the case when all I(ab) are empty. Then we have at most 4 points covered by the I(a), and at most 5 by I(\emptyset), and we are (finally) done.
			QED

	~~I think we have~~ the ~~values~~ of ~~f(1),f(2),f(3) and f(4). Now I am looking at~~ f(5)		'''Towards the value of <math>f(5)</math>
	~~we have it is greater than or equal to 10 and less than or equal to f(4) + f(2) +~~
	~~f(2) -1 = 8+4+4-1=15.~~

	~~The following example shows that~~ f(5) is at least 11: [{}, {1}, {15}, {14, 5},		f(5) is less than or equal to f(4) + f(2) + f(2) -1 = 8+4+4-1=15. Also, it is at least 11: [{}, {1}, {15}, {14, 5},
	{12, 35, 4}, {13, 25, 45}, {245, 3}, {24, 34}, {234}, {23}, {2}]		{12, 35, 4}, {13, 25, 45}, {245, 3}, {24, 34}, {234}, {23}, {2}]
	So f(5) is between 11 and 15.		So f(5) is between 11 and 15.
Line 169:		Line 171:


	I think I can ~~show~~ the following: if an (n-1)-tuple arises in a convex sequence of subsets of [n], then the sequence must have length at most 2n. (I mean this for every n, not only n=5). ~~I have to leave now but will post the argument this afternoon. This means that to find f(5) we should concentrate on sequences using sets of at most three elements.~~		I think the Corollary can be improved to the following: if an (n-1)-tuple arises in a convex sequence of subsets of [n], then the sequence must have length at most 2n. (I mean this for every n, not only n=5). From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.

	From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.

	The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it		The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it

Pacosantos: added thread 4

2010-10-26T21:12:39Z

added thread 4

← Older revision		Revision as of 14:12, 26 October 2010
Line 28:		Line 28:
	* [http://gilkalai.wordpress.com/2010/10/03/polymath-3-the-polynomial-hirsch-conjecture-2 The Polynomial Hirsch Conjecture 2] (Oct 3, 2010) Inactive		* [http://gilkalai.wordpress.com/2010/10/03/polymath-3-the-polynomial-hirsch-conjecture-2 The Polynomial Hirsch Conjecture 2] (Oct 3, 2010) Inactive
	* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-3/ Polymath3 : Polynomial Hirsch Conjecture 3] (Oct 10, 2010) '''Active'''		* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-3/ Polymath3 : Polynomial Hirsch Conjecture 3] (Oct 10, 2010) '''Active'''
			* [http://gilkalai.wordpress.com/2010/10/10/polymath3-polynomial-hirsch-conjecture-4/ Polymath3 : Polynomial Hirsch Conjecture 4] (Oct 21, 2010) '''Active'''

	Here is a list of [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture]		Here is a list of [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture]

KristalCantwell: Minor change

2010-10-22T20:09:32Z

Minor change

← Older revision		Revision as of 13:09, 22 October 2010
Line 172:		Line 172:

	From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.		From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.

	0
	*
	**
	**5
	***5
	~~***~~
	~~****~~
	~~***~~
	**
	**5
	*5
	*

	The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it		The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it

KristalCantwell: addition of material

2010-10-22T20:07:50Z

addition of material

← Older revision		Revision as of 13:07, 22 October 2010
Line 137:		Line 137:

	Last, consider the case when all I(ab) are empty. Then we have at most 4 points covered by the I(a), and at most 5 by I(\emptyset), and we are (finally) done.		Last, consider the case when all I(ab) are empty. Then we have at most 4 points covered by the I(a), and at most 5 by I(\emptyset), and we are (finally) done.

			I think we have the values of f(1),f(2),f(3) and f(4). Now I am looking at f(5)
			we have it is greater than or equal to 10 and less than or equal to f(4) + f(2) +
			f(2) -1 = 8+4+4-1=15.

			The following example shows that f(5) is at least 11: [{}, {1}, {15}, {14, 5},
			{12, 35, 4}, {13, 25, 45}, {245, 3}, {24, 34}, {234}, {23}, {2}]
			So f(5) is between 11 and 15.

			Lemma: Suppose that a convex sequence of families of sets on [n] has an F_i
			containing [n-1] as one of its sets. Then, for every S\in F_j in the sequence we
			have \|i-j\| \le n-\|S\|+1.

			Proof: Suppose wlog that j < i. Convexity implies that F_{j+1} has a set S'
			containing S\cap [n-1]= S\setminus n. Such an S' can only be obtained by either
			removing n from S or adding one (or more) elements of [n-1] to S, or both.
			Repeating this we get a sequence of sets each contained in one of the families
			F_j, F_{j+1}, …, F_i which is increasing except at some point a decreasing step
			(removing n) is allowed. But convexity also implies that the “removing'' step can
			be taken only once in this sequence.
			QED

			Corollary: The length of such a sequence is at most 2n+2.

			Proof: By the Lemma, for every F_j containing a non-empty set we have \|i-j\|\le n.
			Thus, all those F_j‘s are within an interval of length 2n+1 centered at i.
			Counting for the empty set gives 2n+2.
			QED

			So for the cases 13 to 15 for f(5) we need only look at triples since they are greater then 2n+2 for n=5.


			I think I can show the following: if an (n-1)-tuple arises in a convex sequence of subsets of [n], then the sequence must have length at most 2n. (I mean this for every n, not only n=5). I have to leave now but will post the argument this afternoon. This means that to find f(5) we should concentrate on sequences using sets of at most three elements.

			From the proof of the lemma we see that the only way we can get length greater than 2n is if on both sides of F_i we get subsequences that include the step “delete n”. The typical shape of the sequence we get is something like the following (the example is for n=5, the stars represent elements of [4] and are supposed to form a unimodal sequence: increasing from the emptyset to [4] then decreasing back to a singleton.

			0
			*
			**
			**5
			***5
			***
			****
			***
			**
			**5
			*5
			*

			The goal is to show that such a shape implies not convexity with respect to n (5 in this case). This looks obvious in the sequence above but it is not, The initial sequence of families may contain other sets (using 5) in each F_i and those sets could in principle restore convexity. I am pretty convinced this cannot happen but I do not have a clean argument for it