Are there examples of d-regular graphs (i.e. graphs where every node has exactly d adjacent nodes) which are not the 1-skeleton of a simple convex polytope?


New version of the question: is there an example of a d-dimensional "simple" poset, i.e. a collection of k-dimensional "faces" with $k=0, 1, \dots, d$ equipped with partial ordering such that its 1-dimensional skeleton is a d-regular graph, which is not the face lattice of a convex polytope? (Obviously the partial order is to be interpreted as $X < Y$ if $X$ is contained in the boundary of $Y$).

It seems to be that the graph of the previous answer ($K_{3,3}$) cannot be interpreted as the 1-skeleton of a 3-dimensional simple poset.


By convex polytope I mean the intersection of several half-spaces given by linear inequalities. The boundaries of a convex polytope are themselves convex polytopes, the full collection of these boundaries of any co-dimension define the face lattice of the polytope.

We can represent the combinatorics of the face lattice of a d-dimensional convex polytope by giving the collection of its facets $F=\{X_1, \dots, X_F\}$ and vertices $V=(v_1, \dots, v_n)$ and representing each vertex as the intersection of at least $d$ facets, e.g. we can write $v_j = (X_{j_1}, \dots, X_{j_d})$ to say that vertex $v$ lies in the intersection of faces $X_{j_1}, \dots, X_{j_d}$. In particular if the polytope is simple, every vertex will be presented as the intersection of $precisely$ $d$ facets. I am only interested in this case, so let me assume that the set $V$ is always a set of $d$-tuples of elements in $F$.

From this data, we can read all the face lattice structure: two facets $X_a$ and $X_b$ intersect in the polytope if and only if there is at least one vertex containing both. Each facet $X_a$ is itself a polytope whose combinatorial data can be presented in the same way, i.e. by listing all the facets $X_b$ intersecting with $X_a$ and all the vertices lying on $X_a$. Clearly we can iterate down to any dimension.

Now suppose you are given a set of data $(F,V)$, and you are asked to understand wether there exists a simple polytope whose face lattice is given by $(F,V)$. You can do a number of combinatorical and topological checks on $(F,V)$: you can compute the euler characteristic and check that is 1, or you can compute all the homological groups of $(F,V)$ and see that they are compatible with those of a convex set. Admittedly, I do not know what is the set of $all$ checks one can do before trying to find an actual convex realisation of the polytope... My question is: is there a counterexample of a set of data $(F,V)$ that meets all these criteria, but is known not to arise from a simple convex polytope?


David Speyer:

The 0-faces are the vertices (1,2,3,-1,-2,-3). Higher dimensional facets are represented by giving the vertices lying on them. The 3-faces are the five element sets (1,2,−2,3,−3), (−1,2,−2,3,−3), (1,−1,2,3,−3), and (1,−1,−2,3,−3). The 2-faces are (2,−2,3,−3), (1,−1,3,−3) and the eight three-element sets of the form (±1,±2,±3). The 1-faces are the 12 pairs (i,j) with i≠−j.

In this answer the 3-face $(1,2,-2,3,-3)$ it's not a simple polytope, since the vertex 1 is adjacent to more than 3 vertices.

M. Winter:

1) In the hemicube there are three faces $F=\{X_1,X_2,X_3\}$ and each vertex is presented as their intersection $v = (X_1,X_2,X_3)$. So $(F,V)$ cannot arise from a 3-dimensional convex polytope which must have at least 4 vertices. 2) The hemidodecagon is trickier, we have 6 facets $F=\{X_1, \dots, X_6\}$ and 10 vertices $V=\{(X_1,X_2,X_4), (X_1,X_2,X_6), (X_1,X_3,X_4), (X_1,X_3,X_5), (X_1,X_5,X_6), (X_2,X_3,X_5), (X_2,X_3,X_6), (X_2,X_4,X_5), (X_3,X_4,X_6), (X_4,X_5,X_6)\}$. The putative polytope should be 3-dimensional, but from $(F,V)$ we can read an obstruction: start from vertex 1 and orient the facets incident there as $(X_1 \to X_2 \to X_4)$, jump to the vertex 2 and to be consistent with the previous orientation now the faces have to be oriented as $(X_1 \to X_6 \to X_2)$, but is impossible to find an orientation at each vertex consistent with this jump rule.

  • 1
    $\begingroup$ (I think you should un-accept my answer, which addresses only the original question.) $\endgroup$ Sep 28 '19 at 19:04
  • 1
    $\begingroup$ Your question still seems imprecise: what do you require about the poset? $\endgroup$ Sep 28 '19 at 20:50
  • $\begingroup$ 1) Every "vertex", i.e. lowest element of it should have always d adjacent vertices 2) All the combinatorial requirement that would be implied by the poset being the face lattice of a convex polytope be satisfied. (Things such as euler characteristic or more generally homology groups computed by interpreting the poset as a CW complex) $\endgroup$ Sep 28 '19 at 20:55
  • 1
  • $\begingroup$ Until you actually specify the criteria for your data, one of those criteria could just be that it arises from a simple polytope and so your question becomes vacuous. $\endgroup$ Sep 29 '19 at 16:32

