Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable

• 成果类型: Article
• 署名作者: De Loera, Jesus A.; Klee, Steven
• 署名单位: University of California System; University of California Davis
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1120.0554
• 发表日期: 2012
• 页码: 670-674
• 关键词: conjecture; diameter

摘要

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 Delta is bounded above by a polynomial function of the number of k-faces in Delta 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.