Telling a Simple Polytope From its Graph

Peter Mani  (a photograph by Emo Welzl)

Simple polytopes, puzzles


Micha A. Perles conjectured in the ’70s that the graph of a simple d-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 P and Q be two simple d-dimensional polytopes. Let \psi be a bijection from the vertices of P to the vertices of Q which maps edges to edges. In other words, \psi is an isomorphism between the graph G(P) of P to the graph G(Q) of Q. Does \psi extend uniquely to a combinatorial isomorphism between P and Q? The answer is ‘yes’ but the argument is not so easy. There are also several related open problems.

Eric Friedman


A quick reminder about simple polytopes. A d-polytope P is simple if every vertex v of P is contained in d edges. (Equivalently, if the dual polytope P^* is simplicial.) Thus the graph G(P) of a simple d-polytope P is a d-regular graph. The crucial property of simple polytopes that we use is that for every vertex v of P and every collection of k edges of P containing v there is a unique k-face of P which contains v and these k 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 d-polytope P .  A vertex v is a local maximum if for every neighbor w of v, w<v. Of course, the maximum vertex in P with respect to the ordering is a local maximum.   An ordering of the vertices of P is called good, if for every face F  of P every local maximum in F is the global maximum in F.

( Just to make it clear: a vertex v in F is a local maximum in F, if for every neighbor w of v in F, w<v. The global maximum in F is the maximum vertex of F 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 \{v,u\} from v to u if v < u. 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 G be the graph of a simple d-polytope P.

The crucial claim

Given an ordering < of the vertices of the polytope  we define the degree of a vertex v, denoted by deg_<(v)  as the number of neighbors of v which are smaller than v with respect to the ordering. Let h_k^< be the number of vertices of degree k. Consider the following expression:

f^< = h_0^< +2 h_1^< + \dots + 2^kh_k^< + \cdots +2^nh_n^<

Continue reading