DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

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)