An update on the Hirsch conjecture

DOI10.1365/S13291-010-0001-8zbMATH Open1252.05052arXiv0907.1186OpenAlexW3099025364WikidataQ123231741 ScholiaQ123231741MaRDI QIDQ613104FDOQ613104

Edward D. Kim, Francisco Santos

Publication date: 17 December 2010

Published in: Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV) (Search for Journal in Brave)

Abstract: The Hirsch conjecture was posed in 1957 in a letter from Warren M. Hirsch to George Dantzig. It states that the graph of a d-dimensional polytope with n facets cannot have diameter greater than n - d. Despite being one of the most fundamental, basic and old problems in polytope theory, what we know is quite scarce. Most notably, no polynomial upper bound is known for the diameters that are conjectured to be linear. In contrast, very few polytopes are known where the bound $n-d$ is attained. This paper collects known results and remarks both on the positive and on the negative side of the conjecture. Some proofs are included, but only those that we hope are accessible to a general mathematical audience without introducing too many technicalities.

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

zbMATH Keywords

linear programminggraph diameterpolytopesHirsch conjecture

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Distance in graphs (05C12) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Cited In (20)

• On the circuit diameter conjecture
• The width of five-dimensional prismatoids
• Constructing Clustering Transformations
• More bounds on the diameters of convex polytopes
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Title not available (Why is that?)
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Cyclic polytopes, oriented matroids and intersections of quadrics
• On sub-determinants and the diameter of polyhedra
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Quadratic diameter bounds for dual network flow polyhedra
• A counterexample to the Hirsch conjecture
• On the Combinatorial Diameters of Parallel and Series Connections
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
• Obstructions to weak decomposability for simplicial polytopes
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Edges versus circuits: a hierarchy of diameters in polyhedra
• The hierarchy of circuit diameters and transportation polytopes

   Recommendations

• A counterexample to the Hirsch conjecture 👍 👎
• Many polytopes meeting the conjectured Hirsch bound 👍 👎
• On a counter-example to the Hirsch conjecture 👍 👎
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes 👍 👎
• The d-Step Conjecture and Its Relatives 👍 👎

This page was built for publication: An update on the Hirsch conjecture

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