Hirsch polytopes with exponentially long combinatorial segments

DOI10.1007/s10107-016-1099-yzbMath1382.52008arXiv1510.07678OpenAlexW3105575066MaRDI QIDQ1675265

Thibault Manneville, Jean-Philippe Labbé, Francisco Santos

Publication date: 27 October 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.07678

zbMATH Keywords

diametersimplicial complexflag complexbanner complexcombinatorial segmentnormal complex

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Improving bounds on the diameter of a polyhedron in high dimensions, Distance between vertices of lattice polytopes, A Polyhedral Method for Sparse Systems with Many Positive Solutions, On the circuit diameter conjecture, An asymptotically improved upper bound on the diameter of polyhedra

Cites Work

• Unnamed Item
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A counterexample to the Hirsch conjecture
• Intersection homology theory
• Upper bounds for the diameter and height of graphs of convex polyhedra
• An upper bound for the diameter of a polytope
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• From Flag Complexes to Banner Complexes
• Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable
• Diameter of Polyhedra: Limits of Abstraction
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Branched coverings, triangulations, and 3-manifolds
• The width of five-dimensional prismatoids
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• The Hirsch Conjecture Holds for Normal Flag Complexes
• Paths on Polytopes
• The maximum diameter of pure simplicial complexes and pseudo-manifolds
• Branched coverings