Telling a Simple Polytope From its Graph

Posted on January 16, 2009 by Gil Kalai

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^<$ .

Let $f$ be the number of nonempty faces of $P$ .

Claim: 1) $f^< \ge f$

2) Equality holds if and only if $<$ is a good ordering.

Proof: Let $<$ be an ordering of the vertices of $G$ . We will count pairs $(F,v)$ where $F$ is a face of $P$ and $v$ is a vertex in $F$ which is a local maximum with respect to $<$ .

The first thing to note is that if $v$ is a vertex of degree $k$ then it is a local maximum in precisely $2^k$ faces. Therefore the number of pairs is precisely $f^< =$ $h_0^< +2 h_1^<+ \dots + 2^kh_k^< + \cdots +2^nh_n^<$ .

On the other hand, every face $F$ of the polytope has a vertex which is a local maximum with respect to $<$ . This is the vertex of $F$ which is the global maximum! If $<$ is a good ordering then every face $F$ contributes a unique vertex $v$ which is a local maximum and therefore $f^< = f$ . If $<$ is not a good ordering then every face $F$ contributes at least one local maximum and at least one face $F$ contributes more than one! Therefore $f^< > f$ . Sababa!

Telling the number of faces and the good orderings

Now we can tell the total number of faces of $P$ by looking at the graph $G$ . We compute the value $f^<$ for every ordering of the vertices of $G$ . The minimum value over all orderings $<$ is the value of $f$ – the number of non-empty faces of $P$ .

We can tell also the good orderings. We compute the quantity $f^<$ for every ordering $<$ of the vertices of the polytope and identify the minimum value $f$ . Now, $f$ must be the number of faces of the polytope $P$ . By the claim an ordering $<$ is a good ordering if and only if $f^<=f$ .

The proof: part II

Telling the faces

Let $F$ be a $k$ -dimensional face of $P$ and let $H$ be its graph. $F$ is itself a $k$ -dimensional polytope. What do we know about $H$ ? It is a k-regular graph. In fact it is an induced subgraph of $G(P)$ . (Recall that $H$ is an induced subgraph of a graph $G$ if $H$ consists of a subset of the vertices of $G$ and all the edges of $G$ on these vertices.)

Claim: An induced connected k-regular subgraph H of G(P) is the graph of a face if and only if its vertices come first in some good ordering of $P$ .

Proof: There are two directions to prove. We start by showing that the graph of a $k$ -face $F$ is an induced connected $k$ -regular subgraph of $G$ and there is a good ordering that starts with the vertices of $F$ . Suppose that $F$ is a $k$ -face of $P$ . The graph of a face is always an induced subgraph of the graph of the polytope. Next, there is a linear functional $\phi$ on $R^d$ whose minimum on the polytope $P$ is attained precisely at $F$ . (This is essentially the definition of a face: a face is the intersection of the polytope with a supporting hyperplane, and we can take $\phi$ to be a linear functional that vanishes on $H$ and hence also on $F$ .) Now we can perturb $\phi$ a little so that it will attain different values on the vertices of $F$ , and such that all these values are still smaller than the values on all other vertices.

Now suppose that $H$ is an induced connected $k$ -regular graph and that $<$ is a good ordering such that the vertices of $H$ are smaller with respect to $<$ than all other vertices. Let $w$ be the largest vertex of $H$ w.r.t. $<$ . Now $deg(w) = k$ and therefore $w$ is a local maximum in the $k$ -face $F$ which is spanned by the $k$ edges of $H$ containing $w$ . Since $<$ is a good ordering, $w$ is a the global maximum vertex of $F$ . It follows that all the vertices of $F$ are vertices of $H$ . (Because the vertices of $H$ are precisely all the vertices that are smaller than $w$ with respect to the ordering.) Therefore $G(F)$ , the graph of $F$ , is a $k$ -regular subgraph of $H$ . But note that the only $k$ -regular subgraph of a connected $k$ -regular graph is the graph itself! Therefore, the vertices of $H$ are the vertices of the face $F$ . Sababa!

Further results

There are various other results about reconstructions of the entire combinatorial structure of a $d$ -polytope from partial information. My chapter on graphs and skeleta of polytopes in the “Handbook of discrete and computational geometry” contains several further such results. See also the new edition of Grunbaum’s classic book “Convex Polytopes“.

Let me mention two results: Hassler Whitney proved that the graph of a every 3-dimensional polytope determines its faces. The faces are simply the induced non-separating cycles. A theorem of Micha A. Perles asserts that the [ $d/2$ ]-dimensional skeleton of a simplicial $d$ -polytope determines the entire combinatorial structure.

Friedman’s result

The algorithm to tell the polytope from a graph is simple but terrible. To start you have to consider all the orderings of the vertices of the polytope. All other theorems about reconstruction of the entire combinatorial structure of a polytope from partial information give simple polynomial algorithms.

