Thesis Defence: Polytopes of minimal circuit diameter

Jeremiah Yoder, supervised by Dr. Amy Wiebe, will defend their thesis titled “Polytopes of minimal circuit diameter” in partial fulfillment of the requirements for the degree of Master of Science in Mathematics.

An abstract for Jeremiah Yoder’s thesis is included below.

Defences are open to all members of the campus community as well as the general public. Please email amy.wiebe@ubc.ca to receive the Zoom link for this defence.

---

Abstract

Finding the optimal point in a feasible region, such as an n-dimensional polytope, is foundational to the field of optimization. Circuits, the set of all potential edges of a polyhedron, provide us a way to travel the feasible region in search of optimality. This thesis explores the circuit diameter, a generalization of combinatorial diameter using circuits, of certain polytopes, focusing on when the circuit diameter is small and what criteria for small circuit diameter exist. Such classifications of polytopes with small circuit diameter may indicate when a circuit-based optimization algorithm would be preferred.

In this thesis, we use counting arguments and a few general results on circuits to classify when a polytope may have circuit diameter 1. We show that in two dimensions circuits have special properties and there are unique classes of polytope with circuit diameter 1 under affine transformation, which depend on number of vertices. We also provide a way to construct these 1-circuit polygons. We examine polytopes in three dimensions, where the construction and interaction of circuits becomes more complicated. We consider several common classes of 3-dimensional polytopes to determine when we can construct them to have small circuit diameter. We then expand our results to higher dimensions and study some of the generalized polytopes from lower dimensions. We finish with some numerical results of algorithms which calculate circuits of a polytope and generate our 1-circuit polygons.