Polynomial Diameter Conjecture for polytope graphs

About 16 years old · traced to

For a polytope or polyhedron PP of dimension dd with nn facets, let G(P)G(P) denote its graph.

Polynomial Diameter Conjecture. Is there a polynomial function f(n,d)f(n,d) such that

diam⁡(G(P))≤f(n,d)?\operatorname{diam}(G(P)) \leq f(n,d)?

The source states that no polynomial upper bound was known for polytope diameters. The conjecture remains open in the supplied material.

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.