Paths on polyhedra. II

Abstract

Continuing the author's earlier investigation, this paper studies the behavior of paths on (convex) polyhedra relative to the facets of the polyhedra. In Section 1, the poly-topes which are polar to the cyclic poly topes are shown to admit Hamiltonian circuits, and the fact that they do leads to sharp upper bounds for the lengths of simple paths or simple circuits on polyhedra of a given dimension having a given number of facets. Section 2 is devoted to the conjecture, due jointly to Philip Wolfe and the author, that any two vertices of a polytope can be joined by a path which never returns to a facet from which it has earlier departed. This implies a well-known conjecture of Warren Hirsch, asserting that n—d is an upper bound for the diameter of ^-dimensional polytopes having n facets. The Wolfe-Klee conjecture is proved here for 3-dimensional polyhedra, and a stronger conjecture (dealing with polyhedral cell-complexes) is established for certain special cases. Our notation and terminology are as in [10, 11, 12, 13].1 In particular, a polyhedron is a set which is the intersection of finitely many closed half spaces in a finite-dimensional real linear space, and a d-polyhedron is one which is ^-dimensional. The faces of a polyhedron P are the empty set, P itself, and the intersections of P with the various supporting hyperplanes of P. Two faces are incident provided one contains the other. The O-faces and 1-faces of P are its vertices and edges, and when P is a ώ-polyhedron its (d — l)-faces and (d — 2)-faces are called facets and sub facets respectively. A proper polyhedron is one which contains no line, or, equivalently (assuming it is not empty), one which has at least one vertex. A polytope is a bounded poly-hedron; equivalently, it is a set which is the convex hull of a finite set of points. Two vertices of a polyhedron P are adjacent provided they are joined by an edge of P. A path on P is a finite sequence (xQ, xu, Xι) of consecutively adjacent vertices, and the integer I is the length of the path. The diameter of a polyhedron is the smallest number I such that any two vertices of the polyhedron can be joined by a path of length ^l.2