Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

Abstract

We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete approach for disproving the Linear Hirsch Conjecture.

16 pages, 4 figures

References in corpus (3)

• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• Polytopality and Cartesian products of graphs

Cited by in corpus (2)

• Improving bounds on the diameter of a polyhedron in high dimensions
• The maximum diameter of pure simplicial complexes and pseudo-manifolds