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.
My Menu
Saved Items

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)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.106 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)