Polyhedral Embeddings of Cayley Graphs

Polyhedral Embeddings of Cayley Graphs

Available online at www.sciencedirect.com Electronic Notes in Discrete Mathematics 43 (2013) 279–288 www.elsevier.com/locate/endm Polyhedral Embeddi...

Available online at www.sciencedirect.com

Electronic Notes in Discrete Mathematics 43 (2013) 279–288 www.elsevier.com/locate/endm

Polyhedral Embeddings of Cayley Graphs Jes´ us De Loera 1,3 Department of Mathematics University of California, Davis Davis, CA USA

Yvonne Kemper 1,2,4 Department of Mathematics University of California, Davis Davis, CA USA

Abstract When is a Cayley graph the graph of a convex d-polytope? We show that while this is not always the case, some interesting ﬁnite groups have this property. Keywords: Cayley graphs, convex polytopes, realization spaces, embeddings.

1

Introduction

Given a group Γ and a set of generators and relations Λ of Γ, it is well-known [5,11] that we can construct a directed, edge-colored graph C(Γ, Λ) in the 1

Both authors are grateful to Christian Haase, Mikhail Kapovich, and Viera Proulx for very useful suggestions. 2 The second author is grateful for support by VIGRE NSF-grant DMS #0636297. 3 Email: [email protected] 4 Email: [email protected] 1571-0653/\$ – see front matter © 2013 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.endm.2013.07.045

280

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

following way. The elements of Γ are the vertices of the graph, and there is a directed edge of color h from g1 to g2 if there exists a generator h ∈ Λ such that g1 h = g2 . This graph is the Cayley color graph of (Γ, Λ), denoted C(Γ, Λ). If we forget the colors and directions of the edges of a Cayley color graph C(Γ, Λ), we obtain the Cayley graph of (Γ, Λ), denoted G(Γ, Λ). It is immediate to recover the group from a Cayley color graph: all the basic information of the group is contained in the graph. In particular, the relations of the group are the cycles of the graph, and a word in the group is a walk on the graph. In this paper, we restrict ourselves to Cayley graphs that come from minimal presentations of the group, namely presentations in which no generator in Λ can be expressed in terms of the remaining generators. The geometric properties of groups have been studied for a long time in various contexts. First, graph theorists have looked at the embeddability of Cayley graphs on surfaces. For every graph G, we can ﬁnd an orientable surface S of minimal genus such that G has an embedding in S. The genus of G is then the genus of S. The genus of a group Γ, γ(Γ), is the minimal genus among the genera of all possible Cayley graphs of Γ. The classiﬁcation of the groups of a given genus has been completed for genus zero [11], one [13], and two [16], but it remains an open problem for genus greater than two [17]. Further, the embeddings of (mainly inﬁnite) Cayley graphs have been the subject of research investigations by geometric group theorists (see [1]). The combinatorial representation theory of ﬁnite groups has been a third point of intersection for convex geometry and group theory. In this case, polytopes arise as the convex hulls of images of ﬁnite groups under ﬁxed real representations. Of particular interest are permutation polytopes – these are polytopes arising from a subgroup H of the symmetric group Sn , where the representation of H is obtained by restricting a representation of Sn (see e.g., [3,7] and references therein). The focus of this paper is the question: when is a Cayley graph the graph of a d-dimensional convex polytope? We show that this is not always the case, but give a few instances in which the Cayley graph allows for these “convex polyhedral” embeddings: Theorem 1.1 The Cayley graph of a minimal presentation of the quaternion group cannot be embedded as the graph of a convex polytope. Theorem 1.2 Let Γ be a ﬁnite group with a minimal set of generators and relations Λ. The associated Cayley graph is the graph of a 3-dimensional polytope if and only if Γ is a ﬁnite group of isometries in 3-dimensional space.

281

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

2

Not all Cayley graphs are polyhedral

The purpose of this section is to prove Theorem 1.1, and more generally, to show that not all Cayley graphs can be embedded as the graphs of convex polytopes. To prove this theorem, we study in detail the possible presentations of the quaternion group, denoted Q8 . There are many presentations of Q8 , however, the only minimal presentations are those of the form: Λ = x, y | x4 = 1, x2 = y 2 , y −1 xy = x−1 , where, if Q8 = {±1, ±i, ±j, ±k} and {±i, ±j, ±k} are the elements of order four, x, y ∈ {±i, ±j, ±k}, and x = −y. (Since any non-inverse pair in {±i, ±j, ±k} generates the entire group, and we need at least two elements to generate the group, adding further generators would create redundancies.) All presentations of this type have the same Cayley graph, but for concreteness we let Λ = i, j | i4 = 1, i2 = j 2 , j −1 ij = i−1 . This presentation has the Cayley color graph, C(Q8 , Δ) as given below. j

