ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 299-315
Minimal equivelar polytopes
Gabe Cunningham
University of Massachusetts Boston Boston, Massachusetts, USA, 02125
Received 20 July 2012, accepted 5 January 2013, published online 10 May 2013
Abstract
Every equivelar abstract polytope of type {p1,..., pn-1} has at least 2p1 • • • pn-1 flags. In this paper, we study polytopes that attain this lower bound, called tight polytopes. Using properties of flat polytopes, we are able to give a complete local characterization of when a polytope is tight. We then show a way to construct tight polyhedra of type {p, q} when p and q are not both odd, and a way to construct regular tight polytopes of type {2ki,..., 2k„_i}.
Keywords: Abstract regular polytope, equivelar polytope, flat polytope, mixing. Math. Subj. Class.: 51M20, 52B15, 05C25
1 Introduction
Abstract polytopes are purely combinatorial generalizations of convex polytopes, maps on surfaces, and infinite tessellations. Their study is a rich and varied field, tying together combinatorics, group theory, topology, and geometry. The most-studied polytopes are those with a high degree of symmetry, including the regular polytopes (see [9]) and the chiral polytopes (see [11, 12]). We also know a great deal about polytopes in rank 3, thanks in part to the fact that every 3-polytope can be naturally associated to a map on a surface (see [10]). In higher ranks, however, relatively little is known about the landscape of polytopes.
In order to understand the structure of polytopes in higher ranks, it would be useful to have many small examples we could study. Furthermore, finding the smallest polytope that satisfies a certain set of properties is a worthwhile and interesting endeavor in and of itself. There are many ways to interpret "smallest" in this context; here, we will work with the number of flags, which is perhaps the easiest and most natural way to quantify the size of a polytope, particularly when working with regular polytopes.
In this paper, we study the smallest equivelar polytopes; that is, polytopes that have a Schlafli symbol. Regular and chiral polytopes are equivelar, as are many other highly-symmetric polytopes, but there are no a priori bounds on how symmetric an equivelar
E-mail address: gabriel.cunningham@gmail.com (Gabe Cunningham)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
284
Ars Math. Contemp. 7 (2014) 281-300
polytope must be. We are able to show that every equivelar polytope with a fixed Schlafli symbol {pi,... ,pn-1} has at least 2p1 • • • pn-1 flags (Proposition 3.3). Our goal is then to study those polytopes for which this lower bound is tight; appropriately enough, we call these tight polytopes. The term was first used by Marston Conder in a mini-course during the Workshop on Symmetry in Graphs, Maps and Polytopes at the Fields Institute in Toronto, Canada, in October 2011. His lecture on the smallest regular polytopes in every rank (which has now been written up in [4]) inspired the work that led to this paper.
We start by presenting background information on polytopes in Section 2. In Section 3, after proving the lower bound for the number of flags of an equivelar polytope, we investigate some simple properties of tight polytopes. Section 4 explores the connection between tightness and flatness of polytopes, and Theorem 4.4 completely characterizes tightness in terms of a local flatness property. In Section 5, we provide a method for building tight polyhedra. Finally, we present a family of regular tight polytopes in every rank in Section 6.
2 Polytopes
Our background information is mostly taken from [9, Chs. 2, 3, 4], with a few small additions.
2.1 Definition of a polytope
Let P be a ranked partially ordered set whose elements will be called faces, and let us say that two faces are incident if they are comparable. The faces of P will range in rank from -1 to n, and a face of rank j is called a j-face. The 0-faces, 1-faces, and (n - 1)-faces are also called vertices, edges, and facets, respectively. A flag of P is a maximal chain. We say that two flags are adjacent if they differ in exactly one face, and that they are j -adjacent if they differ only in their j -face.
If F and G are faces of P such that F < G, then the section G/F consists of those faces H such that F < H < G. If F is a j-face and G is a k-face, then we say that the rank of G/F is k - j - 1. If removing G and F from the Hasse diagram of G/F leaves us with a connected graph, then we say that G/F is connected. That is, for any two faces H and H' in G/F (other than F and G themselves), there is a sequence of faces
H = Ho, Hi,..., Hk = H'
such that, for each 1 < i < k, the faces Hi-1 and Hi are incident and F < Hi < G. By convention, we also define all sections of rank 1 or less to be connected.
We say that P is an (abstract) polytope of rank n, also called an n-polytope, if it satisfies the following four properties:
(a)	There is a unique greatest face Fn of rank n and a unique least face F-1 of rank -1.
(b)	Each flag has n + 2 faces.
(c)	Every section is connected.
(d)	(Diamond condition) Every section of rank 1 is a diamond. That is, whenever F < G, where F is a (j - 1)-face and G is a (j + 1)-face for some j, then there are exactly two j-faces H with F < H < G.
In ranks -1, 0, and 1, there is a unique polytope up to isomorphism. Abstract polytopes of rank 2 are also called abstract polygons, and for each 2 < p < to, there is a unique abstract polygon with p vertices and p edges, denoted {p}.
G. Cunningham: Minimal equivelar polytopes
301
Note that due to the diamond condition, any flag $ has a unique j-adjacent flag (denoted ) for each j = 0,1,..., n - 1.
If F is a j-face and G is a k-face of a polytope with F < G, then the section G/F is a (k - j - 1)-polytope itself. We identify a face F with the section F/F_i and we call the section Fn/F the co-face at F. The co-face at a vertex F0 is also called a vertex-figure at Fo.
If P is an n-polytope, F is an (i - 2)-face of P, and G is an (i + 1)-face of P such that F < G, then the section G/F is an abstract polygon. We say that P has Schlafli symbol {p1,... ,pn-1}, or that P is of type {p1,... ,pn-1} if, for each 1 < i < n - 1, the section G/F is equal to {pi}, no matter which (i - 2)-face F and (i + 1)-face G we choose. If P has a Schlafli symbol, then we say that P is equivelar.
The sections of an equivelar polytope are all equivelar polytopes themselves. In particular, if P is an equivelar polytope of type {p1,... ,pn-1}, then its facets are all equivelar polytopes of type {p1,... ,pn_2}, and its vertex-figures are all equivelar polytopes of type {P2 , . . . ,Pn_1}.
Let P and Q be two polytopes of the same rank. A surjective function 7 : P ^ Q is called a covering if it preserves incidence of faces, ranks of faces, and adjacency of flags. We say that P covers Q if there exists a covering 7 : P ^ Q.
The dual of a polytope P is the polytope obtained by reversing the partial order. If P is an equivelar polytope of type {p1,... ,pn-1}, then the dual of P is an equivelar polytope of type {pn _ 1,..., P1}.
2.2 Regularity
For polytopes P and Q, an isomorphism from P to Q is an incidence- and rank-preserving bijection on the set of faces. An isomorphism from P to itself is an automorphism of P, and the group of all automorphisms of P is denoted r(P). We say that P is regular if the natural action of r(P) on the flags of P is transitive. For convex polytopes, this definition is equivalent to any of the usual definitions of regularity.
Given a regular polytope P, fix a base flag $. Then the automorphism group r(P) is generated by the abstract reflections p0,..., pn-1, where pi maps $ to the unique flag $i that is i-adjacent to $. These generators satisfy p2 = e for all i, and (pipj )2 = e for all i and j such that |i - j| > 2. Every regular polytope is equivelar, and if its Schlafli symbol is {p1,... ,pn-1}, then the order of each pi_1pi is pi. Note that if P is a regular polytope of type {p1,... ,pn_1}, then r(P) is a quotient of the string Coxeter group [p1,... ,pn_1] whose only defining relations are that p2 = e, (pi_1pi)Pi = e, and (pipj-)2 = e whenever |i - j| > 2.
For I C {0,1,..., n - 1} and a group r = (p0,..., p„_1), we define r_f := (pi | i G I). If P is a regular polytope, then its automorphism group r := r(P) satisfies the following intersection condition:
rinrj = r/nJ fori,jc{o,...,n-1}.	(2.1)
In general, if r = (p0,..., pn_1) is a group such that each pi has order 2 and such that (pipj)2 = e whenever |i - j | > 2, then we say that r is a string group generated by involutions (or sggi). If r also satisfies the intersection condition (2.1) given above, then we call r a string C-group. There is a natural way of building a regular polytope P(r) from a string C-group r such that r(P(r)) ~ r and P(r(P)) ~ P. In particular, the
284
Ars Math. Contemp. 7 (2014) 281-302
¿-faces of P(r) are taken to be the cosets of
ri := {Pj I j = i).
where r^ < r^ if and only if i < j and n rj^ = 0. This construction is also easily applied to any sggi (not just string C-groups), but in that case, the resulting poset is not necessarily a polytope.
2.3	Flatness
The theory of abstract polytopes accomodates certain degeneracies not present in the study of convex polytopes. For example, the face-poset of a convex polytope is a lattice (any two elements have a unique supremum and infimum), but this need not be the case with abstract polytopes. The simplest abstract polytope that is not a lattice is the digon {2}, both of whose edges are incident on both of its vertices. This type of degeneracy can be generalized as follows. If P is an n-polytope, and if 0 < k < m < n — 1, we say that P is (k, m)-flat if each of its k-faces is incident on every one of its m-faces. If P has rank n and it is (0, n — 1)-flat, then we also simply say that it is flat. Note that if 0 < i < k < m < j < n — 1 and if P is (k, m)-flat, then it must also be (i,j)-flat. In particular, if P is (k, m)-flat for any 0 < k < m < n — 1, then it is also flat (i.e., (0, n — 1)-flat).
We will also need Lemma 4E3 in [9], which is stated below.
Proposition 2.1. Let P be an n-polytope, and let 0 < k < m < i < n — 1. If each i-face of P is (k, m)-flat, then P is also (k, m)-flat. Similarly, if 0 < i < k < m < n — 1 and each co-i-face of P is (k — i — 1,m — i — 1)-flat, then P is (k, m)-flat.
2.4	Mixing
The mixing construction on polytopes is analogous to the join of two maps or hypermaps [2]. Its principal use is to find a polytope that covers two or more given regular polytopes. We begin by describing the mixing operation on groups (also called the parallel product in [14]). Let r = {x\,..., xn) and r' = {x[,..., x'n) be groups with n specified generators. Then the elements z' = (xi,x'i) G r x r' (for i =1,... ,n) generate a subgroup of r x r' that we denote r o r' and call the mix of r and r' (see [9, Ch.7A]).
If P and Q are regular n-polytopes, we can mix their automorphism groups. Let r(P) = {P0,..., Pn-i) and r(Q) = {p0,..., pn_i). Let a = (pi, pi) G r(P) x r(Q) for 0 < i < n — 1. Then r(P) o r(Q) = {ao,..., an-i). Note that the order of any word ai1 ■ ■ ■ ait is the least common multiple of the orders of pi1 ■ ■ ■ pit and p'ix ■ ■ ■ p'it. In particular, each a.' is an involution, and (a^j )2 = e whenever |i — j| > 2. Therefore, r(P) o r(Q) is a string group generated by involutions, and we can build a poset out of it, called the mix of P and Q and denoted P o Q. This poset will not, in general, be a polytope; indeed, it is a polytope if and only if the group r(P) o r(Q) satisfies the intersection condition (2.1).
The following properties of P o Q follow immediately from the definitions:
Proposition 2.2. Let P be a regular polytope of type {p1,... ,pn-1}, with facets isomorphic to K and vertex-figures isomorphic to L. Let Q be a regular polytope of type {q1,..., qn-1}, with facets isomorphic to K' and vertex-figures isomorphic to L'. If PoQ is a polytope, then its facets are isomorphic to Ko K', its vertex-figures are isomorphic to
G. Cunningham: Minimal equivelar polytopes
303
L o L', and it has type {¿1,..., £n-i}, where ¿i is the least common multiple of pi and qi for 1 < i < n — 1.
Dual to the mix is the comix of two groups. If r has presentation (x1,... ,xn | R) and r' has presentation ( x1,..., x'n | S), then we define the comix of r and r', denoted r □ r', to be the group with presentation
(x 1, x> i, . . . , n, x> n | RR, *S, x> — x> i, . . . , — x> n ) .
Informally speaking, we can just add the relations from r' to r, rewriting them to use xi in place of xi.
The proof of the following simple proposition is essentially the same as [6, Prop. 3.3].
Proposition 2.3. Let P and Q be finite regular n-polytopes. Then
|r(P)or(Q)| • |r(p)nr(Q)| = |r(p)| • |r(Q)|.
When mixing two polytopes, there is no guarantee that the result is itself a polytope. In the following simple cases, however, polytopality is guaranteed.
Proposition 2.4. Let P and Q be regular polyhedra. Then Po Q is a regular polyhedron.
Proof. See [7, Cor. 3.2]	□
Proposition 2.5. Let P be a regular n-polytope with facets isomorphic to K. Let Q be a regular n-polytope with facets isomorphic to K'. If K covers K', then P o Q is polytopal.
Proof. The argument is essentially the same as for Lemma 3.3 in [1].	□
3 Structure of equivelar polytopes
Let |P| denote the number of flags of a polytope P. We start with a couple of general remarks about the structure of equivelar polytopes.
Proposition 3.1. Let P be an equivelar n-polytope of type {p1,... ,pn-1}, with n > 2. Then P has at least pn-1 facets and at least p1 vertices.
Proof. The claim is obvious when n = 2, since the only equivelar 2-polytopes are abstract polygons. Suppose that n > 3 and that the claim is true for all equivelar (n — 1)-polytopes. The vertex-figures of P are equivelar polytopes of type {p2,... ,pn-1}, so by inductive hypothesis, the vertex-figures have at least pn-1 facets. Since each distinct facet of P yields a distinct facet of a vertex-figure of P, it is clear that P itself has at least pn-1 facets. A dual argument shows that P also has at least p1 vertices.	□
Proposition 3.2. Let P be an n-polytope. Then
|P| = E |K|.
facets K of P
Proof. The flags of a facet of P are in one-to-one correspondence with the flags of P containing that facet. The claim follows immediately.	□
We are now able to give a lower bound on the number of flags of an equivelar polytope:
284
Ars Math. Contemp. 7 (2014) 281-304
Proposition 3.3. Let P be an equivelar n-polytope of type {pi,... ,pn-1}, with n > 2. Suppose that P has f facets. Then |P| > 2p1 • • • pn-2f > 2p1 • • • pn-1.
Proof. The claim is obvious when n = 2; in fact, in that case |P| = 2p1. Suppose that n > 3 and that the claim is true for all equivelar (n - 1)-polytopes. The facets of P are equivelar (n - 1)-polytopes of type {p1,... ,pn-2}, so by inductive hypothesis, they each have at least 2p1 • • • pn-2 flags. Then the first inequality follows from Proposition 3.2, and the second inequality follows from Proposition 3.1.	□
Our main interest is in polytopes for which the bound in Proposition 3.3 is tight, and thus we make the following definition.
Definition 3.4. Let P be a finite equivelar n-polytope of type {p1,... ,pn-1}, with n > 2. (In particular, we suppose that each pi is finite.) If |P| = 2p1 • • • pn-1, then we say that P is tight.
By Proposition 3.3, tight polytopes have the minimal number of flags for their given Schlafli symbol. Note that the dual of a tight polytope is also tight.
Every (finite) polygon is tight, since {p} has 2p flags. There are also many examples in the literature of tight polyhedra, including the hemi-cube {4, 3}3 (see [9, Sect. 4E]), the regular toroidal map {4,4}(2 0) (see [5]), and a chiral map of type {6,9} (denoted C7.1 at [3], and appearing earlier in [15]). There are fewer notable examples in higher ranks, but the locally toroidal 4-polytope {{3, 6}(11), {6, 3}(11)} (see [13]) is one such example.
Many different (non-isomorphic) tight polytopes can share the same Schlafli symbol, even if they are regular. For example, there are three regular polytopes of type {4, 6} with 48 flags listed at [8]. On the other hand, some Schlafli symbols are unable to support any tight polytopes at all:
Proposition 3.5. Let P be an equivelar n-polytope of type {p1,... ,pn-1}, with n > 3. If every pi is odd, then P is not tight.
Proof. First, we note that if n = 3, then every edge is incident on two vertices and two facets, so |P| is divisible by 4. Otherwise, if n > 4, then 4 divides the number of flags in every 3-face of P, so again |P| is divisible by 4. Thus, if every pi is odd, 2p1 • • • pn-1 cannot equal |P|.	□
As a consequence of Proposition 3.5, though every tight polytope is minimal (i.e., has the fewest flags among polytopes with the same Schlafli symbol), not every minimal polytope is tight. For example, for each n, the minimal (and only) polytope of type {3,..., 3} is the n-simplex, which has (n +1)! flags instead of the 2 • 3n-1 required in order to be tight.
We now examine some of the basic structure of tight polytopes.
Proposition 3.6. Let P be a tight n-polytope of type {p1,... ,pn-1}, with n > 2. Then P has pn-1 facets and p1 vertices.
Proof. The first part follows from Proposition 3.3 combined with Definition 3.4, and the second part follows from a dual argument.	□
Proposition 3.7. Let P be a tight n-polytope of type {p1,... ,pn-1}, with n > 3. Then every facet and vertex-figure of P is tight.
G. Cunningham: Minimal equivelar polytopes
305
Proof. By Proposition 3.6, P has pn-1 facets; each of these is an equivelar polytope of type {pi,... ,pn-2}. Then Proposition 3.3 says that each of those facets has at least 2p1 • • • pn-2 flags. If any facet has more than that many flags, then Proposition 3.2 implies that P has more than 2p1 • • • pn-1 flags, contradicting the tightness of P. The other part then follows by a dual argument.	□
Proposition 3.8. Let P be a tight polytope. Then every section of P of rank 2 or greater is tight.
Proof. Let Fj and Fj be faces of P of rank i and j, respectively, such that Fj < Fj and
j - i > 3. Let
F-i < • • • < Fj < • • • < Fj < • • • < Fn
be a flag of P containing Fj and Fj. Now, Proposition 3.7 tells us that since P is tight, so is the section Fn-1/F-1. Similarly, the section Fn-2/F-1 must be tight. Continuing in this manner, we can conclude that Fj/F-1 is tight. Now, since Fj/F-1 is tight, so are its vertex-figures Fj/F0, and by repeatedly applying Proposition 3.7 again, we see that Fj/Fj is itself tight.	□
Propositions 3.7 and 3.8 prove extremely useful in deducing properties of tight poly-topes. Using these results, we are often able to prove that tight polytopes satisfy a certain property by using induction on the rank.
By combining Proposition 3.8 with Proposition 3.5, we can prove the following:
Proposition 3.9. Let P be a tight n-polytope of type {p1,..., pn-1}, with n > 3. Then no two consecutive values pj and pj+1 are both odd.
4 Flatness and tightness
In order for a polytope to be small enough to be tight, there must be a high number of incidences among a small number of faces. These incidences force the polytope to be flat:
Proposition 4.1. Let P be a tight n-polytope, with n > 3. Then P is flat; that is, every facet is incident on every vertex.
Proof. First, suppose that P is a tight 3-polytope of type {p1, p2}. Then the facets are p1-gons and Proposition 3.6 tells us that there are only p1 vertices; therefore, P is flat. Now, suppose that n > 4 and that the claim is true for tight (n-l)-polytopes. By Proposition 3.7, the facets of P are tight. Therefore, by inductive hypothesis, the facets are flat (that is, (0, n - 2)-flat). Then Proposition 2.1 says that P is itself (0, n - 2)-flat, from which it follows that P must also be (0, n - 1)-flat.	□
In fact, tight polytopes actually satisfy a much stronger property:
Proposition 4.2. Let P be a tight n-polytope with n > 2. Then P is (i, i + 2)-flatfor each 0 < i < n - 3.
Proof. For n = 2, there is nothing to prove, and by Proposition 4.1, the claim is true for n = 3. Suppose that n > 4 and that the claim is true for all tight (n - 1)-polytopes. By Proposition 3.7, the facets of P are all tight. Therefore, by inductive hypothesis, the facets are all (i, i + 2)-flat for 0 < i < n - 4. Then we can apply Proposition 2.1 to conclude that
284
Ars Math. Contemp. 7 (2014) 281-306
P is itself (i, i + 2)-flat for 0 < i < n - 4. Similarly, the vertex-figures of P are all tight, and by inductive hypothesis, they are all (i, i + 2)-flat for 0 < i < n - 4 Therefore, by Proposition 2.1, P is (i + 1, i + 3)-flat for 0 < i < n - 4; in other words, it is (i, i + 2)-flat for 1 < i < n — 3, and the claim follows.	□
Using the following lemma, we can show that this strong flatness property fully characterizes tight polytopes.
Lemma 4.3. Let P be a flat equivelar n-polytope of type {pi,... ,pn-i}, with n > 2. If P has tight facets and tight vertex-figures, then P is tight.
Proof. For n = 2, the claim is trivial, since all equivelar polytopes of rank 2 are (abstract) polygons, which are tight. If n > 3, then the vertex-figures of P are polytopes of type {p2,... ,pn-i}. By assumption, the vertex-figures are tight, and thus they have 2p2 • • • pn-i flags. The facets of P are polytopes of type {pi,... ,pn-2}, and these are also tight by assumption. Therefore, Proposition 3.6 says that each facet has pi vertices. Now, since P is flat, every facet is incident on every vertex, and thus the facets all share the same pi vertices. Therefore, P has pi vertices, and thus |P| = 2pi • • • pn-i by the dual version of Proposition 3.2.	□
Theorem 4.4. Let P be an equivelar n-polytope, with n > 2. Then P is tight if and only if it is (i, i + 2)-flatfor each 0 < i < n — 3.
Proof. The claim is trivial for n = 2, and Proposition 4.2 settles one direction for all n > 3. Now, suppose that n > 3, that the claim is true for rank n - 1, and that P is an equivelar n-polytope that is (i, i + 2)-flat for each 0 < i < n - 3. The facets of P are equivelar (n - 1)-polytopes, and since P is (0, 2)-flat, every facet of P must also be (0, 2)-flat. Similarly, for any given facet of P and for every 0 < i < n - 4, that facet is (i, i + 2)-flat. Therefore, by inductive hypothesis, the facets are all tight. A similar argument shows that the vertex-figures are tight. Since P is (0,2)-flat, it is a flat equivelar n-polytope with tight facets and vertex-figures; therefore, Lemma 4.3 says that P is tight.	□
Corollary 4.5. An equivelar polyhedron is tight if and only if it is flat.
Theorem 4.4 turns the global criterion for tightness into a series of local criteria, which makes it much easier to build a tight polytope inductively.
5 Tight polyhedra
As we have seen, tight polytopes have a number of restrictive properties. We begin to wonder to what extent they exist. For example, Proposition 3.5 tells us that if p and q are both odd, then there is no tight polyhedron of type {p, q}. It turns out that the condition that p and q are not both odd is also sufficient for the existence of such polyhedra.
Theorem 5.1. Suppose p and q are not both odd. Then there is a tight polyhedron of type
fe q}.
Proof. By working with the dual if necessary, we can assume that p is even. In light of Corollary 4.5, it suffices to show that there is a flat equivelar polyhedron of type {p, q}. In other words, we need to construct a polyhedron such that
(i) The facets are p-gons.
G. Cunningham: Minimal equivelar polytopes
307
(ii)	The vertex-figures are q-gons.
(iii)	Every facet is incident on every vertex.
(iv)	Every edge is incident on two vertices and two facets.
(v)	For every pair of facet and vertex, there are two edges incident to both.
We start with p vertices, labeled v^ ..., vp. Let m = |_2J, and for 1 < i < p and 1 < j < m, add an edge e^- incident on vertices vi and vi+1 (where vp+1 means vi). That is, we start with ap-cycle with m-tuple edges. To finish the construction, we consider three cases.
(a)	Suppose q is also even, so that q = 2m. For 1 < t < m, the face f2t-1 will consist of the simple cycle e1jt, e2,t,..., ep,t, while the facet f2t will consist of the simple cycle e1t, e2 t+1, e3 t,..., ep t+1 (where ei m+1 is understood to be ei1). It is clear, then, that each facet is a p-gon.
(b)	Suppose that q is odd, so that q = 2m + 1, and suppose that p = 4s + 2 for some s. For each 1 < i < p/2, we add an edge di incident to vi and v2s+1+i (reducing the index 2s + 1 + i modulo p if necessary). Faces f1 through f2m-1 are generated in the same way as in the previous case. Face f2m consists of the edges e1jm, e3,m,..., ep-1,m as well as the edges d1,..., dp/2. Finally, facet f2m+1 consists of the edges e2j1, e4j1,..., ePj1 as well as the edges d1,..., dp/2. Though it is clear that f1,..., f2m-1 are all p-gons (i.e., simple cycles), we need to prove the same for the faces f2m and f2m+1. In f2m, starting from 1, we visit vertices in the order
1, 2, 2s + 3, 2s + 4, 3, 4, ..., 4s + 1, 4s + 2, 2s + 1, 2s + 2, 1;
therefore, we get a simple cycle. Similarly, starting from 2 in f 2m+1, we visit vertices in the order
2, 3, 2s + 4, 2s + 5, 4, 5, ..., 4s + 2, 1, 2s + 2, 2s + 3, 2;
again, we get a simple cycle. See Figure 1 for an illustration of the three faces when p = 6 and q = 3. (In this case, we obtain the toroidal polyhedron {6, 3}(11); see [9, Ch. 1D].)
Figure 1: The three faces of a tight polyhedron of type {6,3}
(c) Suppose again that q is odd, so that q = 2m + 1, but now suppose that p = 4s for some s. Add an edge di incident to vi and v2s+1, and for each 2 < i < 2s, add an
284
Ars Math. Contemp. 7 (2014) 281-308
edge cj incident to v and v4s-i+2 (reducing the index 4s - i + 2 modulo p if necessary). We construct f i,..., f2m-1 as before. The facet f2m consists of the edges ei,m, e3,m,..., ep-i,m as well as d1 and c2,..., c2s. Similarly, the facet f2m+i consists of the edges e2,1, e4,1,..., ep,1, as well as the edges d1 and c2,..., c2s. Once more, we need to show that f2m and f2m+1 are simple cycles. In f2m, we visit the vertices in the order
1, 2, 4s, 4s - 1, 3, 4, ..., 2s - 1, 2s, 2s + 2, 2s + 1, 1, and in f2m+1, we visit the vertices in the order
2, 3, 4s - 1, 4s - 2, 4, 5, ..., 2s, 2s + 1, 1, 4s, 2. See Figure 2 for an illustration of the three faces when p = 8 and q = 3.
Figure 2: The three faces of a tight polyhedron of type {8,3}
Now, in every case, we have demonstrated that the faces are p-gons, and since there are only p vertices, it is clear that every facet is incident to every vertex. Furthermore, each edge is incident on exactly two vertices and two faces. Since each facet is a simple cycle, every facet/vertex pair has exactly two edges in common. It remains to be shown that the vertex-figures are q-gons. In fact, at any given vertex, the sequence f1, f2,..., fq yields a simple cycle of faces, where consecutive faces share one of the edges at that vertex. Therefore, the vertex-figures are q-gons, completing the proof.	□
The construction used here is by no means canonical; there are many tight polyhedra that do not arise in this way. For example, we can build a tight polyhedron of type {4,6} that includes two edges between every pair of vertices (see Figure 3). In the tight polyhedron of type {4, 6} that Theorem 5.1 produces, each vertex shares three edges with each of two other vertices. These two polyhedra are clearly non-isomorphic.
Note also that when q is odd and q > 5, then the tight polyhedron of type {p, q} that we construct is not regular. In fact, it is not even edge-transitive, since some pairs of vertices have m edges between them, while other pairs have only a single edge.
6 Regular tight polytopes
Our goal now is to find tight polytopes that are regular. As we commented earlier, the polyhedra that we construct in Theorem 5.1 often fail to be regular. Is this a defect of the construction, or do such tight regular polyhedra even exist? Consider, for example,
G. Cunningham: Minimal equivelar polytopes
309
Figure 3: The six faces of a tight polyhedron of type {4, 6}
tight polyhedra of type {8, 5} and of type {10, 5}. By checking the list of small regular polytopes at [3], we see that there are no tight regular polyhedra of type {8,5}, but that there is a tight regular polyhedron of type {10,5}. Other than this polyhedron and the universal polyhedron of type {2, 5}, no other tight regular polyhedra of type {p, 5} are listed. Since the list includes all regular polytopes with up to 2000 flags, we can conclude that there are no tight regular polyhedra of type {p, 5} when 11 < p < 200. Similar observations for other odd values of q lead us to the following conjecture.
Conjecture 6.1. Let q be odd and p > 2q. Then there are no regular tight polyhedra of type {p, q}.
When p and q are both even, the situation is entirely different. For even p and q, there is always a regular tight polyhedron of type {p, q}. In fact, with a little more work, we can build a regular tight polytope in any rank as long as each p4 is even. We start by giving a presentation for the automorphism group. We define r(ki,..., kn-1) to be the quotient of [2ki,..., 2kn-1] by the n - 2 extra relations (pipi+1pi+2pi+1)2 = £, where 0 < i < n - 3. That is,
. . . , kn-1 ) = (pc^ . . . , Pn—1 |Po = • • • = Pil-1 = £
(P0P1)2kl = • • • = (Pn-2 Pn— 1 )2kn— 1 = £, (pipj)2 = £ if |i - j| > 2,
(P0P1P2P1)2 = • • • = (Pn—3Pn—2Pn—1Pn—2)2 = e). Thus, for n = 3, we get the presentation
^(k1, k2) = W P1, P2 |P2 = P1 = P2 = £,
(p0P1)2kl =(P0P2)2 = (p1P2)2k2 = £, (P0P1P2P1)2 = e).
284
Ars Math. Contemp. 7 (2014) 281-310
We define P(ki,..., kn_i) to be the poset P(r(ki,..., k„_1)). (See [9, Ch. 2E] for the details of this construction.) Our goal will be to show that P(k1,..., kn-1) is a regular tight polytope of type {2k1,..., 2kn-1}. We start by working with the case n = 3:
Lemma 6.2. The group r(k1, k2) has order 8k1k2.
Proof. Let r(k1,k2) = (p0, p1, p2), and let a = (p1 p2)2. The relation (pop1p2p1)2 = £ implies that
P0(P1P2P1P2)P0 = (P0P1P2P1)P2P0 = (P1P2P1P0)P2P0
= P1 P2 P1 P2 ,
so that P0aP0 = a. Furthermore, P1aP1 = a-1 = P2aP2. Therefore, the cyclic subgroup N of order k2 generated by a is normal in r(k1, k2). Now, by adding the relation a = £ to the relations of r(k1, k2), we can pass to the factor group r(k1, k2)/N. In the factor group, the relation (p0p1p2p1)2 = £ is equivalent to (p0p2)2 = £, rendering the former relation redundant. Then we can remove that relation and the redundant relation (p1p2)2k2 = £ to see that the factor group has presentation
(P0,P1,P2 |P2 = P1 = P2 = £,
(P0P1)2k1 = (P0P2)2 = (P1P2)2 = £).
This is the presentation for the Coxeter group [2k1,2] of order 8k1, and since N has order k2, the order of r(k1,k2) is 8k1k2.	□
Theorem 6.3. The poset P (k1, k2) is a tight regular polyhedron of type {2k1, 2k2}, and
P(k1,k2) = P(k1,1) oP (1,k2) = {2k1, 2}o{2, 2k2}.
Proof. First of all, it is clear from the presentations of their automorphism groups that P(k1,1) = {2k1, 2} and P(1, k2) = {2, 2k2}. Let P = {2k1,2} o {2, 2k2}. By Proposition 2.4, P is a regular polyhedron, and its type is {2k1, 2k2}. Now, in [2k1,2], the generator p2 is in the center, so the relation (p0p1 p2p1)2 = £ holds. Similarly, in [2,2k2], the generator p0 is in the center, and again the relation (p0p1p2p1)2 = £ holds. Therefore, this relation must hold in the mix of the two groups, which is r(P). Then r(P) satisfies all of the relations of r(k1, k2), and thus it is a (not necessarily proper) natural quotient of r(k1, k2). Since r(k1, k2) has order 8k1k2 (by Lemma 6.2), the group r(P) has order 8k1k2 or less. On the other hand, P is a regular polyhedron of type {2k1,2k2}, and so r(P) must have order at least 8k1k2. Therefore, |r(P)| = 8k1k2, from which it follows that r(P) = r(k1, k2). Therefore, P(k1, k2) = P, a regular tight polyhedron of type {2k1,2k2}. □
We note here that the polyhedron P(k1, k2) is isomorphic to the tight polyhedron P of type {2k1,2k2} that we built in Theorem 5.1. Indeed, if we take the base flag $ of P to
G. Cunningham: Minimal equivelar polytopes
311
consist of vi, ei,i and /1, then there are automorphisms po, Pi, and p2 that act as follows.
po : Vj ^ V2fcl+3-i
ei,j ^ e2fci+2-i,j Fixes all faces
pi : Vj ^ V2fci+2-i
ej,j ^ e2fci+i-iifc2+2-j ^ f2fc2 + 2-i
p2 : Fixes all vertices
Jei,fc2+2-j if i is odd, ei,j ^ % .....
[eiifc2+3-j if i is even
^ f2fc2+3-i
(If necessary, we reduce the index of v modulo 2ki, the index of / modulo 2k2, and the indices of e modulo 2ki and k2, respectively.) Since each pj sends $ to $j, this suffices to show that P is regular. It is also simple to verify that (p0pip2pi)2 = e, from which it follows that P is a quotient of P(ki, k2). Then since P and P(ki, k2) have the same number of flags, they must be isomorphic.
In order to extend the result of Theorem 6.3 to higher ranks, we start with several lemmas.
Lemma 6.4. Let r(ki,..., kn-i) = (po,..., pn-i). Then pn-i ^ (po,..., pn-2).
Proof. Let r := r(ki,..., kn-i) = (p0,..., pn-i). Every relator of r contains every generator an even number of times (possibly zero). Therefore, any relation of the form pn-i = w that holds in r must have at least one instance of pn-i appearing in w. In particular, pn-i (po,..., pn-2).	□
Lemma 6.5. Let r(ki,..., kn-i) = (po,..., pn-i). Then
(po,..., pn-2) — r(ki,..., kn-2)
and
n-1 ).
Proof. It suffices to prove the first claim, since the second will then follow from a dual argument. Let r(ki,..., kn-i) = (po,..., pn-i), and let r = (po,..., pn-2). It is clear that r is a natural quotient of r(ki,...,kn-2), since the generators of r satisfy all of the relations that are satisfied by the generators of r(ki,...,kn-2). The generators of r also satisfy the extra relations
(pn-3pn-2pn-ipn-2 )2 = e, (pn-2pn-i)2kn-1 = e,
and
(pjpn-i)2 = e, for 0 < i < n — 3.
284
Ars Math. Contemp. 7 (2014) 281-312
It remains to show that these extra relations do not cause r to collapse to a proper quotient of r(ki,..., kn-2). Suppose we add the relation pn-1 = e to the relations of r to obtain a new group r'. In r', we can rewrite the relations above as
Pn-3 = e,
2fc„-i = e
Pn 2 = e,
and
p2 = e for 0 < i < n - 3.
and these relations are all redundant with the relations that come from r(ki,..., kn-2). Therefore, we can eliminate these relations from r'. Then r' has all of the relations from r(k1,..., kn-2) and the single extra relation pn-1 = e. Since this is the only remaining relation that contains pn-1, and since r' = (p0,..., pn-2), we can remove that relation without affecting r'. So we see that we can take the relations of r(k1,..., kn-2) to be the defining relations of r', from which it follows that r' — r(k1,..., kn-2). Since r' is a natural quotient of r, which is a natural quotient of r(k1,..., kn-2), we see that r - r( k 1,..., kn-2) as well.	□
Lemma 6.6. Suppose that P (k1,..., kn-2) is a tight regular polytope of type {2k1,..., 2kn-2} andthat P (k2,..., kn-2,1) is a tight regular polytope of type {2k2,..., 2kn-2, 2}. Then P (k1,..., kn-2,1) is a tight regular polytope of type {2k1,..., 2kn-2, 2}.
Proof. Let r(k1,..., kn-2,1) = (p0,..., pn—1). To prove polytopality and regularity, it suffices to show that r(k1,..., kn—2,1) is a string C-group. By Lemma 6.5,
(po,..., Pn-2) - r(k1,..., kn-2)
and
(P1, . . . ,Pn-1) - r(k2, . . . , kn-2, 1).
By assumption, both of these subgroups are string C-groups. Then [9, Prop. 2E16 (a)] says that r(k1,..., kn-2,1) is a string C-group if
(po, . . . , Pn-2) n (p1, . . . ,Pn-1) = (P1, . . . , Pn-2). Let v be in this intersection. Now,
v e (P1, . . . ,Pn-1) - r(k2, . . . , kn-2, 1).
By inspecting the presentation for this group, we see that pn-1 is in the center. Therefore, we may write v = upn-1 with u e (p1,..., pn-2) and where i is 0 or 1. On the other hand, v e (p0,..., pn-2), and therefore
Pn-1 = U 1v e (P0, . . . ,Pn-2).
Since pn-1 e (p0,..., pn-2) by Lemma 6.4, it follows that i = 0 and that v = u. Therefore, v e (p1,..., pn-2), and thus
(PQ, . . . ,Pn-2) H (pi, . . . ,Pn-l) < (Pi, . . . ,Pn-2).
G. Cunningham: Minimal equivelar polytopes
313
The other containment being obvious, we see that r(ki,..., kn-2,1) is a string C-group, and therefore, P(k1,..., kn-2,1) is a regular polytope. Next, we observe that
r(ki, . . . ,kn_2, 1) = (po, . . . ,Pn-l)
= (P0, . . . ,Pn-2) X (p„-l),
since pn-1 is in the center. Then since P(k1,..., kn-2) is of type {2k1,..., 2kn-2}, it follows that P(k1,..., kn-2,1) is of type {2k1,..., 2kn-2,2}. Furthermore,
|P (k1,...,k„-2, 1)| =2|P (k1,...,k„-2)|
= 2 • (2k1 ••• 2k„-2 • 2),
and therefore P(k1,..., kn-2,1) is tight.	□
Lemma 6.7. Let k1,..., kn-1 and k',..., be positive integers. If for each i, k' divides kj, then r(k1,..., kn-1) naturally covers r(k1,..., k^-1).
Proof. When each kj divides kj, the group r(k',..., k^-1) satisfies all of the same relations as r(k1,..., kn-1), and the result follows.	□
Theorem 6.8. The poset P(k1,..., kn-1) is a tight regular n-polytope of type {2k1,..., 2kn-1}, andP(k1,... ,kn-) = P(k1,... ,kn-2,1) oP(1,k2,..., kn-1).
Proof. Theorem 6.3 shows that the claim is true for n = 3. Suppose that n > 4 and that the claim is true in rank n - 1. Let r = r(kb ..., kn-2,1), P = P(r), F = r(1, k2,..., kn-1), and P' = P(F). We need to show three things:
(a)	P o P' is a regular polytope of type {2k1,..., 2kn-1}
(b)	|ror'| = 2nk1 ••• kn-1
(c)	r(k1,...,kn-1) = ror'
By inductive hypothesis, P(k1,..., kn-2) is a tight regular polytope of type {2k1,..., 2kn-2}, and P(k2,..., kn-2,1) is a tight regular polytope of type {2k2,..., 2kn-2, 2}. Therefore, by Lemma 6.6, the poset P = P(k1,..., kn-2,1) is a tight regular polytope of type {2k1,..., 2kn-2, 2}. A dual argument shows that P' is a tight regular polytope of type {2, 2k2,..., 2kn-1}. Now, by Lemma 6.5, the facets of P have group r(k1,..., kn-2), whereas the facets of P' have group r(1, k2,..., kn-2). Then Lemma 6.7 says that the group r(k1,..., kn-2) covers r(1, k2,..., kn-2), and thus the facets of P cover the facets of P'. Then P o P' is a regular polytope, by Proposition 2.5. By Proposition 2.2, the facets of PoP' are isomorphic to P(k1,..., kn-2)oP(1, k2,..., kn-2) = P(k1,..., kn-2), the vertex-figures are isomorphic to P(k2,... ,kn-2,1)oP(k2,... ,kn-1) = P(k2,... ,kn-1), and PoP' is of type {2k1,..., 2kn-1}.
Next we show that r o r' has the appropriate size. By Proposition 2.3,
|r o F|-|rHr|
|rnF|' Since P and P' are tight,
|r| = 2nk1 ••• kn-2
284
Ars Math. Contemp. 7 (2014) 281-314
and
|r'| = 2nk2 ••• An-1.
Now, we obtain a presentation for r □ r' by adding the relations for r' to those for r. This gives us a presentation for the group r(1, k2,..., kn-2,1). Using Lemma 6.6 again, we can conclude that P (1, k2,..., kn-2,1) is a tight regular polytope of type {2, k2,..., kn-2,2}. Therefore,
|rnr'| = |r(i,k2,...,kn_2,1)|
= 2"k2 ••• kn_2,
and thus
|r| • r
|r o r'|
|rnr'|
(2nki ••• k„_2)(2"k2 ••• k„-i)
2nk2 • • •kn-2
2"k1 • • • i.
So P o P' is tight.
It remains to show that r o r' is naturally isomorphic to r(ki,..., kn-1). It is clear from the presentation for r that r(k1,..., kn-1) covers r and that the natural covering map is one-to-one on the subgroup (p0,..., pn-2). Then since r is a string C-group (because P is a polytope), we can apply [9, Thm. 2E17] to see that the group r(k1,..., kn-1) is also a string C-group. Therefore, P(k1,..., kn-1) is a regular polytope, and Lemma 6.5 says that its facets are P(k1,..., kn-2) and its vertex-figures are P(k2,..., kn-1). By [9, Thm. 4E5], since P(k1,..., kn-2) and P(k2,..., kn-1) are both flat, there is only a single regular polytope (up to isomorphism) with those facets and vertex-figures. Since PoP' is one such regular polytope, we see that P (k1,..., kn-1) = P (k1,..., kn-2,1) o P(1, k2,..., kn-1), as desired.	□
Theorem 6.8 gives us an easy way to generate small regular polytopes in any rank, providing us with many more examples we can study. We note that it is also possible to prove the existence of a tight regular polytope of type |2ki,..., 2k„_i} in an entirely group-theoretic way; Marston Conder provides such an account as [4, Thm. 5.3] (and indeed, his regular polytopes are isomorphic to ours).
Acknowledgments
The author would like to thank Marston Conder for valuable feedback on an earlier draft of this paper. He also thanks the anonymous referees for several helpful comments.
References
[1]	A. Breda D'Azevedo, G. Jones and E. Schulte, Constructions of chiral polytopes of small rank, Canad. J. Math. 63 (2011), 1254-1283.
[2]	A. Breda D'Azevedo and Roman Nedela, Join and intersection of hypermaps, Acta Univ. M. Belii Ser. Math. 9 (2001), 13-28.
G. Cunningham: Minimal equivelar polytopes
315
[3]	M. Conder, Lists of all regular polytopes with up to 2000 flags, http://www.math. auckland.ac.nz/~conder.
[4]	M. Conder, The smallest regular polytopes of given rank, Adv. Math. 236 (2013), 92-110.
[5]	H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, fourth ed., Ergebnisse der Mathematik und ihrer Grenzgebiete (Results in Mathematics and Related Areas), vol. 14, Springer-Verlag, Berlin, 1980.
[6]	G. Cunningham, Mixing chiral polytopes, J. Alg. Comb. 36 (2012), 263-277.
[7]	G. Cunningham, Self-dual, self-petrie covers of regular polyhedra, Symmetry 4 (2012), 208218.
[8]	M. I. Hartley, An atlas of small regular abstract polytopes, Periodica Mathematica Hungarica 53 (2006), 149-156.
[9]	P. McMullen and E. Schulte, Abstract regular polytopes, Encyclopedia of Mathematics and its Applications, vol. 92, Cambridge University Press, Cambridge, 2002.
[10]	R. Nedela, Maps hypermaps and related topics, 2007, http://www.savbb.sk/ -nedela/CMbook.pdf.
[11]	D. Pellicer, Developments and open problems on chiral polytopes, Ars Math. Contemp. 5 (2012), 333-354.
[12]	E. Schulte and A. Ivic Weiss, Chiral polytopes, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 493-516.
[13]	E. Schulte and A. Ivic Weiss, Chirality and projective linear groups, Discrete Math. 131 (1994), 221-261.
[14]	S. Wilson, Parallel products in groups and maps, J. Algebra 167 (1994), 539-546.
[15]	S. Wilson, The smallest nontoroidal chiral maps, J. Graph Theory 2 (1978), 315-318.