Monday, May 10, 2010

Hirsch Conjecture disproved

Via polybot, Gil Kalai posts that Francisco Santos has disproved the Hirsch Conjecture. This is big news.

The conjecture:
the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d.
The result:
I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the d-step theorem of Klee and Walkup.

The proof will be presented at the 100 Years in Seattle (The mathematics of Klee and Grunbaum) conference in end-July, this year. 
Post a Comment

Disqus for The Geomblog