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$.


Your Answer

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

Browse other questions tagged or ask your own question.