Title:  Not all Simplicial Polytopes are Weakly Vertex-Decomposable

Abstract:  The Simplex Method solves linear programs by testing adjacent vertices in the feasible set (a polytope) in sequence such that each new vertex in the sequence improves or stays the same with respect to the objective function. It is natural to ask how long the Simplex Method could take to solve a given linear program. Stating this in the language of polytopes, we would like to find a bound on the diameter of d-dimensional polytopes with a fixed number of vertices, say n. In 1980, Billera and Provan defined the notions of k-decomposability and weak k-decomposability for simplicial complexes and computed bounds on the diameter of complexes admitting such decompositions. In particular, these bounds become linear in n and d when k=0. Hence, it is reasonable to ask if all simplicial complexes admit such a decomposition. In 2010, De Loera and Klee identified a simple transportation polytope in each dimension greater than three whose dual polytope is not weakly vertex-decomposable. We will introduce the notion of weak k-decomposability and transportation polytopes, and then we will see why the family of polytopes constructed by De Loera and Klee fail to be weakly vertex-decomposable.