Thed-step conjecture for polyhedra of dimensiond<6
Thed-step conjecture for polyhedra of dimensiond<6
复制标题
维数<6的多面体的Thed步猜想
DOI：
10.1007/bf02395040
复制
发表时间：
1967
期刊：
影响因子：
3.7
通讯作者：
D. Walkup
中科院分区：
文献类型：
--
作者：
V. Klee;D. Walkup
定义和研究了组合几何和线性规划理论中有兴趣的两个函数Δ和Δb。Δ（d, n）为尺寸为d - 1的面内尺寸为d的凸多面体的最大直径；同样，Δb（d,n）是维度为d - 1的面内维度为d的有界多面体的最大直径。多面体p的直径是最小的整数，使得p的任意两个顶点可以通过p的1条或更少的边的路径连接起来。证明了有界步猜想Δb(d,2d)=d在≤5时为真。还证明了在线性规划中具有重要意义的泛步猜想Δ(d, 2d)≤d在≥4时是假的。给出了Δ和Δb的许多其他特定值和边界。
Two functions Δ and Δb, of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δb(d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δb(d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δb are presented.