# «Abstract. We discuss two problems in combinatorial geometry. First, given a geometric polyhedral complex in R3 (a family of 3-polytopes attached ...»

## GEOMETRIC REALIZATIONS OF POLYHEDRAL COMPLEXES

## IGOR PAK, STEDMAN WILSON

Abstract. We discuss two problems in combinatorial geometry. First, given a geometric

polyhedral complex in R3 (a family of 3-polytopes attached face-to-face), can it always be

realized over Q? We give a negative answer to this question, by presenting an irrational

polyhedral complex with 1278 convex polyhedra. We then present a universality theorem on the space of realizations of such complexes.

Second, given a pure d-dimensional topological polyhedral complex (embedded in Rd ), we ask when it can be realized geometrically (that is, rectilinearly embedded in Rd ). We present both positive and negative results in this direction.

1. Introduction The notion of realizing topological conﬁgurations geometrically is illustrated elegantly in F´ry’s theorem [F], which states that every planar graph can be drawn in the plane such a that each edge is a straight line segment. In two inﬂuential papers [T1, T2], Tutte ﬁrst showed necessary and suﬃcient conditions for realizing 2-connected planar graphs, with all faces (non-strictly) convex. He then showed that for 3-connected planar graphs one can make all faces strictly convex. Much of this paper was motivated by the possibility of extending Tutte’s results to 3 and higher dimensions.

We begin with the classical Steinitz theorem (see e.g. [G, P, R, Z1]). It states that all 3-connected planar graphs can be realized as graphs of 3-polytopes. As a consequence of the proof, all polytopes in R3 can be realized over Q (i.e. realized with rational vertex coordinates) by applying small perturbations of the vertices which preserve combinatorial structure (the faces of the polytope). There are several directions into which this result has

**been shown to have negative analogues:**

(1) In Rd, d ≥ 4, there exist irrational convex polytopes (see [R, RZ]), (2) There exists an irrational 2-dim polyhedral complex immersed into R3 (see [Br, Z2]), (3) There exists a 3-dim topological simplicial complex that is not geometrically realizable (see [Ca, HZ, K]).

In light of Steinitz’s theorem, (1) and (2), it is natural to ask whether every 3-dim polyhedral complex can be realized over Q. A 3-dim polyhedral complex is a natural generalization of a Schlegel diagram of a 4-polytope, so this question occupies an intermediate position between Steinitz’s theorem and (1). Our ﬁrst result answers this question in the negative (see below for deﬁnitions and notation).

** Theorem 1.1 In R3, there exists an irrational 3-dim geometric polyhedral complex consisting of 1278 convex polyhedra (one pentagonal pyramid and 1277 triangular prisms).**

In other words, we show that there exists an arrangement of ﬁnitely many convex polytopes, attached face-to-face, and which cannot be realized over Q. In particular, in contrast with a single polytope, one cannot perturb (in unison) the vertices of the polytopes to make

## 2 IGOR PAK, STEDMAN WILSON

them all rational. Our construction also shows that Brehm’s construction (2) presented in [Z2] can be replaced with a polyhedral complex that is (convexly) embedded into R3. We refer to Subsection 7.1 for discussion of a strongly related construction by Richter-Gebert.The proof of Theorem 1.1 follows the same general approach as (1), going back to Perles’s ﬁrst original construction of an irrational polytope in R8 (see [G]). We start with an irrational point and line conﬁguration in the plane, and then use polyhedral gadgets to constrain the realization space emulating the conﬁguration. At the end, we explicitly construct an irrational arrangement of 1278 polyhedra.

Later in the paper, we use a similar approach to prove two variations on the universality theorem by Brehm [Br, Z2] and Richter-Gebert [R, §10]. Roughly speaking, we show that every algebraic equation can be encoded by a combinatorics of polyhedral complexes. Since these results are rather technical and their history is tumultuous, we postpone them until Section 5, and their discussion until Subsection 7.2.

Our second result is a variation on (3). There are of course various topological obstructions to embedding an

**Abstract**

simplicial complex into Rd. Furthermore, a geometric embedding is even harder to obtain, even if we assume that we start with a topological polyhedral complex, i.e. a complex that is already embedding into Rd. The results in [HZ, K] (see also [AB, Ca, Wi]) rely on topological triangulations whose 1-skeletons contain a nontrivial knot with 5 or fewer edges (this creates an obstruction to a rectilinear embedding). By a much simpliﬁed variation on a construction from the proof of Theorem 1.1, we show that if one replaces “simplicial” with “polyhedral”, one obtains very small examples of complexes which are not geometrically realizable, much smaller than those in [HZ, Wi].

