On the circuit diameter conjecture

DOI10.1007/S00454-018-9995-YMaRDI QIDQ1991340zbMATH OpenOpenAlexWikidataFDO

Authors Steffen Borgwardt, Tamon Stephen, Timothy Yusun

Publication date 30 October 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

circuitdiameterHirsch conjecturepolyhedra

Mathematics Subject Classification ID

Distance in graphs (05C12) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Linear programming (90C05)

Abstract: From the point of view of optimization, a critical issue is relating the combinatorial diameter of a polyhedron to its number of facets $f$ and dimension $d$. In the seminal paper of Klee and Walkup [KW67], the Hirsch conjecture of an upper bound of $f-d$ was shown to be equivalent to several seemingly simpler statements, and was disproved for unbounded polyhedra through the construction of a particular 4-dimensional polyhedron $U_4$ with 8 facets. The Hirsch bound for bounded polyhedra was only recently disproved by Santos. We consider analogous properties for a variant of the combinatorial diameter called the circuit diameter. In this variant, the walks are built from the circuit directions of the polyhedron, which are the minimal non-trivial solutions to the system defining the polyhedron. We are able to prove that circuit variants of the so-called non-revisiting conjecture and $d$-step conjecture both imply the circuit analogue of the Hirsch conjecture. For the equivalences in [KW67], the wedge construction was a fundamental proof technique. We exhibit why it is not available in the circuit setting, and what are the implications of losing it as a tool. Further, we show the circuit analogue of the non-revisiting conjecture implies a linear bound on the circuit diameter of all unbounded polyhedra - in contrast to what is known for the combinatorial diameter. Finally, we give two proofs of a circuit version of the $4$-step conjecture. These results offer some hope that the circuit version of the Hirsch conjecture may hold in general. A challenge in the circuit setting is that different realizations of polyhedra of the same combinatorial structure may have different diameters. We adapt the notion of simplicity to work with circuits in the form of C-simple and wedge-simple polyhedra. We show that it suffices to consider such polyhedra.

Recommendations

• On the circuit diameter of some combinatorial polytopes
• On circuit diameter bounds via circuit imbalances
• scientific article; zbMATH DE number 205764
• scientific article; zbMATH DE number 147644
• On circuits in graphs
• On the circuit-cocircuit intersection conjecture
• Maximal diameter on a class of circulant graphs
• A note about the dominating circuit conjecture
• Fulkerson's conjecture and circuit covers

Cites work

• A counterexample to the Hirsch conjecture
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An enumeration of simplicial 4-polytopes with 8 vertices
• An update on the Hirsch conjecture
• Computing maximal copies of polyhedra contained in a polyhedron
• Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\)
• Diameter of polyhedra: limits of abstraction
• Edge-graph diameter bounds for convex polytopes with few facets
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
• Hirsch polytopes with exponentially long combinatorial segments
• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3365043 (Why is no real title available?)
• Many polytopes meeting the conjectured Hirsch bound
• More bounds on the diameters of convex polytopes
• More polytopes meeting the conjectured Hirsch bound
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the circuit diameter of dual transportation polyhedra
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The d-Step Conjecture and Its Relatives
• The circuit diameter of the Klee-Walkup polyhedron
• The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The hierarchy of circuit diameters and transportation polytopes
• The Hirsch conjecture is true for (0,1)-polytopes
• The width of five-dimensional prismatoids

Cited in

(11)

• A polyhedral model for enumeration and optimization over the set of circuits
• On circuit diameter bounds via circuit imbalances
• Circuit walks in integral polyhedra
• The circuit diameter of the Klee-Walkup polyhedron
• On the circuit diameter of some combinatorial polytopes
• scientific article; zbMATH DE number 205764 (Why is no real title available?)
• Constructing Clustering Transformations
• On the Combinatorial Diameters of Parallel and Series Connections
• Circuits in extended formulations
• On circuit diameter bounds via circuit imbalances
• On the hardness of short and sign-compatible circuit walks

This page was built for publication: On the circuit diameter conjecture

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