The Hirsch Conjecture Holds for Normal Flag Complexes

DOI10.1287/moor.2014.0661zbMath1319.52017arXiv1303.3598OpenAlexW2107613873WikidataQ123127907 ScholiaQ123127907MaRDI QIDQ5247624

Bruno Benedetti, Karim A. Adiprasito

Publication date: 24 April 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

polytopessimplicial complexessimplex methodgraph diameterdual graphHirsch conjectureCAT(1) spacesflag normal complexes

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Grassmannians, Schubert varieties, flag manifolds (14M15) Distance in graphs (05C12) Methods of global Riemannian geometry, including PDE methods; curvature restrictions (53C21) Polyhedral manifolds (52B70) Combinatorial aspects of simplicial complexes (05E45)

Related Items (11)

A Special Feature of Quadratic Monomial Ideals ⋮ On the diameter of an ideal ⋮ Hirsch polytopes with exponentially long combinatorial segments ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Collapsibility of CAT(0) spaces ⋮ Relating CAT(0) cubical complexes and flag simplicial complexes ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ The diameter of type \(D\) associahedra and the non-leaving-face property ⋮ Geometry and the simplex: results, questions and ideas ⋮ On the shadow simplex method for curved polyhedra ⋮ Square-free Gröbner degenerations

Cites Work

• A counterexample to the Hirsch conjecture
• Upper bounds for the diameter and height of graphs of convex polyhedra
• An upper bound for the diameter of a polytope
• Decompositions of simplicial balls and spheres with knots consisting of few edges
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter of Polyhedra: Limits of Abstraction
• The d-Step Conjecture and Its Relatives
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Paths on Polyhedra. I
• Paths on Polytopes
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Hirsch Conjecture Holds for Normal Flag Complexes