ij

j

ij

−i

1

−i

1

−1

i

−1

i

−ij

−j

−ij

−j

C(Q8 , Δ) Toroidal Embedding of C(Q8 , Δ)

In these Cayley color graphs, the dashed lines represent multiplication on the right by j, and the solid lines represent multiplication on the right by i. This graph is non-planar, but is toroidal, as seen above. Now, we prove our theorem by contradiction. Proof. Suppose that G(Q8 , Λ) is the graph of some convex polytope P . We notice two things: (i) G(Q8 , Λ) is 4-connected, thus dim(P ) ≤ 4 (see [2]). Further, as G(Q8 , Λ)

282

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

is non-planar, dim(P ) > 3. We see that dim(P ) = 4. (ii) Every vertex of G(Q8 , Λ) is of the same degree, thus P is simple. Blind and Mani [4] show that if P is a simple polytope, then its graph G(P ) determines the entire combinatorial structure of P . Kalai [9] gave a simpler construction for a simple polytope P given its graph G(P ). Later, Joswig [8] generalized Kalai’s methods to non-simple polytopes. We will show it is impossible to complete Kalai’s construction for G(Q8 , Λ), henceforth abbreviated as G. As in [9], we consider the set of all acyclic orientations of G in order to ﬁnd the “good” ones. Good acyclic orientations are given as follows. Let O be an acyclic orientation of G, and hO k be the number of vertices with in-degree k with respect to O. Deﬁne O O O O f O := hO 0 + 2h1 + 4h2 + 8h3 + 16h4 .

Let f denote the number of nonempty faces of P . An orientation O is good if and only if f = f O . Of course, we do not know what f is, but if G is indeed the graph of a simple polytope, a good orientation must exist. Therefore, we must ﬁnd the minimum f O among all acyclic orientations O of G. In particular, we will start with a certain orientation O and corresponding f O , and show that we cannot do better. To this end, consider the following orientation of G: 4

1

3 8

7

5

6 2

Orientations of the edges are given by the natural ordering of the vertices. For this orientation, we have: (1)

f O = 1 · 1 + 2 · 2 + 4 · 2 + 8 · 2 + 16 · 1 = 45.

To see that this is the best possible, ﬁrst note that we have the following equalities: O O O O (2) 0 · hO 0 + 1 · h1 + 2 · h2 + 3 · h3 + 4 · h4 = 16, and O O O O (3) hO 0 + h1 + h2 + h3 + h4 = 8.

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

283

Moreover, any good orientation O has f O ≤ 45, as good orientations have minimal values for f O . Further, we must have a “largest” vertex with respect O to any total ordering, thus hO 4 is at least one. Assume for now that h4 = 1. Then, we are able to derive the system consisting of O O O (4) hO 0 + h1 + h2 + h3 = 7, and O O (5) hO 1 + 2h2 + 3h3 = 12.

From these equations and the fact that f O ≤ 45, we have the inequality: O (6) hO 2 + 4h3 ≤ 10.

Note also that hO 0 ≥ 1 and that the in-degree of the vertex labeled ‘2’ is at most one. These facts, the previous (in)equalities, and great deal of algebra O give that f O ≥ 45 when hO 4 = 1. Now, suppose that h4 = 2. (We need not O address the case where h4 = 3, as such an orientation gives f O ≥ 48.) Simple algebra with O O O (7) hO 0 + 2h1 + 4h2 + 8h3 + 16 · 2 ≤ 45, O O (8) hO 1 + 2h2 + 3h3 + 4 · 2 = 16, and O O O (9) hO 0 + h1 + h2 + h3 + 2 = 8 O shows that hO 2 + 4h3 ≤ −1, a contradiction. Therefore, if G is the graph of a simple polytope P , the orientation pictured above is a good one, and the number of nonempty faces of P is 45. The next question is to ﬁnd the faces. We have the following from Kalai’s proof:

