The dd-step Conjecture for polytope diameters

About 16 years old · traced to

Let H(n,d)H(n,d) denote the maximum graph diameter of a dd-dimensional polytope with nn facets.

The dd-step Conjecture. For every d≥2d \geq 2,

H(2d,d)≤d.H(2d,d) \leq d.

The source states that this conjecture is equivalent to the Hirsch Conjecture by the Klee–Walkup theorem. Since the Hirsch conjecture is refuted, this conjecture is also refuted.

References

Primary source

Edward D. Kim, “Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method”, arXiv:1006.2416 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.