On the circuit diameters of polyhedra

In this thesis we develop a framework to study the circuit diameters of polyhedra. The circuit diameter is a generalization of the combinatorial (edge) diameter, where walks are permitted to enter the interior of the polyhedron as long as steps are parallel to its circuit directions. Because the circuit diameter is dependent on the specific realization of the polyhedron, many of the techniques used in the edge case do not transfer easily. We reformulate circuit analogues of the Hirsch conjecture, the d-step conjecture, and the non-revisiting conjecture, and recover some of the edge case relationships in the circuit case. To do this we adapt the notion of simplicity to work with circuit diameter, and so we define C-simplicity and wedge-simplicity. Then, we prove the circuit 4-step conjecture, including for unbounded polyhedra, by showing that the original counterexample U4 to the combinatorial analogue satisfies the Hirsch bound in the circuit case, independent of its realization. This was the first known counterexample to Hirsch, and several families of counterexamples are constructed from U4. In particular, the unbounded Hirsch conjecture could still hold in the circuit case. We also use computational methods to study Q4, the bounded counterpart to U4, and give two realizations with different circuit diameters. It remains open whether Q4 is circuit Hirsch-sharp; however, we are able to lower the distance bound for at least one direction between the two far vertices of Q4. Finally, we present some auxiliary results involving representations of polyhedra and circuit calculations.