Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets

DOI10.1080/10586458.2011.564965zbMath1266.52017arXiv0809.0915OpenAlexW3104186416MaRDI QIDQ4915386

David Bremner, Lars Schewe

Publication date: 10 April 2013

Published in: Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polytopesdiameteroriented matroidssatisfiabilityHirsch conjecture

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Oriented matroids in discrete geometry (52C40)

Related Items

More bounds on the diameters of convex polytopes ⋮ Nonrealizable minimal vertex triangulations of surfaces: showing nonrealizability using oriented matroids and satisfiability solvers ⋮ Enumerating Neighborly Polytopes and Oriented Matroids ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Topological Prismatoids and Small Simplicial Spheres of Large Diameter ⋮ Realizability and inscribability for simplicial polytopes via nonlinear optimization ⋮ A counterexample to the Hirsch conjecture ⋮ A proof of the strict monotone 5-step conjecture ⋮ On Dantzig figures from graded lexicographic orders ⋮ On the circuit diameter conjecture ⋮ On the Holt-Klee property for oriented matroid programming

Uses Software

• nauty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonrealizable minimal vertex triangulations of surfaces: showing nonrealizability using oriented matroids and satisfiability solvers
• Symmetric matroid polytopes and their generation
• Blending simple polytopes at faces
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Some upper bounds for the diameters of convex polytopes
• The d-Step Conjecture and Its Relatives
• Diameters of Polyhedral Graphs