E extracta mathematicae Vol. 31, Núm. 2, 169 – 188 (2016) More Indecomposable Polyhedra Krzysztof Przes lawski, David Yost Wydzia l Matematyki, Informatyki i Ekonometrii, Uniwersytet Zielonogórski, ul. prof. Z. Szafrana 4a, 65 − 516 Zielona Góra, Poland and Wydzia l Matematyki, Informatyki i Architektury Krajobrazu, Katolicki Uniwersytet Lubelski, ul. Konstantynów 1 H, 20 − 708 Lublin, Poland K.Przeslawski@wmie.uz.zgora.pl Centre for Informatics and Applied Optimization, Faculty of Science and Technology, Federation University, PO Box 663, Ballarat, Vic. 3353, Australia d.yost@federation.edu.au Received June 12, 2016 Abstract : We apply combinatorial methods to a geometric problem: the classification of polytopes, in terms of Minkowski decomposability. Various properties of skeletons of poly- topes are exhibited, each sufficient to guarantee indecomposability of a significant class of polytopes. We illustrate further the power of these techniques, compared with the tradi- tional method of examining triangular faces, with several applications. In any dimension d 6= 2, we show that of all the polytopes with d2 + 1 2 d or fewer edges, only one is decom- posable. In 3 dimensions, we complete the classification, in terms of decomposability, of the 260 combinatorial types of polyhedra with 15 or fewer edges. Key words: Polytope, decomposable. AMS Subject Class. (2010): 52B10, 52B11, 52B05. Dedicated to the memory of Carlos Beńıtez What happens if you have two line segments in the plane, oriented in different directions, and you calculate all the sums of all pairs of elements, one from each segment? Of course you end up with a rectangle, or at least a parallelogram. Do the same again with a triangle and a line segment in three dimensions: this time, you get a prism. Thus the prism and the parallelogram are decomposable; they can be expressed as the (Minkowski) sum of two dis- similar convex bodies. (Recall that that two polytopes are similar if one can be obtained from the other by a dilation and a translation.) On the other hand, any triangle, tetrahedron or octahedron is indecomposable. We refer to [7] for a general introduction to the theory of polytopes, as well as for specific results. Determining the decomposability of a polytope 169 170 k. przes lawski, d. yost can be reduced to a computational problem in linear algebra [12, 17]. That is, given the co-ordinates of its vertices, all we have to do is calculate the rank of a rather large matrix. However that is not the approach to be taken here. The edges and vertices of any polytope obviously constitute a graph, some- times known as its skeleton. In the case of a polyhedron, this will be isomor- phic to a planar graph. All the geometric conclusions of this paper will be established by considering the properties of this graph. Section 1 develops a number of sufficient conditions for indecomposability (or decomposability). Our results have wider applicability than earlier results in this area, which generally relied on the existence large families of triangular faces. Section 2 applies them to complete the classification of 3-dimensional polyhedra with up to 15 edges. Section 3 applies them to completely classify, as indecomposable or decomposable, all d-dimensional polytopes with up to d2 + 1 2 d edges. We also show that there is no d-dimensional polytope at all with 2d vertices and d2 + 1 edges, for d 6= 3. 1. Geometric graphs and indecomposability We will not give a thorough history of this topic, but it is important to recall some preliminary information. We depend heavily on the concept of a geometric graph, which was pio- neered by Kallay [9]. He defined a geometric graph as any graph G whose vertex set V is a subset of a finite-dimensional real vector space X, and whose edge set E is a subset of the line segments joining members of V . (Of course, X will be isomorphic to Rd for some d, but we prefer this basis-free formula- tion.) It is largely a formality whether we consider an edge to be an unordered pair or a line segment. It is significant that such a graph need not be the edge graph of any polytope. He then extended the notion of decomposability to such graphs in the following manner. For convenience, let us say that a function f : V → X is a decomposing function for the graph (V,E) if it has the property that f(v)−f(w) is a scalar multiple of v − w for each edge [v,w] ∈ E. (This is slightly different from Kallay’s local similarity; he insisted on strictly positive multiples.) A geomet- ric graph G = (V,E) is then called decomposable if there is a decomposing function which is neither constant, nor the restriction of a homothety on X. If the only non-constant decomposing functions are homotheties then G is called indecomposable. Significantly, Kallay showed [9, Theorem 1] that a polytope is indecompos- more indecomposable polyhedra 171 able if and only if its edge graph is indecomposable in this sense. Exploiting an idea of McMullen [11] and Kallay [9, Theorem 1b], we showed in [14, Theorem 8] that it is even sufficient just to have an indecomposable subgraph which contains at least one vertex from every facet (maximal face). A strategy for proving indecomposability of a polytope is thus to prove that certain simple geometric graphs are indecomposable, and by building up to show that the en- tire skeleton of our polytope is indecomposable. (It also would be interesting to formulate somehow a notion of primitivity for such graphs.) Building on the concept introduced in [18, p. 139], let us say that a geomet- ric graph G = (V,E) is a simple extension of a geometric graph G0 = (V0,E0) if G has one more vertex and two more edges than G0. More precisely, we mean that there is a unique v ∈ V \V0, and distinct vertices u and w in V0, such that E = E0∪{[u,v]}∪{[v,w]}. Observe that the existence of these two edges means that the value of any decomposing function at v is determined by its values at u and w. No assumption is made about whether [u,w] is an edge of either graph. Our first result is a special case of the next one, but it is so useful and so easy to prove that it is worth stating separately. Proposition 1. Suppose that G0,G1, . . . ,Gn are geometric graphs, that Gi+1 is a simple extension of Gi for each i, and that G0 is indecomposable. Then Gn is also indecomposable. Proof. It is clearly sufficient to prove this when n = 1, and this follows from the observation in the preceding paragraph. Let us illustrate how this can be applied in the simplest cases, polyhedra for which “sufficiently many” faces are triangles [15, §3]. Any edge is obviously indecomposable, and then Proposition 1 easily implies that any triangle is indecomposable. Furthermore if an indecomposable geometric graph shares an edge with a triangle, then their union is easily proved to be indecomposable. It follows that the union of a chain of triangles, as defined in [15, p. 92], is an indecomposable graph. This makes it clear that a polyhedron must be indecomposable if every face is a triangle. If every face but one is a triangle, it remains true that the triangular faces can be ordered into a chain, whose union is the entire skeleton of the polyhedron; again indecomposability is assured. The same holds if all faces but two are triangular, and the non- triangular faces do not share an edge. If all faces but two are triangular, but the non-triangular faces do share an edge, then the triangular faces can still be ordered into a chain, whose union will contain every vertex of the polyhedron 172 k. przes lawski, d. yost A D C B EF A C D E B Figure 1: Two indecomposable examples without many triangles and every edge bar one. So, indecomposability is assured, whenever there are two or fewer non-triangular faces. This conclusion no longer holds if we have three non-triangular faces, since the triangular prism is decomposable. On the other hand, there are also many indecomposable polyhedra with precisely three non-triangular faces. For comparison, let us mention that that a polyhedron with only three, or fewer, triangular faces is automatically decomposable [17, §6]. To show how powerful Proposition 1 is, we note that it guarantees in- decomposability of any polyhedron whose graph is either of those shown in Figure 1. In neither example is there a chain of triangles touching every face. For the first example, begin with the edge AB, which is indecomposable, then successively add the vertices C,D,E and F. Each additional vertex is adjacent to two of the preceding ones, so the resulting geometric graph is in- decomposable. Since it touches every face, the polyhedron is indecomposable. The second example is even quicker; beginning with the edge AB, it is enough to add the vertices C,D then E. A similar argument also gives a particularly easy proof of the indecompos- ability of the example in [9, §6]. Further applications are given in [3]. Kallay [9, Theorem 8] showed that if two indecomposable graphs have two common vertices, then their union is indecomposable. A prime example for this result is the 199th polyhedron in the catalogue [4], which will be discussed more indecomposable polyhedra 173 Figure 2: BD199 is indecomposable again in the next section. In Figure 1, it should be clear that the six triangular faces can be partitioned in two groups, each of which constitutes a chain of 3 triangles. It is clear that the resulting two indecomposable geometric graphs have two vertices (but no edge) in common, and that their union contains every vertex. Our next result is a generalization of both Proposition 1 and [9, Theo- rem 8]. Our proof is no different from Kallay’s but, as we shall soon see, our formulation is somewhat more powerful. It is clear from the definition that adding an edge but no vertex to an already indecomposable graph preserves its indecomposability. The point of part (i) is that, with a little care, we can throw away some edges and still preserve indecomposability. Part (ii) says that if one edge of an indecomposable graph is replaced by another indecom- posable graph, then the new graph is indecomposable. Theorem 2. (i) Suppose that G1 = (V1,E1) and G2 = (V2,E2) are two geometric graphs in the same vector space, and that V12 = V1 ∩V2 contains at least two distinct vertices. Let E12 be the collection of those edges of G1, both of whose vertices lie in V12. Let G = (V,E) be another geometric graph with vertex set V = V1 ∪V2 and whose edge set E contains (E1 \E12) ∪E2. If both G1 and G2 are indecomposable, then so is G. (ii) Suppose that G1 = (V1,E1) and G2 = (V2,E2) are two indecomposable 174 k. przes lawski, d. yost geometric graphs, that V1 ∩ V2 contains at least two distinct vertices u and w. Define a new geometric graph G = (V,E) with vertices V = V1 ∪V2 and edges E = (E1 \{[u,w]}) ∪E2. Then G is also indecomposable. Proof. (i) Let f : V → X be a decomposing function, where X is the ambient vector space. Since G2 is indecomposable, f|V2 must be the restriction of a similarity, i.e. there are a scalar α and a vector x such that f(v) = αv +x for all v ∈ V2. In particular, f(u) −f(w) = α(u−w) for all u,w ∈ V12 (even when [u,w] is not an edge of G2). Since E1 ⊆ E12∪E, this implies that f|V1 is also a decomposing function, so by hypothesis must also be the restriction of a similarity. Thus there are a scalar β and a vector y such that f(v) = βv + y for all v ∈ V1. Now, fix distinct u,w ∈ V12. Consistency requires αu + x = βu + y and αw+x = βw+y, which quickly forces x = y and α = β. Thus f is a similarity. (ii) In the notation of part (i), we clearly have (E1 \E12) ∪E2 ⊆ E. Note that we make no assumption about whether the edge [u,w] belongs to either G1 or G2. Recall that a graph G is called a cycle if |V | = k ≥ 3 and V can be ordered as {v1, . . . ,vk}, so that E = {{v1,v2}, . . . ,{vk−1,vk},{vk,v1}}. The number k is said to be the length of the cycle. The next result is a rewording of [14, Proposition 2]. Once formulated it is easy to prove, yet surprisingly useful. The 3-dimensional case has already been used in [14, §4]. We state it explicitly here, since we will use both the 3-dimensional and higher dimensional versions in the next sections. Proposition 3. Any cycle, whose vertices are affinely independent, is an indecomposable geometric graph. In particular, a polytope will be indecom- posable, if its skeleton contains a cycle, whose vertices are not contained in any affine hyperplane, and which touches every facet. The next result indicates further how indecomposability of a graph can be established by considering smaller subgraphs. Theorem 4. (i) Let H = (V,E) be an indecomposable geometric graph and for each e = [u,v] ∈ E, let Ge = (Ve,Ee) be an indecomposable geometric graph containing both vertices u,v. Then the union ⋃ e Ge is an indecompos- able geometric graph. (ii) Let G1 = (V1,E1), G2 = (V2,E2), . . . , Gn = (Vn,En) be indecom- posable geometric graphs and let v1,v2, . . . ,vn be a collection of affinely inde- more indecomposable polyhedra 175 pendent vertices. Set G0 = Gn, v0 = vn and suppose vi ∈ Vi ∩Vi−1 for each i. Then the union G1 ∪G2 ∪·· ·∪Gn is indecomposable. (iii) Let P be a polytope, and let G1 = (V1,E1), G2 = (V2,E2) be two indecomposable subgraphs of the skeleton of P , with V1 ∩ V2 6= ∅, and sup- pose that V1 ∪ V2 contains all but at most d − 2 vertices of P . Then P is indecomposable. Proof. (i) Just apply Theorem 2(ii) successively, replacing each edge e of H with the graph Ge. (ii) The graph with vertices v1, . . . ,vn and edges [v1,v2], . . ., [vn−1,vn], [vn,v1] is indecomposable by Proposition 3. Now we just apply (i). (iii) If V1 ∩V2 contains two or more elements, the conclusion follows from Theorem 2(i). So we assume that V1 ∩V2 contains a unique element, say v2. Set V ′i = Vi \ {v2}, and C = V \ (V ′ 1 ∪ V ′ 2). Then C contains at most d − 1 vertices, so their removal from the graph of P will not disconnect it. Since V ′1 and V ′2 are disjoint, there must then be an edge between them, say between v1 ∈ V ′1 and v3 ∈ V ′ 2. Letting G3 be the graph with the single edge [v1,v3], we can apply (ii) with n = 3. (We cannot claim G1 ∪G2 is indecomposable.) It is easy to see that [9, Theorem 9] is precisely the case n = 3 of part (ii), and that [9, Theorem 10] is implied by the case n = 4. Part (iii) is a strengthening of [16, Corollary 8.6], where it is assumed that every vertex of P lies in V1 ∪ V2. We will indicate the strength of this with another two examples. In both polyhedra whose graphs are shown in Figure 3, we can take G1 and G2 as chains of triangles. Only part (iii) of the preceding Theorem is capable of proving the indecomposability of these two polyhedra. Sufficient conditions for decomposability are not so common. The following result was proved without statement by Shephard [15, Result (15)]. More precisely, he made the stronger assumption that every vertex in F had degree d; however, his proof also works in the formulation presented here. It may be interesting to present a proof using decomposing functions. Proposition 5. A polytope P is decomposable whenever there is a facet F such that every vertex in F has a unique neighbor outside F , and P has at least two vertices outside F. Proof. Let y be a support functional for F . We may suppose that y(F) = {1} and that y(x) < 1 for all other x in the polytope. Label the vertices of F as v1, . . . ,vn. For each vertex vi of F, denote by wi the unique vertex which 176 k. przes lawski, d. yost Figure 3: Another two examples is adjacent to vi but not in F. Set α = max n i=1 y(wi); clearly α < 1. For each i, let xi be the unique point on the edge [vi,wi] satisfying y(xi) = α. Now define a function f by f(vi) = xi and f(v) = v for all other vertices. Clearly f(v) − f(w) = v − w whenever both vertices are outside F . Since f(vi) − f(wi) = xi − wi and xi is a convex combination of vi and wi, the condition for a decomposing function is also satisfied when one vertex lies in F. What if both vertices lie in F? Fix two adjacent vertices vi,vj in F, and consider a 2-face containing them but not contained in F. This face must contain xi and xj. Since y(vi) = y(vj) 6= y(xi) = y(xj), the line segments [vi,vj] and [xi,xj] must be parallel; we do not claim that [xi,xj] is an edge of P . Then f(vi) −f(vj) = xi −xj is a non-negative multiple of vi −vj. So f is a decomposing function, as anticipated. Finally, f is not a similarity, because it coincides with the identity func- tion at all the vertices outside F but is not equal to the identity function. Decomposability follows. The next section requires the 3-dimensional case of the following result. It is not difficult, but appears to be new, so we state it in full generality. Proposition 6. Let F be a facet of a polytope P . Suppose that F is indecomposable. Let Q be obtained from P by stacking a pyramid on F. Then P is decomposable if and only Q is decomposable. Proof. Let V be the vertex set of P , u the unique vertex of Q not in P , S the pyramid being glued onto F and X the ambient vector space. It is easy more indecomposable polyhedra 177 to show that any decomposing function defined on F has a unique extension to S. If P is indecomposable, so is its graph, G(P). Let f : V ∪{u} → X be a decomposing function for Q. Then f|V is a decomposing function for P , so we find α,x so that f(v) = αv + x for all v ∈ V . By the previous paragraph, αu + x is the only conceivable value for f(v). Thus Q is indecomposable. Conversely, suppose Q is indecomposable. Let g : V → X be any de- composing function for P . Again by the first paragraph, there a unique de- composing function f : V ∪{u} → X which extends g. Since f must be the restriction of a homothety on X, so must g. 2. Polyhedra with 15 edges If a given polyhedron has V vertices, E edges and F faces, then Euler’s relation E = V +F−2 suggests that the number of edges is a reasonable mea- sure of its complexity. Accordingly, we gave in [19] the complete classification, in terms of decomposability, of the 58 combinatorial types of polyhedra with 14 edges. The classification of the 44 types of polyhedra with 13 or fewer edges was essentially known [17, §6]. Indeed, there are only four types of polyhedra with 6, 8 or 10 edges, and they are easily seen to be indecomposable. No polyhedron can have 7 edges. Besides the triangular prism, the only other polyhedron with 9 edges is the triangular bipyramid, which is obviously indecomposable. A thorough study of this topic had already been made by Smilansky, who showed [17, Theorem 6.7] that a polyhedron is decomposable if there are more vertices than faces; and that a polyhedron is indecomposable if F ≥ 2V − 6. As remarked in [19, p 719], simply knowing the values of F and V is then enough to decide decomposability in all cases when E ≤ 11 or E = 13. The examples with 12 edges were discussed in more detail in [19], but the results were obviously known to Smilansky. (The only example whose indecomposability is not clear from classical triangle arguments is [19, figure 2], and its indecomposability is guaranteed by [16, Corollary 8.6].) The classification of polyhedra with 14 or fewer edges incidentally com- pleted the classification of all polyhedra with 8 or fewer faces. We should recall that two polytopes are said to be combinatorially equivalent if their face lattices are isomorphic. In three dimensions, Steinitz’s Theorem assures us that two polyhedra are combinatorially equivalent as soon as we know that 178 k. przes lawski, d. yost their graphs are isomorphic. In many cases, two polytopes with the same combinatorial type will either both be decomposable or both be indecompos- able. Smilansky [17, §6] first announced that this is not so for polyhedra with 14 edges, and some explicit examples were given in [19]. We push this project a bit further in this section by completing the clas- sification of the 158 combinatorial types of polyhedra with 15 edges. This also completes the classification of the 301 combinatorial types of polyhedra with 8 or fewer vertices. We also note the indecomposability of all higher dimensional polytopes with 15 or fewer edges. The aforementioned results of Smilansky imply that a polyhedron is de- composable if (V,F) is either (10, 7) or (9, 8) and that a polyhedron is inde- composable if (V,F) = (7, 10); these three cases account for 84 combinatorial types. Our assumption that V + F = 17 then tells us that the only case remaining is V = 8,F = 9. There are 74 combinatorial types of polyhedra with 8 vertices and 9 faces, which were first described verbally, but not visually, by Kirkman [10, pp 362– 364]. It is possible to use computers to generate diagrams of such polyhedra, but we are dealing with a relatively small number of polyhedra, so it is simpler to use a published catalogue. The only one for this class seems to be that of Britton and Dunitz [4]. They exhibited diagrams of all the 301 combinatorially distinct types of polyhedra with up to 8 vertices. On their list, those with 8 vertices and 9 faces are numbers 129 to 202 in [4, Fig. 5]. Of these, we will see that most are indecomposable because they have suf- ficiently many triangles, and 2 are obviously decomposable thanks to Propo- sition 5 (in the simplest geometric realizations, because they have a segment as a summand). The remaining 6 are also indecomposable but arguments using triangular faces alone don’t work; we need to use the results from §1 to establish their indecomposability. Theorem 7. Of the 74 types of polyhedra with 9 faces and 8 vertices, only 2 types are decomposable, 66 types are indecomposable by classical ar- guments, and the remaining 6 require some results from §1 to establish their indecomposability. More precisely: (i) Polyhedra numbers 182 and 198 (on the list of Britton and Dunitz) are decomposable. (ii) Altogether, 66 are indecomposable by virtue of having a connected chain of triangular faces. Specifically, we mean those numbered 129–172, 174–178, 180, 181, 183–186, 188, 189, 191, 193–197, 200–202. more indecomposable polyhedra 179 Figure 4: The Capped Prism, BD182 and BD198 (iii) The other 6, namely numbers 173, 179, 187, 190, 192 and 199, are indecomposable thanks to either Proposition 1 or 3 or Theorem 2. Proof. We begin with the decomposable examples. As remarked in the opening paragraph, a triangular prism is the Minkowski sum of a triangle and a line segment. If we glue a tetrahedron onto one end of a prism, we obtain the capped prism, which is decomposable as the sum of a tetrahedron and a line segment. Better still, Proposition 5 guarantees that any polyhedron combinatorially equivalent to this will be decomposable. There are two ways to glue a second tetrahedron onto the capped prism. Either we glue it onto one face of the first tetrahedron, or we glue it onto the remaining triangular face of the original prism. In both cases, we obtain a polyhedron with 8 vertices and 9 faces. All three are pictured here, the latter two being numbers 182 and 198 respectively from the list of [4]. In case the three edges which lie between pairs of quadrilateral faces are all parallel, each of the latter two polyhedra will be decomposable, being the sum of a triangular bipyramid and a line segment. Since one of them has vertices of degree 5 and the other does not, they are not combinatorially equivalent. This exemplifies the fact that the combinatorial type of two polyhedra does not determine the type of their sum. Our diagrams are not identical to those in [4]; we have drawn them slightly differently to emphasize their decomposability. It is true, but not totally obvious, that any polyhedron combinatorially equivalent to these two will be decomposable. Let us prove it. Proposition 5 clearly implies that [4, 182] is decomposable (but not nec- essarily that a line segment will be a summand). For [4, 198], recall that the capped prism is decomposable, and then apply Proposition 6. Now let us look at the indecomposable examples. Numbers 129, 130 and 180 k. przes lawski, d. yost Figure 5: BD173 and BD179 131 each have one hexagonal face and 8 triangular faces. Each of examples 132–155 has one pentagonal face, one quadrilateral face and 7 triangular faces. Indecomposability of all these examples is assured by our remarks in the pre- vious section, because they have at most two non-triangular faces. Examples 156–181, 183–197 and 199–202 all have three quadrilateral and six triangular faces. By inspection, all but six of them (namely 173, 179, 187, 190, 192 and 199) are indecomposable because (some of) their triangular faces can be ordered into a chain whose union touches every face. We note also that for some examples, the chain of indecomposable triangles does not contain every vertex. (In particular, 157 and several others each have a vertex which does not lie in any triangular face.) Thus the weakness of the assumption, that the chain only touches every face, is significant. Proposition 3 implies the indecomposability of examples 173, 179, 187, 190 and 192 from Britton and Dunitz. Alternatively, their indecomposability can also be established by Proposition 1. None of these examples contains a connected sequence of triangular faces touching every face, so some new technique was needed. We present here their diagrams, with an appropriate 4-cycle highlighted. In each case, three vertices of the 4-cycle lie in one face, while the fourth does not, so the 4-cycle cannot be coplanar. The diagrams make it clear that the 4-cycle touches every face. This time, we have used the same diagrams as in [4], except that for aesthetic reasons we have reversed the front and back faces of 190 and 192. Finally, we recall from §1 that 199 is also indecomposable. We remark that all higher dimensional polytopes with 15 or fewer edges are indecomposable; this extends [19, Proposition 2.11]. The “smallest” d- dimensional polytope, the simplex, obviously has exactly 1 2 d(d + 1) edges. So more indecomposable polyhedra 181 Figure 6: BD187, BD190 and BD192 in dimensions 6 and higher, there are in fact no polytopes with 15 or fewer edges. In dimension 5, the only polytope with 15 or fewer edges is the simplex. Two more examples exist in dimension 4, but the next result shows they are both indecomposable. Proposition 8. The assertion “every 4-dimensional polytope with n edges is indecomposable” is true if and only if n ≤ 15 or n = 17. Proof. Any polytope satisfying these restrictions on n will have at most 7 vertices [7, 10.4.2]. This condition forces indecomposability by [18, Proposi- tion 6]. For the converse, we need to consider various possible values for n. We will simply describe the examples, and not verify all the details. A particularly simple decomposable polytope with 18 edges is the sum of two triangles lying in orthogonal planes. The sum of a 4-dimensional simplex with a line segment, which is parallel to one 2-face but not parallel to any edge of the simplex, will have 19 edges. The sum of a 4-dimensional simplex with a line segment, which is not parallel to any proper face of the simplex, will have 20 edges. Denoting by ei the usual basis vectors, let P be the convex hull of {0,e1,e2, e3,e4,e3 + e4}. Then the sum of P with the segment [0,e1] has 22 edges. The sum of the cyclic polytope C(6, 4) with a line segment which is parallel to one of its edges, will have 25 edges. The sum of a 4-dimensional simplex with a triangle, which is parallel to one of its 2-faces but has the opposite orientation, will have 27 edges. If P is a polyhedron with E edges and V vertices, then the sum of a P with a line segment (not parallel to the affine hull of P) is easily seen to have 182 k. przes lawski, d. yost 2E +V edges. (This is equally true in higher dimensions.) The possible values of E and V for polyhedra are well known [7, §10.3], and the corresponding values of 2E + V account for all remaining values of n. In particular, the sum of a tetrahedron with a line segment has 16 edges. In the next section, we will see that this is (up to combinatorial equivalence) the only example with 16 edges. 3. Polytopes with not too many edges A simplicial prism, i.e. the sum of a segment with a (d− 1)-dimensional simplex, has 2d vertices, d2 edges and d + 2 facets. These numbers turn out be the minimum possible, for a d-dimensional decomposable polytope. In the case of vertices or edges, the prism is (up to combinatorial equivalence) the unique minimiser. In d dimensions, any polytope has at least d+1 facets, and only the simplex has d + 1 facets. So no non-trivial bound on the number of facets will imply indecomposability. Nor can uniqueness be expected; a (d − 2)-fold pyramid over a quadrilateral also has d + 2 facets. For further examples, see Lemma 10 below. The conclusions regarding the numbers of vertices and edges are more in- teresting; for edges, this extends Proposition 8 to higher dimensions. Propo- sition 3 is an essential tool for these. So also is Gale’s result [15, (14)] that any pyramid, i.e. the convex hull of a maximal face and a single point, is indecomposable. This is clear, because every 2-face outside the base must be triangular. As noted in [18, Proposition 6], a d-dimensional polytope with strictly fewer than 2d vertices is automatically indecomposable, and this estimate is the best possible. We will prove now that the simplicial prism is the only decomposable d-polytope with 2d or fewer vertices, before the corresponding result about edges. We have learnt recently that this result was first proved by Kallay [8, Theorem 7.1, page 39] but never published; his argument is different, using Balinski’s Theorem. Recall that a d-polytope P is simple if every vertex is simple, i.e. has degree d. Clearly every simple d-polytope, other than a simplex, is decomposable. Theorem 9. Let P be a decomposable d-dimensional polytope with 2d or fewer vertices. Then P is combinatorially equivalent to the sum of a line more indecomposable polyhedra 183 segment and a (d−1)-dimensional simplex (and hence has precisely d2 edges). Proof. The 2-dimensional case is almost obvious and the 3-dimensional case is quite easy, from §2. We proceed by induction on d. So let P be a decomposable (d + 1)-dimensional polytope with 2(d + 1) or fewer vertices. Then some d-dimensional facet, say F, must be decomposable. Since P is not a pyramid, there must be (at least) two vertices of P outside F; this implies that F has at most 2d vertices. By the inductive hypothesis, F is combinatorially equivalent to the sum of a line segment and a (d−1)-simplex. This means that F has two faces which are simplices, whose vertex sets {v1,v2, . . . ,vd} and {w1,w2, . . . ,wd} can be labelled in such a way that vi is adjacent to wi for each i. In particular F has 2d vertices and d 2 edges. Furthermore there must be precisely two vertices of P outside F , say x and y. Suppose that one of them is adjacent to vertices in both simplices, say [x,vi] and [x,wj] are both edges of P for some i and j. A routine degree argument shows that x is adjacent to at least two vertices in one simplex, so without loss of generality i 6= j. We may renumber the vertices so that i = 1,j = d. But then {v1,v2, . . . ,vd,wd,x} will be an affinely independent (d+2)-cycle. It touches every facet, since P has only 2d+ 2 vertices. This contradicts our assumption that P is decomposable. Thus each of x,y is adjacent to vertices in only one simplex, say x is not adjacent to any wj and y is not adjacent to any vi. Since all vertices have degree at least d + 1, it follows that x is adjacent to each vi, y is adjacent to each wj, and x and y are adjacent to each other. This means that the skeleton of P is isomorphic to the skeleton of the sum of a line segment and a simplex. Now observe that P is simple and so is in fact combinatorially equivalent to the sum of a line segment and a simplex, thanks to a result of Blind and Mani [2]. Proposition 5 implies that if we cut any vertex from any polytope, the resulting polytope will be decomposable. This makes it easy to construct de- composable polytopes with any number of vertices greater than 2d. On the other hand, Proposition 8 asserts that there are gaps in the possibe num- bers of edges of decomposable polytopes, at least in dimension 4. We show now that this is also true in higher dimensions. In fact, a decomposable 184 k. przes lawski, d. yost d-dimensional polytope with strictly less than d2 + 1 2 d edges must be combi- natorially equivalent to a prism; this is an easy consequence of Theorem 9. With some additional material, we can prove a stronger result. We will first examine the existence of simple polytopes with less than 3d vertices. Being decomposable, Theorem 9 implies that no simple d-polytope has between d + 1 and 2d vertices. This also follows from Barnette’s Lower Bound theorem. For results concerning higher numbers of vertices, see [13] and the references therein. We denote by ∆m,n the sum of an m-dimensional simplex and an n- dimensional simplex lying in complementary subspaces. It is routine to check that ∆m,n is a simple (m + n)-dimensional polytope with (m + 1)(n + 1) ver- tices, 1 2 (m + n)(m + 1)(n + 1) edges and m + n + 2 facets. We denote by Wd the result of cutting a vertex from a d-dimensional simplicial prism ∆1,d−1. This simple polytope has 3d− 1 vertices, 1 2 d(3d− 1) edges, and d + 3 facets, comprising 2 simplices, 2 prisms and d − 1 copies of Wd−1. In dimension 3, W3 is simply the 5-wedge. Lemma 10. (i) The (combinatorial types of) simple d-dimensional poly- topes with d + 2 facets are precisely the polytopes ∆k,d−k for 1 ≤ k ≤ 12d. (ii) Up to combinatorial equivalence, the only simple d-dimensional poly- topes with fewer than 3d vertices are the simplex ∆0,d, the simplicial prism ∆1,d−1, the polytope ∆2,d−2, the 6-dimensional polytope ∆3,3, the polytope Wd, the 3-dimensional cube ∆1,1,1 and the 7-dimensional polytope ∆3,4. (iii) For every d 6= 6, the smallest vertex counts of simple d-polytopes are d+1, 2d, 3d−3 and 3d−1. In dimension 6 only, there is also a simple polytope with 3d− 2 vertices. Proof. (i) The simplicial polytopes with d + 2 vertices are described in detail by Grünbaum [7, §6.1], and these are their duals. (ii) Obviously the simplex is the only polytope with d+ 1 (or fewer) facets. Barnette, [1] or [5, §19], showed that a polytope with d + 4 or more facets has at least 4d− 2 ≥ 3d vertices. He also showed that a polytope with d + 3 facets has at least 3d − 1 vertices, and that if d > 3 the only such example with precisely 3d−1 vertices arises from truncating a vertex from a simplicial prism, i.e. it is Wd. If d = 3, the cube ∆1,1,1 is the unique other example. We are left with the case of d + 2 facets. Clearly ∆1,d−1 and ∆2,d−2 have respectively 2d and 3d− 3 vertices. If 3 ≤ k ≤ 1 2 d, then d ≥ 6. If d ≥ 8, then ∆k,d−k has at least (3 + 1)(d−3 + 1) > 3d−1 vertices. If d = 7, we have the example ∆3,4, which has 20 = 3d−1 more indecomposable polyhedra 185 vertices. If d = 6, we must also consider ∆3,3, which has 16 = 3d−2 vertices. (iii) This follows immediately from (ii). Theorem 11. Let P be a decomposable d-dimensional polytope with no more than d2 + 1 2 d edges. Then either P is combinatorially equivalent to a simplicial prism ∆1,d−1 (and hence has precisely d 2 edges), or d = 4 and P is combinatorially equivalent to ∆2,2. Proof. A d-dimensional polytope with 2d + 1 or more vertices must have at least 1 2 (2d + 1)d edges. So if P has 2d + 1 vertices, it must be simple, and Lemma 10 implies that 2d + 1 ≥ 3d− 3. Thus d = 4 and P is ∆2,2. Otherwise, P has at most 2d vertices and the conclusion follows from Theorem 9. In particular, a polychoron with 17 edges is necessarily indecomposable. Grünbaum [7, p 193] showed that there is no polychoron at all with 8 vertices and 17 edges. We finish by using the preceding results to show that this is not an isolated curiosity: in fact, there is no d-dimensional polytope with 2d vertices and d2 + 1 edges for any higher value of d. (There are two easy examples when d = 3; see [4, Fig. 3].) Lemma 12. The polytope ∆2,d−3 cannot be a facet of any decomposable d-dimensional polytope with 3d− 4 vertices. Proof. We can realize ∆2,d−3 as the convex hull of three (d−3)-simplices, say S,T,U, all translates of one another, so that the convex hull of any two of them is a facet therein, combinatorially equivalent to ∆1,d−3. Moreover in each such facet, e.g. co(S,T), each of the d − 2 edges joining S and T also belongs to a triangular face whose third vertex lies in U. Suppose that this copy of ∆2,d−3 is a facet of a decomposable polytope P with 3d − 4 vertices. Denote v,w the two vertices of P lying outside this facet. Then co(S,T) is a ridge in P ; denote by F the other facet containing it. Then F contains at least one of v,w. In particular, F omits at most d − 1 vertices of P . These d − 1 vertices cannot form a facet, so F touches every facet. Decomposability of P then implies that F is also decomposable. Since F has at most 2d − 2 vertices, it can only be a copy of the prism ∆1,d−2, with one of v,w adjacent to every vertex in S and no vertex in T, 186 k. przes lawski, d. yost and the other adjacent to every vertex in T and no vertex in S. The same argument applied to co(T,U) and co(S,U) quickly yields a contradiction. Theorem 13. Let P be a d-dimensional polytope with 2d vertices and d2 + 1 or fewer edges. Then either P is combinatorially equivalent to the prism ∆1,d−1 (and hence has precisely d 2 edges), or d = 3. Proof. If d is 1 or 2, the conclusion is obvious. In case we can establish decomposability, the conclusion will follow from Theorem 11. If P has exactly d2 edges, then it is simple, hence decomposable by Shep- hard’s result, Proposition 5. Since every vertex has degree at least d, P cannot have fewer than d2 edges. We are forced to contemplate the possibility that P has precisely d2 + 1 edges. Then P is indecomposable by Theorem 11. Since 2E −dV = 2, there are at most two vertices which are not simple. Now suppose that some vertex has degree d + 2, and choose a facet F not containing v. Then P must be a pyramid over F, otherwise it would be decomposable by Shephard’s result. Then F has v = 2d − 1 = 2(d − 1) + 1 vertices, and hence at least 1 2 (d− 1)v = (d− 1)2 + 1 2 (d− 1) edges. Hence P will have at least (d − 1)2 + 1 2 (d − 1) + (2d − 1) = d2 + 1 2 d − 1 2 edges. The hypothesis then implies that 1 2 d− 1 2 ≤ 1. We conclude that d = 3 and P is a pentagonal prism. Next consider the case that one vertex v has degree d + 1 and that all its neighbors are simple vertices. If we cut this vertex from P , the resulting facet will be simple and contain d + 1 vertices. This facet cannot be a simplex, so Lemma 10 implies that d + 1 ≥ 2(d− 1), i.e. d ≤ 3. Finally consider the case that P has two adjacent vertices of degree d + 1. We can find a hyperplane which has this edge on one side, and all other vertices of P on the other side. This divides P into two polytopes, say Q and R respectively, with a common facet F. All other vertices are simple, so F will be simple and contain 2d vertices. Now F cannot be a simplex or a prism, because it has more than (d− 1) + 1 or 2(d− 1) vertices. Lemma 10(iii) then forces 2d ≥ 3(d− 1) − 3, i.e. d ≤ 6. If d = 6, then F has 12 vertices, and can only be ∆2,3. But Q has 14 vertices, which is impossible according to Lemma 12. If d = 5, then F is simple and has 10 = 3(d − 1) − 2 vertices, which according to Lemma 10 is impossible unless d − 1 = 6. Grünbaum [7, p 193] showed that the case d = 4 is impossible. The only remaining possibility is that d = 3 and P is combinatorially equivalent to the second last example in [4, Fig. 3]. more indecomposable polyhedra 187 Acknowledgements We thank Eran Nevo for assistance in translating reference [8], and Vladimir Fonf for assistance in translating reference [17]. The second au- thor records his thanks to the University of Zielona Góra, for hospitality during his visits in 2008 and 2011. References [1] D. W. Barnette, The minimum number of vertices of a simple polytope, Israel J. Math. 10 (1971), 121 – 125. [2] R. Blind, P. Mani-Levitska, Puzzles and polytope isomorphisms, Aequa- tiones Math. 34 (2-3) (1987), 287 – 297. [3] D. Briggs, D. Yost, Polyhedra with 16 edges, In preparation. [4] D. Britton, J. D. Dunitz, A complete catalogue of polyhedra with eight or fewer vertices, Acta Cryst. Ser. A 29 (4) (1973), 362 – 371. [5] A. Brøndsted, “An Introduction to Convex Polytopes”, Graduate Texts in Mathematics, 90, Springer-Verlag, New York-Berlin, 1983. [6] E. J. Friedman, Finding a simple polytope from its graph in polynomial time, Discrete Comput Geom. 41 (2) (2009), 249 – 256. [7] B. Grünbaum, “Convex Polytopes”, Second edition, Graduate Texts in Math- ematics, 221, Springer-Verlag, New York, 2003. [8] M. Kallay, “Decomposability of Convex Polytopes”, Ph.D. Dissertation, The Hebrew University of Jerusalem, 1979. [9] M. Kallay, Indecomposable Polytopes, Israel J. Math. 41 (3) (1982), 235 – 243. [10] T. P. Kirkman, Applications of the theory of the polyedra to the enumeration and registration of results, Proc. Roy. Soc. London 12 (1863), 341 – 380. [11] P. McMullen, Indecomposable convex polytopes, Israel J. Math. 58 (3) (1987), 321 – 323. [12] W. J. Meyer, Indecomposable polytopes, Trans. Amer. Math. Soc. 190 (1974), 77 – 86. [13] N. Prabhu, Hamiltonian simple polytopes, Discrete Comput. Geom. 14 (3) (1995), 301 – 304. [14] K. Przes lawski, D. Yost, Decomposability of polytopes, Discrete Comput. Geom. 39 (1-3) (2008), 460 – 468. [15] G. C. Shephard, Decomposable convex polyhedra, Mathematika 10 (1963), 89 – 95. [16] Z. Smilansky, “Decomposability of Polytopes and Polyhedra”, Ph.D. Disser- tation, Hebrew University of Jerusalem, 1986. [17] Z. Smilansky, Decomposability of polytopes and polyhedra, Geom. Dedicata, 24 (1) (1987), 29 – 49. 188 k. przes lawski, d. yost [18] D. Yost, Irreducible convex sets, Mathematika 38 (1) (1991), 134 – 155. [19] D. Yost, Some indecomposable polyhedra, Optimization 56 (5-6) (2007), 715 – 724.