Counterexamples to the Strong d -Step Conjecture for d≥5

A Dantzig figure is a triple (P,x,y) in which P is a simple d -polytope with precisely 2d facets, x and y are vertices of P , and each facet is incident to x or y but not both. The famous d -step conjecture of linear programming is equivalent to the claim that always # ^d P(x,y) ≥ 1 , where # ^d P(x,y) denotes the number of paths that connect x to y by using precisely d edges of P . The recently formulated strong d -step conjecture makes a still stronger claim—namely, that always # ^d P(x,y) ≥ 2 ^d-1 . It is shown here that the strong d -step conjecture holds for d ≤ 4 , but fails for d ≥ 5 . Received December 27, 1995, and in revised form April 8, 1996.