Theory of Combinatorial Algorithms, Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich

No Title

Variations on the upper bound theorem

Gil Kalai, Hebrew University of Jerusalem

The upper bound theorem (UBT) asserts that among all the d-polytopes with n vertices the cyclic polytope C(d,n) have the maximum number of k-faces for every k between 1 and d-1.

This was conjectured by Motzkin and proved by McMullen. The cyclic polytopes are not the only examples for equality. Equality holds for all neighborly polytopes. Stanley proved the UBT for all simplicial (d-1)-dimensional spheres. Novik proved the UBT even for large classes of (d-1)-dimensional simplicial manifolds.

In the talk I explained Stanley's general approach in the language of Grobner bases (or algebraic shifting). For every simplicial polytope Pwith n vertices (or a subcomplex of a simplicial polytope) one can associate a set of monomials M(P) in the variables y₁, y₂, .... . The number of k-faces of P can easily be read from the number of monomials of degree k+1 of M(P) and the crucial fact is that always M(P) is a SUBSET of the set of monomials associated to the cyclic polytopes.

This not only gives the UBT but a very strong extension (of Kruskal-Katona type) which give an upper bound for the number of k-faces given the number of (k-1)-faces. We call this extension the Generalized upper bound theorem (GUBT).

Before telling how general we believe the GUBT might be let me mention the following conjecture of Imre Barany which (shamefully) we cannot answer: The number of k-faces of a d-polytope is at least the minimum of the numbers of vertices and facets.

It is believed that the GUBT applies not only to simplicial spheres but also to simplicial manifolds with vanishing middle homology (in particular, to odd-dimensional simplicial manifolds). And even to a large class of pseudomanifolds with vanishing middle (intersection) homology (the so called Witt spaces).

Moreover, it is also conjectured that the GUBT applies to general polytopes (simplicial or not). This will not only imply Barany's conjecture mentioned above but will show (using an argument of Bjorner) that the face numbers of all d-polytopes are unimodal in the lower and upper quarters of the face numbers (namely, $f_0 \le f_1 \le ...\le f_{d/4}$ ).

Back