Hirsch-sharpness conjecture for 3-way transportation polytopes

About 16 years old · traced to

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

Hirsch-sharpness conjecture for 3-way transportation polytopes.

diam⁡(G(P))=n−d.\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.

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.