Peter Mani (a photograph by Emo Welzl)
Simple polytopes, puzzles
Micha A. Perles conjectured in the ’70s that the graph of a simple -polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind and Mani and shortly afterwards I gave a simple proof which I like very much to present.
Let and be two simple d-dimensional polytopes. Let be a bijection from the vertices of to the vertices of which maps edges to edges. In other words, is an isomorphism between the graph of to the graph of . Does extend uniquely to a combinatorial isomorphism between and ? The answer is ‘yes’ but the argument is not so easy. There are also several related open problems.
A quick reminder about simple polytopes. A -polytope is simple if every vertex of is contained in edges. (Equivalently, if the dual polytope is simplicial.) Thus the graph of a simple -polytope is a -regular graph. The crucial property of simple polytopes that we use is that for every vertex of and every collection of edges of containing there is a unique -face of P which contains and these edges.
Among the famous simple polytopes are the cubes and simplices (in any dimension), polygons in the plane, and the dodecahedron in dimension 3 (but not the icosahedron or octahedron).
More background on polytopes can be found at the end of the post. (It is taken from this post presenting five open problems regarding polytopes.).
Good orderings, unique sink acyclic orientations, and shelling.
Consider a total ordering of the vertices of a simple -polytope . A vertex is a local maximum if for every neighbor of , . Of course, the maximum vertex in with respect to the ordering is a local maximum. An ordering of the vertices of is called good, if for every face of every local maximum in is the global maximum in .
( Just to make it clear: a vertex in is a local maximum in , if for every neighbor of in , . The global maximum in is the maximum vertex of with respect to .)
There are several variations of this notion. Instead of talking about the entire ordering we can talk just about the orientation it induces on edges of the graph. We orient an edge from to if . This is an acyclic orientation of the graph and being good or bad depends only on the orientation. Good orientations are called “unique-sink acyclic orientations”. Also, as we will mention later, good orderings of the vertices of a simple polytope are closely connected to shelling order on the facets of the dual polytope.
The proof: part I
Let be the graph of a simple -polytope .
The crucial claim
Given an ordering of the vertices of the polytope we define the degree of a vertex , denoted by as the number of neighbors of which are smaller than with respect to the ordering. Let be the number of vertices of degree . Consider the following expression: