The [Hirsch conjecture](http://en.wikipedia.org/wiki/Hirsch_conjecture) asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional [convex polytope](http://en.wikipedia.org/wiki/Polytope) with $n$ facets has [diameter](http://en.wikipedia.org/wiki/Distance_%28graph_theory%29) at most $n - d$.


After being open for decades, [Francisco Santos has recently proved](http://annals.math.princeton.edu/articles/3941) 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.



Does the Hirsch conjecture hold for $n < 2d$?
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.


