MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

The$d$-step conjecture for polyhedra of dimension$d$<6

Victor Klee University of Washington and Boeing Scientific Research Laboratories, Seattle, Wash., USA David W. Walkup University of Washington and Boeing Scientific Research Laboratories, Seattle, Wash., USA

TBD mathscidoc:1701.331312

Acta Mathematica, 117, (1), 53-78, 1966.4
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 dimension$d$with$n$faces of dimension$d$−1; similarly, Δ_{$b$}($d,n$) is the maximum diameter of bounded polyhedra of dimension$d$with$n$faces of dimension$d$−1. The diameter of a polyhedron$P$is the smallest integer$l$such that any two vertices of$P$can be joined by a path of$l$or fewer edges of$P$. It is shown that the bounded$d$-step conjecture, i.e. Δ_{$b$}$(d,2d)=d$, is true for$d$≤5. It is also shown that the general$d$-step conjecture, i.e. Δ($d, 2d$)≤$d$, of significance in linear programming, is false for$d$≥4. A number of other specific values and bounds for Δ and Δ_{$b$}are presented.
No keywords uploaded!
[ Download ] [ 2017-01-08 20:32:09 uploaded by actaadmin ] [ 951 downloads ] [ 0 comments ] 
@inproceedings{victor1966the$d$-step,
  title={The$d$-step conjecture for polyhedra of dimension$d$<6},
  author={Victor Klee, and David W. Walkup},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203209983887021},
  booktitle={Acta Mathematica},
  volume={117},
  number={1},
  pages={53-78},
  year={1966},
}
Victor Klee, and David W. Walkup. The$d$-step conjecture for polyhedra of dimension$d$<6. 1966. Vol. 117. In Acta Mathematica. pp.53-78. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203209983887021.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved