Thed-step conjecture for polyhedra of dimensiond<6 |
| |
Authors: | Victor Klee David W Walkup |
| |
Institution: | (1) University of Washington and Boeing Scientific Research Laboratories, Seattle, Wash., USA |
| |
Abstract: | 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.
This revised version was published online in November 2006 with corrections to the Cover Date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|