1967/01/01 by Victor Klee, David W. Walkup · 168 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems #Polyhedron #Mathematics #Combinatorics #Conjecture #Dimension (graph theory) #Bounded function #Regular polygon #Integer (computer science) #Discrete mathematics #Geometry #Mathematical analysis
paper · pdf · doi:10.1007/bf02395040
published in Acta Mathematica 117(0), 53-78 (Mittag-Leffler Institute)
openalex publication_date 1967/01/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/22
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.