A counterexample to the Hirsch conjecture

DOI10.4007/annals.2012.176.1.7zbMath1252.52007arXiv1006.2814OpenAlexW2151888904WikidataQ28109653 ScholiaQ28109653MaRDI QIDQ447933

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

polytopes simplex algorithm graph diameter Hirsch conjecture

Mathematics Subject Classification ID

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

Related Items

Diameters of cocircuit graphs of oriented matroids: an update, Improving bounds on the diameter of a polyhedron in high dimensions, Formalizing the Face Lattice of Polyhedra, Quadratic diameter bounds for dual network flow polyhedra, The circuit diameter of the Klee-Walkup polyhedron, Obstructions to weak decomposability for simplicial polytopes, Discrete differential geometry. Abstracts from the workshop held July 8--14, 2012., Enumerating Neighborly Polytopes and Oriented Matroids, Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Improving the Cook et al. proximity bound given integral valued constraints, On circuit diameter bounds via circuit imbalances, On the diameter of an ideal, Distance between vertices of lattice polytopes, Connectivity and \(W_v\)-paths in polyhedral maps on surfaces, Hirsch polytopes with exponentially long combinatorial segments, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Topological Prismatoids and Small Simplicial Spheres of Large Diameter, Circuit walks in integral polyhedra, An exponential lower bound for Zadeh's pivot rule, Primitive point packing, Inapproximability of shortest paths on perfect matching polytopes, Simple extensions of polytopes, Twenty years of EUROPT, the EURO working group on continuous optimization, The diameter of lattice zonotopes, On the Combinatorial Diameters of Parallel and Series Connections, Positive Plücker tree certificates for non-realizability, Unimodular covers of \(3\)-dimensional parallelepipeds and Cayley sums, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), Polyhedral graph abstractions and an approach to the linear Hirsch conjecture, The hierarchy of circuit diameters and transportation polytopes, ARITHMETIC ASPECTS OF SYMMETRIC EDGE POLYTOPES, A Friendly Smoothed Analysis of the Simplex Method, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, A note on the diameter of convex polytope, Lattices from graph associahedra and subalgebras of the Malvenuto-Reutenauer algebra, The Hirsch conjecture for the fractional stable set polytope, The maximum diameter of pure simplicial complexes and pseudo-manifolds, A proof of the strict monotone 5-step conjecture, On sub-determinants and the diameter of polyhedra, A \(d\)-step approach to the maximum number of distinct squares and runs in strings, Constructing Clustering Transformations, On Dantzig figures from graded lexicographic orders, On the Circuit Diameter of Some Combinatorial Polytopes, Improved bounds on the diameter of lattice polytopes, Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count, On the circuit diameter conjecture, Bannai et al. method proves the \(d\)-step conjecture for strings, On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes, Unnamed Item, Many projectively unique polytopes, Random Walks on Polytopes of Constant Corank, Lipschitz polytopes of posets and permutation statistics, A formalization of convex polyhedra based on the simplex method, The diameters of network-flow polytopes satisfy the Hirsch conjecture, A refinement of Todd's bound for the diameter of a polyhedron, Unnamed Item, Primitive zonotopes, Monotone paths in geometric triangulations, On the shadow simplex method for curved polyhedra, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Randomized construction of complexes with large diameter, A polyhedral model for enumeration and optimization over the set of circuits, On Vertices and Facets of Combinatorial 2-Level Polytopes, Computing in combinatorial optimization, An asymptotically improved upper bound on the diameter of polyhedra, Diameter, Decomposability, and Minkowski Sums of Polytopes, The width of five-dimensional prismatoids, Monotone Paths in Planar Convex Subdivisions and Polytopes, Exploiting Symmetries in Polyhedral Computations, Selected Open Problems in Discrete Geometry and Optimization, The Hirsch Conjecture Holds for Normal Flag Complexes, Diameter estimates for graph associahedra

Uses Software

polymake

Cites Work