Can we realize a graph as the skeleton of a polytope that has the same symmetries?

Question

Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton.

A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $G$, if for each graph-automorphism $\phi\in\mathrm{Aut}(G)$ there is an isometry of $\Bbb R^n$ inducing the same automorphism on the edges and vertices of $P$.

Question: Let $G$ be the 1-skeleton of a polytope. Is there a realization of $G$ that realizes all its symmetries?

Note that if we know $G$ to be the skeleton of an $n$-polytope, then the symmetric realization does not have to be of the same dimension. In fact, this is not always possible. The complete graph $K_n,n\ge 6$ is realized as a neighborly 4-polytope, but its only symmetric realization is the simplex in $n-1\ge5$ dimensions. However, this is the only example I know of.

One way to construct a counter-example would be to find an $n$-polytope with a skeleton $G$ that is not more than $n$-connected (e.g. $n$-regular), but where $\mathrm{Aut}(G)$ is no subgroup of the point group $O(n)$. Its symmetric realization must be in dimension $\ge n+1$, but it cannot be because of Balinski's theorem.

Answer 1

A counterexample is giving by the edge graph of the dual to the polytope of Bokowski, Ewald and Kleinschmidt, described in Gil Kalai's answer. Let $P$ be the BEK polytope, let $P^{\vee}$ be its dual and let $G$ be the edge graph of $P^{\vee}$. The polytope $P$ is simplicial so $P^{\vee}$ is simple and its edge graph $G$ is $4$-regular. The symmetry $\phi$ in BEK is a symmetry of the simplicial complex $\partial P$, so it induces a symmetry of $G$.

By a theorem of Gil Kalai, any $4$-polytope $Q$ with edge graph $G$ is combinatorially isomorphic to $P^{\vee}$. So the dual polytope $Q^{\vee}$ of such a $Q$ would be combinatorially isomorphic to $P$. If $\phi$ were realized by a linear symmetry of $Q$, then this would induce a linear symmetry of $Q^{\vee}$, contradicting the result of Bokowski, Ewald and Kleinschmidt.

It remains to check that $G$ is not the edge graph of a polytope in some dimension $d \neq 4$. Since $G$ is $d$-regular, we would have to have $d<4$ and $d \leq 2$ is clearly impossible. According to Mathematica's PlanarGraphQ function, $G$ is not a planar graph, so it is not the edge graph of a $3$-polytope.

For those who want to experiment on their own, here are the facets (vertices numbered 0 through 9) of $P$:

{{1,2,3,7}, {1,2,4,8}, {9,2,3,8}, {9,2,0,7}, {1,3,4,7}, {2,3,4,8}, {9,3,0,8}, {2,3,0,7}, {1,4,6,7}, {1,5,6,8}, {9,0,6,8}, {9,5,6,7}, {4,5,6,7}, {1,4,5,8}, {0,5,6,8}, {9,0,5,7}, {1,2,6,7}, {1,2,6,8}, {9,2,6,8}, {9,2,6,7}, {3,4,5,7}, {3,4,5,8}, {3,0,5,8}, {3,0,5,7}, {1,4,5,6}, {1,2,3,4}, {9,0,5,6}, {9,2,3,0}}

and the edges of $G$ (vertices numbered 1 through 28).

{{5, 1}, {6, 2}, {6, 3}, {7, 3}, {8, 1}, {8, 4}, {9, 5}, {11, 7}, {13, 9}, {13, 12}, {14, 2}, {14, 10}, {15, 10}, {15, 11}, {16, 4}, {16, 12}, {17, 1}, {17, 9}, {18, 2}, {18, 10}, {18, 17}, {19, 3}, {19, 11}, {19, 18}, {20, 4}, {20, 12}, {20, 17}, {20, 19}, {21, 5}, {21, 13}, {22, 6}, {22, 14}, {22, 21}, {23, 7}, {23, 15}, {23, 22}, {24, 8}, {24, 16}, {24, 21}, {24, 23}, {25, 9}, {25, 10}, {25, 13}, {25, 14}, {26, 1}, {26, 2}, {26, 5}, {26, 6}, {27, 11}, {27, 12}, {27, 15}, {27, 16}, {28, 3}, {28, 4}, {28, 7}, {28, 8}}

The symmetry $\phi$ switches $1 \leftrightarrow 9$, $7 \leftrightarrow 8$, $0 \leftrightarrow 4$ and fixes $2$, $3$, $5$, $6$. Here is a drawing of $G$:

Answer 2

This is true for 2- and 3-dimensional polytopes. The 2-dimensional case is the trivial observation that there exists regular polygons.

For the 3-dimensional case, Steinitz' theorem characterizes 1-skeleta of 3-dimensional polyhedra as 3-connected planar graphs. Whitney proved that a 3-connected graph has a unique planar embedding. Hence any symmetry of the graph extends to a combinatorial symmetry of the polyhedron.

The circle packing proof of Steinitz' theorem implies that there is a realization of a polyhedron which is unique up to projective transformations preserving the sphere on which the circle packing lies.

This is $PO(3,1;\mathbb{R})\leq PGL_4(\mathbb{R})$, the isometries of hyperbolic space. There is an associated hyperbolic polyhedron whose faces lie in geodesic planes bounding the circles corresponding to the vertices and faces of the planar graph embedding, and has right angles and ideal vertices. Taking the barycenter of this polyhedron at the center of the ball model of hyperbolic space gives a polyhedral realization in which all symmetries are rotations. Hence the symmetry group of the graph extends to this polyhedron.

Addendum: As pointed out in Gil Kalai's answer, this was originally proved here:

Mani, P., Automorphismen von polyedrischen Graphen, Math. Ann. 192, 279-303 (1971). ZBL0206.51402. MR0296808.

Answer 3

There is an example of Bokowski, Ewald and Kleinschmidt of a 4-polytope with a certain symmetry of the graph that cannot be realized geometrically. The combinatorial construction is due to Kleinschmidt and the method for realizing it as a polytope were developed by Bokowski and Ewald. (Positive answer for d=3 and when the number of vertices is $d+3$ were fist proved by Mani and Perles respectively.)

correction:

What is known in BEK's example is that a certain automorphism $\phi$ of the combinatrial structure cannot be realized geometrically. It is possible that for other polytopes with the same graph the graph automorphism described by $\phi$ can be realized geometrically. (See comments below.)