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.

  • $\begingroup$ A partly-baked idea: The common facet shared by a pair of vertices is a $(d-1, 2d-2)$ polytope, which might serve as a basis for induction...? $\endgroup$ Feb 7 '12 at 21:51

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.

  • 5
    $\begingroup$ Welcome to Mathoverflow! $\endgroup$ Apr 3 '12 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.