Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

PhD Exit Seminar: Combinatorial Problems Motivated by the Simplex Method

Special Events

Speaker: Zhenyang Zhang, UC Davis
Location: 3106 MSB
Start time: Thu, Jun 9 2022, 12:00PM

Title: Combinatorial Problems Motivated by the Simplex Method

Abstract: The simplex method is one of the most important algorithms for solving linear programs. Yet it is still not known whether there is a pivot rule that reaches optimum in polynomial number of steps. In fact, whether the diameter of the 1-skeleton of polytopes is bounded by a polynomial in dimension and number of constraints is still open (Polynomial Hirsch Conjecture). This talk focuses on two different topics: the counting problems on directed polytope graphs, and diameter of cocircuit graphs of oriented matroids, and discusses how they are related to Polynomial Hirsch Conjecture and the simplex method.