Does the Hirsch conjecture hold for $n < 2d$?

2012-02-07T20:03:03Z

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.

After being open for decades, Francisco Santos has recently proved that this fails in general.

Is it possible that the conjecture holds for $n < 2d$? Santos's counterexample had $(n,d) = (86, 43)$.

One observation which may be relevant: If $n < 2d$, then every pair of vertices has a common facet. One can use this to show that the general Hirsch conjecture reduces to the $n \ge 2d$ case, (see Ziegler's book Lectures on Polytopes, p. 84). But this doesn't seem to answer the question here.

Answer by Francisco Santos for Does the Hirsch conjecture hold for $n < 2d$?

2012-04-03T09:32:31Z

The answer is no, as follows from the following Lemma of Klee and Walkup:

Lemma: If P is a d-polytope with n facets and we perform a "wedge" over any facet F we get a (d+1)-polytope P' with n+1 facets and with diameter(P') $\ge$ diameter(P).

Corollary: since there is a 43-polytope with 86 facets and diameter (at least) 44, for every positive integer k there is a (43+k)-polytope with 86+k facets and diameter at least 44. These polytopes have n<2d.

I take the occasion to announce an update. My recent paper http://arxiv.org/abs/1202.4701 (joint with Matschke and Weibel) contains smaller counter-examples to the Hirsch conjecture. The current record is a polytope with dimension 20, 40 facets, and diameter 21.

Does the Hirsch conjecture hold for $n < 2d$? - MathOverflow

Does the Hirsch conjecture hold for $n < 2d$?

Answer by Francisco Santos for Does the Hirsch conjecture hold for $n < 2d$?