Francisco Santos disproves Hirsch conjecture

The Hirsch conjecture has been around for over 50 years. The conjecture states that a d-dimensional polytope with n facets has diameter at most n-d. (The facets of a polytope are the maximal dimensional faces (i.e. the (d-1)-dimensional faces), and saying that the diameter is at most n-d is just saying that every pair of vertices can be connected by a path of length at most n-d.)

The upper bounds on diameter are very far away from n-d; in fact no bound that is even polynomial (much less linear) in n and d is known. It was considered substantial progress when Gil Kalai got the first subexponential upper bounds. This fact led many to speculate that the conjecture is false, and apparently Victor Klee encouraged many people to try disproving it over the years.

Francisco Santos has just announced an explicit counterexample to the Hirsch conjecture, in dimension d = 43 with n =86 facets. Details to be described at the Grünbaum–Klee meeting in Seattle this summer.

To researchers on polytopes, this result may not be too surprising. Nevertheless, it is an old problem and it is nice to see it finally resolved. And there is something pleasing about finding explicit counterexamples in higher dimensional spaces. It offers a concrete way to see how bad our intuition for higher dimensions really is. Kahn and Kalai’s spectacular counterexample to “Borsuk’s conjecture” (in dimension d = 1325) comes to mind. I look forward to seeing the details of Santos’s construction.