Is there a polynomial time algorithm for telling the polytope from its graph? Eric Friedman proved a startling theorem asserting that there is a polynomial algorithm! (It deserves a whole separate post.)

A dual form: puzzles.

Let $K$ be a pure $d$ -dimensional simplicial complex. The puzzle of $K$ , denoted by $puzz(K)$ is the graph whose vertices are the facets of $K$ (a facet =a maximal face) and two facets are adjacent if their intersection is $(d-1)$ -dimensional. (The puzzle is precisely the same graph we associated to families of sets in the longish series of posts about Hirsch’s conjecture.)

Blind-Mani’s theorem stated in a dual form asserts that simplicial polytopes are determined by their puzzles and this is the way Blind and Mani stated it. We can talk also about puzzles where the pieces are themselves complicated polytopes which come with instructions how to glue two pieces locally, and ask if there is a unique global solution. (If the pieces are simplices, then all ways to glue them along facets are the same.) This was studied by Michael Joswig.

The first part of the proof described above asserts that for shellable simplicial complexes, the shelling orders, the total number of faces, and (by a slight extension of the proof) the f-vector are determined by the puzzle. In fact, the proof gives the following claim.

Claim: Let $K$ and $L$ be two pure $d$ -dimensional simplicial complexes. Suppose that $puzz(K) =puzz(L)$ and that $K$ is shellable. Then $f_i(K) \ge f_i(L)$ for every $i$ .

It is not always true that for shellable complexes the entire complex is detemined by the puzzle. Here are two 2-dimensional shellable complexes with the same puzzle. (A reminder of the notion of shellability is given below.)

Problems:

Spherical puzzles

Conjecture 1: A spherical puzzle always has a unique solution!

(By a spherical puzzle we mean a puzzle of a triangulation of a $d$ -dimensional sphere.)

Conjecture 2: The puzzle of a $d$ -dimensional Cohen-Macaulay simplicial complex $K$ determines the $f$ -vector of $K$ .

Conjecture 3:Let $K$ and $L$ be two pure $d$ -dimensional simplicial complexes. Suppose that $puzz(K)=puzz(L)$ and that $K$ is Cohen-Macaulay. Then $f_i(K) \ge f_i(L)$ for every $i$ .

The Cohen-Macaulay property can be regarded as an algebraic generalization of “shellability” (just like vanishing homology is an algebraic generalization of “collapsibility”). Triangulations of spheres are Cohen-Macaulay simplicial complexes.

Characterizing the facets.

Conjecture 4: Let $G$ be the graph of a simple 4-dimensional polytope. Then a 3-regular induced subgraph $H$ of $G$ is the graph of a facet if and only if it is planar and non-separating.

An even stronger conjecture proposed by Perles (where $H$ is not assumed to be planar) was refuted by Christian Haase and Gunter M. Ziegler. Here is a modelby Nikolaus Witte of their example.

Conjecture 5: Let $G$ be the graph of a 4-dimensional spherical puzzle. Then a 3-regular induced subgraph of $G$ corresponds to the link of a vertex if and only if it is planar and non-separating.

We can also ask similar questions for puzzles of simplicial manifolds. Puzzles of general triangulated closed surfaces do not determine the triangulations; note that the puzzle of the 6-vertex triangulation of the real projective plane (which is the Peterson graph) has more automorphisms than the entire triangulation has!

And here is a conjecture (that we will not explain here) which is a little analogous to the conjecture that the f-vectors of Cohen-Macaulay complexes are determined by the puzzles.

Kazhdan-Lusztig polynomials.

Conjecture (Lusztig): For intervals of the Bruhat order of Coxeter groups the Kazhdan-Lusztig polynomial can be read from the Bruhat interval. (In other words, two isomorphic intervals have the same Kazhdan-Lusztig polynomials.)

Reminder: shellability

We say that a $d$ -dimensional pure polyhedral complex is shellable if its maximal faces (facets) can be ordered by a sequence $F_1,F_t,\dots ,F_t$ such that for every $k$ , $1 < k \le t$ , the intersection of $F_k$ with the union of $F_1,\dots,F_{k-1}$ is homeomorphic to a $(d-1)$ -dimensional ball or sphere. This condition implies that the entire complex is homeomorphic to a sphere or a ball. (We mentioned shellability here and here.)

For simplicial complexes, shellability is especially simple and becomes a purely combinatorial condition. The intersection of $F_k$ with the previous facets should be a (nonempty) union of some (or all) of its own facets. In a shelling sequence of facets, adding $F_k$ to the simplicial complex $K_k$ generated by $\{F_1,F_2,\dots,F_{k-1} \}$ has a very simple form. We add to $K_k$ a subset $S_k \subset F_k$ and all sets that contain $S_k$ which are contained in $F_k$ . If $|S_k| =m$ we say that adding $F_k$ is a shelling step of type $m$ .

