The polynomial Hirsch conjecture: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
New page: : '''The Hirsch conjecture''': The graph of a d-polytope with n facets has diameter at most n-d. A weaker conjecture which is also open is: : '''Polynomial Diameter Conjecture''': Let G... |
|||
| Line 11: | Line 11: | ||
* [http://gilkalai.wordpress.com/2009/07/17/the-polynomial-hirsch-conjecture-a-proposal-for-polymath3 The polynomial Hirsch conjecture, a proposal for Polymath 3] (July 17) | * [http://gilkalai.wordpress.com/2009/07/17/the-polynomial-hirsch-conjecture-a-proposal-for-polymath3 The polynomial Hirsch conjecture, a proposal for Polymath 3] (July 17) | ||
* [http://gilkalai.wordpress.com/2009/07/28/polymath3-abstract-polynomial-hirsch-conjecture-aphc/ The polynomial Hirsch conjecture, a proposal for Polymath 3 cont.] (July 28) | * [http://gilkalai.wordpress.com/2009/07/28/polymath3-abstract-polynomial-hirsch-conjecture-aphc/ The polynomial Hirsch conjecture, a proposal for Polymath 3 cont.] (July 28) | ||
* [http://gilkalai.wordpress.com/2009/07/30/the-polynomial-hirsch-conjecture-how-to-improve-the-upper-bounds/ | * [http://gilkalai.wordpress.com/2009/07/30/the-polynomial-hirsch-conjecture-how-to-improve-the-upper-bounds/ The polynomial Hirsch conjecture - how to improve the upper bounds] (July 30) | ||
* [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture] | * [http://en.wordpress.com/tag/hirsch-conjecture/ Wordpress posts on the Hirsch conjecture] | ||
Revision as of 04:47, 3 August 2009
- The Hirsch conjecture: The graph of a d-polytope with n facets has diameter at most n-d.
A weaker conjecture which is also open is:
- Polynomial Diameter Conjecture: Let G be the graph of a d-polytope with n facets. Then the diameter of G is bounded above by a polynomial of d and n.
