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

Prof. Emo Welzl and Prof. Bernd Gärtner

**
Enumeration of faces of polytopes: the current state of affairs
**

**
Billera Louis J., Cornell University**

The enumerative theory of convex polytopes is rich with numerical
invariants related to the problem of counting faces or chains of
faces (*flags*). Most basic of these invariants is the flag
*f*-vector, which counts the number of flags having any possible
dimension set. The simplest components of this make up the
ordinary *f*-vector, counting faces in each dimension.
While the theory of the *f*-vector has been complete for
twenty years in the case of simplicial and simple polytopes,
the situation for general polytopes remains unsettled.

In recent years, there have been a number of advances in this
area. In addition to the flag *f*-vector, two other invariants,
each expressible in terms of the flag *f*-vector, have attracted
much attention. The *g*-polynomial of MacPherson and Stanley
is derived from the intersection homology Betti numbers of the
toric variety associated to a rational polytope, while the
**cd**-index of Bayer, Fine and Klapper gives a concise
description of the linearly independent components of the flag
*f*-vector. Each of these invariants is known to be nonnegative,
as well as to satisfy other monotonicity properties, at least
for rational polytopes.

We define these invariants and discuss some of the more recent
developments. We speculate on the situation for dimension 4 as
well as on possible geometric properties related to inequalities
satisfied by all flag *f*-vectors.

Back