Lemma 2.1 An induced, connected, k-regular subgraph H of G is the graph of some k-face of P (G) if and only if its vertices are initial with respect to some good acyclic orientation O of G. The total number of non-empty faces is thus 45, and as (f0 , f1 , f2 , f3 , f4 ) = (8, 16, ?, ?, 1), we have f2 + f3 = 20. However, using the vertex labeling from above, the set of 2- and 3-faces include (but are not limited to): 1234, 1256, 1278, 1458, 1568, 2-faces

1467, 2358, 2367, 2567, 3456, 3478, 3678, 4578, 5678,... 123456, 123478, 123458,

3-faces

123467, 125678, 145678, 235678, 345678,...

284

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

This is not an exhaustive list of all faces of dimensions two and three, and it already includes more than 20 faces. We see that G cannot be the graph of a polytope, and no minimal presentation of Q8 can be embedded as the graph of a convex polytope. 2 Remark 2.2 The condition of minimality is an important one. If we take the presentation of Q8 : Λ = i, j, k, −1|(−1)2 = 1, i2 = j 2 = k 2 = ijk = −1, then G(Q8 , Λ) is the complete graph on eight vertices, which can be embedded as the graph of the 8-simplex. Note that Q8 is also the smallest example of a group whose Cayley graph cannot be embedded as the graph of a convex d-polytope. All other groups of order less than or equal to eight are planar. 2.1

Cayley graphs of 3-dimensional convex polytopes

In 1896, Maschke [11] provided a classiﬁcation of all possible ﬁnite planar Cayley graphs, i.e., those that can be drawn on the plane without improper intersections of the edges. Maschke’s list relates ﬁnite planar groups with subgroups of symmetries of the Platonic solids. In this section, we make use of results of Steinitz [14] and Mani [10] to reconsider the classiﬁcation question for planar graphs, and provide an alternative and an extension to Maschke’s proof. Intuitively, for each planar Cayley graph we will show that there exists a “rigid” model with the property that the symmetries of this model realize the group of automorphisms of the associated Cayley graph. A natural choice is the 3-dimensional polyhedra. In [14], Steinitz proved that a graph is the graph of a polyhedron if and only if it is 3-connected and planar (for a nice proof see [6]). A result of Mani [10] extends Steinitz’s theorem in a convenient way: every 3-connected, planar graph G is the graph of a polyhedron P such that every automorphism of G is induced by a symmetry of P . Our main goal is to show that if a Cayley graph of the group Γ embeds in the sphere, then it acts on the sphere by isometries. We ﬁrst give some deﬁnitions. A separator of a graph is a subset of its vertices such that if we remove the subset, then the resulting graph is disconnected, and has at least two non-empty subgraphs called components. A k-separator is a separator of cardinality k. A graph is k-connected if there exist no separators of cardinality less than k. An automorphism of a Cayley color graph C(Γ, Δ) is a permutation of its vertices that preserves the edge

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

285

coloration and directions. It is well-known that the group of automorphisms of a Cayley color graph corresponding to a group Γ is isomorphic to Γ. A Cayley graph has Γ as a subgroup of its automorphism group, and Γ acts transitively on the vertices of the graph. We will show that any planar Cayley graph is either 3-connected or a cycle; we make use of the transitive action of Γ to prove this. First, we recall several useful concepts. Deﬁnition 2.3 Let A and B be two separators of the graph G. Suppose A separates G into the components A1 and A2 , and B separates G into B1 and B2 . The quadrant Qij is given (see also the ﬁgure below): Qij = (Ai ∩ B) ∪ (Bj ∩ A) ∪ (A ∩ B). B1 B B2 A1

A

A2

The graph G, represented by the outer rectangle, with A and B drawn as orthogonal strips. Q11 has been shaded.

These ideas, including the following remark, are due to Neumann-Lara [12]. Remark 2.4 Let A and B be two separators of the same connected graph G. If Ai ∩ Bj is non-empty then the quadrant Qij is a separator. Proof. The proof is simple. Assume without loss of generality that i = j = 1. Further, assume A1 ∩ B1 is non-empty. Then there are no edges connecting A1 ∩ B1 and B2 because B is a separator. Similarly, there are no edges connecting A1 ∩ B1 and A2 . Thus, Q11 separates A1 ∩ B1 and A2 ∪ B2 .2 Now we are able to prove the following result: Proposition 2.5 Let G be a connected, vertex-transitive graph with minimum degree at least two. Then G is a cycle or a 3-connected graph. Proof. First, note that G must be at least 2-connected, as it is vertextransitive with minimum degree at least two. Second, we assume that G = K3

