A counterexample to the Hirsch conjecture

DOI10.4007/ANNALS.2012.176.1.7zbMATH Open1252.52007arXiv1006.2814OpenAlexW2151888904WikidataQ28109653 ScholiaQ28109653MaRDI QIDQ447933FDOQ447933

Authors: Francisco Santos 

Publication date: 30 August 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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.

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

Recommendations

• On a counter-example to the Hirsch conjecture
• An update on the Hirsch conjecture
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Many polytopes meeting the conjectured Hirsch bound
• The width of five-dimensional prismatoids

zbMATH Keywords

graph diameterpolytopesHirsch conjecturesimplex algorithm

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Distance in graphs (05C12)

Cites Work

• polymake: a framework for analyzing convex polytopes
• A new polynomial-time algorithm for linear programming
• Lectures on Polytopes
• Triangulations. Structures for algorithms and applications
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Neighborly cubical polytopes
• Title not available (Why is that?)
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• Convex Polytopes
• More bounds on the diameters of convex polytopes
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• A proof of the lower bound conjecture for convex polytopes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Title not available (Why is that?)
• Smoothed analysis of algorithms
• On the exact maximum complexity of Minkowski sums of polytopes
• Pivot rules for linear programming: A survey on recent theoretical developments
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An update on the Hirsch conjecture
• Title not available (Why is that?)
• The simplex method. A probabilistic analysis
• An upper bound for the diameter of a polytope
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Diameter of polyhedra: limits of abstraction
• The d-Step Conjecture and Its Relatives
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
• Edge-graph diameter bounds for convex polytopes with few facets
• Paths on Polyhedra. I
• Paths on Polytopes
• Diameters of Polyhedral Graphs
• The width of five-dimensional prismatoids
• Many polytopes meeting the conjectured Hirsch bound
• The cubical \(d\)-polytopes with fewer than 2\(^{d+1}\) vertices
• Title not available (Why is that?)
• On the Number of Vertices of a Convex Polytope
• Book Review: The basic George B. Dantzig
• Wv paths on 3-polytopes

Cited In (only showing first 100 items - show all)

• A double-pivot simplex algorithm and its upper bounds of the iteration numbers
• Characterising \(3\)-polytopes of radius one with unique realisation
• A Friendly Smoothed Analysis of the Simplex Method
• Constructing Clustering Transformations
• ARITHMETIC ASPECTS OF SYMMETRIC EDGE POLYTOPES
• Diameters of cocircuit graphs of oriented matroids: an update
• Topological Prismatoids and Small Simplicial Spheres of Large Diameter
• Exploiting Symmetries in Polyhedral Computations
• On circuit diameter bounds via circuit imbalances
• On the Combinatorial Diameters of Parallel and Series Connections
• Positive Plücker tree certificates for non-realizability
• Primitive point packing
• Lattices from graph associahedra and subalgebras of the Malvenuto-Reutenauer algebra
• An exponential lower bound for Zadeh's pivot rule
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• Randomized construction of complexes with large diameter
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• Improving the Cook et al. proximity bound given integral valued constraints
• Unimodular covers of \(3\)-dimensional parallelepipeds and Cayley sums
• A spectral approach to polytope diameter
• The diameter of lattice zonotopes
• A polyhedral model for enumeration and optimization over the set of circuits
• Rock extensions with linear diameters
• A proof of the strict monotone 5-step conjecture
• Computing in combinatorial optimization
• A formalization of convex polyhedra based on the simplex method
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Circuit walks in integral polyhedra
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
• Title not available (Why is that?)
• Random Walks on Polytopes of Constant Corank
• Diameter estimates for graph associahedra
• Counterexample to a conjecture on Hamilton cycles
• Enumerating Neighborly Polytopes and Oriented Matroids
• On the Circuit Diameter of Some Combinatorial Polytopes
• On the circuit diameter conjecture
• The width of five-dimensional prismatoids
• Twenty years of EUROPT, the EURO working group on continuous optimization
• On counterexamples to the Hughes conjecture.
• On circuit diameter bounds via circuit imbalances
• Diameter, Decomposability, and Minkowski Sums of Polytopes
• Blending simple polytopes at faces
• A counterexample to the finite height conjecture
• On Dantzig figures from graded lexicographic orders
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• A counterexample to a conjecture of Hutchinson and Lai
• Counterexamples to Jaeger's circular flow conjecture
• Edge-graph diameter bounds for convex polytopes with few facets
• Title not available (Why is that?)
• On sub-determinants and the diameter of polyhedra
• Lipschitz polytopes of posets and permutation statistics
• Primitive zonotopes
• Monotone paths in geometric triangulations
• Examples and counterexamples for the Perles conjecture
• A counter-example to Hausmann's conjecture
• On the shadow simplex method for curved polyhedra
• On a counter-example to the Hirsch conjecture
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• The maximum diameter of pure simplicial complexes and pseudo-manifolds
• Quadratic diameter bounds for dual network flow polyhedra
• The circuit diameter of the Klee-Walkup polyhedron
• Connectivity and \(W_v\)-paths in polyhedral maps on surfaces
• The Hirsch conjecture is true for (0,1)-polytopes
• The Hirsch conjecture for the fractional stable set polytope
• Selected Open Problems in Discrete Geometry and Optimization
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• Many projectively unique polytopes
• An update on the Hirsch conjecture
• A refinement of Todd's bound for the diameter of a polyhedron
• Improved bounds on the diameter of lattice polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
• An asymptotically improved upper bound on the diameter of polyhedra
• Title not available (Why is that?)
• A counterexample to the Perles conjecture
• A note on the diameter of convex polytope
• Simple extensions of polytopes
• Obstructions to weak decomposability for simplicial polytopes
• A counter-example to the theorem of Hiemer and Snurnikov
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• Hirsch polytopes with exponentially long combinatorial segments
• Discrete differential geometry. Abstracts from the workshop held July 8--14, 2012.
• The d-Step Conjecture and Its Relatives
• A counterexample to a conjecture on the connectivity of \(0\)-\(1\) polytope graphs
• Improving bounds on the diameter of a polyhedron in high dimensions
• Formalizing the Face Lattice of Polyhedra
• Heinrich's counterexample to Azevedo's conjecture
• Title not available (Why is that?)
• Inapproximability of shortest paths on perfect matching polytopes
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• The hierarchy of circuit diameters and transportation polytopes
• Monotone Paths in Planar Convex Subdivisions and Polytopes
• Distance between vertices of lattice polytopes
• Bannai et al. method proves the \(d\)-step conjecture for strings
• On the diameter of an ideal
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• The Hirsch Conjecture Holds for Normal Flag Complexes
• On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids

Uses Software

• polymake

This page was built for publication: A counterexample to the Hirsch conjecture

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