7 - Diameter

Summary

The \textit{diameter} of a graph $G$, denoted $\diam G$, is the maximum distance between any two vertices in the graph. The \textit{diameter} of polyhedra is defined as the diameter of their graphs. While the chapter focusses on polytopes, polyhedra also feature in it.There is a connection between diameters of polyhedra and linear programming, and this is partially materialised through the \defn{Hirsch conjectures}, conjectures that relate the diameter of a polyhedra with its dimension and number of facets. We first show that the unbounded and monotonic versions of these conjectures are false (Section 7.2). Early on, Klee and Walkup (1967) realised that problems on the diameter of polyhedra can be reduced to problems on the diameter of simple polyhedra; this and other reductions are the focus of Section 7.3. We also present the counterexample of Santos (2012) for the bounded Hirsch conjecture. We then move to examine lower and upper bounds for the diameter of general polytopes and the diameter of specific polytopes. The final section is devoted to generalisations of polyhedra where diameters may be easier to compute or estimate.