科研之友
微信
新浪微博
Facebook
分享链接
摘要
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. %26lt;br%26gt;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.
- 出版日期2012-7