** Theorem 1.2 There exists a topological 3-dim polyhedral complex X in R3 with 8 vertices and 3 polyhedra, that is not geometrically realizable.**

In fact, it is easy to show that this is a minimal such example, i.e. two polyhedra are not enough (see Remark 4.1. In a diﬀerent direction, we may extend this polyhedral complex

**to a polyhedral subdivision of a ball:**

** Theorem 1.3 There exists a topological 3-dim polyhedral complex X ′ in R3 consisting of 9 vertices and 9 polyhedra, such that X ′ is homeomorphic to a ball, and the complex X of Theorem 1.**

2 is a subcomplex of X ′. In particular, X ′ is not geometrically realizable.

** Theorem 1.4 Let X be a topological d-dim simplicial complex in Rd that is homeomorphic to a ball and strongly vertex decomposable.**

Then there is a geometric simplicial complex Y in Rd such that Y is a realization of X.

This result may seem restrictive, but for d = 2 it is equivalent F´ry’s theorem. To see a this, note ﬁrst that it suﬃces to prove F´ry’s theorem for triangulations (added edges can a be removed later). But in the plane, every triangulation X is vertex decomposable [BP] (see also [FPP] for a short proof). But then, by deﬁnition, X is also strongly vertex decomposable, and thus Theorem 1.4 is just F´ry’s theorem.

a In the most interesting case of d = 3, we then extend our theorem to general polyhedral complexes with triangular interior faces and any given boundary realization (Theorem 6.1).

This is a rare positive result in this direction. We use an inductive argument to construct the desired realization. We postpone the (technical) statement and the discussion of this result.

The rest of the paper is structured as follows. We begin with Deﬁnitions and Notations in Section 2. We then discuss irrational polyhedral complexes in Section 3, but move some ﬁgures to the Appendix. A short Section 4 contains proofs of theorems 1.2 and 1.3, based on the same ideas. In the next, lengthy Section 5 we present two universality theorems.

Again, based on ideas in Section 3, it can be viewed as an advanced generalization of that construction; this is the only section where our exposition is not self-contained. We then turn to positive results in Section 6, proving Theorem 1.4 and a more technically involved Theorem 6.1. We conclude with historical remarks and further discussion in Section ??.

2. Definitions and notation Given A ⊆ Rn, let conv(A) and aﬀ(A) denote the convex and aﬃne hulls of A in Rn, respectively. Given a set A ⊆ Rn, we write int(A) for the topological interior of A. If A is a manifold then we write ∂A for the manifold boundary of A. Let B d = {x ∈ Rd | x = 1} denote the unit d-ball. If two topological spaces A, B are homeomorphic, we shall write A ∼ B.

A polytope P is the convex hull of ﬁnitely many points x1,..., xk ∈ Rn. A polytope P is a d-polytope if aﬀ(P ) is a d-dimensional aﬃne subspace of Rn. We call a poset X a geometric d-polyhedron in Rn if X is the face poset of a d-polytope. By abuse of notation we will sometimes refer to a geometric polyhedron as a polytope.

For a geometric d-polyhedron X, an element F ∈ X is a face of X. We shall call a 0-face of X a vertex, a 1-face an edge, a (d − 1)-face a facet, and the d-face the cell. A polyhedron is called simplicial if each of its facets is a (d − 1)-simplex.

A poset X, ordered by set inclusion, is a topological d-polyhedron (in Rn ) if there exists a geometric d-polyhedron Y in Rn and a poset isomorphism ϕ : X → Y such that for each F ∈ X, F ⊆ Rn and F ∼ ϕ(F ). Note that every geometric polyhedron is a topological polyhedron.

A topological d-polyhedral complex (in Rn ) is a set X = n Xi, where each Xi is a i=1 topological d-polyhedron in Rn, and such that if A ∈ Xi and B ∈ Xj then A ∩ B ∈ Xi ∩ Xj.

We call X a geometric d-polyhedral complex (in Rn ) if each Xi is a geometric d-polyhedron.

For brevity, we will write polyhedron instead of topological polyhedron and polyhedral complex instead of topological polyhedral complex.

Note that every polyhedron is a polyhedral complex. If X = k Xi is a polyhedral i=1 complex in Rn, we shall write PX = {X1,..., Xk } and |X| = F ∈X F. Note that |X| ⊆ Rn.

## 4 IGOR PAK, STEDMAN WILSON

If F ∈ X, we deﬁne PX (F ) = {P ∈ PX | F ∈ P }. Let ∂X = {F ∈ X | F ⊆ ∂X}. Note that ∂X is also a polyhedral complex. Two polyhedral complexes are isomorphic, written X ≃ Y, if they are isomorphic as posets under inclusion.A (geometric) realization of a polyhedral complex X is a geometric polyhedral complex Y such that X ≃ Y. We say that Y (geometrically) realizes X. If a polyhedral complex has a geometric realization, then we say that it is (geometrically) realizable.

3. An irrational polyhedral complex In what follows we will work in real projective space RPd, and we extend the deﬁnitions of convex hull and aﬃne hull appropriately. We regard Rd ⊆ RPd under the standard inclusion (p1,..., pd ) → [p1 :... : pd : 1]. We say that distinct points p1,..., pn ∈ RPd are collinear if they are contained in the same line. We say that distinct projective lines ℓ1,..., ℓn are concurrent if ℓ1 ∩· · ·∩ℓn is non-empty. If e1,..., en are edges of a polytope and the edge supporting lines aﬀ(e1 ),..., aﬀ(en ) are concurrent, we say that the edges e1,..., en are concurrent.

An (abstract) point and line conﬁguration L = ([n], E) consists of a ﬁnite set [n] = {1,..., n}, together with a set of (abstract) lines E = {e1,..., ek }, where each ei ⊆ [n].

We require that each point is contained in at least 2 lines, and each line contains at least 3 points. A realization of L is a set of points Λ = {p1,..., pn } ⊆ RPd such that each collection {pi1,..., pik } of 3 or more points is collinear if and only if {i1,... ik } ⊆ e for some e ∈ E. A line ℓ ⊂ RPd is a line of Λ if ℓ ∩ Λ = {pi1,..., pik } and {i1,..., ik } ∈ E. A point and line conﬁguration L is said to be realizable over a ﬁeld F if there is a realization Λ of L such that each point of Λ has coordinates in F.

A realizable point and line conﬁguration L is said to be irrational if it is not realizable over Q. That is, for every realization Λ of L there is some point p ∈ Λ such that p has an irrational coordinate. The following 9-point conﬁguration due to Perles is irrational.

** Lemma 3.1 (Perles, [G]) The point and line conﬁguration depicted in Figure 1 is irrational.**

We say that a geometric polyhedral complex X generates a realization Λ of a point and line conﬁguration L, if each point of Λ is the intersection of aﬃne hulls of faces of X. We say that a polyhedral complex X is realizable over a ﬁeld F if there is a geometric realization X ′ of X such that each vertex of X ′ has coordinates in F. Note that realizable over R

## GEOMETRIC REALIZATIONS OF POLYHEDRAL COMPLEXES 5

is equivalent to realizable. A geometric polyhedral complex X is called irrational if it is not realizable over Q. In this section we will construct a geometric polyhedral complex X such that every realization of X generates the Perles conﬁguration. This implies that X is irrational.In what follows we let T denote any geometric realization of a triangular prism in R3.

The edges of T not contained in the triangular facets of T are the lateral edges of T, and the facets containing these edges (i.e. the tetragonal facets) are the lateral facets.

** Lemma 3.2 In every geometric realization T of a triangular prism, the lateral edges of T are concurrent.**

Proof. Let ℓ1, ℓ2, ℓ3 denote the supporting lines of the lateral edges of T. These lines are pairwise coplanar. Indeed, P1,2 = aﬀ(ℓ1 ∪ℓ2 ), P1,3 = aﬀ(ℓ1 ∪ℓ3 ) and P2,3 = aﬀ(ℓ2 ∪ℓ3 ) are the supporting planes of the lateral facets of T. Since ℓ1, ℓ2 are coplanar projective lines, they intersect in a point p. Thus {p} = ℓ1 ∩ℓ2 ⊆ P1,3 ∩P2,3 = ℓ3. Therefore {p} = ℓ1 ∩ℓ2 ∩ℓ3.

A belt is a polyhedral complex B consisting of triangular prisms T1,..., Tm attached consecutively along their lateral facets (see Fig. 2). We introduce notation that will be used in Lemma 3.3 below. Let B = m Ti be a belt. For i = 1,..., m and j = 1, 2, 3 i=1 let z(i,j) and z(i,j ′ ) denote the adjacent vertices of Ti contained in opposite triangular facets. For i = 1,..., m and j = 1, 2 let F(i,j) denote the facet containing the vertices z(i,1), z(i,1′ ), z(i,2), z(i,2′ ). Then each F(i,k) is a lateral facet of Ti. We assume that the prisms are attached so that F(i,2) = F(i+1,1) for all i = 1,..., m − 1.

** Figure 3. Left: Attaching one belt in the construction of Theorem 1.**

1.

Right: The complete irrational complex with all four belts attached.