Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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...? –  Joseph O'Rourke Feb 7 '12 at 21:51
add comment

1 Answer 1

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.

share|improve this answer
5  
Welcome to Mathoverflow! –  David Speyer Apr 3 '12 at 11:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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