# MathSciDoc: An Archive for Mathematician ∫

#### TBDmathscidoc: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.
```@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.