286

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

(our arguments do not apply in this case, but the proposition clearly holds). Suppose G is not 3-connected. Let A = {x, y} be a 2-separator with components A1 and A2 such that A1 is minimal among all possible components of 2-separators in G. Since G is vertex-transitive, there exists an automorphism f such that f (x) belongs to A1 . The image set of A under f , f (A) = B, is another separator of the graph. The elements x, y, f (x), and f (y) are arranged in the following way (up to swapping x and y): x f (x)

B1 f (y)

B2

y A1

A

B

A2

To show this, we must consider a variety of cases, all of which are eliminated by ﬁnding contradictions to the minimality of A1 or the fact that G is 2connected – we omit the details. Given the arrangement above, we see that A1 ∩ B1 and A1 ∩ B2 must be empty. Otherwise, the quadrants Q11 and Q12 would be separators, but removing either quadrant would leave a component with fewer vertices than A1 . Therefore, f (x) is the only vertex in A1 , and it must be adjacent to both x and y (as every vertex has degree at least two). Therefore f (x) is a vertex of degree exactly two, which implies that G is regular of degree two. Since G is connected, G must be a cycle. 2 Now we can prove Theorem 1.2. Proof. G(Γ, Λ) satisﬁes the hypotheses of Proposition 2.5. If G(Γ, Λ) is a cycle, then Γ is a dihedral group or a cyclic group. Both groups have an isometric action on the sphere as symmetries of an n-dihedron. In the case that G(Γ, Λ) is 3-connected, Mani’s result [10] gives the required action. See [15] for a diﬀerent view of the theorem. 2

References [1] Arzhantseva, G. and P. Cherix, On the Cayley graph of a generic ﬁnitely presented group, Bull. Belg. Math. Soc. Simon Stevin 11 (2004), pp. 589–601.

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

287

URL http://projecteuclid.org/getRecord?id=euclid.bbms/1102689123 [2] Balinski, M., On the graph structure of convex polyhedra in n-space, Paciﬁc J. Math. 11 (1961), pp. 431–434. [3] Baumeister, B., C. Haase, B. Nill and A. Paﬀenholz, On permutation polytopes, Adv. Math. 222 (2009), pp. 431–452. URL http://dx.doi.org/10.1016/j.aim.2009.05.003 [4] Blind, R. and P. Mani-Levitska, Puzzles and polytope isomorphisms, Aequationes Math. 34 (1987), pp. 287–297. URL http://dx.doi.org/10.1007/BF01830678 [5] Cayley, A., Desiderata and Suggestions: No. 2. The Theory of Groups: Graphical Representation, Amer. J. Math. 1 (1878), pp. 174–176. URL http://dx.doi.org/10.2307/2369306 [6] Gr¨ unbaum, B., “Convex polytopes,” Graduate Texts in Mathematics 221, Springer-Verlag, New York, 2003, second edition, xvi+468 pp., prepared and with a preface by Volker Kaibel, Victor Klee and G¨ unter M. Ziegler. URL http://dx.doi.org/10.1007/978-1-4613-0019-9 [7] Guralnick, R. M. and D. Perkinson, Permutation polytopes and indecomposable elements in permutation groups, J. Combin. Theory Ser. A 113 (2006), pp. 1243–1256. URL http://dx.doi.org/10.1016/j.jcta.2005.11.004 [8] Joswig, M., Reconstructing a non-simple polytope from its graph, in: Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem. 29, Birkh¨ auser, Basel, 2000 pp. 167–176. [9] Kalai, G., A simple way to tell a simple polytope from its graph, J. Combin. Theory Ser. A 49 (1988), pp. 381–383. URL http://dx.doi.org/10.1016/0097-3165(88)90064-7 [10] Mani, P., Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971), pp. 279–303. [11] Maschke, H., The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley’s Color Diagrams, Amer. J. Math. 18 (1896), pp. 156–194. URL http://dx.doi.org/10.2307/2369680 [12] Neumann-Lara, V., Personal communication (1989). [13] Proulx, V., Classiﬁcation of the toroidal groups, J. Graph Theory 2 (1978), pp. 269–273.

288

J. De Loera, Y. Kemper / Electronic Notes in Discrete Mathematics 43 (2013) 279–288

[14] Steinitz, S., “Polyeder und Raumeinteilungen,” mathematischen Wissenschaften 3, 1922, 1-139 pp.