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

Consider a realization X ′ of X, and let Λ′ be the realization of Λ generated by X ′. For a point p′ ∈ Λ′, let e′, e′, e′, e′ be the edges corresponding to e1, e2, e3, e4 in the above construction. Since they are the lateral edges of a belt, these edges will be concurrent, at p′. Since the point of concurrency of e′ and e′ is a vertex of X ′, we have that p′ is a vertex of X ′. Thus, for any realization X ′ of X, the realization Λ′ of L generated by X ′ consists entirely of vertices of X ′. In particular, Λ′ does not contain points at inﬁnity.

We will now deﬁne a map F : R(X ) → R(L) such that F assigns to each realization ′ of X the corresponding realization of L generated by X ′. We show that F is a staX ble equivalence, by showing that it is the composition of stable projections and rational homeomorphisms.

Let n denote the number of points of L and N the number of vertices of X. Then we have R(L) ⊂ R3n, and R(X ) ⊂ R3N. From the construction of X(L) in Theorem 5.2, we see that each point i of L corresponds to a belt Bi of X. In particular, we choose Bi to be one of the belts such that the lateral edges of Bi are concurrent at the point pi ∈ Λ.

For each belt Bi, ﬁx an ordering of the its vertices v i1, v i2,..., v isi, such that the ﬁrst four vertices are the (cyclically ordered) vertices of a lateral facet fi of Bi, and such that v i1 v i2 and v i3 v i4 are the two lateral edges of fi. Let w 1,..., w r denote the remaining vertices of X. Let f1 : R3N → R3N be a map that permutes the coordinates, in such a way that

While the above result shows that the realization space of a polyhedral arrangement is stably equivalent to the underlying point and line conﬁguration, we would like a stronger result, which states that realization spaces of polyhedral arrangements can be stably equivalent to arbitrary semialgebraic sets. For this, we will need to add an additional structure to our point and line conﬁgurations, to obtain an oriented matroid. We provide an equivalent deﬁnition of an oriented matroid, which will prove convenient for our purposes.

A line L ⊂ Rd has two possible orientations, each of which induces a linear order on the points x ∈ L. Let L = (X, E) be a planar point and line conﬁguration, such that every two abstract lines e1, e2 ∈ E share a point of X (that is, e1 ∩ e2 = ∅). Let Λ ⊂ Rd be a realization of L. For each e ∈ E, let L be the line of Λ realizing e, and choose an orientation γ of L. Write e = {i1,..., ik }, where (pi1, pi2, · · · pik ) is the order of the pj ∈ L induced by γ. We deﬁne the oriented line e′ to be the ordered tuple (i1,..., ik ). Let E ′ denote the resulting set of oriented lines e′. Then M = (X, E ′ ) is an oriented matroid. One can readily check that this deﬁnition is equivalent to those given elsewhere (see e.g. [R]). In particular, the fact that we require every two lines of M to intersect in a point of M means that all realizations of M (which will agree on the order of the points) will agree on the set of half planes in which a given point lies.

If M = (X, E ′ ) is an oriented matroid, let E be the set obtained by replacing each tuple (i1,..., ik ) ∈ E ′ with the set {i1,..., ik }. Then we say that L(M) = (X, E) is the point and line conﬁguration corresponding to M. A realization of M is a set Λ = {p1,..., pn } ⊂ Rd such that Λ is a realization of L(M), and such that if L is a line of Λ corresponding to e′ = (i1,..., ik ), then there is an orientation γ of L such that (pi1, pi2, · · · pik ) is the order of the pj ∈ L induced by γ. In other words, a realization of M is a realization of the underlying point and line conﬁguration in which the points of each line have a prescribed order, up to reversing the orientation of the line.

** Figure 9. The arrangement Iijk, with the two prisms T1 and T2 shown in blue and the belt Hijk shown schematically in purple.**

The diagonals of the facet f of T1 are shown in red.

Proof. Let M be an oriented matroid, and let Λ ⊂ R3 be a realization of L(M). Let X (L(M)) be the polyhedral arrangement constructed from Λ as in Theorem 5.3. We write X = X (L(M)). We introduce a new polyhedral gadget which, when added to X, will yield a polyhedral arrangement Y = Y(M) such that every realization of Y generates a realization of M. That is, every realization of Y generates a realization of L(M) in which the points occur on each line in the order prescribed by M. The proof of stable equivalence is then identical to the proof of Theorem 5.3.

Let pi, pj, pk denote three points of Λ which appear consecutively on a line L of Λ. We construct a belt Gijk consisting of two triangular prisms, call them T1 and T2, as follows.

Let v 1, v 2, v 3, v 4 denote the vertices of a lateral facet f of T1 labeled cyclically, where e1 = v 1 v 4 and e2 = v 2 v 3 are the lateral edges of f. We may choose the vertices xi so that if ℓ1 = aﬀ(v 1, v 2 ), ℓ2 = aﬀ(v 1, v 3 ), and ℓ3 = aﬀ(v 1, v 4 ), then pi ∈ ℓ1, pj ∈ ℓ2, and pk ∈ ℓ3.

