9/22/2004

Gil Kalai
Hebrew and Yale University

The Upper Bound Theorem for Convex Polytopes

The upper bound theorem proved by McMullen in 1970 asserts that among all d-dimensional polytopes with n vertices the CYCLIC d-polytope with n vertices has the maximum number of k-dimensional faces for every k. Our tour of the combinatorics and algebra related to the upper bound theorem will proceed along the following stops:
1. h-numbers and abstract objective functions. (A certain linear combinations of face numbers is the right object to study.)
2. face rings and generic initial ideals. (A simple but fruitful algebraic constructions.)
3. The g-theorem and the g-conjecture: (A complete description of face numbers of simplicial polytopes and spheres.)
4. How far does the upper bound theorem extend. (From spheres to manifolds, and perhaps to a large class of pseudomanifolds.)
5. Fractional Helly theorems. A homological analog of VC-dimension? (A qualitative version of the upper bound theorem have remarkable combinatorial consequences. How far can we go?)
6. Polyhedral complexes and general polytopes: where are the rings? (Moving from the simplicial to polyhedral case offers new mysteries.)
If time allowas we will mention Welzl's and Khovanskii's extensions and discuss the related problem of counting Nash equilibrium points.