Thursday, May 6 2021
2:45pm - 3:15pm
Operations Research Seminar
The Hirsch Conjecture under 2-Sums

The Hirsch Conjecture is a well-known, but disproven conjecture in polyhedral theory pertaining to the diameter of a polytope’s skeleton. However, there are still many classes of polyhedra for which it is unknown whether or not they satisfy the Hirsch Conjecture, including some common classes of polyhedra such as those defined through a totally-unimodular matrix.

In this talk, we present an introduction to the combinatorial diameter and the Hirsch Conjecture. Then we discuss some ongoing work on the so-called 2-sum of polyhedra, an important operation for the construction of totally-unimodular matrices, and partial results on the Hirsch bound being preserved under the 2-sum.
Speaker:Weston Grewe
Affiliation:University of Colorado Denver

Download as iCalendar