Note that ℓ2 is the line spanned by the diagonal v 1 v 3 of the facet f. Let z denote the point of intersection of the diagonals v 1 v 3 and v 2 v 4. We attach T2 to T1 along the unique lateral facet g of T1 that contains the edge e2 and does not contain e1. Let e3 denote the non-lateral edge of T2 containing the vertex v 3, and not contained in g. We may choose the vertices of T2 such that e3 ⊂ ℓ2.

Attach a belt Hijk to Gijk along the edges e1, e2, e3 of Gijk. Call the resulting arrangement Iijk (see Figure 9). Then in every realization of Iijk, the edges e1, e2, e3 will be concurrent.

Thus the vertex v 1 will be contained in aﬀ(e3 ). Since v 3 ∈ e3 by construction, this implies that ℓ2 = aﬀ(e3 ). That is, the diagonal v 1 v 3 will be collinear with the line spanned by e3.

If Ba denotes a belt of X with all lateral edges concurrent at pa, then attach a lateral edge of the belt Bi to the edge e1 of Iijk, a lateral edge of Bk to e2, and a lateral edge of Bj to e3. Let Y denote the arrangement obtained by adding Iijk to X for each such consecutive collinear triple of points pi, pj, pk, and performing the belt attachments just described.

Now suppose pi, pj, pk are three consecutive collinear points of Λ, contained in a line L of Λ. Let Y ′ be a realization of Y, and for each point, edge, line, or facet a of Y, let a′ denote the corresponding object of Y ′. Then z′ must lie between v ′ and v ′ on the line aﬀ(v ′, v ′ ), since z′ is the intersection of the diagonals v ′ v ′ and v ′ v ′ of f ′, and f ′ is convex. From 18 IGOR PAK, STEDMAN WILSON the attachment of the belts Bi, Bj, Bk to Iijk, we see that pi ∈ ℓ′, pj ∈ aﬀ(e′ ) = ℓ′, and pk ∈ ℓ′. Thus the point p′ must lie between the points p′ and p′ on the line L′ containing 3 j i k them.

It follows that in every realization Y ′ of Y, the realization Λ′ of L(M) generated by Y ′ has the property that all points occur along each line in the order prescribed by M. That is, Λ′ is a realization of M.

From Theorem 5.4, together with the universality theorem for oriented matroids (see [R]), we obtain the following universality theorem for polyhedral arrangements.

Corollary 5.5 (Strong Universality Theorem) Let V ⊆ Rm be a basic primary semialgebraic set, deﬁned over Z. Then there is a polyhedral arrangement X such that R(X ) is stably equivalent to V.

6. Geometrically realizing a class of polyhedral complexes In this section we prove two positive results. The ﬁrst result is Theorem 1.4, which tells us that we may geometrically realize a certain class of simplicial complexes in arbitrary dimension. The second is an analogous result for general polyhedral complexes, and holds only for d ≤ 3. Before we present the statement of these theorems and their proofs we will need to introduce some relevant deﬁnitions. Some of these deﬁnitions (such as star, link, and vertex decomposable) are standard, while others (such as strongly vertex decomposable and vertex truncatable) are not.

6.1. Strongly vertex decomposable simplicial complexes. Let X be a polyhedral complex and let F be a face of X. The star of F in X is the set stX (F ) = {A ∈ X | F ⊆ A}.

Let cstX (F ) = {A ∈ X | A ⊆ B ∈ stX (F )} denote the closed star of F. Note that cstX (F ) is a polyhedral complex, while stX (F ) may not be (since it may not be closed under taking subfaces). If F ∈ X, let X F = X − stX (F ) denote the deletion of F from X, which is clearly a polyhedral complex. The link of F in X is the polyhedral complex lkX (F ) = cstX (F ) F.

Let X be a topological d-polyhedral complex such that |X| ∼ B d, and let v be a boundary vertex of X. We say that v is boundary minimal if v is contained in exactly d boundary facets, each of which is a (d − 1)-simplex. We call v a shedding vertex of X if |X v| ∼ B d, and a strong shedding vertex if in addition v is boundary minimal. We say that X is strongly vertex decomposable if either X is a single polyhedron, or recursively, X has a strong shedding vertex v such that X v is strongly vertex decomposable. A boundary vertex w of X is a solitary vertex if there is exactly one polyhedron Pw ∈ PX such that w ∈ Pw, and a strong solitary vertex if in addition w it is boundary minimal.

If we restrict ourselves to simplicial complexes, then we ﬁnd that in any dimension d, a strongly vertex decomposable simplicial d-ball is always geometrically realizable. This is the statement of Theorem 1.4, and the proof is straightforward.

