Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
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