I think a counterexample can be obtained via simplicial spheres. It is known that in higher dimensions, most simplicial spheres do not belong to a polytope. The dual of the face lattice of such a $d$-dimensional non-polytopal simplicial sphere is a $d$-regular "simple" poset in your sense, and cannot belong to a $d$-polytope (as otherwise, the original poset would too). However, it is not clear that the graph of such a poset does not belong to a $d$-polytope either.

Another approach that comes to my mind are abstract polytopes which are defined purely in term of posets. Here, I have two explicit 3-dimensional examples from the class of projective polyhedra:

  • the face structure of the hemi cube does not belong to a polyhedron, but its graph is $K_4$, which does belong to the tetrahedron.
  • the hemi dodecahedron cannot be realized as a polyhedron. Its graph is the Petersen graph, which is not planar and hence cannot belong to a polyhedron either (in fact, it cannot belong to any convex polytope). Its poset can be construct quite easily from the face lattice of the dodecahedron by identifying antipodal faces.

Similar examples can be obtained from all centrally symmetric simple polytopes.

  • 1
    $\begingroup$ Every time I asked this question to friend mathematicians I eventually get this answer. But would you be able to provide an explicit example? That is to give all combinatorical data I need to define a poset which is not the face lattice of a convex polytope? $\endgroup$ Sep 28 '19 at 20:45
  • 4
    $\begingroup$ @giuliobullsaver Right now, I cannot. But Wikipedia states that Grünbaum explicitly constructed such a simplicial sphere (the smallest example known for $d=4$ has eight vertices). Unfortunately no source is given for that claim. I might err, but I remember to have read something like this in Ziegler's "Lectures on Polytopes" (I might check later). But I assume it should not be too hard to track down this claim. $\endgroup$
    – M. Winter
    Sep 28 '19 at 21:47
  • 1
    $\begingroup$ More specifically, search for "(8, 27, 38, 19) 76 non-real" and "(8, 28, 40, 20) 80 non-real" to find non-polytopal simplicial examples. $\endgroup$ Sep 29 '19 at 13:13
  • 2
    $\begingroup$ @giuliobullsaver: That's (probably) true (I didn't check it); but the $f$-vector being realizable is not the same as the whole simplicial complex being realizable. $\endgroup$ Sep 30 '19 at 1:19
  • 2
    $\begingroup$ It's true that the $g$-conjecture/theorem is quite an amazing thing, but I'm trying to stress again that the "combinatorial structure" of a polytope is much more than its $f$-vector. $\endgroup$ Sep 30 '19 at 3:26

I couldn't find the definition of a simple poset, but I think the following should count as a counterexample. Let $G$ be the edge graph of the octahedron, so $G$ has $6$ vertices which I'll label by $V:=\{ -3,-2,-1,1,2,3 \}$ and has as edges all pairs $(i,j)$ from $V$ except those of the form $(i, -i)$. So $G$ is $4$-regular. I claim that

  • $G$ is not the edge graph of a $4$-polytope but

  • There is a regular CW decomposition of the $3$-sphere with edge graph $G$.

Verification that $G$ is not the edge graph of a $4$-polytope. Consider what the $3$-faces of sch a polytope can be. Any $3$-polytope must have at least four vertices, and if it has exactly four then it is a tetrahedron, so its edge graph is a $K_4$. But $G$ contains no $K_4$, so none of its $4$-element subsets can be the vertices of a $3$-face. If all six vertices were the vertices of a $3$-face, then we would have a $3$-dimensional polytope, not a $4$-dimensional one.

So all faces must use five vertices. If $V \setminus \{ i \}$ is a face, then it must be a square pyramid, with $-i$ at the apex.

