Hirsch polytopes with exponentially long combinatorial segments

• 成果类型: Article
• 署名作者: Labbe, Jean-Philippe; Manneville, Thibault; Santos, Francisco
• 署名单位: Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Institut Polytechnique de Paris; Ecole Polytechnique; Universidad de Cantabria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1099-y
• 发表日期: 2017
• 页码: 663-688
• 关键词: simplicial complexes; branched-coverings; convex polyhedra; diameter; conjecture; graphs

摘要

In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340-1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use these definitions to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length . This includes vertex-decomposable-therefore Hirsch-polytopes.