Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

It was known for a long time that it sufficed to prove it for $n \ge 2d$ --- indeed, if $n < 2d$ then every pair of vertices shares a common facet, and iterating if necessary, one eventually ends up with a case where $N = 2D$. (See Ziegler's book Lectures on Polytopes, p. 84).

Now it is known that the Hirsch conjecture fails in general, but does it hold for $n < 2d$? So far I haven't been able to think of a simple proof, and actually I don't even know if it's true. The counterexample due to Santos has $d=43$ and $n=86$.

share|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.