Proof of Theorem 1.4. Let X denote a d-simplicial complex, such that |X| ∼ B d and X is strongly vertex decomposable and. We proceed by induction on n, the number of vertices of X. If n = d + 1, then X consists of a single d-simplex, which is obviously realizable. If n d + 1, let v be a strong shedding vertex of X, and let X ′ = X v. Then by deﬁnition X ′ is a strongly vertex decomposable d-ball. Since X ′ has one fewer vertex than X, by the induction hypothesis X ′ has a geometric realization Y ′. Since v is a strong shedding vertex, it is adjacent to exactly d boundary vertices of X, call them w1,... wd. Then lk∂X (v) (the

## GEOMETRIC REALIZATIONS OF POLYHEDRAL COMPLEXES 19

link of v in the complex ∂X) has exactly d faces of maximal dimension, call them F1,..., Fd, each of which is a (d − 2)-face of X. Each face Fi is contained in exactly one facet τi of X ′.Let Hi = aﬀ(τi ) and let H ′ = aﬀ(w1,..., wd ).

Since d hyperplanes in RPd always intersect in a point, we may let x denote the point of intersection of the hyperplanes Hi. If x is a point at inﬁnity, or x lies on the same side of the hyperplane H ′ as |Y ′ |, then apply a projective transformation so that x is a ﬁnite point and x and |Y ′ | lie on diﬀerent sides of H ′. Now let u be a point contained in conv(Y ′ ∪ v) such that u is very close to v. Add straight line segments between u and all vertices of |Y ′ | that correspond to neighbors of v in X. By taking u arbitrarily close to v, we may ensure that these added line segments intersect |Y ′ | only in the desired vertices. These line segments, together with u and its neighbors, determine a collection of k-simplices for 2 ≤ k ≤ d. Adding these simplices to Y ′ yields a geometric d-simplicial complex Y such that X ∼ Y.

6.2. Vertex truncatable polyhedral complexes. Now we consider the general case that X is a d-polyhedral complex. We will need to develop some more involved deﬁnitions in order to prove a result analogous to Theorem 1.4.

Suppose X1 and X2 are two d-polyhedra that share exactly one facet Q. Then let X1 #Q X2 denote the polyhedron obtained from X1 ∪ X2 by replacing the two cells |X1 | and |X2 | by the single cell |X1 | ∪ |X2 | and removing the facet Q.

We now deﬁne a construction called subdivision by facet. Let X be a polyhedral complex, let v be a boundary vertex of X, and let P ∈ PX (v). Let τ (v, P ) ⊆ |P | denote a (topological) (d−1)-ball such that τ (v, P )∩|lk∂P (v)| = ∂τ (v, P ). In particular, the vertices of X contained in τ (v, P ) are exactly the neighbors of v in ∂X. We may construct a new polyhedral complex X ⊕ τ (v, P ), called the subdivision of X at v and P, as follows. If X already contains a facet F ⊆ P such that F ∩ |lk∂P (v)| = ∂F, then take X ⊕ τ (v, P ) = X. If X contains no such facet, then X ⊕ τ (v, P ) is obtained by adding the facet τ (v, P ) and replacing P ∈ X with two new cells σ1, σ2 such that σ1 ∪ σ2 = P and σ1 ∩ σ2 = τ (v, P ). Note that subdivision by facet has no eﬀect on simplicial complexes.

For a boundary vertex v of X we deﬁne the full subdivision of X at v by X ∗ (v) = X τ (v, P ).

P ∈PX (v) That is, X ∗ (v) is obtained from X by repeatedly doing subdivision by facet, in eﬀect subdividing X at v and P for each P ∈ PX (v) (see Fig. 10).

**We say that X is vertex truncatable if |X| ∼ B d and at least one of the following holds:**

(a) X is a d-simplex.

(b) X has a strong shedding vertex v such that X ∗ (v) v is vertex truncatable.

X ∗ (v) (c) X has a strong solitary vertex v such that v is vertex truncatable.

Note that if |X| ∼ B d and v is a strong shedding vertex of X, then v is clearly a strong shedding vertex of X ∗ (v). Thus |X ∗ (v) v| ∼ B d. It follows that strongly vertex decomposable implies vertex truncatable.

Two k-faces F1, F2 ∈ X are said to be strongly adjacent if dim(F1 ∩ F2 ) = k − 1. If X1 is a polyhedron of X and F1, F2 ∈ X1 are strongly adjacent facets, then we deﬁne α(F1, F2 ) to be the interior angle of X1 formed between F1 and F2. More precisely, α(F1, F2 ) is the angle between the normal vectors to the hyperplanes aﬀ(F1 ) and aﬀ(F2 ), with sign chosen 20 IGOR PAK, STEDMAN WILSON Figure 10. A 2-polyhedral complex with vertex v encircled, and the resulting complex X ∗ (v) with the added facets τ (v, P ) shown in red.

so that the angle is interior to X1. If d = 2 then α(F1, F2 ) is a vertex angle, and if d = 3 then α(F1, F2 ) is a dihedral angle.