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.

Links

• The polynomial Hirsch conjecture, a proposal for Polymath 3 (July 17)
• The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. (July 28)
• The polynomial Hirsch conjecture - how to improve the upper bounds (July 30)
• Wordpress posts on the Hirsch conjecture