Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**
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 *P*with n vertices (or a subcomplex of a simplicial polytope) one can
associate a set of monomials *M*(*P*) in the variables *y*_{1}, *y*_{2}, .... .
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,
).

Back