If $P$ is a simplicial polytope then a shelling order on the facets of $P$ amounts to good ordering on the vertices of the dual polytope. The type of a facet in the shelling is the degree of the corresponding vertex in the good ordering.

The fact that the boundary complex every $d$ -polytope is shellable was assumed in 19th century proofs of Euler’s theorem in high dimension but it was first proved by Bruggesser and Mani in 1970. Peter Mani once told me that he found a crucial ingredient of the proof in a dream.

Reminder: background

A convex polytope is the convex hull of a finite set of points in an Euclidean space. A proper faceof a polytope P is the intersection of P with a supporting hyperplane. The empty face and P itself are regarded as trivial faces. The convex hull of a set of points which affinely span a d-dimensional space is a d-dimensional polytope or briefly a d-polytope. Faces of polytopes are themselves polytopes, a k-face is a short way to say k-dimensional face. 0-faces are called vertices, 1-faces are called edges and (d-1)-faces of a d-polytope are called facets. The set of faces of a polytope is a POSET (=partially ordered set) which is a “lattice”, “atomic”, and “graded”. For a polytope P $f_k(P)$ denotes the number of k-faces of P. The f-vector of P is the vector $(f_{-1}(P),f_0(P),f_2(P), \cdots , f_d(P))$ . Two d-polytopes P and Q are combinatorially equivalent if there is a bijection between the faces of P and the faces of Q which preserves the order relation.

The simplest d-polytope is the simplex: the convex hull of d+1 affinely independent points. The face lattice (=POSET of faces) of a simplex is just the Boolean lattice. A d-polytope is simplicial if all its proper faces are simplicies. A polytope is simple if its dual is simplicial or, equivalently, if every vertex is included in precisely d edges. A d-polytope is k-simplicial if all its k-faces are simplices. (Here d>k.) The d-cube is the convex hull of all vextors of length d with entries +1/-1.

The five open questions in this post belong to the combinatorial theory of polytopes that deal with the set of faces of polytopes. (There are also interesting metrical and arithmetic questions about polytopes.)

If P is a convex polytope which contains the origin in its interior, the polar dual of P is the set of all points y so that $<x,y> \le 1$ for every $x \in P$ . There is a 1-1 order reversing bijection between the faces of P and the faces of its polar.

A polytope P is centrally symmetric if whenever x belongs to P so is -x.

This entry was posted in Convex polytopes, Open problems and tagged Eric Friedman, Peter Mani, Roswitta Blind. Bookmark the permalink.

10 Responses to Telling a Simple Polytope From its Graph

Gil Kalai says:

January 21, 2009 at 7:49 pm

Let me also mention that Friedman’s polynomial algorithm uses an earlier result by Joswig, Kaibel, and Korner who provided a “polynomial certificate” for the problem. Joswig, Kaibel, and Korner introduced a pair of combinatorial optimization problems which is used in Friedman’s proof.

Reply
Daniel Gertsch says:

November 30, 2010 at 9:34 pm

The p-polytope proof can be considered different: A reduction of A to A’ is simply the reduction of G(p)=p :=: G(Q)=Q to G(x1,x2,x3,…)=x1,x2,x3,… and therefore n-1 in complexity and n-1=x for n=x+1 which means that the polytope is not determined if it determines not the figure with vertices 1 in addition. But this is a contradiction for P(X)=X and P(X)=X+1 for complexity n of P(X)=X or X+1 and invaluable for proof.

Reply
Pingback: Is Backgammon in P? | Combinatorics and more
Pingback: Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? | Combinatorics and more
Pingback: Updates and plans III. | Combinatorics and more
Pingback: The beginnings of Shellability - Quantum Calculus
Gil Kalai says:

October 9, 2018 at 3:29 pm

Conjecture 4 is false. This was proved by Joseph Doolittle in his paper A minimal counterexample to a strengthening of Perles’ conjecture .

Reply
Pingback: To cheer you up in difficult times 26: Two real-life lectures yesterday at the Technion | Combinatorics and more
Andrew Sack says:

August 19, 2022 at 7:14 pm

Are you aware of any software that implements Friedman’s algorithm?

Reply
Pingback: Updates and Plans IV | Combinatorics and more

	Gil Kalai on Physics Related News: Israel J…
	My Notices AMS Paper… on Three Remarkable Quantum Event…
	My Notices AMS Paper… on The Quantum Computer Puzzle @…
	My Notices AMS Paper… on Random Circuit Sampling: Fouri…
	My Notices AMS Paper… on Photonic Huge Quantum Advantag…
	My Notices AMS Paper… on Ordinary computers can beat Go…
	My Notices AMS Paper… on Amazing: Feng Pan and Pan Zhan…
	Gil Kalai on Three Remarkable Quantum Event…
	Arturo Merino, Torst… on Updates from Cambridge
	ryeguy10 on Updates from Cambridge
	Gil Kalai on Updates from Cambridge
	Gil Kalai on Updates from Cambridge