COUNTEREXAMPLES TO THE STRONG D-STEP CONJECTURE FOR D-GREATER-THAN-OR-EQUAL-TO-5

A Dantzig figure is a triple (P, x, y) in which P is a simple d-polyto pe 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 l inear programming is equivalent to the claim that always #(d) P(x, y) greater than or equal to 1, where #(d) P(x, y) denotes the number of p aths that connect x to y by using precisely d edges of P. The recently formulated strong d-step conjecture makes a still stronger claim-name ly, that always #(d) P(x, y) greater than or equal to 2(d-1). It is sh own here that the strong d-step conjecture holds for d less than or eq ual to 4, but fails for d greater than or equal to 5.