Does the Hirsch conjecture hold for \$n < 2d\$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T19:22:04Z http://mathoverflow.net/feeds/question/87837 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87837/does-the-hirsch-conjecture-hold-for-n-2d Does the Hirsch conjecture hold for \$n < 2d\$? Matthew Kahle 2012-02-07T20:03:03Z 2012-04-03T09:32:31Z <p>The <a href="http://en.wikipedia.org/wiki/Hirsch_conjecture" rel="nofollow">Hirsch conjecture</a> asserts that the graph (i.e. \$1\$-skeleton) of a \$d\$-dimensional <a href="http://en.wikipedia.org/wiki/Polytope" rel="nofollow">convex polytope</a> with \$n\$ facets has <a href="http://en.wikipedia.org/wiki/Distance_%28graph_theory%29" rel="nofollow">diameter</a> at most \$n - d\$.</p> <p>After being open for decades, <a href="http://annals.math.princeton.edu/articles/3941" rel="nofollow">Francisco Santos has recently proved</a> that this fails in general.</p> <blockquote> <p>Is it possible that the conjecture holds for \$n &lt; 2d\$? Santos's counterexample had \$(n,d) = (86, 43)\$.</p> </blockquote> <p>One observation which may be relevant: If \$n &lt; 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 <em>Lectures on Polytopes</em>, p. 84). But this doesn't seem to answer the question here.</p> http://mathoverflow.net/questions/87837/does-the-hirsch-conjecture-hold-for-n-2d/92980#92980 Answer by Francisco Santos for Does the Hirsch conjecture hold for \$n < 2d\$? Francisco Santos 2012-04-03T09:32:31Z 2012-04-03T09:32:31Z <p>The answer is no, as follows from the following Lemma of Klee and Walkup:</p> <p>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).</p> <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&lt;2d.</p> <p>I take the occasion to announce an update. My recent paper <a href="http://arxiv.org/abs/1202.4701" rel="nofollow">http://arxiv.org/abs/1202.4701</a> (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.</p>