2010/06/14 by Francisco Santos · 1 voice · 3 citations
Computer Science · Mathematics · #cs.DM #math.CO #math.OC #msc:52B05 #msc:52B55 #msc:90C05
paper · pdf · doi:10.4007/annals.2012.176.1.7
published as Annals of Math. (2), 176 (July 2012), 383-412 · 28 pages, 10 Figures: Changes from v2: Minor edits suggested by referees. This version has been accepted in the Annals of Mathematics
arxiv published 2010/06/14 · arxiv created 2011/11/08 · arxiv updated 2013/04/30
The Hirsch Conjecture (1957) stated that the graph of a d-dimensional polytope with n facets cannot have (combinatorial) diameter greater than n-d. That is, that any two vertices of the polytope can be connected by a path of at most n-d edges. This paper presents the first counterexample to the conjecture. Our polytope has dimension 43 and 86 facets. It is obtained from a 5-dimensional polytope with 48 facets which violates a certain generalization of the d-step conjecture of Klee and Walkup.