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

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.

• 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...? Feb 7 '12 at 21:51

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