A counterexample to the Hirsch Conjecture

• 成果类型: Article
• 署名作者: Santos, Francisco
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2012.176.1.7
• 发表日期: 2012
• 页码: 383-412
• 关键词: d-step conjecture; polytopes; diameter; dimension; algorithm; polyhedra; bounds; paths

摘要

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, 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 that violates a certain generalization of the d-step conjecture of Klee and Walkup.