The Hirsch conjecture holds for normal flag complexes

DOI10.1287/MOOR.2014.0661MaRDI QIDQ5247624zbMATH OpenOpenAlexWikidataFDO

Authors Karim Adiprasito, Bruno Benedetti

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

CAT(1) spacesdual graphflag normal complexesgraph diameterHirsch conjecturepolytopessimplex methodsimplicial complexes

Mathematics Subject Classification ID

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

Abstract: Using an intuition from metric geometry, we prove that any flag and normal simplicial complex satisfies the non-revisiting path conjecture. As a consequence, the diameter of its facet-ridge graph is smaller than the number of vertices minus the dimension, as in the Hirsch conjecture. This proves the Hirsch conjecture for all flag polytopes, and more generally, for all (connected) flag homology manifolds.

Recommendations

• Hirsch polytopes with exponentially long combinatorial segments
• A counterexample to the Hirsch conjecture
• On a counter-example to the Hirsch conjecture
• The Hirsch conjecture is true for (0,1)-polytopes
• An update on the Hirsch conjecture

Cites work

• A counterexample to the Hirsch conjecture
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An upper bound for the diameter of a polytope
• Decompositions of simplicial balls and spheres with knots consisting of few edges
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• Diameter of polyhedra: limits of abstraction
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3000476 (Why is no real title available?)
• scientific article; zbMATH DE number 1444572 (Why is no real title available?)
• Paths on Polyhedra. I
• Paths on Polytopes
• The d-Step Conjecture and Its Relatives
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Upper bounds for the diameter and height of graphs of convex polyhedra

Cited in

(13)

• On the diameter of an ideal
• Hirsch polytopes with exponentially long combinatorial segments
• The Hirsch conjecture is true for (0,1)-polytopes
• Geometry and the simplex: results, questions and ideas
• Collapsibility of CAT(0) spaces
• Relating CAT(0) cubical complexes and flag simplicial complexes
• A special feature of quadratic monomial ideals
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• The diameter of type \(D\) associahedra and the non-leaving-face property
• A friendly smoothed analysis of the simplex method
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• On the shadow simplex method for curved polyhedra
• Square-free Gröbner degenerations

This page was built for publication: The Hirsch conjecture holds for normal flag complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5247624)