# Accession Number:

## AD0628199

# Title:

## THE D-STEP CONJECTURE FOR POLYHEDRA OF DIMENSION D<6,

# Descriptive Note:

# Corporate Author:

## BOEING SCIENTIFIC RESEARCH LABS SEATTLE WASH MATHEMATICS RESEARCH LAB

# Personal Author(s):

# Report Date:

## 1965-12-01

# Pagination or Media Count:

## 47.0

# Abstract:

Two functions A and B, of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Ad,n is the maximum diameter of convex polyhedra of dimension d with n faces of dimension d-1 similarly, Bd,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 k such that any two vertices of P can be joined by a path of k or fewer edges of P. It is shown that the bounded d-step conjecture, i.e. Bd,2d d, is true for d or 5. It is also shown that the general d-step conjecture, i.e. Ad,2d or d, of significance in linear programming, is false for d equal to or greater than 4. A number of other specific values and bounds for A and B are presented.

# Descriptors:

# Subject Categories:

- Operations Research