Polyhedral graph abstractions and an approach to the linear Hirsch conjecture

DOI10.1007/s10107-012-0611-2zbMath1290.05067arXiv1103.3362OpenAlexW3103532334WikidataQ123165705 ScholiaQ123165705MaRDI QIDQ2436640

Edward D. Kim

Publication date: 25 February 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

convex polytopesHirsch conjecturesubset partition graph

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) Distance in graphs (05C12)

Related Items (4)

Improving bounds on the diameter of a polyhedron in high dimensions ⋮ The maximum diameter of pure simplicial complexes and pseudo-manifolds ⋮ Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count ⋮ An asymptotically improved upper bound on the diameter of polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• A counterexample to the Hirsch conjecture
• Prodsimplicial-neighborly polytopes
• An update on the Hirsch conjecture
• On the graph structure of convex polyhedra in \(n\)-space
• Upper bounds for the diameter and height of graphs of convex polyhedra
• Neighborly cubical polytopes
• Polytopality and Cartesian products of graphs
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter of Polyhedra: Limits of Abstraction
• The graph of an abstract polytope
• The d-Step Conjecture and Its Relatives
• Long Monotone Paths in Abstract Polytopes
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Projected products of polygons

This page was built for publication: Polyhedral graph abstractions and an approach to the linear Hirsch conjecture