The Life and Death of the Hirsch Conjecture

The simplex method for maximizing a linear functional on a polytope is to simply start at a vertex, and then move to an adjacent vertex on which the functional takes a larger value, and then repeating. A question of interest for both academic and practical purposes is how fast this algorithm can be made to be. The sticking point to this question is the number of steps to be made - starting from a vertex on a polytope, how many steps must be made to reach the target vertex? The Hirsch conjecture, for which a counterexample was recently found, was an attempt to provide a strong upper bound on the number of steps. I will discuss the construction of the counterexample, and several natural questions that still remain unanswered.