The polynomial Hirsch conjecture

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.

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)

• Wordpress posts on the Hirsch conjecture

The disproof of the Hirsch conjecture

• Francisco Santos Disproves the Hirsch Conjecture (May 10, 2010)
• “A Counterexample to the Hirsch Conjecture,” is Now Out (Jun 15, 2010)