A counterexample to the Hirsch Conjecture
A counterexample to the Hirsch Conjecture
复制标题
DOI：
10.4007/annals.2012.176.1.7
复制
发表时间：
2012-07-01
影响因子：
4.9
通讯作者：
Santos, Francisco
中科院分区：
文献类型：
--
作者：
Santos, Francisco
Hirsch猜想（1957年）指出，具有n个方面的D维多物的图不能大于n-d（组合）直径（组合）。也就是说，多层的任何两个顶点都可以通过最多的n -d边缘的路径连接。本文提出了猜想的第一个反例。我们的多层尺寸为43和86个方面。它是从5维多层的，有48个方面违反了Klee和Walkup的D-步骤猜想的一定概括。
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.