Now, suppose that $V \setminus \{ i \}$ and $V \setminus \{ j \}$ are both faces. I claim that we must have $i = -j$. Suppose otherwise. Then the vertices of $V \setminus \{ i \}$ lie in an affine $3$-plane. Moreover, since $j$ is NOT the apex of the pyramid $V \setminus \{ i \}$, this $3$-plane is affinely spanned by $V \setminus \{ i,j \}$. So vertex $i$ is in the $3$-plane spanned by $V \setminus \{ i,j \}$. But the same holds for vertex $j$. So all six vertices would be in an affine $3$-plane, a contradiction.

We have now shown that there are at most two $3$-faces in our polytope, which is absurd.

Construction of a regular CW decomposition of $S^3$ with edge graph $G$.

Take four square pyramids, with vertex sets $(1, \pm 2, \pm 3)$, $(-1, \pm 2, \pm 3)$, $(\pm 1, 2, \pm 3)$ and $(\pm 1, -2, \pm 3)$, and with $1$, $-1$, $2$ and $-2$ at their apices respectively. Gluing the first two together along their square faces gives a $3$-ball with boundary the octahedron; gluing the latter two along their square faces gives another $3$-ball with boundary the octahedron; now glue the two octahedra together to give an $S^3$.

This is the face structure of the totally nonnegative part of the Grassmannian $G(2,4)$.

  • $\begingroup$ Dear David, this example is amazing, but it is not precisely the answer to my question (or at least after the update): you are not giving a d-dimensional poset where every "vertex" has d adjacent vertices, but only a 1-dimensional poset which you check cannot be the 1-skeleton of a polytope. $\endgroup$ Sep 29 '19 at 12:54
  • $\begingroup$ Perhaps I am not formulating correctly my question? I would like an example where one has all the combinatorical data of a putative simple polytope (all the face lattice structure, e.g. for every vertex I know the d-faces on which it lies), these data match all the check for being a convex polytope...but it is not $\endgroup$ Sep 29 '19 at 12:54
  • $\begingroup$ The second part of my answer gives you such such a poset. The $3$-faces are the five element sets $(1, 2, -2, 3, -3)$, $(-1, 2, -2, 3, -3)$, $(1, -1, 2, 3, -3)$, and $(1, -1, -2, 3, -3)$. The $2$-faces are $(2,-2,3,-3)$, $(1,-1,3,-3)$ and the eight three-element sets of the form $(\pm 1, \pm 2, \pm 3)$. The $1$-faces are the $12$ pairs $(i,j)$ with $i \neq -j$. The first part of my answer proves something better than you ask for in this comment -- not only can this poset not be realized as the face lattice of a $4$-polytope, but even the edge graph cannot. $\endgroup$ Sep 29 '19 at 12:58
  • $\begingroup$ If you just want a poset which can't be realized, take the face lattice of a non-polytopal simplicial sphere, as M. Winter says. $\endgroup$ Sep 29 '19 at 12:59
  • $\begingroup$ I am a little bit confused though: choose the 3-face (1,2,-2,3,-3). On this face 1 is adjacent to 4 vertices, so this face cannot be a simple polytope (while on a simple polytope each facet is a simple polytope itself). So it seems to me that this poset fails a combinatorical test to be the face lattice of a simple polytope. $\endgroup$ Sep 29 '19 at 13:04

Yes, $K_{3,3}$ is such an example. $K_{3,3}$ is cubic, i.e., $3$-regular, but not planar.

          Image from Wikipedia.
Steinitz's theorem says that the polyhedral graphs ($1$-skeletons of convex polyhedra) are exactly the $3$-connected planar graphs (with at least $4$ vertices).

  • $\begingroup$ The question didn't specify a 3-dimensional polytope. $\endgroup$
    – lambda
    Sep 28 '19 at 18:31
  • 1
    $\begingroup$ @lambda Shouldn't a skeleton of 4-dimensional polytope be 4-connected, or at least have degrees not smaller than 4? $\endgroup$ Sep 28 '19 at 18:36
  • $\begingroup$ Any kind of counterexample is appreciated, however I changed the question in such a way that this example no longer applies: the reason why K_{3,3} cannot be the 1-skeleton of a polytope is due to some combinatorical/topological obstruction, i.e. one cannot even find a poset with that 1-skeleton. I would like an example where a poset satisfies all the topological checks but a convex realisation its known to be impossible $\endgroup$ Sep 28 '19 at 18:41
  • 1
    $\begingroup$ Good point, @lambda. This is overkill, but: Theorem 47. $K_{m,n}$ is $d$-realizable if and only if $n = m = d \in \{1,2\}$. Espenschied, William Joshua. "Graphs of polytopes." PhD diss., University of Kansas, 2014. $\endgroup$ Sep 28 '19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.