Recent progress on the combinatorial diameter of polytopes and simplicial complexes
From MaRDI portal
Abstract: The Hirsch conjecture, posed in 1957, stated that the graph of a -dimensional polytope or polyhedron with facets cannot have diameter greater than . The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25% is known. This paper reviews several recent attempts and progress on the question. Some work in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we include here our recent and previously unpublished proof that the maximum diameter of arbitrary simplicial complexes is in and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e. g., simplicial manifolds).
Recommendations
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Recent results around the diameter of polyhedra
- An update on the Hirsch conjecture
- A counterexample to the Hirsch conjecture
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
Cites work
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 1503621 (Why is no real title available?)
- scientific article; zbMATH DE number 227006 (Why is no real title available?)
- A continuous \(d\)-step conjecture for polytopes
- A counterexample to the Hirsch conjecture
- A new polynomial-time algorithm for linear programming
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- A simple polynomial-time rescaling algorithm for solving linear programs
- A strongly polynomial algorithm for linear systems having a binary solution
- 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
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Branched coverings, triangulations, and 3-manifolds
- Central path curvature and iteration-complexity for redundant Klee-Minty cubes
- 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
- More bounds on the diameters of convex polytopes
- Nonrealizable minimal vertex triangulations of surfaces: showing nonrealizability using oriented matroids and satisfiability solvers
- Obstructions to weak decomposability for simplicial polytopes
- On the diameter of convex polytopes
- Paths on Polyhedra. I
- Paths on Polytopes
- Polytopes and arrangements: diameter and curvature
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Some upper bounds for the diameters of convex polytopes
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- The d-Step Conjecture and Its Relatives
- The Hirsch conjecture holds for normal flag complexes
- The Hirsch conjecture is true for (0,1)-polytopes
- The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
- The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
- The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
- Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
- Triangulations. Structures for algorithms and applications
- Upper bounds for the diameter and height of graphs of convex polyhedra
Cited in
(18)- Diameters of cocircuit graphs of oriented matroids: an update
- An asymptotically improved upper bound on the diameter of polyhedra
- Topological prismatoids and small simplicial spheres of large diameter
- Improving bounds on the diameter of a polyhedron in high dimensions
- Topological properties on the diameters of the integer simplex
- On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Hirsch polytopes with exponentially long combinatorial segments
- Recent results around the diameter of polyhedra
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- The diameter of type \(D\) associahedra and the non-leaving-face property
- The circuit diameter of the Klee-Walkup polyhedron
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- An update on the Hirsch conjecture
- A refinement of Todd's bound for the diameter of a polyhedron
- Randomized construction of complexes with large diameter
This page was built for publication: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q384506)
