Polynomial Diameter Conjecture for polytope graphs

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.

Sources & referencesView supporting material

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.