Hirsch-sharpness conjecture for 3-way transportation polytopes

Let PP be a non-degenerate 33-way transportation polytope of size p×q×sp \times q \times s, with p,q,s3p,q,s \geq 3, defined by 11-marginals. Let G(P)G(P) be its graph, let d=pqspqs+2d=pqs-p-q-s+2 be its dimension, and let npqsn \leq pqs be the number of facets of PP.

Hirsch-sharpness conjecture for 3-way transportation polytopes.

diam(G(P))=nd.\operatorname{diam}(G(P))=n-d.

The claim predicts that these transportation polytopes attain the Hirsch bound exactly. The supplied material gives no resolution status.

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.