An example of a "simple poset" which does not belong to a convex polytope

Question

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?

UPDATE:

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.

NEW UPDATE:

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?

SUMMARY OF PREVIOUS ANSWERS:

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.

Answer 1

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.

Answer 2

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

Answer 3

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).