Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

In 1957, Warren Hirsch conjectured that the graph of a $d$-dimensional polytope with $n$ facets cannot have diameter greater than $n-d$. Very few ``Hirsch-tight polytopes'' are known, where the bound $n-d$ is attained exactly. In this talk, we discuss the status of the Hirsch Conjecture as of last week. Portions of this talk are joint work with Jes\'us A. De Loera, Shmuel Onn, and Francisco Santos. The talk will be of interest to researchers in algorithms, combinatorics, geometry, graph theory, and optimization. This talk is self-contained with no prerequisites. Part one is an introduction to polytopes and everything we need will be described completely.

In part two, we present our work on diameter bounds for transportation polytopes. We prove the Hirsch Conjecture holds for a certain class of $2$-way transportation polytope. We prove a quadratic upper bound on the diameter of a certain class of $3$-way transportation polytope. We also prove that there are infinitely-many Hirsch-tight transportation polytopes. We close with a survey on diameters of faces of transportation polytopes.

In part three, we survey results on the positive and negative sides of the conjecture. For the positive side, we survey the best-known general upper bounds for all polyhedra, including the sub-exponential bound of Kalai-Kleitman and the linear bounds (in fixed dimension) by Barnette and Larman. For the negative side, we start with four variants of the Hirsch Conjecture: unbounded, monotone, topological, and combinatorial. Then, we will discuss values of $(n,d)$ where Hirsch-tight polytopes are known to exist.

This talk is part of the VIGRE RFG on Optimization.