Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:****Andrew Baxter**, Rutgers University, baxter{at} math [dot] rutgers [dot] edu**Lara Pudwell**, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu**Doron Zeilberger**, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: The Diameter Problem for Convex Polytopes

Speaker: **Gil Kalai**, The Hebrew University of Jerusalem

Date: Thursday, October 2, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The famous Hirsch Conjecture asserts that the diameter of graphs of d-polytopes with n facets is at most n-d. We will discuss this question, connections to linear programming, and progress that was made since it was posed in the late 50s. Specifically I would like to discuss:

a) Developing different/better strategies for moving between vertices. b)Creating a more sophisticated way to get an upper bound on the diameter c) Can these processes be automatized? Can they be made "quasi-automatic" (in the sense of Gowers)?

(Note: This is an abbreviated abstract. For the full abstract, see http://math.rutgers.edu/~baxter/expmath/KalaiFull.html)