The polynomial Hirsch conjecture: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
No edit summary |
|||
| Line 1: | Line 1: | ||
: '''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. | : '''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. | ||
| Line 21: | Line 19: | ||
== The disproof of the Hirsch conjecture == | == The disproof of the Hirsch conjecture == | ||
: '''The Hirsch conjecture''': The graph of a d-polytope with n facets has diameter at most n-d. | |||
This conjecture was [http://arxiv.org/abs/1006.2814 recently disproven] by Francisco Santos. | |||
* [http://personales.unican.es/santosf/Hirsch/ Santos's page on the Hirsch conjecture] | |||
* [http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/ Francisco Santos Disproves the Hirsch Conjecture] (May 10, 2010) | * [http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/ Francisco Santos Disproves the Hirsch Conjecture] (May 10, 2010) | ||
* [http://gilkalai.wordpress.com/2010/06/15/a-counterexample-to-the-hirsch-conjecture-is-now-out/ “A Counterexample to the Hirsch Conjecture,” is Now Out] (Jun 15, 2010) | * [http://gilkalai.wordpress.com/2010/06/15/a-counterexample-to-the-hirsch-conjecture-is-now-out/ “A Counterexample to the Hirsch Conjecture,” is Now Out] (Jun 15, 2010) | ||
Revision as of 20:55, 29 September 2010
- 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.
Threads
- The polynomial Hirsch conjecture, a proposal for Polymath 3 (July 17, 2009)
- The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. (July 28, 2009)
- The polynomial Hirsch conjecture - how to improve the upper bounds (July 30, 2009)
- The Polynomial Hirsch Conjecture: Discussion Thread (Aug 9, 2009)
- The Polynomial Hirsch Conjecture: Discussion Thread, Continued (Oct 6, 2009)
- Plans for polymath3 (Dec 8, 2009)
- The Polynomial Hirsch Conjecture: The Crux of the Matter. (Jun 19, 2010)
- Polynomial Hirsch Conjecture (Sep 29, 2010)
The disproof of the Hirsch conjecture
- The Hirsch conjecture: The graph of a d-polytope with n facets has diameter at most n-d.
This conjecture was recently disproven by Francisco Santos.
