Polyhedral graph abstractions and an approach to the linear Hirsch conjecture

DOI10.1007/S10107-012-0611-2MaRDI QIDQ2436640zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

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.

Review text

This paper introduces a combinatorial abstraction for the graphs of polyhedra. The author formally explain some previous abstractions and survey the upper and lower bound. This paper discuss combinatorial properties defining special cases and then a new combinatorial abstraction namely \textit{subset partition graphs}. The upper and lower bounds as the diameters of the subset partition graphs satisfying a particular set of properties is discussed. Finally, a strategy is presented for disproving Linear Hirsch Conjecture.

Recommendations

• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• A counterexample to the Hirsch conjecture
• Diameter of polyhedra: limits of abstraction
• Diameter of polyhedra: limits of abstraction
• On a counter-example to the Hirsch conjecture

Cites work

• A counterexample to the Hirsch conjecture
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An update on the Hirsch conjecture
• Diameter of polyhedra: limits of abstraction
• scientific article; zbMATH DE number 3548722 (Why is no real title available?)
• scientific article; zbMATH DE number 3614497 (Why is no real title available?)
• Long Monotone Paths in Abstract Polytopes
• Neighborly cubical polytopes
• On the graph structure of convex polyhedra in n-space
• Polytopality and Cartesian products of graphs
• Prodsimplicial-neighborly polytopes
• Projected products of polygons
• The d-Step Conjecture and Its Relatives
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The graph of an abstract polytope
• Upper bounds for the diameter and height of graphs of convex polyhedra

Cited in

(7)

• Hirsch polytopes with exponentially long combinatorial segments
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• An asymptotically improved upper bound on the diameter of polyhedra
• Improving bounds on the diameter of a polyhedron in high dimensions
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Refinement to Certify Abstract Interpretations, Illustrated on Linearization for Polyhedra
• On the circuit diameter conjecture for counterexamples to the Hirsch conjecture

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436640)