A counterexample to the Hirsch conjecture

Abstract

The Hirsch Conjecture (1957) stated that the graph of a $d$-dimensional polytope with $n$ facets cannot have (combinatorial) diameter greater than $n-d$. That is, that any two vertices of the polytope can be connected by a path of at most $n-d$ edges. This paper presents the first counterexample to the conjecture. Our polytope has dimension 43 and 86 facets. It is obtained from a 5-dimensional polytope with 48 facets which violates a certain generalization of the $d$-step conjecture of Klee and Walkup.

28 pages, 10 Figures: Changes from v2: Minor edits suggested by referees. This version has been accepted in the Annals of Mathematics

References in corpus (4)

• An update on the Hirsch conjecture
• Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
• Companion to "An update on the Hirsch conjecture"

Cited by in corpus (56)

• The width of 5-dimensional prismatoids
• Arithmetic aspects of symmetric edge polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Improved bounds on the diameter of lattice polytopes
• Improving bounds on the diameter of a polyhedron in high dimensions
• Diameter estimates for graph associahedra
• On Simplex Pivoting Rules and Complexity Theory
• Hirsch polytopes with exponentially long combinatorial segments
• Primitive point packing
• Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture
• Topological Prismatoids and Small Simplicial Spheres of Large Diameter
• Constructing subset partition graphs with strong adjacency and end-point count properties
• The maximum diameter of pure simplicial complexes and pseudo-manifolds
• On Dantzig figures from graded lexicographic orders
• On the Graph of the Pedigree Polytope
• Diameter, decomposability, and Minkowski sums of polytopes
• Transportation Polytope and its Applications in Parallel Server Systems
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• Tail diameter upper bounds for polytopes and polyhedra
• Polynomial time vertex enumeration of convex polytopes of bounded branch-width
• On the diameter of dual graphs of Stanley-Reisner rings with Serre $(S_2)$ property and Hirsch type bounds on abstractions of polytopes
• A linear optimization oracle for zonotope computation
• An improved upper bound on the diameters of subset partition graphs
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• Polytopes with Special Simplices
• The Hierarchy of Circuit Diameters and Transportation Polytopes
• Enumerating neighborly polytopes and oriented matroids
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers
• On 2-level polytopes arising in combinatorial settings
• A simple proof of tail--polynomial bounds on the diameter of polyhedra
• On the dual graph of Cohen-Macaulay algebras
• Simple Extensions of Polytopes
• The Hirsch conjecture holds for normal flag complexes
• Many projectively unique polytopes
• Obstructions to weak decomposability for simplicial polytopes
• Constrained Triangulations, Volumes of Polytopes, and Unit Equations
• Sobre un contraejemplo a la conjetura de Hirsch
• Wigglyhedra
• Counterexamples to Siegel's Conjecture
• On the Circuit Diameter of some Combinatorial Polytopes
• The Diameters of Network-flow Polytopes satisfy the Hirsch Conjecture
• Monotone Paths in Geometric Triangulations
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• On the Shadow Simplex Method for Curved Polyhedra
• Not all simplicial polytopes are weakly vertex-decomposable
• Observations on the Perturbed Wedge
• A note on the diameter of transportation polytopes with prescribed source degrees
• Quadratic diameter bounds for dual network flow polyhedra
• On the Existence of Hamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes
• A note on the diameter of convex polytope
• Stable set polytopes and their 1-skeleta
• Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
• Unimodular covers of 3-dimensional parallelepipeds and Cayley sums
• Connectivity and $W_v$-Paths in Polyhedral Maps on Surfaces
• Properties of Polytopes Representing Natural Numbers
• Formalizing the Face Lattice of Polyhedra