3 Combinatorial Structure

In this section we collect problems that are concerned with computing certain combinatorial information from compact descriptions of the combinatorial structure of a polytope. Such compact encodings might be the vertex-facet incidences, or, for simple polytopes, the abstract graphs. An example of such a problem is to compute the dimension of a polytope from its vertex-facet incidences. Initialize a set S by the vertex set of an arbitrary facet. For each facet F compute the intersection of S with the vertex set of F. Replace S by a maximal one among the proper intersections and continue. The dimension is the number of "rounds" performed until S becomes empty.

All data is meant to be purely combinatorial. For all problems in this section it is unknown if the "integrity" of the input data can be checked, proved, or disproved in polynomial time. For instance, it is rather unlikely that one can efficiently prove or disprove that a lattice is the face lattice of some polytope (see Problems 30, 31).

Sometimes, it might be worthwhile to exchange the roles of vertices and facets by duality of polytopes. Our choices of view points have mainly been guided by personal taste.

Some orientations of the abstract graph G_P of a simple polytope P play important roles (although such orientations can also be considered for non-simple polytopes, they have not yet proven to be useful in the more general context). An orientation is called a unique-sink orientation (US-orientation) if it induces a unique sink on every subgraph of G_P corresponding to a non-empty face of P. A US-orientation is called an abstract objective function orientation (AOF-orientation) if it is acyclic. General US-orientations of graphs of cubes have recently received some attention (Szabó and Welzl [63]). AOF-orientations were used, e.g., by Kalai [35]. Since their linear extensions are precisely the shelling orders of the dual polytope, they have been considered much earlier.

Why are some symbols not displayed correctly?