Return to Colloquia & Seminar listing
55+ years of the Hirsch Conjecture
Student-Run Discrete Math Seminar| Speaker: | Edward D. Kim, UC Davis |
| Location: | 3106 MSB |
| Start time: | Wed, May 29 2013, 4:15PM |
Motivated by the efficiency of the simplex algorithm for linear programming, in 1957 Warren Hirsch conjectured that the diameter of the graph of a polytope is never more than its number of facets minus its dimension. After precisely presenting the Hirsch Conjecture, we survey the positive and negative results on the conjecture. Then, we give a complete discussion of the recent (May 2010) counterexample to the conjecture due to Francisco Santos. We end with an outlook on remaining questions, new questions, and the future of the Hirsch saga.