A counterexample to the Hirsch conjecture

DOI10.4007/ANNALS.2012.176.1.7MaRDI QIDQ447933zbMATHOpenAlexWikidataFDO

Authors Francisco Santos

Publication date 30 August 2012

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

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

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)

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.

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

Cites work

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

Cited in

(96)

• The Hirsch conjecture for the fractional stable set polytope
• Edge-graph diameter bounds for convex polytopes with few facets
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• An asymptotically improved upper bound on the diameter of polyhedra
• Connectivity and \(W_v\)-paths in polyhedral maps on surfaces
• The Demyanov-Ryabova conjecture is false
• A counterexample to the finite height conjecture
• Discrete differential geometry. Abstracts from the workshop held July 8--14, 2012.
• scientific article; zbMATH DE number 1933066 (Why is no real title available?)
• Distance between vertices of lattice polytopes
• Selected open problems in discrete geometry and optimization
• Improved bounds on the diameter of lattice polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Improving bounds on the diameter of a polyhedron in high dimensions
• Diameter, decomposability, and Minkowski sums of polytopes
• Formalizing the face lattice of polyhedra
• scientific article; zbMATH DE number 4152413 (Why is no real title available?)
• The Hirsch conjecture holds for normal flag complexes
• On the circuit diameter conjecture
• A counterexample to a conjecture of Hutchinson and Lai
• Formalizing the Face Lattice of Polyhedra
• Inapproximability of shortest paths on perfect matching polytopes
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
• On a counter-example to the Hirsch conjecture
• The Hirsch conjecture is true for (0,1)-polytopes
• The hierarchy of circuit diameters and transportation polytopes
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• A counterexample to the Perles conjecture
• Counterexamples to Jaeger's circular flow conjecture
• A note on the diameter of convex polytope
• A counter-example to the theorem of Hiemer and Snurnikov
• Counterexample to a variant of a conjecture of Ziegler concerning a simple polytope and its dual
• The width of five-dimensional prismatoids
• On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes
• Examples and counterexamples for the Perles conjecture
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• A counter-example to Hausmann's conjecture
• On the shadow simplex method for curved polyhedra
• Lipschitz polytopes of posets and permutation statistics
• Hirsch polytopes with exponentially long combinatorial segments
• Primitive zonotopes
• Quadratic diameter bounds for dual network flow polyhedra
• On Dantzig figures from graded lexicographic orders
• Twenty years of EUROPT, the EURO working group on continuous optimization
• On the circuit diameter of some combinatorial polytopes
• Bannai et al. method proves the \(d\)-step conjecture for strings
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• On counterexamples to the Hughes conjecture.
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
• The d-Step Conjecture and Its Relatives
• Obstructions to weak decomposability for simplicial polytopes
• On the diameter of an ideal
• Many projectively unique polytopes
• On circuit diameter bounds via circuit imbalances
• Enumerating neighborly polytopes and oriented matroids
• The circuit diameter of the Klee-Walkup polyhedron
• A counterexample to a conjecture on the connectivity of \(0\)-\(1\) polytope graphs
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• An update on the Hirsch conjecture
• Counterexample to a conjecture on Hamilton cycles
• A refinement of Todd's bound for the diameter of a polyhedron
• Monotone paths in planar convex subdivisions and polytopes
• Blending simple polytopes at faces
• Randomized construction of complexes with large diameter
• Heinrich's counterexample to Azevedo's conjecture
• Diameter estimates for graph associahedra
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A friendly smoothed analysis of the simplex method
• Diameters of cocircuit graphs of oriented matroids: an update
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• Topological prismatoids and small simplicial spheres of large diameter
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• A proof of the strict monotone 5-step conjecture
• On circuit diameter bounds via circuit imbalances
• Rock extensions with linear diameters
• Exploiting symmetries in polyhedral computations
• Shortest reconfiguration of perfect matchings via alternating cycles
• Unimodular covers of \(3\)-dimensional parallelepipeds and Cayley sums
• scientific article; zbMATH DE number 7525498 (Why is no real title available?)
• Constructing Clustering Transformations
• Computing in combinatorial optimization
• A spectral approach to polytope diameter
• The diameter of lattice zonotopes
• A polyhedral model for enumeration and optimization over the set of circuits
• Circuit walks in integral polyhedra
• Random walks on polytopes of constant corank
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers
• Arithmetic aspects of symmetric edge polytopes
• Characterising \(3\)-polytopes of radius one with unique realisation
• On the Combinatorial Diameters of Parallel and Series Connections
• Improving the Cook et al. proximity bound given integral valued constraints
• An exponential lower bound for Zadeh's pivot rule
• Positive Plücker tree certificates for non-realizability
• Lattices from graph associahedra and subalgebras of the Malvenuto-Reutenauer algebra
• Primitive point packing

Describes a project that uses

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)