Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Counterexamples to the Strong
d
-Step Conjecture for
d≥5
| |
|
Counterexamples to the Strong d -Step Conjecture for d≥5
F. Holt1 and V. Klee1
| (1) |
Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195-4350, USA holt@math.washington.edu klee@math.washington.edu, US |
Abstract. 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.
Fulltext Preview (Small, Large)
|
|
|
|
|
|