Date: Thursday, October 2, 2008
Speaker: Gil Kalai, The Hebrew University of Jerusalem
Title: The Diameter Problem for Convex Polytopes
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, connection to linear programming, and progress that was made since it was posed in the late 50s. Most progress regarding upper bounds is based on the following steps:
1) Vast abstraction of the problem,
2) Simple combinatorial strategies to create a path between two vertices,
3) Finding recursive estimates based on the strategy,
4) solving the recursion.

The challenges I would like to talk about are:
(a) Can we come up with a different/better strategy for moving between two vertices?
(b) Can we think about a mathematically more sophisticated way to get an upper bound for the diameter?
(c) Can this process of *finding a strategy/writing the associated recurrence/solving the recurrence *be automatized? The type of proofs wewill describe are very simple and this looks like a nice example for a "quasi-automatic" (href="http://gowers.wordpress.com/2008/07/28/more-quasi-automatic-theorem-proving/) proof process.

The third question is related to a debate I have with the host of the seminar (D.Z.). While Zeilberger sees computers' prominent role in the future as "symbol crunchers" leaving humans to do "idea crunching" (that computers cannot do) I think this distinction may well be artificial.

More can be read about it in the posts on my blog:

http://gilkalai.wordpress.com/2008/07/30/a-diamater-problem-for-families-of-sets/"
http://gilkalai.wordpress.com/2008/08/31/a-diameter-problem-2/
http://gilkalai.wordpress.com/2008/09/07/diameter-problem-3/
http://gilkalai.wordpress.com/2008/09/09/diameter-problem-4/
http://gilkalai.wordpress.com/2008/09/16/a-diameter-problem-5/
and the last point may be related also to
http://gilkalai.wordpress.com/2008/06/25/amir-ban-on-deep-junior/