Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable
Jesús A. De Loera, Steven H. Klee · Mathematics of Operations Research · 2012
Provan and Billera defined the notion of weak k-decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly k-decomposable simplicial complex Δ is bounded above by a polynomial function of the number of k-faces in Δ and its dimension. For weakly 0-decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non-weakly 0-decomposable simplicial polytopes. Our examples are in fact polar to certain transportation polytopes.