Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Abstract

The Hirsch conjecture, posed in 1957, stated that the graph of a $d$-dimensional polytope or polyhedron with $n$ facets cannot have diameter greater than $n-d$. 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 $n^{Theta(d)}$ 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).

34 pages. This paper supersedes one cited as "On the maximum diameter of simplicial complexes and abstractions of them, in preparation"

References in corpus (1)

• Constructing subset partition graphs with strong adjacency and end-point count properties

Cited by in corpus (13)

• The diameter of type D associahedra and the non-leaving-face property
• Improving bounds on the diameter of a polyhedron in high dimensions
• Hirsch polytopes with exponentially long combinatorial segments
• The maximum diameter of pure simplicial complexes and pseudo-manifolds
• Topological Prismatoids and Small Simplicial Spheres of Large Diameter
• An improved upper bound on the diameters of subset partition graphs
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• On the diameter of dual graphs of Stanley-Reisner rings with Serre $(S_2)$ property and Hirsch type bounds on abstractions of polytopes
• Tail diameter upper bounds for polytopes and polyhedra
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• On the dual graph of Cohen-Macaulay algebras
• Monotone Paths in Geometric Triangulations
• Wigglyhedra